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

Dagstuhl Service Team

Documents

Aims & Scope
List of Participants
Dagstuhl Seminar Schedule [pdf]

Summary

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.

Summary text license
  Creative Commons BY 4.0
  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).

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.

Publications

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