2026-08-05T05:55:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11600 2024-03-12T11:57:12Z ddc:004 open_access

Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata Droste, Manfred Dziadek, Sven Kuich, Werner Weighted omega-Context-Free Grammars Algebraic Systems Greibach Normal Form Weighted Automata omega-Pushdown Automata 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 (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted 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. Our second main result proves that simple omega-reset pushdown automata recognize all omega-algebraic series that are a solution of an omega-algebraic system in Greibach normal form. Simple 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 languages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manfred Droste and Sven Dziadek and Werner Kuich 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.38 urn:nbn:de:0030-drops-116003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode