Beyond the Horizon of Computability: 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy, June 29–July 3, 2020, Proceedings

Front Matter ....Pages i-xxxvii
 A Note on Computable Embeddings for Ordinals and Their Reverses  (Nikolay Bazhenov, Stefan Vatev)....Pages 1-13
 Clockability for Ordinal Turing Machines  (Merlin Carl)....Pages 14-25
 Some Notes on Spaces of Ideals and Computable Topology  (Matthew de Brecht)....Pages 26-37
 Parallelizations in Weihrauch Reducibility and Constructive Reverse Mathematics  (Makoto Fujiwara)....Pages 38-49
 Liouville Numbers and the Computational Complexity of Changing Bases  (Sune Kristian Jakobsen, Jakob Grue Simonsen)....Pages 50-62
 On Interpretability Between Some Weak Essentially Undecidable Theories  (Lars Kristiansen, Juvenal Murwanashyaka)....Pages 63-74
 On the Complexity of Conversion Between Classic Real Number Representations  (Lars Kristiansen, Jakob Grue Simonsen)....Pages 75-86
 Deterministic and Nondeterministic Iterated Uniform Finite-State Transducers: Computational and Descriptional Power  (Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano)....Pages 87-99
 Computable Analysis and Classification Problems  (Rodney G. Downey, Alexander G. Melnikov)....Pages 100-111
 Non-coding Enumeration Operators  (Russell Miller)....Pages 112-123
 On the Interplay Between Inductive Inference of Recursive Functions, Complexity Theory and Recursive Numberings  (Thomas Zeugmann)....Pages 124-136
 Prawf: An Interactive Proof System for Program Extraction  (Ulrich Berger, Olga Petrovska, Hideki Tsuiki)....Pages 137-148
 ASNP: A Tame Fragment of Existential Second-Order Logic  (Manuel Bodirsky, Simon Knäuer, Florian Starke)....Pages 149-162
 Ackermannian Goodstein Sequences of Intermediate Growth  (David Fernández-Duque, Andreas Weiermann)....Pages 163-174
 On the Complexity of Validity Degrees in Łukasiewicz Logic  (Zuzana Haniková)....Pages 175-188
 Degrees of Non-computability of Homeomorphism Types of Polish Spaces  (Mathieu Hoyrup, Takayuki Kihara, Victor Selivanov)....Pages 189-192
 Time-Aware Uniformization of Winning Strategies  (Stéphane Le Roux)....Pages 193-204
 Quantitative Coding and Complexity Theory of Compact Metric Spaces  (Donghyun Lim, Martin Ziegler)....Pages 205-214
 Functions of Baire Class One over a Bishop Topology  (Iosif Petrakis)....Pages 215-227
 Combinatorial Properties of Degree Sequences of 3-Uniform Hypergraphs Arising from Saind Arrays  (A. Frosini, G. Palma, S. Rinaldi)....Pages 228-238
 The Computational Significance of Hausdorff’s Maximal Chain Principle  (Peter Schuster, Daniel Wessel)....Pages 239-250
 Number of Prefixes in Trace Monoids: Clique Polynomials and Dependency Graphs  (Cyril Banderier, Massimiliano Goldwurm)....Pages 251-263
 Repetitions in Toeplitz Words and the Thue Threshold  (Antonio Boccuto, Arturo Carpi)....Pages 264-276
 On Simulation in Automata Networks  (Florian Bridoux, Maximilien Gadouleau, Guillaume Theyssier)....Pages 277-288
 Theoretical and Implementational Aspects of the Formal Language Server (LaSer)  (Stavros Konstantinidis)....Pages 289-295
 Balancing Straight-Line Programs for Strings and Trees  (Markus Lohrey)....Pages 296-300
 Two-Dimensional Codes  (Maria Madonia)....Pages 301-305
 Formal Languages in Information Extraction and Graph Databases  (Wim Martens)....Pages 306-309
 On the Perceptron’s Compression  (Shay Moran, Ido Nachum, Itai Panasoff, Amir Yehudayoff)....Pages 310-325
 #P-completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method  (Camille Noûs, Kévin Perrot, Sylvain Sené, Lucas Venturini)....Pages 326-338
 Faster Online Computation of the Succinct Longest Previous Factor Array  (Nicola Prezza, Giovanna Rosone)....Pages 339-352
 Recent Advances in Text-to-Pattern Distance Algorithms  (Przemysław Uznański)....Pages 353-365
 Insertion-Deletion Systems with Substitutions I  (Martin Vu, Henning Fernau)....Pages 366-378
Back Matter ....Pages 379-379