Formal language theory : perspectives and open problems ; [... Symposium on Formal Language Theory, Santa Barbara, Calif., Dec. 10-14, 1979

Formal Language Theory: Perspectives and Open Problems focuses on the trends and major open problems on the formal language theory. The selection first ponders on the methods for specifying families of formal languages, open problems about regular languages, and generators of cones and cylinders. Discussions focus on cylinders of algebraic languages, cone of algebraic languages, regularity of noncounting classes, group complexity, specification formalism, and grammars. The publication then elaborates on very small families of algebraic nonrational languages and formal languages and their relation to automata. The book tackles morphisms on free monoids and language theory, homomorphisms, and survey of results and open problems in the mathematical theory of L systems. Topics include single finite substitutions iterated, single homomorphisms iterated, representation of language families, homomorphism equivalence on a language, and problems about infinite words. The selection is a valuable source of data for researchers interested in the formal language theory. Content: Front Matter, Page iii Copyright, Page iv LIST OF CONTRIBUTORS, Page ix PREFACE, Pages xi-xii ACKNOWLEDGMENTS, Page xiii METHODS FOR SPECIFYING FAMILIES OF FORMAL LANGUAGES — PAST-PRESENT-FUTURE, Pages 1-22, Seymour Ginsburg OPEN PROBLEMS ABOUT REGULAR LANGUAGES, Pages 23-47, Janusz Brzozowski GENERATORS OF CONES AND CYLINDERS, Pages 49-87, Jean-Michel Autebert, Luc Boasson VERY SMALL FAMILIES OF ALGEBRAIC NONRATIONAL LANGUAGES, Pages 89-108, Jean-Michel Autebert, Joffroy Beauquier, Luc Boasson, Michel Latteux FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA: WHAT HOPCROFT & ULLMAN DIDN'T TELL US, Pages 109-140, Jonathan Goldstine MORPHISMS ON FREE MONOIDS AND LANGUAGE THEORY, Pages 141-166, Arto Salomaa HOMOMORPHISMS: DECIDABILITY, EQUALITY AND TEST SETS, Pages 167-194, Karel Culik II A SURVEY OF RESULTS AND OPEN PROBLEMS IN THE MATHEMATICAL THEORY OF L SYSTEMS, Pages 195-239, Grzegorz Rozenberg SOME OPEN QUESTIONS AND RECENT RESULTS ON TREE TRANSDUCERS AND TREE LANGUAGES, Pages 241-286, Joost Engelfriet THE INTERFACE BETWEEN LANGUAGE THEORY AND COMPLEXITY THEORY, Pages 287-323, Burkhard Monien, Ivan Hal Sudborough Pattern Matching in Strings, Pages 325-347, Alfred V. Aho Equations and Rewrite Rules: A Survey, Pages 349-405, Gérard Huet, Derek C. Oppen APPLICATION OF FORMAL LANGUAGE THEORY TO PROBLEMS OF SECURITY AND SYNCHRONIZATION, Pages 407-454, Joffroy Beauquier, Maurice Nivat Edited By Ronald V. Book. Proceedings Of A Conference Held Dec. 10-14, 1979, In Santa Barbara, Calif. Includes Bibliographical References.