Talk by Sven Dziadek: « Greibach Normal Form and Simple Automata for Weighted ω-Context-Free Languages »
For a new seminar of the proofs and algorithms pole of LIX, we are happy to welcome Sven Dziadek (Universität Leipzig), invited by the Cosynus team.
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 ω-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 context-free languages, or ω-algebraic series, can be represented as solutions of (mixed) ω-algebraic systems of equations and by weighted ω-pushdown automata.
In our first main result, we show that (mixed) ω-algebraic systems can be transformed into Greibach normal form. We use the Greibach normal form in our second main result to prove that simple ω-reset pushdown automata recognize all ω-algebraic series. Simple ω-reset automata do not use ε-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.
This talk is based on this article and its corresponding short version.
The list of next seminars can be found at: https://smimram.gitlabpages.inria.fr/proofs-algorithms/seminar/
The calendar of seminars can be found at: https://smimram.gitlabpages.inria.fr/proofs-algorithms/seminar/calendar.ics