Mathematical Theory and Computational Practice: 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings

Front Matter....Pages -
First-Order Universality for Real Programs....Pages 1-10
Skolem + Tetration Is Well-Ordered....Pages 11-20
Structures of Some Strong Reducibilities....Pages 21-30
Complexity of Existential Positive First-Order Logic....Pages 31-36
Stochastic Programs and Hybrid Automata for (Biological) Modeling....Pages 37-48
Numberings and Randomness....Pages 49-58
The Strength of the Grätzer-Schmidt Theorem....Pages 59-67
Hyperloops Do Not Threaten the Notion of an Effective Procedure....Pages 68-78
Minimum Entropy Combinatorial Optimization Problems....Pages 79-88
Program Self-reference in Constructive Scott Subdomains....Pages 89-98
 $\Sigma^0_1$ and $\Pi^0_1$ Equivalence Structures....Pages 99-108
Immunity for Closed Sets....Pages 109-117
Lower Bounds for Kernelizations and Other Preprocessing Procedures....Pages 118-128
Infinite-Time Turing Machines and Borel Reducibility....Pages 129-133
Cutting Planes and the Parameter Cutwidth....Pages 134-143
Members of Random Closed Sets....Pages 144-153
Lowness for Demuth Randomness....Pages 154-166
Graph States and the Necessity of Euler Decomposition....Pages 167-177
On Stateless Multicounter Machines....Pages 178-187
Computability of Continuous Solutions of Higher-Type Equations....Pages 188-197
Equivalence Relations on Classes of Computable Structures....Pages 198-207
Fractals Generated by Algorithmically Random Brownian Motion....Pages 208-217
Computable Exchangeable Sequences Have Computable de Finetti Measures....Pages 218-231
Spectra of Algebraic Fields and Subfields....Pages 232-241
Definability in the Local Theory of the ω -Enumeration Degrees....Pages 242-249
Computability of Analytic Functions with Analytic Machines....Pages 250-259
An Application of Martin-Löf Randomness to Effective Probability Theory....Pages 260-269
Index Sets and Universal Numberings....Pages 270-279
Ordinal Computability....Pages 280-289
A Gandy Theorem for Abstract Structures and Applications to First-Order Definability....Pages 290-299
Constructing New Aperiodic Self-simulating Tile Sets....Pages 300-309
Relationship between Kanamori-McAloon Principle and Paris-Harrington Theorem....Pages 310-323
The First Order Theories of the Medvedev and Muchnik Lattices....Pages 324-331
Infima of d . r . e . Degrees....Pages 332-341
A Divergence Formula for Randomness and Dimension....Pages 342-351
On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants....Pages 352-361
0 ″ -Categorical Completely Decomposable Torsion-Free Abelian Groups....Pages 362-371
Notes on the Jump of a Structure....Pages 372-378
A General Representation Theorem for Probability Functions Satisfying Spectrum Exchangeability....Pages 379-388
Stability under Strategy Switching....Pages 389-398
Computational Heuristics for Simplifying a Biological Model....Pages 399-408
Functions Definable by Arithmetic Circuits....Pages 409-418
Survey on Oblivious Routing Strategies....Pages 419-429
An Approach to the Engineering of Cellular Models Based on P Systems....Pages 430-436
Decidability of Sub-theories of Polynomials over a Finite Field....Pages 437-446
Chaitin Ω Numbers and Halting Problems....Pages 447-456
Bayesian Data Integration and Enrichment Analysis for Predicting Gene Function in Malaria....Pages 457-466
Dialectica Interpretation with Fine Computational Control....Pages 467-477
Algorithmic Minimal Sufficient Statistic Revisited....Pages 478-487
A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets....Pages 488-498
On Generating Independent Random Strings....Pages 499-508
Back Matter....Pages -