Cooper / Löwe New Computational Paradigms

First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005, Proceedings
2005
ISBN: 978-3-540-32266-5
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 3526, 578 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Cooper, Barry S.

Löwe, Benedikt

Inhaltsverzeichnis

Introduction: If CiE Did Not Exist, It Would Be Necessary to Invent It.- Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees.- The Fan Theorem and Uniform Continuity.- Continuous Semantics for Strong Normalization.- A Thread Algebra with Multi-level Strategic Interleaving.- Membrane Computing — Current Results and Future Problems.- How to Compare the Power of Computational Models.- Recombinant DNA ,Gene Splicing as Generative Devices of Formal Languages.- Quantum Computing.- Symbol Grounding in Connectionist and Adaptive Agent Models.- The Complexity of Inductive Definability.- A Logical Approach to Abstract Algebra.- Schnorr Dimension.- Abstract Geometrical Computation: Turing-Computing Ability and Undecidability.- Computability in Computational Geometry.- Shrad: A Language for Sequential Real Number Computation.- Borel Ranks and Wadge Degrees of Context Free ?-Languages.- Fewer Epistemological Challenges for Connectionism.- An Algebraic View on Exact Learning from Queries.- The Church-Turing Thesis: Breaking the Myth.- Robust Simulations of Turing Machines with Analytic Maps and Flows.- Infinitary Computability with Infinite Time Turing Machines.- Combinatorial Models of Gene Assembly.- Symmetric Enumeration Reducibility.- Computability-Theoretic and Proof-Theoretic Aspects of Vaughtian Model Theory.- Finite Trees as Ordinals.- On the Problems of Definability in the Enumeration Degrees.- Computing a Model of Set Theory.- Proof Mining in Functional Analysis.- Towards Computability of Higher Type Continuous Data.- The Power of Mobility: Four Membranes Suffice.- The Small Grzegorczyk Classes and the Typed ?-Calculus.- The Flow of Data and the Complexity of Algorithms.- On a Question of Sacks — A Partial Solution on the Positive Side.-The Low Splitting Theorem in the Difference Hierarchy.- Geometric Software: Robustness Issues and Model of Computation.- The Dimension of a Point: Computability Meets Fractal Geometry.- Accepting Networks of Splicing Processors.- Hilbert’s Tenth Problem and Paradigms of Computation.- On Some Relations Between Approximation Problems and PCPs over the Real Numbers.- Correlation Dimension and the Quality of Forecasts Given by a Neural Network.- The Computational Complexity of One-Dimensional Sandpiles.- Categoricity in Restricted Classes.- Recursion and Complexity.- FM-Representability and Beyond.- Formalising Exact Arithmetic in Type Theory.- Complexity in Predicative Arithmetic.- Domain-Theoretic Formulation of Linear Boundary Value Problems.- Membrane Computing: Power, Efficiency, Applications.- The Analogue of Büchi’s Problem for Polynomials.- On the Turing Degrees of Divergence Bounded Computable Reals.- New Algorithmic Paradigms in Exponential Time Algorithms.- Some Reducibilities on Regular Sets.- Computability and Discrete Dynamical Systems.- Uniform Operators.- Minimal Pairs and Quasi-minimal Degrees for the Joint Spectra of Structures.- Presentations of K-Trivial Reals and Kolmogorov Complexity.- Presentations of Structures in Admissible Sets.- An Environment Aware P-System Model of Quorum Sensing.- Kripke Models, Distributive Lattices, and Medvedev Degrees.- Arthur-Merlin Games and the Problem of Isomorphism Testing.- Beyond the Super-Turing Snare: Analog Computation and Digital Virtuality.- A Network Model of Analogue Computation over Metric Algebras.- Computable Analysis.- The Transfinite Action of 1 Tape Turing Machines.- Complexity of Continuous Space Machine Operations.- Computable Analysis of a Non-homogeneous Boundary-Value Problem for theKorteweg-de Vries Equation.- Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism.