The meeting ALGORITHMS IN AUTOMATA THEORY was the fourth in a series of automata theory seminars held at Dagstuhl Castle. It was motivated by the observation that although many fields in computer science use automata as computational models there is only very little scientific exchange between the groups. Rather, one observes an independent development of similar algorithms for the various fields of application, which range from classical applications like language recognition, e.g. for syntax analysis, to the modelling of distributed systems and the generation of code selectors, the implementation of term-rewriting systems and the construction of type-checkers.

Historically, algorithms for the automatic analysis or transformation of automata, e.g. for the verification of the equivalence of two automata or for the minimization of a single automaton are well-known from classical automata theory. However, to cope with the new applications, such algorithms have in general to be modified. Particularly important is the refinement of the usual view of automata in terms of languages, which identifies those machines accepting the same language, to more discriminative criteria, which in particular take the branching potential of an automaton into account. On this basis, a number of equivalence-provers, model-checkers and static program-analyzers have been developed and implemented in the last few years. Also on the classical automata theoretical side several new methods and implementations have been developed, which raise the question of integration of available tools.

Therefore, the aims of the seminar were to investigate the rich panorama of automatabased algorithms, to compare implementations, to exchange experiences, and to enhance the cooperation among the active research groups. The lively discussions both during the sessions and in the evenings confirmed the need for such an exchange between the different research communities and they illustrated the success of the meeting. In fact, all participants agreed about the stimulating atmosphere of the seminar, both from the scientific point of view and the hospitality of the local organizers, and they are all looking forward to the next Dagstuhl meeting.

Creative Commons BY 3.0 Unported license