2017/08/22 by Manfred Droste, Zoltán Ésik, Werner Kuich
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.252.12
published as EPTCS 252, 2017, pp. 101-113 · In Proceedings AFL 2017, arXiv:1708.06226. The article was prepared as a joint work with the late Zoltán Ésik (1951-2016) whose definite intention was to publish the results
arxiv created 2017/08/22 · arxiv updated 2017/08/23
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<<Sigmaomega>>)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.