Introduction | p. 1 |
Word Automata and Time Granularities | p. 5 |
Background Knowledge | p. 7 |
Words and Languages | p. 7 |
Periodicity of Words | p. 8 |
Word Automata | p. 12 |
Time Granularities | p. 13 |
The String-Based and Automaton-Based Approaches | p. 17 |
The Granspec Formalism | p. 18 |
From Granspecs to Single-String Automata | p. 19 |
Counters and Multiple Transitions | p. 20 |
The Logical Counterpart of RCSSA | p. 23 |
Compact and Tractable Representations | p. 25 |
Nested Repetitions of Words | p. 28 |
Algorithms on NCSSA | p. 31 |
Optimizing Representations | p. 40 |
Reasoning on Sets of Granularities | p. 57 |
Languages of Ultimately Periodic Words | p. 57 |
Ultimately Periodic Automata | p. 62 |
Algorithms on UPA | p. 73 |
Applications to Time Granularity | p. 81 |
Discussion | p. 86 |
Tree Automata and Logics | p. 89 |
Background Knowledge | p. 91 |
Graphs and Trees | p. 91 |
Tree Automata | p. 92 |
Monadic Second-Order Logic | p. 95 |
The Model Checking Problem | p. 96 |
The Contraction Method for Tree Automata | p. 100 |
Features and Types | p. 102 |
Types and the Acceptance Problem | p. 104 |
From Trees to Their Retractions | p. 105 |
An Example | p. 111 |
Tree Transformations | p. 113 |
Tree Recolorings | p. 113 |
Tree Substitutions | p. 116 |
Tree Transducers | p. 121 |
Inverse Substitutions | p. 125 |
A Summary | p. 128 |
The Class of Reducible Trees | p. 128 |
Compositional Properties of Types | p. 131 |
Closure Properties | p. 136 |
Effectiveness of the Contraction Method | p. 148 |
Reducible Trees and the Caucal Hierarchy | p. 148 |
Two-Way Alternating Tree Automata | p. 151 |
Morphic Trees | p. 154 |
Layered Temporal Structures | p. 158 |
Discussion | p. 166 |
Summary | p. 169 |
Technical Proofs | p. 171 |
Proofs of Theorem 5 and Theorem 6 | p. 171 |
Proof of Theorem 8 | p. 181 |
Proof of Proposition 34 | p. 187 |
References | p. 191 |
Notation | p. 199 |
Index | p. 201 |
Table of Contents provided by Ingram. All Rights Reserved. |
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.