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
Tax/VAT will be calculated at check-out Price includes VAT (GST)
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
54.95
38.47
38.47
38.47
38.47
38.47
43.96
43.96
72.95
51.06
51.06
51.06
51.06
51.06
58.36
58.36
43.99
30.79
30.79
30.79
30.79
30.79
35.19
35.19
Unavailable
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.

Description

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

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

Details

No. of pages:
468
Language:
English
Copyright:
© Academic Press 1980
Published:
Imprint:
Academic Press
eBook ISBN:
9781483267500

About the Editor

Ronald V. Book