Automata Implementation

This volume contains the revised versions of papers presented at the fourth international Workshop on Implementing Automata (WIA), held 17–19 July, 1999, at Potsdam University, Germany. As for its predecessors, the theme of WIA99 was the implementation of au- mata and grammars of all types and their application in other ?elds. The papers contributed to this volume address, among others, algorithmic issues regarding automata, image and dictionarystorage byautomata, and natural language p- cessing. In addition to the papers presented in these proceedings, the workshop - cluded a paper on quantum computing byC. Calude, E. Calude, and K. Svozil (published elsewhere), an invited lecture byW. Thomas on Algorithmic P- blems in the Theory of ?-Automata, a tutorial byM. Silberztein on the INTEX linguistic development environment, and several demonstrations of systems. The local arrangements for WIA99 were conducted byHelmut J¨urgensen, Suna Aydin, Oliver Boldt, Carsten Haustein, Beatrice Mix, and Lynda R- bins. The meeting was held in the Communs building, now the main university building, of the New Palace in the park of Sanssouci, Potsdam. The program committee for WIA99 was: A. Bruggemann-Klein ¨ Technische Universit¨at Munc ¨ hen J.-M. Champarnaud Universit´e de Rouen F. Gun ¨ thner Universit¨at Munc ¨ hen H. Jurgensen ¨ Universit¨at Potsdam and Universityof Western Ontario D. Maurel Universit´e de Tours D. Raymond Gateway Group Inc. K. Salomaa Universityof Western Ontario W. Thomas Rheinisch-Westf¨alische Technische Hochschule Aachen B. Watson Ribbit Software Systems Inc.