Algebra Seminar talk
2019-01-18 (11:30-12:00)
Sven Dziadek
Weighted $\omega$-pushdown automata
Abstract:
Context-free languages of infinite words have recently found increasing interest. Here,
we will present a second-order logic with the same expressive power as Büchi or Muller
pushdown automata for infinite words. This extends fundamental logical characterizations of Büchi, Elgot, Trakhtenbrot for regular languages of finite and infinite words
and a more recent logical characterization of Lautemann, Schwentick and Therien for
context-free languages of finite words to ω-context-free languages.
For our argument, we will investigate Greibach normal forms of ω-context-free grammars as well as a new type of Büchi pushdown automata which can alter their stack by at most one element and without $\epsilon$-transitions. We show that they suffice to accept all ω-context-free languages. This enables us to use similar results developed for infinite nested words.
Recently, weighted ω-pushdown automata have been introduced by Droste, Ésik, Kuich. These automata generalize the aforementioned class of ω-context-free languages. We will give a short overview on how the above defined unweighted second-order logic can be extended to this new type.