Ambos-Spies / Löwe / Merkle Mathematical Theory and Computational Practice

5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009, Proceedings
2009
ISBN: 978-3-642-03073-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 5635, 510 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Ambos-Spies, Klaus

Löwe, Benedikt

Merkle, Wolfgang

Inhaltsverzeichnis

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 forRandomness 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.