October 14 – 18 , 1991, Dagstuhl Seminar 9142

Trends and Applications in Formal Language Theory


F.J. Brandenburg, J. Berstel, D. Wotschke

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 23


Formal language theory is one of the classical and fundamental areas of Computer Science. For more than four decades a broad theoretical basis and a wide spectrum of applications of language theory has been developed, with the l960's and l970's as the "golden age" of formal language theory. Since then other areas became more attractive to many theoretical computer scientists and research on formal languages is often presented as part of other theories. Under this perspective the seminar on Trends and Applications in Formal Language Theory aims at serving as a forum for formal language theorists to make their research transparent as part of their theory.

The presented talks addressed a wide range of themes with informal language theory. Particular emphasis was laid upon the complexity of languages and their descriptions, i.e. both static and dynamic complexity theory. A more detailed classification can be done along the following keywords:

  • description complexity and general complexity
  • nondeterminism, unambiguity, determinism
  • generation of complex objects
  • special use of regular and context-free methods
  • parallel rewriting and codes

Besides the 27 presented talks there were a lot of discussions in small groups and a general one focussing on perspectives of formal language theory. Among the participants there was a broad consensus that the visibility of formal language theory must be improved. Activities in this direction of some participants were gratefully acknowledged. Clearly, the best support would come from a regular conference on formal language theory or a devoted section within an established conference series, with Dagstuhl seminars as a first step.

All participants appreciated the stimulating Dagstuhl atmosphere and wished to thank the staff for doing a perfect job.


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.