Sailing routes in the world of computation : 14th conference on computability in Europe, CiE 2018, Kiel, Germany, July 30 - August 3, 2018 : proceedings

This book constitutes the refereed proceedings of the 14th Conference on Computability in Europe, CiE 2018, held in Kiel, Germany, in July/ August 2017. The 26 revised full papers were carefully reviewed and selected from 55 submissions. In addition, this volume includes 15 invited papers. The conference CiE 2018 has six special sessions, namely: Approximation and optimization, Bioinformatics and bio-inspired computing, computing with imperfect information, continuous computation, history and philosophy of computing (celebrating the 80 th birthday of Martin Davis), and SAT-solving. Front Matter ....Pages I-XV A Journey to Computably Enumerable Structures (Tutorial Lectures) (Bakh Khoussainov)....Pages 1-19 Polynomial-Time Presentations of Algebraic Number Fields (Pavel Alaev, Victor Selivanov)....Pages 20-29 Multiple Permitting and Array Noncomputability (Klaus Ambos-Spies)....Pages 30-39 Degrees of Categoricity for Prime and Homogeneous Models (Nikolay Bazhenov, Margarita Marchuk)....Pages 40-49 Universality in Freezing Cellular Automata (Florent Becker, Diego Maldonado, Nicolas Ollinger, Guillaume Theyssier)....Pages 50-59 A Deontic Logic Reasoning Infrastructure (Christoph Benzmüller, Xavier Parent, Leendert van der Torre)....Pages 60-69 Optimized Program Extraction for Induction and Coinduction (Ulrich Berger, Olga Petrovska)....Pages 70-80 Computing Tree Width: From Theory to Practice and Back (Sebastian Berndt)....Pages 81-88 Using Structural Properties for Integer Programs (Sebastian Berndt, Kim-Manuel Klein)....Pages 89-96 From Eventually Different Functions to Pandemic Numberings (Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen, André Nies)....Pages 97-106 Divide and Conquer Computation of the Multi-string BWT and LCP Array (Paola Bonizzoni, Gianluca Della Vedova, Serena Nicosia, Yuri Pirola, Marco Previtali, Raffaella Rizzi)....Pages 107-117 Some Observations on Infinitary Complexity (Merlin Carl)....Pages 118-125 Taming Koepke’s Zoo (Merlin Carl, Sabrina Ouazzani, Philip Welch)....Pages 126-135 Online Computability and Differentiation in the Cantor Space (Douglas Cenzer, Diego A. Rojas)....Pages 136-145 Turing’s Vision and Deep Learning (Martin Davis)....Pages 146-155 Computing and Scheduling with Explorable Uncertainty (Thomas Erlebach)....Pages 156-160 Diminishable Parameterized Problems and Strict Polynomial Kernelization (Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier)....Pages 161-171 New Nonterminal Complexity Results for Semi-conditional Grammars (Henning Fernau, Lakshmanan Kuppusamy, Rufus O. Oladele)....Pages 172-182 Kernelization Lower Bounds for Finding Constant-Size Subgraphs (Till Fluschnik, George B. Mertzios, André Nichterlein)....Pages 183-193 On General Sum Approximations of Irrational Numbers (Ivan Georgiev, Lars Kristiansen, Frank Stephan)....Pages 194-203 Computability of Ordinary Differential Equations (Daniel S. Graça, Ning Zhong)....Pages 204-213 Topological Analysis of Representations (Mathieu Hoyrup)....Pages 214-223 A Unified Framework for Designing EPTAS’s for Load Balancing on Parallel Machines (Ishai Kones, Asaf Levin)....Pages 224-233 Weak Reduction Principle and Computable Metric Spaces (Margarita Korovina, Oleg Kudinov)....Pages 234-243 Decidable and Undecidable Fragments of First-Order Concatenation Theory (Lars Kristiansen, Juvenal Murwanashyaka)....Pages 244-253 Algorithm Analysis Through Proof Complexity (Massimo Lauria)....Pages 254-263 Computing with SAT Oracles: Past, Present and Future (Joao Marques-Silva)....Pages 264-276 The Isometry Degree of a Computable Copy of \(\ell ^p\) (Timothy H. McNicholl, Don Stull)....Pages 277-286 Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms (Alexey Milovanov)....Pages 287-296 A C.E. Weak Truth Table Degree Which Is Array Noncomputable and R-maximal (Martin Monath)....Pages 297-306 The Complexity of Tukey Types and Cofinal Types (Marie Nicholson)....Pages 307-317 Functionals of Type 3 as Realisers of Classical Theorems in Analysis (Dag Normann)....Pages 318-327 Enumeration Degrees and Topology (Arno Pauly)....Pages 328-337 A Taxonomy of Deviant Encodings (Paula Quinon)....Pages 338-348 Elementary Bi-embeddability Spectra of Structures (Dino Rossegger)....Pages 349-358 A Generic m-Reducibility (Alexander Rybalov)....Pages 359-364 Some Nonstandard Equivalences in Reverse Mathematics (Sam Sanders)....Pages 365-375 Bit Complexity of Computing Solutions for Symmetric Hyperbolic Systems of PDEs (Extended Abstract) (Svetlana V. Selivanova, Victor L. Selivanov)....Pages 376-385 What Is the Concept of Computation? (Wilfried Sieg)....Pages 386-396 Witness Hiding Without Extractors or Simulators (André Souto, Luís Antunes, Paulo Mateus, Andreia Teixeira)....Pages 397-409 Algorithms and Geometric Constructions (Vladimir Uspenskiy, Alexander Shen)....Pages 410-420 Computing with Multisets: A Survey on Reaction Automata Theory (Takashi Yokomori, Fumiya Okubo)....Pages 421-431 Back Matter ....Pages 433-434 A Journey To Computably Enumerable Structures (Tutorial Lectures) -- Polynomial-time Presentations of Algebraic Number Fields (Extended abstract) -- Multiple Permitting and Array Noncomputability -- Degrees of Categoricity for Prime and Homogeneous Models -- Universality in Freezing Cellular Automata -- A Deontic Logic Reasoning Infrastructure -- Optimised Program Extraction for Induction and Coinduction -- Computing Tree Width: From Theory to Practice and Back -- Using Structural Properties for Integer Programs -- From Eventually Different Functions to Pandemic Numberings -- Divide and Conquer Computation of the Multi-String BWT and LCP Array -- Some Observations on Infinitary Complexity -- Taming Koepke's Zoo -- Online Computability and Differentiation in the Cantor Space -- Turing's Vision and Deep Learning -- Computing and Scheduling with Explorable Uncertainty -- Diminishable Parameterized Problems and Strict Polynomial Kernelization -- New Nonterminal Complexity Results for Semi-Conditional Grammars -- Kernelization Lower Bounds for Finding Constant-Size Subgraphs -- On General Sum Approximations of Irrational Numbers -- Computability of Ordinary Differential Equations -- Topological Analysis of Representations -- A Unified Framework for Designing EPTAS's for Load Balancing on Parallel Machines -- Weak Reduction Principle and Computable Metric Spaces -- Decidable and Undecidable Fragments of First-Order Concatenation Theory -- Algorithm Analysis through Proof Complexity -- Computing with SAT Oracles: Past, Present & Future -- The Isometry Degree of a Computable Copy of lp -- Algorithmic Statistics and Prediction for Polynomial Time-Bounded Algorithms -- A c.e. Weak Truth Table Degree which is Array Noncomputable and r-maximal -- The Complexity of Tukey Types and Cofinal Types -- Functionals of Type 3 as Realisers of Classical Theorems in Analysis -- Enumeration Degrees and Topology -- A Taxonomy of Deviant Encodings -- Elementary Bi-embeddability Spectra of Structures -- A Generic m-reducibility -- Some Nonstandard Equivalences in Reverse Mathematics -- Bit Complexity of Computing Solutions for Symmetric Hyperbolic Systems of PDEs (Extended abstract) -- What is the Concept of Computation? -- Witness Hiding without Extractors or Simulators -- Algorithms and Geometric Constructions -- Computing with Multisets : A Survey on Reaction Automata Theory "This book constitutes the refereed proceedings of the 14th Conference on Computability in Europe, CiE 2018, held in Kiel, Germany, in July/ August 2017. The 26 revised full papers were carefully reviewed and selected from 55 submissions. In addition, this volume includes 15 invited papers. The conference CiE 2018 has six special sessions, namely: Approximation and optimization, Bioinformatics and bio-inspired computing, computing with imperfect information, continuous computation, history and philosophy of computing (celebrating the 80th birthday of Martin Davis), and SAT-solving." -- Publisher's website