Formal Language Theory - 1st Edition - ISBN: 9780121153502, 9781483267500

Formal Language Theory

1st Edition

Perspectives and Open Problems

Editors: Ronald V. Book
eBook ISBN: 9781483267500
Imprint: Academic Press
Published Date: 28th December 1980
Page Count: 468
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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.

Table of Contents

List of Contributors



Methods for Specifying Families of Formal Languages — Past- Present- Future

I. Introduction

II. Origins

III. Specification Formalism

IV. Grammars

V. Conclusions


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



Generators of Cones and Cylinders

I. Preliminaries

II. The Cone of Algebraic Languages

III. Cylinders of Algebraic Languages

IV. Conclusion


Very Small Families of Algebraic Nonrational Languages

I. Languages That Are Nearly Regular

II. Minimal Cones

III. The Decreasing Hierarchy


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


Morphisms on Free Monoids and Language Theory

I. Thue and Lindenmayer

II. Problems about Infinite Words

III. Equality Sets

IV. Forms


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


A Survey of Results and Open Problems in the Mathematical Theory of L Systems


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



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



The Interface Between Languages Theory and Complexity Theory

I. Introduction

II. Complete Problems and Characterization Theorems

III. Separation and Containment Results


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



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


I. Problems of Security

II. Synchronization of Concurrent Processes



No. of pages:
© Academic Press 1980
Academic Press
eBook ISBN:

About the Editor

Ronald V. Book

Ratings and Reviews