Paper detail

Greibach Normal Form for $ω$-Algebraic Systems and Weighted Simple $ω$-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 $ω$-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted context-free languages, or $ω$-algebraic series, can be represented as solutions of mixed $ω$-algebraic systems of equations and by weighted $ω$-pushdown automata. In our first main result, we show that (mixed) $ω$-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple $ω$-reset pushdown automata recognize all $ω$-algebraic series. Simple $ω$-reset automata do not use $ε$-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.