New Computational Paradigms First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings / [electronic resource] :
edited by S. Barry Cooper, Benedikt Löwe, Leen Torenvliet.
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2005.
- XVIII, 578 p. online resource.
- Lecture Notes in Computer Science, 3526 0302-9743 ; .
- Lecture Notes in Computer Science, 3526 .
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 the Korteweg-de Vries Equation -- Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism.
9783540322665
10.1007/b136981 doi
Computer science.
Information theory.
Computer software.
Electronic data processing.
Bioinformatics.
Algorithms.
Computer Science.
Theory of Computation.
Algorithm Analysis and Problem Complexity.
Mathematics of Computing.
Computing Methodologies.
Bioinformatics.
Algorithms.
QA75.5-76.95
004.0151
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 the Korteweg-de Vries Equation -- Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism.
9783540322665
10.1007/b136981 doi
Computer science.
Information theory.
Computer software.
Electronic data processing.
Bioinformatics.
Algorithms.
Computer Science.
Theory of Computation.
Algorithm Analysis and Problem Complexity.
Mathematics of Computing.
Computing Methodologies.
Bioinformatics.
Algorithms.
QA75.5-76.95
004.0151