Greibach normal form for \omega-algebraic systems and weighted simple \omega-pushdown automata


In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of \omega-context-free languages (as introduced by Cohen and Gold in 1977) and an extension of weighted context-free languages of finite words (that were already investigated by Chomsky and Schützenberger in 1963). As in the theory of formal grammars, these weighted context-free languages, or \omega-algebraic series, can be represented as solutions of mixed \omega-algebraic systems of equations and by weighted \omega-pushdown automata. In our first main result, we show that (mixed) \omega-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple \omega-reset pushdown automata recognize all \omega-algebraic series. Simple \omega-reset automata do not use \epsilon-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted context-free languages.