January 14 – 18 , 1991, Dagstuhl Seminar 9103

Automata Theory and Applications in Logic and Complexity


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

For support, please contact

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 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.