Manfred Droste (Universität Leipzig, Institut für Informatik) |
Zoltán Ésik (University of Szeged, Department of Foundations of Computer Science) |
Werner Kuich (Technische Universität Wien, Institut für Diskrete Mathematik und Geometrie) |
Let S be a complete star-omega semiring and Sigma be an alphabet. For a weighted omega-pushdown automaton P with stateset 1...n, n greater or equal to 1, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ((S<<Sigma*>> )^nxn, (S<<Sigma^omega>>)^n) such that the behavior ||P|| of P is a component of a solution of this system. In case the basic semiring is the Boolean semiring or the semiring of natural numbers (augmented with infinity), we show that there exists a mixed context-free grammar that generates ||P||. The construction of the mixed context-free grammar from P is a generalization of the well known triple construction and is called now triple-pair construction for omega-pushdown automata. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.252.12 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |