View source for Publications/droste.22.iandc

{{Publication
| published = true
| date = 2022-06-30
| authors = Manfred Droste, Sven Dziadek, Werner Kuich
| title = Greibach normal form for ω-algebraic systems and weighted simple ω-pushdown automata
| journal = Information and Computation
| volume = 285
| number = B
| pages = 104871
| None = https://doi.org/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
| lrdepaper = http://www.lrde.epita.fr/dload/papers/droste.22.iandc.pdf
| lrdenewsdate = 2022-06-30
| lrdeprojects = AA
| 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 <math>\omega</math>-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 <math>\omega</math>-algebraic series, can be represented as solutions of mixed <math>\omega</math>-algebraic systems of equations and by weighted <math>\omega</math>-pushdown automata. In our first main result, we show that (mixed) <math>\omega</math>-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple <math>\omega</math>-reset pushdown automata recognize all <math>\omega</math>-algebraic series. Simple <math>\omega</math>-reset automata do not use <math>\epsilon</math>-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.
| type = article
| id = droste.22.iandc
| identifier = doi:10.1016/j.ic.2022.104871
| bibtex = 
@Article<nowiki>{</nowiki>	  droste.22.iandc,
  author	= <nowiki>{</nowiki>Manfred Droste and Sven Dziadek and Werner Kuich<nowiki>}</nowiki>,
  title		= <nowiki>{</nowiki>Greibach normal form for $\omega$-algebraic systems and
		  weighted simple $\omega$-pushdown automata<nowiki>}</nowiki>,
  journal	= <nowiki>{</nowiki>Information and Computation<nowiki>}</nowiki>,
  volume	= <nowiki>{</nowiki>285<nowiki>}</nowiki>,
  number	= <nowiki>{</nowiki>B<nowiki>}</nowiki>,
  pages		= <nowiki>{</nowiki>104871<nowiki>}</nowiki>,
  year		= <nowiki>{</nowiki>2022<nowiki>}</nowiki>,
  month		= may,
  url		= <nowiki>{</nowiki>https://doi.org/10.1016/j.ic.2022.104871<nowiki>}</nowiki>,
  doi		= <nowiki>{</nowiki>10.1016/j.ic.2022.104871<nowiki>}</nowiki>,
  timestamp	= <nowiki>{</nowiki>Mon, 13 Jun 2022 16:53:29 +0200<nowiki>}</nowiki>,
  biburl	= <nowiki>{</nowiki>https://dblp.org/rec/journals/iandc/DrosteDK22a.bib<nowiki>}</nowiki>,
  bibsource	= <nowiki>{</nowiki>dblp computer science bibliography, https://dblp.org<nowiki>}</nowiki>,
  abstract	= <nowiki>{</nowiki>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<nowiki>{</nowiki>\"u<nowiki>}</nowiki>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.<nowiki>}</nowiki>
<nowiki>}</nowiki>

}}