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

by ; ; ;
  • ISBN13:


  • ISBN10:


  • Edition: 1st
  • Format: Paperback
  • Copyright: 2010-02-25
  • Publisher: Springer-Verlag New York Inc
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $99.00


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

Introductionp. 1
Word Automata and Time Granularitiesp. 5
Background Knowledgep. 7
Words and Languagesp. 7
Periodicity of Wordsp. 8
Word Automatap. 12
Time Granularitiesp. 13
The String-Based and Automaton-Based Approachesp. 17
The Granspec Formalismp. 18
From Granspecs to Single-String Automatap. 19
Counters and Multiple Transitionsp. 20
The Logical Counterpart of RCSSAp. 23
Compact and Tractable Representationsp. 25
Nested Repetitions of Wordsp. 28
Algorithms on NCSSAp. 31
Optimizing Representationsp. 40
Reasoning on Sets of Granularitiesp. 57
Languages of Ultimately Periodic Wordsp. 57
Ultimately Periodic Automatap. 62
Algorithms on UPAp. 73
Applications to Time Granularityp. 81
Discussionp. 86
Tree Automata and Logicsp. 89
Background Knowledgep. 91
Graphs and Treesp. 91
Tree Automatap. 92
Monadic Second-Order Logicp. 95
The Model Checking Problemp. 96
The Contraction Method for Tree Automatap. 100
Features and Typesp. 102
Types and the Acceptance Problemp. 104
From Trees to Their Retractionsp. 105
An Examplep. 111
Tree Transformationsp. 113
Tree Recoloringsp. 113
Tree Substitutionsp. 116
Tree Transducersp. 121
Inverse Substitutionsp. 125
A Summaryp. 128
The Class of Reducible Treesp. 128
Compositional Properties of Typesp. 131
Closure Propertiesp. 136
Effectiveness of the Contraction Methodp. 148
Reducible Trees and the Caucal Hierarchyp. 148
Two-Way Alternating Tree Automatap. 151
Morphic Treesp. 154
Layered Temporal Structuresp. 158
Discussionp. 166
Summaryp. 169
Technical Proofsp. 171
Proofs of Theorem 5 and Theorem 6p. 171
Proof of Theorem 8p. 181
Proof of Proposition 34p. 187
Referencesp. 191
Notationp. 199
Indexp. 201
Table of Contents provided by Ingram. All Rights Reserved.

Rewards Program

Write a Review