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

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

• Paper

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,
  url		= {https://doi.org/10.1016/j.ic.2022.104871},
  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.}
}