Author name cluster

Sven Dziadek

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

Highlights Conference 2024 Conference Abstract

Acceptance Conditions for Weighted $\omega$-Automata

Sven Dziadek

Ésik and Kuich extended the theory of weighted formal languages to infinite words in 2005. There, automata are matrices over a semiring and Büchi acceptance is an operation over those matrices. We are extending the theory to other acceptance conditions (Muller, generalized Büchi, etc.) and face several challenges. Mainly, the former operator allows for a disjunction of constraints but now we need conjunction. I will briefly introduce the theory and give an overview of the challenges. Joint work with Uli Fahrenberg.

Details

I&C Journal 2022 Journal Article

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

Manfred Droste
Sven Dziadek
Werner Kuich

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 (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 ω-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.

Details DOI

I&C Journal 2022 Journal Article

Logic for ω-pushdown automata

Manfred Droste
Sven Dziadek
Werner Kuich

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 Thérien 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 ϵ-transitions. We show that they suffice to accept all ω-context-free languages. This enables us to use similar results recently developed for infinite nested words.

Details DOI

TCS Journal 2019 Journal Article

Weighted simple reset pushdown automata

Manfred Droste
Sven Dziadek
Werner Kuich

We define a new normal form for weighted pushdown automata. The new type of automaton uses a stack but has only limited access to it. Only three stack commands are available: popping a symbol, pushing a symbol or leaving the stack unaltered. Additionally, ϵ-transitions are not used. We prove that this automaton model can recognize all weighted context-free languages (i. e. , generates all algebraic power series).

Details DOI