https://www.dagstuhl.de/21452

07. – 12. November 2021, Dagstuhl-Seminar 21452

Unambiguity in Automata Theory

Organisatoren

Thomas Colcombet (CNRS – Paris, FR)
Karin Quaas (Universität Leipzig, DE)
Michal Skrzypczak (University of Warsaw, PL)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Simone Schilke zu administrativen Fragen

Shida Kunz zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl-Seminar Wiki
Programm des Dagstuhl-Seminars (Hochladen)

(Zum Einloggen bitte persönliche DOOR-Zugangsdaten verwenden)

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Thomas Colcombet, Karin Quaas, and Michal Skrzypczak

Classification

  • Computational Complexity
  • Formal Languages And Automata Theory
  • Logic In Computer Science

Keywords

  • Automata Theory
  • Unambiguity
  • Ambiguity
  • Determinism
  • Nondeterminism

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.