The Nature of Computation: Logic, Algorithms, Applications

This book constitutes the refereed proceedings of the 9th Conference on Computability in Europe, CiE 2013, held in Milan, Italy, in July 2013. The 48 revised papers presented together with 1 invited lecture and 2 tutorials were carefully reviewed and selected with an acceptance rate of under 31,7%. Both the conference series and the association promote the development of computability-related science, ranging over mathematics, computer science and applications in various natural and engineering sciences such as physics and biology, and also including the promotion of related non-scientific fields such as philosophy and history of computing.

Inhalt

Real Benefit of Promises and Advice.- Computability and Computational Complexity of the Evolution of Nonlinear Dynamical Systems.- An Overview of Genomic Distances Modeled with Indels.- Noise versus Computational Intractability in Dynamics.- Cluster Editing.- Beyond Rogers' Non-constructively Computable Function.- Constructing Continuous Systems from Discrete Cellular Automata.- Latency-Bounded Target Set Selection in Social Networks.- Summary Data Structures for Massive Data.- Determinant versus Permanent: Salvation via Generalization.- Aligning and Labeling Genomes under the Duplication-Loss Model.- Irrationality Is Needed to Compute with Signal Machines with Only Three Speeds.- Processes Inspired by the Functioning of Living Cells: Natural Computing Approach.- Recent Developments in Collective Decision Making in Combinatorial Domains.- Software Streams: Big Data Challenges in Dynamic Program Analysis.- On -Definable Functions on Ordinals.- A Personal View of the P versus NP Problem.- An Investigation on Genomic Repeats.- Local Computability for Ordinals.- A Note on the Sequential Version of 12 Statements.- On Conservative Learning of Recursively Enumerable Languages.- Topology of Asymptotic Cones and Non-deterministic Polynomial Time Computations.- On Decidable and Computable Models of Theories.- Discovering Hidden Repetitions in Words.- Language Forbidding-Enforcing Systems Defining DNA Codewords.- Computing K-Trivial Sets by Incomplete Random Sets.- Cardinal-Recognizing Infinite Time Turing Machines.- 'Stored Program Concept' Considered Harmful: History and Historiography.- The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games.- The Computation of Nature, Or: Does the Computer Drive Science and Technology.- Negative Glues and Non-determinism in Nanocomputations by Self-assembly.- Structures without Scattered-Automatic Presentation.- Some Classes of Generalised Communicating P Systems and Simple Kernel P Systems.- Closed Choice for Finite and for Convex Sets.- Realizability Models Separating Various Fan Theorems.- Towards a Theory of Homomorphic Compression.- The Classification Problem for Compact Computable Metric Spaces.- Exploiting Co-evolution across Protein Families for Predicting Native Contacts and Protein-Protein Interaction Surfaces.- A Compositional Semantics of Reaction Systems with Restriction.- Using Random Graphs in Population Genomics.- The Tarski-Lindenbaum Algebra of the Class of All Strongly Constructivizable Countable Saturated Models.- The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words.- A Note on -Jump Inversion of Degree Spectra of Structures.- The Turing Universe in the Context of Enumeration Reducibility.- Computing Game Strategies.- On Processes and Structures.- Various Regularity Lemmas in Graphs and Hypergraphs.- Three Debates about Computing.- Another Jump Inversion Theorem for Structures.- On Algorithmic Strong Sufficient Statistics.- Analytic Root Clustering: A Complete Algorithm Using Soft Zero Tests.