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 9142

Trends and Applications in Formal Language Theory

( Oct 14 – Oct 18, 1991 )

Please use the following short url to reference this page:

  • D. Wotschke
  • F.J. Brandenburg
  • J. Berstel


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