14. – 18. Januar 1991, Dagstuhl-Seminar 9103

Automata Theory and Applications in Logic and Complexity


J. Berstel, J.E. Pin, W. Thomas

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl-Seminar-Report 5


The aim of this seminar was to work on and further develop promising connections between automata and formal language theory to neighbour fields as well as to application areas. Since (project-) research in theoretical computer science today is split into many rather special topics and methods,it seemed worthwile to invite scientists working in the intersection of automata theory,logic, and complexity theory for an exchange of questions and results

Despite of some difficulties due to the rather short preparation of the seminar,the reaction to the invitations was very positive. The date early in January was difficult to meet especially by scientists in the US, Canada, and Israel,which had an effect on the planned seminar topic "circuit complexity". But the 27 participants who finally could come covered quite a wide range of themes, which nevertheless was so specific that the invited scientists had an interest in the entire program of talks(and not just part of it). All talks were attended by virtually all participants, and - as hoped- the discussions resulted in stimulations across the borders of more specialized fields.

It is difficult to classify the contributions into the sections automata theory, theory of formal languages, logic, and complexity. In many talks these aspects were so much intertwined that such a division would be artificial. It might be more appropriate to refer to an orthogonal classification distinguishing by means of the types of objects under consideration (words,trees,graphs,etc.). Here the original objective of automata and language theory, the analysis of word properties or word languages, was extended to several more general types of languages:ω-languages, tree languages, trace languages, picture languages, as well as graph languages. All these fields were represented by talks during the seminar,with different methodological emphasis (towards complexity, logic, automata, combinatorics, or algebra).


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.