Automata Theory and Applications: Games, Learning and Structures

Overview

The workshop addresses important areas of automata theory including the following three main topics:

1. Two-person-games played on finite graphs like parity games and Muller games;
2. Learning of languages in the setting of automata theory;
3. Structures represented by finite automata, like, for example, groups and semigroups.

Besides the three main topics, the workshop is open to all topics related to finite automata and formal languages. Details of the three main topics are as follows:

1. Recently, parity games has received a lot of attention, with the emergence of quasipolynomial time algorithms to decide the winner of a game. An important open problem in this area is still whether one can, in whatever way, code some problems not known to be solvable in polynomial time into parity games or alternatively, settle this question by providing a polynomial time algorithm. Within this research, authors have studied also related games like energy-parity games in order to investigate whether some near variant of this game is outside polynomial time.
2. The learning of classes of regular languages was from the beginning a central point in learning theory and it studied in various branches of learning theory, from inductive inference to query learning. However, the main framework of inductive inference was recursion-theoretic and classes of regular languages were mainly considered as an example of what can be learnt. Within the last decade, researchers have worked towards a model where both the concept classes as well as the learner are modelled with the tools of automata theory and automatic structures and this workshop is also dedicated at extensions of these studies.
3. Automatic structures were invented independently by Hodgson; Khoussainov and Nerode; Blumensath and Grädel. These structures use methods from automata theory to model basic mathematical concepts in a way that the first-order theory remains decidable. This naturally leads to a limitation of the expressiveness. The field has been well-studied within the last twenty years, but it is still not mature and various questions remain open. One interesting question is, for example, whether there is an automatic presentation of the integers with the addition being a binary automatic function such that the subset of natural numbers is not regular.