Automata for Branching and Layered Temporal Structures: An Investigation into Regularities of Infinite Transition Systems

by Puppis, Gabriele; Goebel, Randy; Siekmann, Jorg; Wahlster, Wolfgang

• ISBN13: 9783642118807
• ISBN10: 3642118801
• Edition: 1st
• Format: Paperback
• Copyright: 2010-02-25
• Publisher: Springer-Verlag New York Inc

Summary

Since 2002, FoLLI awards an annual prize for an outstanding dissertation in the fields of Logic, Language, and Information. This book is based on the Ph.D. thesis of Gabriele Puppis, who was the winner of the E.W. Beth dissertation award for 2007. Puppis' thesis focuses on Logic and Computation and, more specifically, on automata-based decidability techniques for time granularity and on a new method for deciding Monadic Second Order theories of trees. The results presented represent a significant step towards a better understanding of the changes in granularity levels that humans make so easily in cognition of time, space, and other phenomena, whereas their logical and computational structure poses difficult conceptual and computational challenges.

Table of Contents

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.