12. – 17. Dezember 2010, Dagstuhl-Seminar 10501

Advances and Applications of Automata on Words and Trees


Christian Glasser (Universität Würzburg, DE)
Jean-Eric Pin (University of Paris VII, FR)
Nicole Schweikardt (Goethe-Universität – Frankfurt a. M., DE)
Victor Selivanov (A. P. Ershov Institute – Novosibirsk, RU)
Wolfgang Thomas (RWTH Aachen, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Programm des Dagstuhl-Seminars [pdf]


Automata theory is one of the longest established areas in computer science. Over the past few years, automata theory has not only developed in many different directions, but has also evolved in an exciting way at several levels: the exploration of specific new models and applications has at the same time stimulated a variety of deep mathematical theories.

The insights developed in automata theory had a strong impact on numerous scientific areas. Standard applications include pattern matching, syntax analysis, foundations of XML, and hardware and software verification. In recent years, novel applications have emerged from biology, physics, cognitive sciences, neurosciences, control, tomography, linguistics, mathematics, etc. The new developments in information technology have increased the need for formally-based design and verification methods to cope with emerging technical challenges in network security, electronic business, mobile intelligent devices, and high performance computing.

At the same time, the mathematical foundations of automata theory rely on more and more advanced parts of mathematics. While, in the early sixties, only elementary graph theory and combinatorics were required, new tools from non-commutative algebra (semigroups, semirings and formal power series), logic, probability theory and symbolic dynamics have been successively introduced and the latest developments borrow ideas from game theory, topology and geometry. Both trends have enhanced the role of fundamental research in automata theory and the importance of closer interaction between theoretical and applied scientists.

On the one hand, significant advances in fundamental aspects of automata theory can be measured by recent progress on some deep open questions of the classical theory. On the other hand, new theoretical problems arise from applications and also from the sprouting of new automata models and generative devices, motivated by applications, which require a systematic investigation of their theoretical aspects.

The aim of the seminar was to discuss and systematize the recent fast progress in automata theory and to identify important directions for future research. For this, the seminar brought together more than 40 researchers from automata theory and related fields of applications. We had 19 talks of 30 minutes and 5 one-hour lectures, leaving ample room for discussions. The talks in this seminar ranged over a broad assortment of subjects with the underlying theme of automata on words and trees. It was a very fruitful seminar and has hopefully initiated new directions in research. We look forward to similar meetings in the future!


  • Data Structures / Algorithms / Complexity
  • Verification / Logic
  • Automata Theory
  • Ehrenfeucht-Fra¨ýss´e Games And Gale-Stewart Games


  • Infinite games with perfect information
  • Reactive systems
  • Specification and verification
  • Combinatorics
  • Hierarchies and reducibilities


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.