The nature of computation : logic, algorithms, applications : 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Proceedings

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. Front Matter....Pages - Real Benefit of Promises and Advice....Pages 1-11 Computability and Computational Complexity of the Evolution of Nonlinear Dynamical Systems....Pages 12-21 An Overview of Genomic Distances Modeled with Indels....Pages 22-31 Noise versus Computational Intractability in Dynamics....Pages 32-32 Cluster Editing....Pages 33-44 Beyond Rogers’ Non-constructively Computable Function....Pages 45-54 Constructing Continuous Systems from Discrete Cellular Automata....Pages 55-64 Latency-Bounded Target Set Selection in Social Networks....Pages 65-77 Summary Data Structures for Massive Data....Pages 78-86 Determinant versus Permanent: Salvation via Generalization?....Pages 87-96 Aligning and Labeling Genomes under the Duplication-Loss Model....Pages 97-107 Irrationality Is Needed to Compute with Signal Machines with Only Three Speeds....Pages 108-119 Processes Inspired by the Functioning of Living Cells: Natural Computing Approach....Pages 120-122 Recent Developments in Collective Decision Making in Combinatorial Domains....Pages 123-123 Software Streams: Big Data Challenges in Dynamic Program Analysis....Pages 124-134 On λ -Definable Functions on Ordinals....Pages 135-146 A Personal View of the P versus NP Problem....Pages 147-148 An Investigation on Genomic Repeats....Pages 149-160 Local Computability for Ordinals....Pages 161-170 A Note on the Sequential Version of ${\rm \Pi^1_2}$ Statements....Pages 171-180 On Conservative Learning of Recursively Enumerable Languages....Pages 181-190 Topology of Asymptotic Cones and Non-deterministic Polynomial Time Computations....Pages 191-199 On Decidable and Computable Models of Theories....Pages 200-209 Discovering Hidden Repetitions in Words....Pages 210-219 Language Forbidding-Enforcing Systems Defining DNA Codewords....Pages 220-229 Computing K -Trivial Sets by Incomplete Random Sets....Pages 230-230 Cardinal-Recognizing Infinite Time Turing Machines....Pages 231-240 ‘Stored Program Concept’ Considered Harmful: History and Historiography....Pages 241-251 The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games....Pages 252-262 The Computation of Nature, Or: Does the Computer Drive Science and Technology?....Pages 263-270 Negative Glues and Non-determinism in Nanocomputations by Self-assembly....Pages 271-272 Structures without Scattered-Automatic Presentation....Pages 273-283 Some Classes of Generalised Communicating P Systems and Simple Kernel P Systems....Pages 284-293 Closed Choice for Finite and for Convex Sets....Pages 294-305 Realizability Models Separating Various Fan Theorems....Pages 306-315 Towards a Theory of Homomorphic Compression....Pages 316-319 The Classification Problem for Compact Computable Metric Spaces....Pages 320-328 Exploiting Co-evolution across Protein Families for Predicting Native Contacts and Protein-Protein Interaction Surfaces....Pages 329-329 A Compositional Semantics of Reaction Systems with Restriction....Pages 330-339 Using Random Graphs in Population Genomics....Pages 340-341 The Tarski-Lindenbaum Algebra of the Class of All Strongly Constructivizable Countable Saturated Models....Pages 342-352 The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words....Pages 353-364 A Note on ω -Jump Inversion of Degree Spectra of Structures....Pages 365-370 The Turing Universe in the Context of Enumeration Reducibility....Pages 371-382 Computing Game Strategies....Pages 383-392 On Processes and Structures....Pages 393-402 Various Regularity Lemmas in Graphs and Hypergraphs....Pages 403-403 Three Debates about Computing....Pages 404-413 Another Jump Inversion Theorem for Structures....Pages 414-423 On Algorithmic Strong Sufficient Statistics....Pages 424-433 Analytic Root Clustering: A Complete Algorithm Using Soft Zero Tests....Pages 434-444 Back Matter....Pages -