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

From LRDE

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