|
" Handbook of Formal Languages Volume 3 Beyond Words "
Grzegorz Rozenberg
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
733233
|
| Doc. No
|
:
|
b553029
|
| Main Entry
|
:
|
Grzegorz Rozenberg
|
| Title & Author
|
:
|
Handbook of Formal Languages Volume 3 Beyond Words\ Grzegorz Rozenberg
|
| Publication Statement
|
:
|
Berlin Springer Berlin, 2013
|
| Page. NO
|
:
|
XX, 625 Seiten 38 schw.-w. Illustrationen, 8 farbige Illustrationen 235 x 155 mm
|
| ISBN
|
:
|
3642638597
|
|
|
:
|
: 9783642638596
|
| Contents
|
:
|
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.
|
|
|
:
|
Black and white images and finite automata.- 3. Grayscale images and WFA.- 4. Weighted finite transducers.- 5. Examples of WFT.- References.
|
| LC Classification
|
:
|
QA267.3G794 2013
|
| Added Entry
|
:
|
Arto Salomaa
|
|
|
:
|
Grzegorz Rozenberg
|
| |