Unambiguity in Automata Theory

Motivation

Determinism and nondeterminism are fundamental concepts in automata theory. One of the main interests of research in automata theory is to identify restricted versions of nondeterministic models that unify the advantages in expressive power and succinctness of nondeterminism on the one side, and the tractability of deterministic models on the other side. A promising direction is to study a class of machines that lies between deterministic and nondeterministic machines: the class of unambiguous machines. A machine is unambiguous if it can make nondeterministic choices, but it is guaranteed that for every input there is at most one accepting computation.

Unambiguous computational models and formalisms have been in the focus of much research work during the last decades, and with increasing tendency over the last five years. Some of the striking new results are

• The state complexity of the complementation of an unambiguous finite automaton is superpolynomial.
• The containment problem for register automata is undecidable in general, but decidable for unambiguous register automata.
• The emptiness problem for probabilistic automata is undecidable, but the problem admits efficient algorithms for unambiguous probabilistic automata.

Despite these motivating examples, many research questions related to unambiguity are open for a long time and seem to be complicated. Many researchers working in theoretical computer science and in particular in automata theory consider the current state of the art regarding unambiguous computational models rather unsatisfying. The goal of this Dagstuhl Seminar Unambiguity in Automata Theory is to bring together researchers from the field of automata theory to improve the understanding of unambiguity, and solving some of the most urgent open problems regarding that form of nondeterminism.

In the seminar, we plan to discuss and advance on topics related to

• the state complexity of unambiguous automata, in particular concerning their complementation;
• unambiguous versions of infinite-state systems, such as register automata, timed automata, and vector addition systems with states. Here, questions of interest are, for instance: What can be new techniques for proving lower bounds for the containment problem? Are languages accepted by unambiguous register automata with guessing closed under complement?
• unambiguous tree automata: An important question in this direction is how to decide whether a given a tree-regular language is recognizable by an unambiguous one.
• Büchi automata and probabilistic automata: In particular, the computational complexity of the containment of unambiguous Büchi automata remains open.
• tropical automata, for which the important question of deciding whether a given series is polynomially ambiguous remains open.

The seminar will consist of talks and working group sessions. We aim to make this Dagstuhl Seminar highly interactive, and give the participants the opportunity to work on specific problems in smaller groups.