Tree Automata Techniques and Applications

Errata......Page 9
Introduction......Page 11
Preliminaries......Page 15
Recognizable Tree Languages and Finite Tree Automata......Page 19
Finite Tree Automata......Page 20
The Pumping Lemma for Recognizable Tree Languages......Page 28
Closure Properties of Recognizable Tree Languages......Page 29
Tree Homomorphisms......Page 31
Minimizing Tree Automata......Page 35
Top Down Tree Automata......Page 38
Decision Problems and their Complexity......Page 39
Exercises......Page 43
Bibliographic Notes......Page 47
Definitions......Page 51
Regular Expressions. Kleene's Theorem for Tree Languages......Page 54
Substitution and Iteration......Page 55
Regular Expressions and Regular Tree Languages......Page 57
Regular Equations......Page 61
Context-free Word Languages and Regular Tree Languages......Page 63
Context-free Tree Languages......Page 66
IO and OI Tree Grammars......Page 67
Exercises......Page 68
Bibliographic notes......Page 71
Introduction......Page 73
Three Notions of Recognizability......Page 75
Examples of The Three Notions of Recognizability......Page 77
Comparisons Between the Three Classes......Page 78
Closure Properties for Rec and Rec; Cylindrification and Projection......Page 80
Closure of GTT by Composition and Iteration......Page 82
Syntax......Page 87
Examples......Page 88
Restricting the Syntax......Page 89
Definable Sets are Recognizable Sets......Page 90
Recognizable Sets are Definable......Page 94
Extensions......Page 95
Terms and Sorts......Page 96
The Encompassment Theory for Linear Terms......Page 97
The First-order Theory of a Reduction Relation: the Case Where no Variables are Shared......Page 99
Reduction Strategies......Page 100
Application to Rigid E-unification......Page 102
Application to Higher-order Matching......Page 103
Exercises......Page 106
Applications of tree automata to constraint solving......Page 109
Application of tree automata to decision problems in term rewriting......Page 110
Other applications......Page 111
Introduction......Page 113
The Most General Class......Page 114
Reducing Non-determinism and Closure Properties......Page 117
Decision Problems......Page 120
Emptiness Decision......Page 122
Reduction Automata......Page 125
Closure Properties......Page 126
Emptiness Decision......Page 127
Term Rewriting Systems......Page 132
Exercises......Page 133
Bibliographic notes......Page 135
Introduction......Page 137
Tree Set Automata......Page 142
Hierarchy of GTSA-recognizable Languages......Page 145
Regular Generalized Tree Sets, Regular Runs......Page 146
Closure properties......Page 149
Emptiness Property......Page 152
Other Decision Results......Page 154
Set Constraints and Automata......Page 155
Decidability Results for Set Constraints......Page 156
Bibliographical Notes......Page 158
Introduction......Page 161
Introduction to Rational Transducers......Page 162
The Homomorphic Approach......Page 166
Introduction to Tree Transducers......Page 167
Bottom-up Tree Transducers......Page 171
Top-down Tree Transducers......Page 174
Structural Properties......Page 176
Homomorphisms and Tree Transducers......Page 177
Exercises......Page 178
Bibliographic notes......Page 181
Alternating Word Automata......Page 183
Alternating Tree Automata......Page 185
Closure Properties......Page 187
From Alternating to Deterministic Automata......Page 188
The Clausal Formalism......Page 189
The Set Constraints Formalism......Page 190
Two Way Alternating Tree Automata......Page 191
Two Way Automata and Definite Set Constraints......Page 193
Exercises......Page 195
Bibliographic Notes......Page 196
Introduction......Page 199
Unranked Trees and Hedges......Page 200
Hedge Automata......Page 201
Deterministic Automata......Page 205
Encodings and Closure Properties......Page 206
First-Child-Next-Sibling Encoding......Page 207
Extension Operator......Page 210
Closure Properties......Page 211
Weak Monadic Second Order Logic......Page 212
Representations of Horizontal Languages......Page 214
Membership......Page 216
Emptiness......Page 219
Inclusion......Page 220
Minimizing the Number of States......Page 221
Problems for Minimizing the Whole Representation......Page 223
Stepwise automata......Page 224
XML Schema Languages......Page 229
Document Type Definition (DTD)......Page 232
XML Schema......Page 236
Exercises......Page 239
Bibliographic Notes......Page 242
Bibliography......Page 245
Index......Page 259