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

• Corporate Author: SpringerLink (Online service)
• Other Authors: Ambos-Spies, Klaus (Editor), Löwe, Benedikt (Editor), Merkle, Wolfgang (Editor)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2009.
• Series: Lecture Notes in Computer Science, 5635
• Subjects: Computer science.; Computers.; Algorithms.; Computer science > Mathematics.; Bioinformatics.; Computer Science.; Theory of Computation.; Mathematics of Computing.; Algorithm Analysis and Problem Complexity.; Computing Methodologies.; Computational Biology/Bioinformatics.

This book constitutes the proceedings of the 5th Conference on Computability in Europe, CiE 2009, held in Heidelberg, Germany, during July 19-24, 2009. The 34 papers presented together with 17 invited lectures were carefully reviewed and selected from 100 submissions. The aims of the conference is t...

Table of Contents:

• First-Order Universality for Real Programs
• Skolem + Tetration Is Well-Ordered
• Structures of Some Strong Reducibilities
• Complexity of Existential Positive First-Order Logic
• Stochastic Programs and Hybrid Automata for (Biological) Modeling
• Numberings and Randomness
• The Strength of the Grätzer-Schmidt Theorem
• Hyperloops Do Not Threaten the Notion of an Effective Procedure
• Minimum Entropy Combinatorial Optimization Problems
• Program Self-reference in Constructive Scott Subdomains
• and Equivalence Structures
• Immunity for Closed Sets
• Lower Bounds for Kernelizations and Other Preprocessing Procedures
• Infinite-Time Turing Machines and Borel Reducibility
• Cutting Planes and the Parameter Cutwidth
• Members of Random Closed Sets
• Lowness for Demuth Randomness
• Graph States and the Necessity of Euler Decomposition
• On Stateless Multicounter Machines
• Computability of Continuous Solutions of Higher-Type Equations
• Equivalence Relations on Classes of Computable Structures
• Fractals Generated by Algorithmically Random Brownian Motion
• Computable Exchangeable Sequences Have Computable de Finetti Measures
• Spectra of Algebraic Fields and Subfields
• Definability in the Local Theory of the ?-Enumeration Degrees
• Computability of Analytic Functions with Analytic Machines
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Index Sets and Universal Numberings
• Ordinal Computability
• A Gandy Theorem for Abstract Structures and Applications to First-Order Definability
• Constructing New Aperiodic Self-simulating Tile Sets
• Relationship between Kanamori-McAloon Principle and Paris-Harrington Theorem
• The First Order Theories of the Medvedev and Muchnik Lattices
• Infima of d.r.e. Degrees
• A Divergence Formula for Randomness and Dimension
• On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants
• 0?-Categorical Completely Decomposable Torsion-Free Abelian Groups
• Notes on the Jump of a Structure
• A General Representation Theorem for Probability Functions Satisfying Spectrum Exchangeability
• Stability under Strategy Switching
• Computational Heuristics for Simplifying a Biological Model
• Functions Definable by Arithmetic Circuits
• Survey on Oblivious Routing Strategies
• An Approach to the Engineering of Cellular Models Based on P Systems
• Decidability of Sub-theories of Polynomials over a Finite Field
• Chaitin ? Numbers and Halting Problems
• Bayesian Data Integration and Enrichment Analysis for Predicting Gene Function in Malaria
• Dialectica Interpretation with Fine Computational Control
• Algorithmic Minimal Sufficient Statistic Revisited
• A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets
• On Generating Independent Random Strings.