Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 10501

Advances and Applications of Automata on Words and Trees

( Dec 12 – Dec 17, 2010 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:





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!

  • Bahareh Afshari (University of Edinburgh, GB)
  • Marie-Pierre Béal (University Paris-Est - Marne-la-Vallée, FR)
  • Dietmar Berwanger (ENS - Cachan, FR) [dblp]
  • André Böhm (Goethe-Universität - Frankfurt a. M., DE)
  • Julian Bradfield (University of Edinburgh, GB) [dblp]
  • Véronique Bruyère (University of Mons, BE) [dblp]
  • Olivier Carton (University Paris-Diderot, FR) [dblp]
  • Christian Choffrut (University of Paris VII, FR) [dblp]
  • Thomas Colcombet (University of Paris VII, FR) [dblp]
  • Volker Diekert (Universität Stuttgart, DE) [dblp]
  • Manfred Droste (Universität Leipzig, DE) [dblp]
  • Jacques Duparc (University of Lausanne, CH) [dblp]
  • Zoltan Esik (University of Szeged, HU) [dblp]
  • Paul Gastin (ENS - Cachan, FR) [dblp]
  • Christian Glasser (Universität Würzburg, DE) [dblp]
  • Serge Grigorieff (University of Paris VII, FR) [dblp]
  • André Hernich (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Markus Holzer (Universität Gießen, DE) [dblp]
  • Juhani Karhumäki (University of Turku, FI) [dblp]
  • Manfred Kufleitner (Universität Stuttgart, DE) [dblp]
  • Dietrich Kuske (TU Ilmenau, DE) [dblp]
  • Christof Löding (RWTH Aachen, DE) [dblp]
  • Markus Lohrey (Universität Leipzig, DE) [dblp]
  • Pierre McKenzie (University of Montréal, CA) [dblp]
  • Damian Niwinski (University of Warsaw, PL) [dblp]
  • Alexander Okhotin (University of Turku, FI) [dblp]
  • Friedrich Otto (Universität Kassel, DE)
  • Yann Pequignot (University of Lausanne, CH) [dblp]
  • Jean-Eric Pin (University of Paris VII, FR) [dblp]
  • Alexander Rabinovich (Tel Aviv University, IL) [dblp]
  • Christian Reitwießner (Universität Würzburg, DE) [dblp]
  • Jacques Sakarovitch (ENST - Paris, FR) [dblp]
  • Heinz Schmitz (Hochschule Trier, DE) [dblp]
  • Nicole Schweikardt (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Thomas Schwentick (TU Dortmund, DE) [dblp]
  • Luc Segoufin (ENS - Cachan, FR) [dblp]
  • Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
  • Ludwig Staiger (Martin-Luther-Universität Halle-Wittenberg, DE)
  • Howard Straubing (Boston College, US) [dblp]
  • Wolfgang Thomas (RWTH Aachen, DE) [dblp]
  • Bill Wadge (University of Victoria, CA) [dblp]
  • Pascal Weil (University of Bordeaux, FR) [dblp]
  • Thomas Wilke (Universität Kiel, DE) [dblp]
  • Ludmila Yartseva (EPFL - Lausanne, CH)

  • 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