Logical Approaches to Computational Barriers : Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings /
edited by Arnold Beckmann, Ulrich Berger, Benedikt Löwe, John V. Tucker.
- xv, 608 páginas Also available online. recurso en línea.
- Lecture Notes in Computer Science, 3988 0302-9743 ; .
Springer eBooks
Heap-Abstraction for an Object-Oriented Calculus with Thread Classes -- From Constructibility and Absoluteness to Computability and Domain Independence -- Datatype-Generic Reasoning -- The Logical Strength of the Uniform Continuity Theorem -- Elementary Algebraic Specifications of the Rational Function Field -- Random Closed Sets -- Deep Inference and Its Normal Form of Derivations -- Logspace Complexity of Functions and Structures -- Prefix-Like Complexities and Computability in the Limit -- Partial Continuous Functions and Admissible Domain Representations -- An Invariant Cost Model for the Lambda Calculus -- On the Complexity of the Sperner Lemma -- The Church-Turing Thesis: Consensus and Opposition -- Gödel and the Origins of Computer Science -- The Role of Algebraic Models and Type-2 Theory of Effectivity in Special Purpose Processor Design -- Turing Universality in Dynamical Systems -- Every Sequence Is Decompressible from a Random One -- Reversible Conservative Rational Abstract Geometrical Computation Is Turing-Universal -- LJQ: A Strongly Focused Calculus for Intuitionistic Logic -- Böhm Trees, Krivine’s Machine and the Taylor Expansion of Lambda-Terms -- What Does the Incompleteness Theorem Add to the Unsolvability of the Halting Problem? -- An Analysis of the Lemmas of Urysohn and Urysohn-Tietze According to Effective Borel Measurability -- Enumeration Reducibility with Polynomial Time Bounds -- Coinductive Proofs for Basic Real Computation -- A Measure of Space for Computing over the Reals -- On Graph Isomorphism for Restricted Graph Classes -- Infinite Time Register Machines -- Upper and Lower Bounds on Sizes of Finite Bisimulations of Pfaffian Hybrid Systems -- Forcing with Random Variables and Proof Complexity -- Complexity-Theoretic Hierarchies -- Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests -- Lower Bounds Using Kolmogorov Complexity -- The Jump Classes of Minimal Covers -- Space Bounds for Infinitary Computation -- From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials -- Towards a Trichotomy for Quantified H-Coloring -- Two Open Problems on Effective Dimension -- Optimization and Approximation Problems Related to Polynomial System Solving -- Uncomputability Below the Real Halting Problem -- Constraints on Hypercomputation -- Martingale Families and Dimension in P -- Can General Relativistic Computers Break the Turing Barrier? -- Degrees of Weakly Computable Reals -- Understanding and Using Spector’s Bar Recursive Interpretation of Classical Analysis -- A Subrecursive Refinement of the Fundamental Theorem of Algebra -- An Introduction to Program and Thread Algebra -- Fast Quantifier Elimination Means P = NP -- Admissible Representations in Computable Analysis -- Do Noetherian Modules Have Noetherian Basis Functions? -- Inverting Monotone Continuous Functions in Constructive Analysis -- Partial Recursive Functions in Martin-Löf Type Theory -- Partially Ordered Connectives and ?1 1 on Finite Models -- Upper and Lower Bounds for the Computational Power of P Systems with Mobile Membranes -- Gödel’s Conflicting Approaches to Effective Calculability -- Co-total Enumeration Degrees -- Relativized Degree Spectra -- Phase Transition Thresholds for Some Natural Subclasses of the Computable Functions -- Non-deterministic Halting Times for Hamkins-Kidder Turing Machines -- Kurt Gödel and Computability Theory -- A Computability Theory of Real Numbers -- Primitive Recursive Selection Functions over Abstract Algebras.
This book constitutes the refereed proceedings of the Second International Conference on Computability in Europe, CiE 2006, held in Swansea, UK, in June/July 2006. The 31 revised full papers presented together with 30 invited papers were carefully reviewed and selected from about 80 submissions. Among them are papers corresponding to 8 plenary talks and papers of 6 special sessions entitled proofs and computation, computable analysis, challenges in complexity, foundations of programming, mathematical models of computers and hypercomputers, and Gödel centenary: Gödel's legacy for computability.