Dagstuhl Seminar 9142
Trends and Applications in Formal Language Theory
( Oct 14 – Oct 18, 1991 )
Permalink
Organizers
- D. Wotschke
- F.J. Brandenburg
- J. Berstel
Contact
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.

- D. Wotschke
- F.J. Brandenburg
- J. Berstel