December 12 – 17 , 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)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl Seminar Schedule [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 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.


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