Logic and Theory of Algorithms: 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008 Proceedings

Front Matter....Pages -
Deterministic Graphical Games Revisited....Pages 1-10
Program Schemes with Deep Pushdown Storage....Pages 11-21
Herbrand Theorems and Skolemization for Prenex Fuzzy Logics....Pages 22-31
Decidability of Hybrid Logic with Local Common Knowledge Based on Linear Temporal Logic LTL....Pages 32-41
Pure Iteration and Periodicity....Pages 42-51
Programming Experimental Procedures for Newtonian Kinematic Machines....Pages 52-66
Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time....Pages 67-76
A Summation Algorithm from 11 th Century China....Pages 77-83
Sequential Automatic Algebras....Pages 84-93
The Role of Classical Computation in Measurement-Based Quantum Computation....Pages 94-99
The Algebraic Counterpart of the Wagner Hierarchy....Pages 100-109
Computing by Observing: A Brief Survey....Pages 110-119
A Quantum Information-Theoretic Proof of the Relation between Horn’s Problem and the Littlewood-Richardson Coefficients....Pages 120-128
Pell Equations and Weak Regularity Principles....Pages 129-138
Computable Categoricity of Graphs with Finite Components....Pages 139-148
P Automata: Membrane Systems as Acceptors....Pages 149-151
On the Processing Power of Protozoa....Pages 152-153
Computing Equilibria in Large Games We Play....Pages 154-157
A Week-End Off: The First Extensive Number-Theoretical Computation on the ENIAC....Pages 158-167
Phase Transitions for Weakly Increasing Sequences....Pages 168-174
Succinct NP Proofs from an Extractability Assumption....Pages 175-185
Describing the Wadge Hierarchy for the Alternation Free Fragment of μ -Calculus (I)....Pages 186-195
Subrecursive Complexity of Identifying the Ramsey Structure of Posets....Pages 196-205
Solving Simple Stochastic Games....Pages 206-209
The Shrinking Property for NP and coNP....Pages 210-220
On the Hardness of Truthful Online Auctions with Multidimensional Constraints....Pages 221-230
Effective Dimensions and Relative Frequencies....Pages 231-240
Reachability in Linear Dynamical Systems....Pages 241-250
Hybrid Functional Interpretations....Pages 251-260
The Algorithm Concept – Tool for Historiographic Interpretation or Red Herring?....Pages 261-272
Adversarial Scheduling Analysis of Game-Theoretic Models of Norm Diffusion....Pages 273-282
A Simple P-Matrix Linear Complementarity Problem for Discounted Games....Pages 283-293
Implementing Spi Calculus Using Nominal Techniques....Pages 294-305
An Enhanced Theory of Infinite Time Register Machines....Pages 306-315
Many Facets of Complexity in Logic....Pages 316-325
On the Computational Power of Enhanced Mobile Membranes....Pages 326-335
Recursion in Higher Types and Resource Bounded Turing Machines....Pages 336-348
Computability and Complexity in Self-assembly....Pages 349-358
Extraction in Coq: An Overview....Pages 359-369
Joining to High Degrees....Pages 370-378
Factoring Out Intuitionistic Theorems: Continuity Principles and the Uniform Continuity Theorem....Pages 379-388
Interpreting Localized Computational Effects Using Operators of Higher Type....Pages 389-402
Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants....Pages 403-406
Updatable Timed Automata with Additive and Diagonal Constraints....Pages 407-416
First-Order Model Checking Problems Parameterized by the Model....Pages 417-427
Domain Theory and the Causal Structure of Space-Time....Pages 428-430
Recursion on Nested Datatypes in Dependent Type Theory....Pages 431-446
Perfect Local Computability and Computable Simulations....Pages 447-456
Complete Determinacy and Subsystems of Second Order Arithmetic....Pages 457-466
Internal Density Theorems for Hierarchies of Continuous Functionals....Pages 467-475
Two-by-Two Substitution Systems and the Undecidability of the Domino Problem....Pages 476-485
The Relative Consistency of the Axiom of Choice — Mechanized Using Isabelle/ZF....Pages 486-490
Upper Semilattices in Many-One Degrees....Pages 491-497
Union of Reducibility Candidates for Orthogonal Constructor Rewriting....Pages 498-510
The Quantum Complexity of Markov Chain Monte Carlo....Pages 511-522
Topological Dynamics of 2D Cellular Automata....Pages 523-532
Complexity of Aperiodicity for Topological Properties of Regular ω -Languages....Pages 533-543
 ω -Degree Spectra....Pages 544-553
Cupping Classes of $\\Sigma^0_2$ Enumeration Degrees....Pages 554-566
Principal Typings for Explicit Substitutions Calculi....Pages 567-578
How We Think of Computing Today....Pages 579-593
Back Matter....Pages -