Formal Language Theory
Perspectives and Open Problems
- 1st Edition - September 23, 2014
- Editor: Ronald V. Book
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 3 6 4 1 - 4
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 6 7 5 0 - 0
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… Read more
Purchase options
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.
List of Contributors
Preface
Acknowledgments
Methods for Specifying Families of Formal Languages — Past- Present- Future
I. Introduction
II. Origins
III. Specification Formalism
IV. Grammars
V. Conclusions
References
Open 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
References
Generators of Cones and Cylinders
I. Preliminaries
II. The Cone of Algebraic Languages
III. Cylinders of Algebraic Languages
IV. Conclusion
References
Very Small Families of Algebraic Nonrational Languages
I. Languages That Are Nearly Regular
II. Minimal Cones
III. The Decreasing Hierarchy
References
Formal 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
References
Morphisms on Free Monoids and Language Theory
I. Thue and Lindenmayer
II. Problems about Infinite Words
III. Equality Sets
IV. Forms
References
Homomorphisms: 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
References
A 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
References
Some 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
References
The Interface Between Languages Theory and Complexity Theory
I. Introduction
II. Complete Problems and Characterization Theorems
III. Separation and Containment Results
References
Pattern 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
References
Equations 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. References
Application of Formal Language Theory to Problems of Security and Synchronization
Introduction
I. Problems of Security
II. Synchronization of Concurrent Processes
References
- Edition: 1
- Published: September 23, 2014
- Language: English
Read Formal Language Theory on ScienceDirect