+612 9045 4394
Automata for Branching and Layered Temporal Structures : An Investigation Into Regularities of Infinite Transition Systems - Gabriele Puppis

Automata for Branching and Layered Temporal Structures

An Investigation Into Regularities of Infinite Transition Systems

Paperback Published: 18th February 2010
ISBN: 9783642118807
Number Of Pages: 206

Share This Book:


or 4 easy payments of $31.26 with Learn more
Ships in 5 to 9 business days

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.

Industry Reviews

"The thesis is a very nice introduction to the area of time granularities and indeed also automata on infinite strings or trees. All major notions are discussed, formally introduced, exemplified, and compared to similar notions. The language is generally appropriate and understandable and the mathematics in the contribution should be understandable by any graduate student. Since the essential definitions and proofs are provided, the book can easily be read without additional literature." (Andreas Maletti, Mathematical Reviews, February, 2016)

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.

ISBN: 9783642118807
ISBN-10: 3642118801
Series: Lecture Notes in Artificial Intelligence
Audience: General
Format: Paperback
Language: English
Number Of Pages: 206
Published: 18th February 2010
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.11 x 15.49  x 1.27
Weight (kg): 0.34