عنوان

Handbook of Formal Languages Volume 3 Beyond Words

(Number (ISBN

3642638597

(Number (ISBN

9783642638596

Number

b553029

Title Proper

Handbook of Formal Languages Volume 3 Beyond Words

General Material Designation

[Book]

First Statement of Responsibility

Grzegorz Rozenberg

Name of Publisher, Distributor, etc.

Berlin Springer Berlin

Date of Publication, Distribution, etc.

2013

Specific Material Designation and Extent of Item

XX, 625 Seiten 38 schw.-w. Illustrationen, 8 farbige Illustrationen 235 x 155 mm

Text of Note

Black and white images and finite automata.- 3. Grayscale images and WFA.- 4. Weighted finite transducers.- 5. Examples of WFT.- References.

Text of Note

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-Fraisse 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 Moebius 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-Fraisse 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 Buchi 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.

Class number

Book number

Grzegorz Rozenberg

Arto Salomaa

Grzegorz Rozenberg

Electronic name

[Book]

Y