https://www.dagstuhl.de/21452

November 7 – 12 , 2021, Dagstuhl Seminar 21452

Unambiguity in Automata Theory

Organizers

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

For support, please contact

Simone Schilke for administrative matters

Shida Kunz for scientific matters

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule (Upload here)

(Use personal credentials as created in DOOR to log in)

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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.