目录：
Real Benefit of Promises and Advice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Klaus Ambos-Spies, Ulrike Brandt, and Martin Ziegler
Computability and Computational Complexity of the Evolution of
Nonlinear Dynamical Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Olivier Bournez, Daniel S. Gra¸ca, Amaury Pouly, and Ning Zhong
An Overview of Genomic Distances Modeled with Indels . . . . . . . . . . . . . . 22
Mar′ılia D.V. Braga
Noise versus Computational Intractability in Dynamics . . . . . . . . . . . . . . . 32
Mark Braverman
Cluster Editing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Sebastian B¨ocker and Jan Baumbach
Beyond Rogers’ Non-constructively Computable Function . . . . . . . . . . . . . 45
John Case and Michael Ralston
Constructing Continuous Systems from Discrete Cellular Automata . . . . 55
Julien Cervelle
Latency-Bounded Target Set Selection in Social Networks . . . . . . . . . . . . . 65
Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano,
Martin Milaniˇc, and Ugo Vaccaro
Summary Data Structures for Massive Data . . . . . . . . . . . . . . . . . . . . . . . . . 78
Graham Cormode
Determinant versus Permanent: Salvation via Generalization? . . . . . . . . . 87
Nicolas de Rugy-Altherre
Aligning and Labeling Genomes under the Duplication-Loss Model . . . . . 97
Riccardo Dondi and Nadia El-Mabrouk
Irrationality Is Needed to Compute with Signal Machines with Only
Three Speeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
J′erˆome Durand-Lose
Processes Inspired by the Functioning of Living Cells: Natural
Computing Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Andrzej Ehrenfeucht and Grzegorz Rozenberg
XVI Table of Contents
Recent Developments in Collective Decision Making in Combinatorial
Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Ulle Endriss
Software Streams: Big Data Challenges in Dynamic Program
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Irene Finocchi
On λ-Definable Functions on Ordinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Tim Fischbach and Benjamin Seyfferth
A Personal View of the P versus NP Problem. . . . . . . . . . . . . . . . . . . . . . . . 147
Lance Fortnow
An Investigation on Genomic Repeats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Giuditta Franco and Alessio Milanese
Local Computability for Ordinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Johanna N.Y. Franklin, Asher M. Kach, Russell Miller, and
Reed Solomon
A Note on the Sequential Version of Π12
Statements . . . . . . . . . . . . . . . . . . 171
Makoto Fujiwara and Keita Yokoyama
On Conservative Learning of Recursively Enumerable Languages . . . . . . . 181
Ziyuan Gao, Sanjay Jain, and Frank Stephan
Topology of Asymptotic Cones and Non-deterministic Polynomial Time
Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Anthony Gasperin
On Decidable and Computable Models of Theories . . . . . . . . . . . . . . . . . . . 200
Alexander Gavruskin and Bakhadyr Khoussainov
Discovering Hidden Repetitions in Words . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Pawel Gawrychowski, Florin Manea, and Dirk Nowotka
Language Forbidding-Enforcing Systems Defining DNA Codewords . . . . . 220
Daniela Genova
Computing K-Trivial Sets by Incomplete Random Sets . . . . . . . . . . . . . . . 230
Noam Greenberg
Cardinal-Recognizing Infinite Time Turing Machines . . . . . . . . . . . . . . . . . 231
Miha E. Habiˇc
‘Stored Program Concept’ Considered Harmful: History and
Historiography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Thomas Haigh
Table of Contents XVII
The Complexity of Interior Point Methods for Solving Discounted
Turn-Based Stochastic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
Thomas Dueholm Hansen and Rasmus Ibsen-Jensen
The Computation of Nature, Or: Does the Computer Drive Science and
Technology? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Ulf Hashagen
Negative Glues and Non-determinism in Nanocomputations by
Self-assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Lila Kari
Structures without Scattered-Automatic Presentation. . . . . . . . . . . . . . . . . 273
Alexander Kartzow and Philipp Schlicht
Some Classes of Generalised Communicating P Systems and Simple
Kernel P Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Shankara Narayanan Krishna, Marian Gheorghe, and
Ciprian Dragomir
Closed Choice for Finite and for Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . 294
St′ephane Le Roux and Arno Pauly
Realizability Models Separating Various Fan Theorems . . . . . . . . . . . . . . . 306
Robert S. Lubarsky and Michael Rathjen
Towards a Theory of Homomorphic Compression. . . . . . . . . . . . . . . . . . . . . 316
Andrew McGregor
The Classification Problem for Compact Computable Metric Spaces . . . . 320
Alexander G. Melnikov and Andr′e Nies
Exploiting Co-evolution across Protein Families for Predicting Native
Contacts and Protein-Protein Interaction Surfaces. . . . . . . . . . . . . . . . . . . . 329
Andrea Pagnani
A Compositional Semantics of Reaction Systems with Restriction . . . . . . 330
Giovanni Pardini, Roberto Barbuti, Andrea Maggiolo-Schettini,
Paolo Milazzo, and Simone Tini
Using Random Graphs in Population Genomics . . . . . . . . . . . . . . . . . . . . . . 340
Laxmi Parida
The Tarski-Lindenbaum Algebra of the Class of All Strongly
Constructivizable Countable Saturated Models . . . . . . . . . . . . . . . . . . . . . . 342
Mikhail G. Peretyat’kin
The Burrows-Wheeler Transform between Data Compression and
Combinatorics on Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
Giovanna Rosone and Marinella Sciortino
XVIII Table of Contents
A Note on ω-Jump Inversion of Degree Spectra of Structures . . . . . . . . . . 365
Ivan N. Soskov
The Turing Universe in the Context of Enumeration Reducibility . . . . . . 371
Mariya I. Soskova
Computing Game Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Darko Stefanovic and Milan N. Stojanovic
On Processes and Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Alexey Stukachev
Various Regularity Lemmas in Graphs and Hypergraphs . . . . . . . . . . . . . . 403
Endre Szemer′edi
Three Debates about Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
Matti Tedre
Another Jump Inversion Theorem for Structures . . . . . . . . . . . . . . . . . . . . . 414
Stefan Vatev
On Algorithmic Strong Sufficient Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 424
Nikolay Vereshchagin
Analytic Root Clustering: A Complete Algorithm Using Soft
Zero Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
Chee Yap, Michael Sagraloff, and Vikram Sharma
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445