Handbook of formal languages. Vol. 1–3. (English) Zbl 0866.68057

Berlin: Springer. not consec. pag. (1997).

The three-volumes Handbook of Formal Languages represents a really outstanding enterprise, and constitutes both a necessary and unique collection of information resources for the (theoretical) computer science community. This Handbook presents the current state of the art in formal language theory, and within the theoretical areas related to its main sources (mathematics, mathematical logic, linguistics, artificial intelligence, molecular genetics etc.), as well as application and development directions (e.g. mathematical and/or computational linguistics, parsing technologies, information theory, developmental biology, computer graphics, concurrent and distributed systems, molecular biology, pattern matching, cryptology etc.).
Volume 1 (Word, Language, Grammar) is mainly devoted to mathematical (grammatical, computational, and algebraic) aspects of the basic theory of formal languages. Risking to (apparently) be boring, it is however impossible not to mention (at least) the titles and the authors of the contained papers: they speak best for themselves and for those who want and know to listen. For Volume 1: Formal Languages: an Introduction and a Synopsis (A. Mateescu, A. Salomaa), Regular Languages (S. Yu), Context-Free Languages and Pushdown Automata (J.-M. Autebert, J. Berstel, L. Boasson), Aspects of Classical Language Theory (A. Mateescu, A. Salomaa), L Systems (Lila Kari, G. Rozenberg, A. Salomaa), Combinatorics on Words (Ch. Choffrut, J. Karhumäki), Morphisms (T. Harju, J. Karhumäki), Codes (H. Jürgensen, S. Konstantinidis), Semirings and Formal Power Series (W. Kuich), Syntactic Semirings (J.-E. Pin), Regularity and Finiteness Conditions (A. de Luca, S. Varricchio), Families Generated by Grammars and L Systems (G. Păun, A. Salomaa).
Volume 2 (Linear Modeling: Background and Application) contains papers dealing with linear models of the word functioning, with a special emphasis on computational linguistics and complexity, molecular genetics, and cryptology: Complexity: A Lanquage-Theoretic Point of View (C. Calude, J. Hromkovič), Parsing of Context-Free Languages (K. Sikkel, A. Nijholt), Grammars with Controlled Derivations (J. Dassow, G. Păun, A. Salomaa), Grammar Systems (J. Dassow, G. Păun, G. Rozenberg), Contextual Grammars and Natural Languages (S. Marcus), Contextual Grammars: and Formal Languages (A. Ehrenfeucht, G. Păun, G. Rosenberg), Language Theory and molecular Genetics (T. Head, G. Păun, D. Pixton), String Editing and Longest Common Subsequences (A. Apostolico), Automata for Matching Patterns (M. Crochemore, Ch. Hancart), Symbolic Dynamics and Finite Automata (M.-P. Béal, D. Perrin), Cryptology: Language-Theoretic Aspects (V. Niemi).
Finally, Volume 3 (Beyond Words) comprises non-linear models on words (trees, graphs etc.) and their applications (linguistics, mathematical logic, theory of programming, computer graphics etc.): Tree Languages (F. Gécseg, M. Steinby), Tree-Adjoining Grammars (A. Joshi, Y. Schabes), Context-Free Graph Grammars (J. Engelfriet), Two-Dimensional Languages (Dora Giammarresi, A. Restivo), Basics of Term Rewriting (M. Jantzen), \(\omega\)-Languages (L. Staiger), Languages, Automata, and Logic (W. Thomas), Partial Commutation and Traces (V. Diekert, Y. Metivier), Visual models of Plant Development (P. Prusinkiewicz et al.), Digital Images and Formal Languages (K. Culik II, J. Kari). A final remark on the Handbook: the contributions show the current prominence of some national mathematical and computer science schools into the formal language theory field: namely, the tradition and value of the American, Finlander, French, Romanian, Canadian, Polish, Hollandish, German, and Italian schools.

Reviewer: Neculai Curteanu (Iaşi)

MSC:

68Q45	Formal languages and automata
68-00	General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science
68-XX	Computer science
68P25	Data encryption (aspects in computer science)

Keywords:

mathematical logic; linguistics; artificial intellignce; molecular genetics; formal languages; computational linguistics; complexity; cryptology