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

### From LRDE

- Authors
- Manfred Droste, Sven Dziadek, Werner Kuich
- Journal
- Information and Computation
- Type
- article
- Projects
- AA"AA" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.
- Date
- 2022-06-30

## 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.

## Documents

## 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.} }