Formal Language Theory

Perspectives and Open Problems

1st Edition - May 10, 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

SUSTAINABLE DEVELOPMENT

Innovate. Sustain. Transform.

Save up to 30% on top Physical Sciences & Engineering titles!

Explore today

Physical science & engineering for sustainable development book covers

Institutional subscription on ScienceDirect

Request a sales quote

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

Life Sciences

Physical Sciences & Engineering

Social Sciences & Humanities

Health

Formal Language Theory

Perspectives and Open Problems

Purchase options

Innovate. Sustain. Transform.

Institutional subscription on ScienceDirect