Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this volume constitutes a selection of papers presented at the Internatonal Conference on Infinity in Logic and Computation, ILC 2007, held in Cape Town, South Africa, in November 2007.
The 7 revised papers presented together with 2 invited talks were carefully selected from 27 initial submissions during two rounds of reviewing and improvement. The papers address all aspects of infinity in automata theory, logic, computability and verification and focus on topics such as automata on infinite objects; combinatorics, cryptography and complexity; computability and complexity on the real numbers; infinite games and their connections to logic; logic, computability, and complexity in finitely presentable infinite structures; randomness and computability; transfinite computation; and verification of infinite state systems.
Author(s): Margaret Archibald, Vasco Brattka, Valentin F. Goranko, Benedikt Löwe
Series: Lecture Notes in Computer Science - Lecture Notes Artificial Intelligence
Publisher: Springer
Year: 2009
Language: English
Pages: 150
Infinity in Logic and Computation......Page 3
Copyright......Page 4
Preface......Page 5
Table of Contents......Page 12
Nadia Busi (1968–2007)......Page 13
Introduction......Page 14
Rational Transducers and Rational Relations......Page 16
Rational Graphs......Page 17
Synchronized Products of Transducers and Automata......Page 19
Model Checking of $K_{t}$ in Rational Kripke Models......Page 21
Normal Forms and Ranks of Formulae......Page 23
Formula Complexity......Page 24
Model Checking Hybrid Extensions of $K_{t}$......Page 25
Counting Modalities......Page 27
A Presentation Based Extension......Page 28
Concluding Remarks......Page 30
References......Page 31
Introduction......Page 33
Basic Definitions......Page 35
Genetic Systems......Page 36
Computational Power of Genetic Systems......Page 39
References......Page 42
Introduction......Page 44
Definitions......Page 46
Basic Results on MDPs......Page 49
MDPs with Limsup Objectives......Page 51
MDPs with Liminf Objectives......Page 54
References......Page 56
Introduction......Page 58
Alternating Tree Automata......Page 60
Playing the Wadge Games......Page 61
Game Automata and Game Languages......Page 62
Two-Way Alternating Parity Tree Automata......Page 64
The Strictness of the Hierarchy......Page 65
References......Page 66
Introduction......Page 68
Preliminaries......Page 71
Counter Systems......Page 72
Pointer Systems......Page 73
Model Checking Issues......Page 75
Model-Checking Programs with Pointers......Page 76
From Pointer Systems to Counter Systems......Page 77
Decidability Results for Programs without Destructive Update......Page 79
Roots Memory Shape......Page 80
From Pointers to Counters......Page 82
Translating the Symbolic Configurations......Page 85
Proof of Theorem 4......Page 88
Proof of Theorem 5......Page 89
Undecidability Results......Page 90
Conclusion......Page 92
References......Page 93
A Examples of Programs......Page 95
B Description of the Translation POST2......Page 96
Introduction......Page 99
The Gaussian Limit – Approximation near the Mean......Page 101
The Case $j=n^{7/4}-x$......Page 107
References......Page 108
Introduction......Page 109
Preliminaries......Page 110
Infinite Words and Deterministic One-Turn Pushdown Automata......Page 112
The Case When the Subset F of Final States is in $K_{1}$......Page 113
The Case When the Subset of Final States is in $K_{2}$......Page 114
Closure Properties......Page 117
One-Turn PDM with Muller Condition......Page 119
References......Page 120
Introduction......Page 121
Fine-Topology and Brattka's Function......Page 122
Self-similar Sets......Page 125
An Infinite System of Contractions......Page 127
Graph-Directed Sets......Page 130
Markov Self-similar Sets versus Graph-Directed Sets......Page 134
References......Page 137
Definitions......Page 138
P $ ubseteq$ PSPACE for Infinite Time Turing Machines......Page 140
P$_{\alpha} \neq$ PSPACE$_{\alpha}$ for Ordinals Up to $\omega^{2}$......Page 143
The Case of Recursive Ordinals......Page 145
The Case of Clockable Ordinals......Page 146
The Case of Suitable Functions $f$......Page 147
However, P$_{f}$ = PSPACE$_{f}$ for `Almost All' $f$......Page 148
References......Page 149
