Handbook of Formal Languages, Softcover reprint of the original 1st ed. 1997 Volume 3 Beyond Words

The need for a comprehensive survey-type exposition on formal languages and related mainstream areas of computer science has been evident for some years. In the early 1970s, when . the book Formal Languages by the second­ mentioned editor appeared, it was still quite feasible to write a comprehensive book with that title and include also topics of current research interest. This would not be possible anymore. A standard-sized book on formal languages would either have to stay on a fairly low level or else be specialized and restricted to some narrow sector of the field. The setup becomes drastically different in a collection of contributions, where the best authorities in the world join forces, each of them concentrat­ ing on their own areas of specialization. The present three-volume Handbook constitutes such a unique collection. In these three volumes we present the current state of the art in formal language theory. We were most satisfied with the enthusiastic response given to our request for contributions by specialists representing various subfields. The need for a Handbook of Formal Languages was in many answers expressed in different ways: as an easily accessible his­ torical reference, a general source of information, an overall course-aid, and a compact collection of material for self-study. We are convinced that the final result will satisfy such various needs. The theory of formal languages constitutes the stem or backbone of the field of science now generally known as theoretical computer science.

of Volume 3.- 1. Tree Languages.- 1. Introduction.- 2. Trees and terms.- 3. Algebraic preliminaries.- 4. Term rewriting systems.- 5. Finite tree recognizers.- 6. Regular tree grammars.- 7. Tree language operations and closure properties of Rec.- 8. Local tree languages.- 9. A Kleene theorem for tree languages.- 10. Regular tree systems.- 11. Algebraic characterizations of recognizability.- 12. Monadic second-order logic and regular tree languages.- 13. Families of special regular tree languages.- 14. The yield-function and context-free languages.- 15. Context-free tree grammars and pushdown tree recognizers.- 16. Tree transformations and tree transducers.- 17. Composition and decomposition of tree transformations.- 18. Tree transducers with regular look-ahead.- 19. Generalized syntax directed translations.- 20. Surface tree languages.- 21. The hierarchies of surface tree languages and transformational languages.- 22. Some further topics.- References.- 2. Tree-Adjoining Grammars.- 1. Introduction.- 2. Tree-adjoining grammars.- 2.1 Adjoining constraints.- 2.2 Derivation in TAG.- 2.3 Some properties of the string languages and tree sets.- 3. Lexicalized grammars.- 4. ‘Lexicalization’ of CFGs.- 4.1 Substitution and lexicalization of CFGs.- 4.2 Lexicalization of CFGs with TAGs.- 5. Closure of TAGs under lexicalization.- 6. Summary of lexicalization.- 7. Embedded push-down automaton (EPDA).- 7.1 Crossed dependencies.- 8. Linguistic relevance.- 9. Some variants of TAGs.- 9.1 Feature structure based TAGs.- 9.2 Synchronous TAGs.- 9.3 Probabilistic LTAGs.- 9.4 Using description trees in TAG.- 9.5 Muti-component TAGs (MCTAG).- 10. Parsing lexicalized tree-adjoining grammars (LTAG).- 10.1 Left to right parsing of TAGs.- 10.2 The algorithm.- 10.3 An example.- 10.4 Implementation.- 10.5 Complexity.- 10.6 The parser.- 10.7 Parsing substitution.- 10.8 The valid prefix property and parsing of tree-adjoining grammar.- 11 Summary.- References.- 3. Context-Free Graph Grammars.- 1. Introduction.- 2. Node and edge replacement.- 3. Hyperedge replacement grammars.- 3.1 Definitions and examples.- 3.2 Normal forms.- 3.3 Subclasses.- 4. Node replacement grammars.- 4.1 Definitions and examples.- 4.2 Subclasses and normal forms.- 4.3 Comparison of HR and NR.- 5. Monadic second order logic.- 6. Graph grammars generating strings and trees.- 7. Tree grammars generating graphs.- References.- 4. Two-Dimensional Languages.- 1. Introduction.- 2. Preliminaries.- 3. Regular expressions.- 4. Automata.- 4.1 Four-way automata.- 4.2 On-line tesselation automata.- 5. Grammars.- 6. Logic formulas.- 7. Tiling systems.- 7.1 Local two-dimensional languages.- 7.2 Tiling recognizable languages.- 7.3 Closure properties.- 7.4 Domino systems.- 7.5 Generalizations of local languages.- 8. Equivalence theorems.- 8.1 Tiling systems and automata.- 8.2 Tiling systems and logic formulas.- 8.3 Tiling systems and regular expressions.- 8.4 Comparing all families.- 9. Properties of recognizable languages.- 9.1 Necessary conditions for recognizability.- 9.2 Undecidability results.- 10. Recognizable functions.- 11. Beyond finite state recognizability.- References.- 5. Basics of Term Rewriting.- 1. Introduction.- 2. Terms.- 3. Church—Rosser properties.- 4. Orderings.- 5. Completion.- 6. Rewriting modulo a relation.- 7. Sundries.- References and further reading.- 6. ?-Languages.- 1. Introduction.- 2. Topology for languages and ?-languages.- 2.1 Cantor topology.- 2.2 Continuous mappings.- 2.3 Wadge’s hierarchy.- 2.4 Joint topologies on X* ? X?.- 3. The Chomsky hierarchy of ?-languages.- 3.1 Acceptance of ?-languages by automata.- 3.2 Finite automata and regular ?-languages.- 3.3 Context-free ?-languages.- 3.4 ?-languages accepted by Turing machines.- 4. Languages and ?-languages.- 4.1 ?-Kleene closure.- 4.2 ?-power languages.- 4.3 ?-transducers, gsm-mappings, and ?-transductions.- 4.4 Limit-closure.- 5. Wagner’s hierarchy.- 5.1 Wagner classes.- 5.2 gsm-reducibility.- References.- 7. Languages, Automata, and Logic.- 1. Introduction.- 2. Models and formulas.- 2.1 Words, trees, and graphs as models.- 2.2 First-order logic.- 2.3 Monadic second-order logic.- 3. Automata and MSO-logic on finite words and trees.- 3.1 MSO-logic on words.- 3.2 MSO-logic on traces and trees.- 4. First-order definability.- 4.1 The Ehrenfeucht—Fraïssé game.- 4.2 Locally threshold testable sets.- 4.3 Star-free languages.- 5. Automata and MSO-logic on infinite words.- 5.1 ?-automata.- 5.2 Determinization of ?-automata.- 5.3 Applications to definability and decision problems.- 6. Automata and MSO-logic on infinite trees.- 6.1 Automata on infinite trees.- 6.2 Determinacy and complementation.- 6.3 Applications to decision problems of MSO-logic.- References.- 8. Partial Commutation and Traces.- 1. Introduction.- 2. Free partially commutative monoids.- 2.1 First definitions and basic properties.- 2.2 Projection techniques and Levi’s lemma.- 2.3 Normal forms.- 2.4 A simple algorithm to compute normal forms.- 2.5 Möbius functions and normal forms.- 2.6 Bibliographical remarks.- 3. Combinatorial properties.- 3.1 Equations.- 3.2 Strong homomorphisms and codings.- 3.3 Trace codes.- 3.4 Bibliographical remarks.- 4. Recognizable trace languages.- 4.1 Basic facts about recognizable and rational sets.- 4.2 Recognizability and rational operations.- 4.3 The rank.- 4.4 Recognizability and the lexicographic normal form.- 4.5 The star problem and the finite power property.- 4.6 An algorithm to compute closures.- 4.7 Bibliographical remarks.- 5. Rational trace languages.- 5.1 Unambiguous languages.- 5.2 Decidability results.- 5.3 Bibliographical remarks.- 6. Dependence graphs and logic.- 6.1 Dependence graphs.- 6.2 Traces and logic.- 6.3 Ehrenfeucht—Fraïssé games.- 6.4 Bibliographical remarks.- 7. Asynchronous automata.- 7.1 Zielonka’s theorem.- 7.2 Asynchronous cellular automata.- 7.3 Changing concurrent-read to exclusive-read.- 7.4 Changing exclusive-write to owner-write.- 7.5 The construction for triangulated dependence alphabets.- 7.6 Bounded time-stamps in a distributed system.- 7.7 Bibliographical remarks.- 8. Infinite traces.- 8.1 Real traces.- 8.2 Asynchronous Büchi and Muller automata.- 8.3 Complex traces.- 8.4 Topological properties and the domain of ?-traces.- 8.5 Bibliographical remarks and further reading.- References.- 9. Visual Models of Plant Development.- 1. Introduction.- 2. Developmental models of plant architecture.- 2.1 The modular structure of plants.- 2.2 Plant development as a rewriting process.- 3. Formal description of branching structures.- 3.1 Axial trees and bracketed strings.- 3.2 The bracketed string notation.- 3.3 The turtle interpretation of bracketed strings.- 4. Fundamentals of modeling using L-systems.- 4.1 Parametric D0L-systems.- 4.2 Examples of parametric D0L-system models.- 4.2.1 Fractal generation.- 4.2.2 Simulation of development.- 4.2.3 Exploration of parameter space.- 4.2.4 Modeling mesotonic and acrotonic structures.- 5. Random factors in development.- 5.1 The role of randomness in the description of development.- 5.2 Stochastic 0L-systems.- 5.3 A stochastic tree model.- 6. Life, death, and reproduction.- 6.1 Non-propagating L-systems.- 6.2 L-systems with a cut symbol.- 6.3 Fragmentation.- 7. Development controlled by endogenous mechanisms.- 7.1 Information flow in growing plants.- 7.2 Context-sensitive L-systems.- 7.3 Examples.- 7.3.1 Development of a mesotonic structure.- 7.3.2 Attack of a plant by an insect.- 7.3.3 Development controlled by resource allocation.- 8. Development controlled by exogenous mechanisms.- 8.1 Plants and their environment.- 8.2 Environmentally-sensitive L-systems.- 8.3 Examples.- 8.3.1 A deterministic model of plant response to pruning.- 8.3.2 A stochastic model of tree response to pruning.- 8.3.3 Plant climbing.- 8.3.4 Directional cues in development.- 9. Conclusions.- 10. Acknowledgements.- References.- 10. Digital Images and Formal Languages.- 1. Introduction.- 2. Black and white images and finite automata.- 3. Grayscale images and WFA.- 4. Weighted finite transducers.- 5. Examples of WFT.- References.