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.
The Dagstuhl Seminar 21452 “Unambiguity in Automata Theory” was a seminar of five days that took place from November 7th to 12th, 2021, organized by Thomas Colcombet, Karin Quaas, and Michał Skrzypczak. A general goal of the seminar was to bring together experts from different fields of automata theory, to stimulate an exchange of recent results and new proof techniques concerning unambiguity and related topics from automata theory. There were 26 on-site participants from nine different countries (Belgium, Czech Republic, France, Germany, India, Italy, Poland, UK), and further 10 remote participants from seven countries (France, Germany, Poland, Sweden, Switzerland, UK, USA). The central topic of the seminar was unambiguous automata. An automaton is unambiguous if it can make nondeterministic choices, but it is guaranteed that for every input there is at most one accepting run. There have recently been numerous new results concerning unambiguous automata; at the same time, a lot of natural and interesting problems have been open for decades. Before the seminar, we identified the following key topics/open problems:
- Unambiguous Finite Automata What is the state complexity of the complementation of unambiguous automata? Here, the state complexity refers to how the number of states of the resulting automaton depends on the number of states of the original automaton.
- Unambiguous versions of infinite state systems, such as vector addition systems with states (VASS) or register automata Open problems concerning such systems 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 One of the most important open questions is how to decide whether a given tree-regular language is recognizable by an unambiguous automaton.
- Büchi automata and probabilistic automata What is the computational complexity of the containment of unambiguous Büchi automata? Tropical automata For this class of weighted automata one of the most important and long standing open questions is whether a given series is polynomially ambiguous.
The seminar was planned to consist of talks and working group sessions, where participants could work on-site on open problems. In order to integrate all participants and to initiate new collaborations, we started the seminar on Monday with introductory talks, where every participant shortly introduced herself to the group. In these introductory sessions, it was also possible to announce open problems the participants were interested to work on during the seminar. We had additionally collected such open problems before the seminar to make them available to the participants in advance.
The second day of the seminar (Tuesday) was dedicated to presentations given by the participants. This day started with an invited talk by Denis Kuperberg on good-for-games automata. Later the day, eight participants of the seminar presented short contributed talks on topics related to unambiguity.
Wednesday began with the invited talk by Gabriele Puppis on register automata. Later, a single contributed talk was given and the whole afternoon was devoted to an excursion and group work.
On Thursday morning, Wojtek Czerwiński gave an invited talk on future-determinisation. After that, four contributed talks were given, and the late afternoon was devoted to work in subgroups.
Finally, on Friday morning we held a closing ceremony. The rest of the day was left to participants to summarise their discussions in subgroups and prepare for departure.
During all days, we have used Schloss Dagstuhl's excellent technical facilities to connect and communicate to remote participants of the seminar. Our experiences regarding such a hybrid Dagstuhl seminar are twofold. On the one hand, it is practical to give remote participants the opportunity to follow the on-site presentations (and Sylvain Lombardi also gave a remote talk). On the other hand, our main aim was to bring together researchers to actually work on concrete problems. It was difficult to integrate participants in group work, when groups gather at different places in the facilities, or when important discussions are led during the excursion or the dinner. We appreciated very much the opportunity to gather on-site at Schloss Dagstuhl after a long time of only non-physical meetings due to the Covid pandemics. As summarized in Session 4, several new collaborations between participants of the seminar have been initiated. We hope that the seminar has inspired new ideas, and interesting new results will be published by the participants.
We would like to warmly thank Schloss Dagstuhl for making this seminar possible. We especially would like to thank for the great help and support in the organization before and during the seminar.
- Achim Blumensath (Masaryk University - Brno, CZ) [dblp]
- Udi Boker (Reichman University - Herzliya, IL) [dblp]
- Dmitry Chistikov (University of Warwick - Coventry, GB) [dblp]
- Lorenzo Clemente (University of Warsaw, PL) [dblp]
- Thomas Colcombet (CNRS - Paris, FR) [dblp]
- Wojciech Czerwinski (University of Warsaw, PL) [dblp]
- Diego Figueira (CNRS & Université de Bordeaux, FR) [dblp]
- Emmanuel Filiot (UL - Brussels, BE) [dblp]
- Simon Jantsch (TU Dresden, DE) [dblp]
- Ismaël Jecker (University of Warsaw, PL) [dblp]
- Shankaranarayanan Krishna (Indian Institute of Technology - Mumbai, IN) [dblp]
- Denis Kuperberg (ENS - Lyon, FR) [dblp]
- Karoliina Lehtinen (Aix-Marseille University, FR) [dblp]
- Antoine Mottet (Charles University - Prague, CZ) [dblp]
- Anca Muscholl (University of Bordeaux, FR) [dblp]
- Pierre Ohlmann (CNRS - Paris, FR)
- Guillermo A. Pérez (University of Antwerp, BE) [dblp]
- Jakob Piribauer (TU Dresden, DE)
- Gabriele Puppis (University of Udine, IT) [dblp]
- Karin Quaas (Universität Leipzig, DE) [dblp]
- Alexander Rabinovich (Tel Aviv University, IL) [dblp]
- Michael Raskin (TU München, DE) [dblp]
- Mahsa Shirmohammadi (University Paris Diderot, FR) [dblp]
- Michal Skrzypczak (University of Warsaw, PL) [dblp]
- Sarah Winter (UL - Brussels, BE) [dblp]
- Georg Zetzsche (MPI-SWS - Kaiserslautern, DE) [dblp]
- Christel Baier (TU Dresden, DE) [dblp]
- Johanna Björklund (University of Umeå, SE) [dblp]
- Michaël Cadilhac (DePaul University - Chicago, US) [dblp]
- Antonio Casares (University of Bordeaux, FR)
- Nathanael Fijalkow (University of Bordeaux, FR) [dblp]
- Mika Göös (EPFL Lausanne, CH) [dblp]
- Arthur Jaquard (CNRS - Paris, FR)
- Stefan Kiefer (University of Oxford, GB) [dblp]
- Christof Löding (RWTH Aachen, DE) [dblp]
- Sylvain Lombardy (University of Bordeaux, FR) [dblp]
- Radek Piórkowski (University of Warsaw, PL) [dblp]
- Mikhail V. Volkov (Ural Federal University - Ekaterinburg, RU) [dblp]
- Computational Complexity
- Formal Languages and Automata Theory
- Logic in Computer Science
- Automata Theory