Automata Theory and Applications: Games, Learning and Structures

(20 Sep 2021–24 Sep 2021)

Organizing Committee

 

Co-chairs

 
 

Contact Information

General Enquiries: ims(AT)nus.edu.sg
Scientific Aspects Enquiries: fstephan(AT)comp.nus.edu.sg

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.

 

Activities

The programme consists of a one-week workshop where researchers will give talks about the state of the art in automata theory with some emphasis on the three areas mentioned above.

TitleDateAbstract
Workshop on Automata Theory and Applications: Games, Learning and Structures20–24 September 2021View

Confirmed Invited Speakers

  • Volker Diekert, University of Stuttgart, Germany
  • Murray Elder, University of Technology Sydney, Australia
  • Ekaterina Fokina, Technical University of Vienna, Austria
  • Erich Grädel, RWTH Aachen University, Germany
  • Marcin Jurdziński, University of Warwick, UK
  • Bjørn Kjos-Hanssen, University of Hawaii at Mānoa, Hawaii
  • Karoliina Lehtinen, CNRS, Aix-Marseille Université, France
  • André Nies, University of Auckland, New Zealand

Poster

 

Public Lecture

Speaker

Jeffrey Shallit, University of Waterloo, Canada

24 September, Friday

(GMT-4) Waterloo, Ontario, Canada, 7am
(GMT +8) Singapore, 7pm

   

Scroll to Top