The Triple-Pair Construction for Weighted ω-Pushdown Automata

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.

In Erzsébet Csuhaj-Varjú, Pál Dömösi and György Vaszil: Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science 252, pp. 101–113.
The article was prepared as a joint work with the late Zoltán Ésik (1951-2016) whose definite intention was to publish the results.
Published: 21st August 2017.

ArXived at: https://dx.doi.org/10.4204/EPTCS.252.12 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org