# Greibach normal form for ω-algebraic systems and weighted simple ω-pushdown automata

## Abstract

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 '"UNIQ--postMath-00000001-QINU"'-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 '"UNIQ--postMath-00000002-QINU"'-algebraic series, can be represented as solutions of mixed '"UNIQ--postMath-00000003-QINU"'-algebraic systems of equations and by weighted '"UNIQ--postMath-00000004-QINU"'-pushdown automata. In our first main result, we show that (mixed) '"UNIQ--postMath-00000005-QINU"'-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple '"UNIQ--postMath-00000006-QINU"'-reset pushdown automata recognize all '"UNIQ--postMath-00000007-QINU"'-algebraic series. Simple '"UNIQ--postMath-00000008-QINU"'-reset automata do not use '"UNIQ--postMath-00000009-QINU"'-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.

## Bibtex (lrde.bib)

@Article{	  droste.22.iandc,
author	= {Manfred Droste and Sven Dziadek and Werner Kuich},
title		= {Greibach normal form for $\omega$-algebraic systems and
weighted simple $\omega$-pushdown automata},
journal	= {Information and Computation},
volume	= {285},
number	= {B},
pages		= {104871},
year		= {2022},
month		= may,
doi		= {10.1016/j.ic.2022.104871},
timestamp	= {Mon, 13 Jun 2022 16:53:29 +0200},
biburl	= {https://dblp.org/rec/journals/iandc/DrosteDK22a.bib},
bibsource	= {dblp computer science bibliography, https://dblp.org},
abstract	= {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{\"u}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.}
}