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