Overview

To our families The formal language theory was born in the middle of our century as a tool for modelling and investigating the syntax of natural languages, and it has been developed mainly in connection with programming language handling. Of course, one cannot deny the impulses from neuronal net investigations, from logic, as well as the mathematical motivation of the early researches. The theory has rapidly become a mature one, with specific problems, techniques and results and with an internal self-motivated life. Abstract enough to deal with the essence of modelled phenomena, formal language theory has been applied during the last years to many further non-linguistical fields, sometimes surprisingly far from the previous areas of applications; such fields are developmental biology, economic modelling, semiotics of folklore, dramatic and musical works, cryptography, sociology, psychology, and so on. All these applications as well as the traditional ones to natural and programming languages revealed a rather common conclusion: very frequently, context-free gram­ mars, the most developed and the most ""tractable"" type of Chomsky grammars, are not sufficient. ""The world is non-context-free"" (and we shall ""prove"" this statement in Section 0.4). On the other hand, the context-sensitive grammars are too powerful and definitely ""intractable"" (many problems are undecidable or are still open; there is no semantic interpretation of the nonterminals an so on). This is the reason to look for intermediate generative devices, conjoining the simpli­ city and the beauty of context-free grammars with the power of context-sensitive ones.

Full Product Details

Author:   Jürgen Dassow ,  Gheorghe Paun
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   Softcover reprint of the original 1st ed. 1989
Volume:   18
Dimensions:   Width: 17.00cm , Height: 1.70cm , Length: 24.20cm
Weight:   0.537kg
ISBN:  

9783642749346

ISBN 10:   3642749348
Pages:   308
Publication Date:   13 December 2011
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

0. Introduction.- 0.1. Languages and Language Families.- 0.2. Language Generating Devices.- 0.3. Algorithms and Decidability.- 0.4. Seven Circumstances Where Context-Free Grammars Are Not Enough.- 1. Three Types of Regulation: Matrix, Programmed, and Random Context Grammars.- 1.1. Definitions and Examples.- 1.2. The Generative Capacity.- 1.3. Fundamental Properties.- 1.4. Leftmost Derivations.- 1.5. Special Cases.- 2. Other Grammars with Regulation.- 2.1. Prescribed Sequences.- 2.2. Dependence on Previous Productions.- 2.3. Context Conditions.- 2.4. Further Regulated Devices.- 2.5. Conclusions.- 3. Grammars of Finite Index.- 3.1. The Generative Power of Finite Index Grammars.- 3.2. Properties of Grammars and Languages of Finite Index.- 4. The Syntactic Complexity of Regulated Rewriting.- 4.1. Nonterminal Complexity. Comparison.- 4.2. Nonterminal Complexity. Families of Languages with Bounded Complexity.- 4.3. Further Complexity Measures.- 5. Pure Regulated Grammars and Languages and Their Codings.- 5.1. Hierarchy of Pure Regulated Languages.- 5.2. Codings of Pure Languages.- 6. Combined Regulations.- 6.1. Indian and Russian Parallel Versions of Regulated Grammars.- 6.2. Ordered Versions of Regulated Rewriting.- 6.3. Random Context Versions of Regulated Grammars.- 7. Some Special Problems.- 7.1. Automata Characterizations.- 7.2. Szilard Language of Regulated Grammars.- 7.3. Grammar Forms.- 8. Regulated L Systems.- 9. Applications of Regulated Rewritting.- 9.1. Relationships with Programming Languages.- 9.2. Regulated Rewritting and Petri Nets.- 9.3. Modelling of Economic Processes.- 9.4. Modelling Folklore Fairy-Tales, Dramatic, Musical and Visual Art Works.- 9.5. The Mappings Investigation.- 10. A Common Generalization: Selective Substitution Grammars.- Notation Index.-Author Index.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions