Sailing Routes in the World of Computation: 14th Conference on Computability in Europe, Cie 2018, Kiel, Germany, July 30 - August 3, 2018, Proceedings

ISBN-13: 9783319944173 / Angielski / Miękka / 2018 / 434 str.

Manea, Florin

Opis

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 and 15 invited papers were carefully reviewed and selected from 55 submissions. 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.

Spis treści

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 ℓᵖ.- 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.