Formal Language Theory

¿List of ContributorsPrefaceAcknowledgmentsMethods for Specifying Families of Formal Languages - Past- Present- Future I. Introduction II. Origins III. Specification Formalism IV. Grammars V. Conclusions ReferencesOpen Problems About Regular Languages I. Introduction II. Star Height III. Restricted Star Height IV. Group Complexity V. Star Removal VI. Regularity of Noncounting Classes VII. Optimality of Prefix Codes VIII. Concluding Remarks Acknowledgment ReferencesGenerators of Cones and Cylinders I. Preliminaries II. The Cone of Algebraic Languages III. Cylinders of Algebraic Languages IV. Conclusion ReferencesVery Small Families of Algebraic Nonrational Languages I. Languages That Are Nearly Regular II. Minimal Cones III. The Decreasing Hierarchy ReferencesFormal Languages and their Relation to Automata: What Hopcroft & Ullman Didn't Tell Us I. Introduction II. Coordinate-Free Automata III. Pushdown Automata IV. Turing Machines V. Conclusions ReferencesMorphisms on Free Monoids and Language Theory I. Thue and Lindenmayer II. Problems about Infinite Words III. Equality Sets IV. Forms ReferencesHomomorphisms: Decidability, Equality and Test Sets I. Introduction II. Iterated Homomorphisms III. Homomorphism Equivalence on a Language IV. Elementary Homomorphisms and Equality Sets V. Homomorphism Compatibility VI. Test Sets and Checking Words VII. Representation of Language Families ReferencesA Survey of Results and Open Problems in the Mathematical Theory of L Systems Introduction I. Single Homomorphisms Iterated II. Single Finite Substitutions Iterated III. Several Homomorphisms Iterated IV. Several Finite Substitutions Iterated V. The Relationship to Other Classes of Languages VI. Discussion Acknowledgments ReferencesSome Open Questions and Recent Results on Tree Transducers and Tree Languages I. Introduction II. Tree Transducers and Tree Grammars III. Attribute Grammars as Tree Transducers IV. Computation Trees of Alternating Automata V. The Equivalence Problem for Deterministic Tree Transducers VI. Conclusion Acknowledgments ReferencesThe Interface Between Languages Theory and Complexity Theory I. Introduction II. Complete Problems and Characterization Theorems III. Separation and Containment Results ReferencesPattern Matching in Strings I. Introduction II. Pattern-Matching Problems III. Matching Finite Sets of Keywords IV. Matching Regular Expressions V. Matching Regular Expressions with Back Referencing VI. Conclusions Acknowledgments ReferencesEquations and Rewrite Rules: A Survey 1. Introduction 2. Sorted Algebras 3. Equations and Varieties 4. Proof Theory 5. Initial Algebras and the Word Problem 6. Unification 7. Term Rewriting Systems 8. Termination 9. Compiling Canonical Forms 10. Decidability and Complexity of Word Problems 11. Separable Equational Theories 12. A Meta-Unification Algorithm 13. Extensions and Combinations of Equational Theories 14. Further Results 15. Acknowledgments 16. Appendix 17. ReferencesApplication of Formal Language Theory to Problems of Security and Synchronization Introduction I. Problems of Security II. Synchronization of Concurrent Processes References