Unveiling Dynamics and Complexity

1. Front Matter

   Pages I-XIII

   PDF

2. Invited Papers

   1. Front Matter

      Pages 1-1

      PDF

   2. Character-Based Phylogeny Construction and Its Application to Tumor Evolution

      • Gianluca Della Vedova, Murray Patterson, Raffaella Rizzi, Mauricio Soto

      Pages 3-13

   3. Is there any Real Substance to the Claims for a ‘New Computationalism’?

      • Alberto Hernández-Espinosa, Francisco Hernández-Quiroz, Héctor Zenil

      Pages 14-23

   4. Formalizing a Fragment of Combinatorics on Words

      • Štěpán Holub, Robert Veroff

      Pages 24-31

   5. Turing’s 1949 Paper in Context

      • Cliff B. Jones

      Pages 32-41

   6. Gödel’s Reception of Turing’s Model of Computability: The “Shift of Perception” in 1934

      • Juliette Kennedy

      Pages 42-49

   7. A Guided Tour to Computational Haplotyping

      • Gunnar W. Klau, Tobias Marschall

      Pages 50-63

   8. Outline of Partial Computability in Computable Topology

      • Margarita Korovina, Oleg Kudinov

      Pages 64-76

   9. Eliminating Unbounded Search in Computable Algebra

      • Alexander G. Melnikov

      Pages 77-87

   10. Computable Transformations of Structures

       • Russell Miller

       Pages 88-97

   11. Formulas with Reversal

       • Narad Rampersad

       Pages 98-100

   12. Compressibility and Probabilistic Proofs

       • Alexander Shen

       Pages 101-111

   13. Delayed-Input Cryptographic Protocols

       • Ivan Visconti

       Pages 112-115

3. Contributed Papers

   1. Front Matter

      Pages 117-117

      PDF

   2. A Deterministic Algorithm for Testing the Equivalence of Read-Once Branching Programs with Small Discrepancy

      • Stefan Arnold, Jacobo Torán

      Pages 119-128

   3. Counting Substrate Cycles in Topologically Restricted Metabolic Networks

      • Robert D. Barish, Akira Suyama

      Pages 129-140

   4. Turing Computable Embeddings, Computable Infinitary Equivalence, and Linear Orders

      • Nikolay Bazhenov

      Pages 141-151

   5. Degrees of Categoricity of Rigid Structures

      • Nikolay A. Bazhenov, Mars M. Yamaleev

      Pages 152-161

   6. Flexible Indexing of Repetitive Collections

      • Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, Mathieu Raffinot

      Pages 162-174

This book constitutes the refereed proceedings of the 13th Conference on Computability in Europe, CiE 2017, held in Turku, Finland, in June 2017. The 24 revised full papers and 12 invited papers were carefully reviewed and selected from 69 submissions. The conference CiE 2016 has six special sessions, namly: algorithmics for biology; combinatorics and algorithmics on words; computability in analysis, algebra, and geometry; cryptography and information theory; formal languages and automata theory; and history and philosophy of computing.

• algorithmics
• computability
• formal languages and automata theory
• natural computing
• turing machine model
• automated theorem proving
• cellular automation
• classical computation
• cryptography and information theory
• geometric computation
• history and philosophy of computing
• logic
• mathematics of computing
• models of computation
• regular languages
• reversible computation
• signal machine
• theory of computation
• total turing machines
• uniformization theorem

• University of Turku, Turku, Finland

  Jarkko Kari

• Christian-Albrechts-University of Kiel, Kiel, Germany

  Florin Manea

• Åbo Akademi University, Turku, Finland

  Ion Petre

Policies and ethics