The Nature of Computation. Logic, Algorithms, Applications: 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Proceedings

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 -