
Computing with Foresight and Industry
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
This book constitutes the refereed proceedings of the 15th Conference on Computability in Europe, CiE 2019, held in Durham, UK, in July 2019.
The 20 revised full papers presented were carefully reviewed and selected from 35 submissions. In addition, this volume includes 7 invited papers. The conference CiE 2018 had the following six special sessions: computational neuroscience, history and philosophy of computing, lowness notions in computability, probabilistic programming and higher-order computation, smoothed and probabilistic analysis of algorithms, and transnite computations.
More details
Other editions
Additional editions

Content
- Intro
- Preface
- Computability in Europe 2019: Computing with Foresight and Industry Durham, UK, July 15-19, 2019
- Organization
- Contents
- Recent Advances in the Computation of the Homology of Semialgebraic Sets
- 1 Semialgebraic Sets
- 2 Some Computational Problems
- 3 Algorithms and Complexity
- 3.1 Symbolic Algorithms
- 3.2 Numerical Algorithms
- 3.3 Probabilistic Analyses
- 4 Computing the Homology of Semialgebraic Sets
- 4.1 Ill-Posedness and Condition
- 4.2 Main Result
- 4.3 Final Remarks
- References
- Surreal Blum-Shub-Smale Machines
- 1 Introduction
- 2 Surreal Numbers
- 3 Generalising Infinite Time BSSMs
- 4 Surreal Blum-Shub-Smale Machines
- 5 Computational Power of Surreal Blum-Shub-Smale Machines
- References
- Non-Recursive Trade-Offs Are ``Almost Everywhere''
- 1 Introduction
- 2 Preliminaries
- 3 Non-recursive Trade-Offs
- 4 Levels of Non-Recursive Trade-Offs
- 4.1 Bounds for Non-Recursive Trade-Offs
- 4.2 Deriving Non-recursive Trade-Offs from Closure Properties
- 5 Conclusions
- References
- Probabilistic Analysis of Facility Location on Random Shortest Path Metrics
- 1 Introduction
- 1.1 Related Work
- 1.2 Our Results
- 2 Notation and Model
- 3 A Simple Heuristic and Some of Its Properties
- 4 Technical Observations
- 5 Bounds for the Optimal Solution
- 6 Main Results
- 7 Concluding Remarks
- References
- Uniform Relativization
- 1 Introduction
- 1.1 Relativization
- 1.2 Algorithmic Randomness
- 2 Preliminaries
- 2.1 Reduction
- 2.2 Randomness Notions
- 2.3 Computable Analysis
- 3 Uniform Relativization
- 3.1 Uniform Relativization of c.e. Sets
- 3.2 Uniform Relativization of c.e Open Sets
- 3.3 Uniform Relativization of Schnorr Randomness
- 3.4 Other Characterizations
- 3.5 Related Work
- 4 Uniform Lowness
- 4.1 Characterization of Triviality via Lowness
- 4.2 Other Characterizations
- 4.3 Related Work
- References
- Correctness, Explanation and Intention
- 1 Physical Correctness
- 2 Mathematical Correctness
- 3 Explanation and Correctness
- 4 Intention and Correctness
- 5 Physical Computation and Physical Correctness
- References
- Higher Type Recursion for Transfinite Machine Theory
- 1 Introduction
- 2 Inductive Operators
- 3 Higher Type Recursion
- 4 Conclusions
- References
- Effective Embeddings for Pairs of Structures
- 1 Introduction
- 2 Preliminaries
- 3 The tc-degree of { , }
- 4 The Top Pair
- 5 An Infinite Chain of Pairs
- 6 Future Work
- References
- Bounded Reducibility for Computable Numberings
- 1 Introduction
- 2 Preliminaries and General Facts
- 3 Lattices
- 4 Cardinalities of Rogers Semilattices
- 4.1 Finite Families
- 4.2 Infinite Families
- 5 Further Discussion
- References
- Complexity of Conjunctive Regular Path Query Homomorphisms
- 1 Introduction
- 2 Preliminaries
- 3 Lower Bounds
- 4 An EXPTIME Algorithm for RGPHOM
- 5 RGPs Over a Unary Alphabet: The {a,a+} Case
- 5.1 Undirected {a,a+}-RGPs
- 5.2 Directed Path {a}-RGPs
- 5.3 Directed Path {a,a+}-RGPs
- 6 Conclusion
- References
- Towards Uniform Online Spherical Tessellations
- 1 Introduction
- 2 Notation
- 2.1 Spherical Trigonometry
- 2.2 Online Point Placing on the Unit Sphere
- 3 Overview of Online Vertex Insertion Algorithm
- 4 Gap Ratio of Equilateral Spherical Triangles
- 5 Regular Icosahedral Tessellation
- 6 Conclusion
- References
- Complexity of Maximum Fixed Point Problem in Boolean Networks
- 1 Introduction
- 2 Definitions and Notations
- 3 k-Maximum Fixed Point Problem for k = 1
- 4 k-Maximum Fixed Point Problem for k 2
- 5 Maximum Fixed Point Problem
- 6 Conclusion
- References
- A Note on the Ordinal Analysis of RCA0 + WO()
- 1 Introduction
- 2 Ordinal Analysis of I1 + TI(, 1)
- 2.1 Embedding T in an Infinitary System
- 2.2 Eliminating Cuts with 0-Formulas
- 3 Upper Bounds for the Provable Well-Orderings of T
- 4 11-Conservativity
- References
- Study of Stepwise Simulation Between ASM
- 1 Introduction
- 2 Definitions
- 2.1 Traces in a General Setting of Model of Computation
- 2.2 Definition of ASM
- 2.3 Trace
- 2.4 Self-detection of a Halting ASM
- 3 Analysis
- 4 Conclusion
- References
- Cohesive Powers of Linear Orders
- 1 Introduction and Preliminaries
- 2 Cohesive Powers of Linear Orders
- 3 Non-isomorphic Cohesive Powers of Isomorphic Structures
- 4 Orders of Type with Cohesive Powers Not Isomorphic to N+QZ
- References
- An algorithmic approach to characterizations of admissibles
- 1 Gaps and ranks
- 1.1 The constructible hierarchy
- 1.2 Gaps in the constructible hierarchy
- 1.3 Definability and coding
- 1.4 Clockability
- 2 Sacks' theorem revisited
- 3 Jensen's theorem revisited
- References
- Destroying Bicolored P3s by DeletingFew Edges
- 1 Introduction
- 2 Preliminaries
- 3 Bicolored P3 Deletion is NP-Hard
- 4 Polynomial-Time Solvable Cases
- 5 Parameterized Complexity
- 6 Outlook
- References
- Degree Spectra for Transcendence in Fields
- 1 Introduction
- 2 Curves of Positive Genus
- 3 Background on Algebraic Curves
- 4 Examples of Degree Spectra
- References
- More Intensional Versions of Rice's Theorem
- 1 Introduction
- 2 Preliminaries and Notation
- 3 Rice's Theorem and the Rice Equivalence Relation
- 4 Intensionality I: A Simple Generalisation of Rice's Theorem
- 5 Intensionality II: A General Theorem
- 5.1 Examples
- 6 Future Work
- A Material Omitted from the Main Text
- References
- On Approximate Uncomputability of the Kolmogorov Complexity Function
- 1 Introduction
- 1.1 Related Work
- 1.2 Roadmap
- 2 Preliminaries
- 2.1 Kolmogorov Complexity
- 2.2 Generic and Coarse Computability
- 3 Approximating Kolmogorov Complexity with Constant Accuracy
- 4 Measuring the Exact Accuracy
- 4.1 Approximating Length Conditional Complexity
- 4.2 Approximating Plain Complexity
- 5 Conclusion
- References
- Borel and Baire Sets in Bishop Spaces
- 1 Introduction
- 2 F-Complemented Subsets
- 3 Borel Sets
- 4 Baire Sets
- 5 Uniformly F-Complemented Subsets
- References
- Nets and Reverse Mathematics
- 1 Introduction
- 2 Preliminaries
- 2.1 Reverse Mathematics
- 2.2 Some Axioms of Higher-Order RM
- 3 Main Results
- 3.1 Introducing Nets
- 3.2 The Bolzano-Weierstrass Theorem for Nets
- 3.3 Dini's Theorem for Nets
- 4 Nets and the Gödel Hierarchy
- References
- Kalmár's Argument for the Independence of Computer Science
- 1 Introduction
- 2 Kalmár on the Independence of Computing Science
- 3 A Strong Parallel: Kalmár and Perlis
- References
- The d.r.e wtt-Degrees are Dense
- 1 Preliminary and Requirements
- 2 Satisfying the P-Requirement
- 3 Satisfying One N-Requirement
- 4 Construction
- 5 Verification
- References
- Finite State Machines with Feedback: An Architecture Supporting Minimal Machine Consciousness
- 1 Introduction
- 2 An Automata-Based Model of Cognitive Machines
- 3 Classifying Cognitive Machines
- 4 Machine Qualia
- 5 Justification of the Model
- 6 On the Power of Minimal Machine Consciousness
- 7 Conclusions
- References
- Representations of Natural Numbers and Computability of Various Functions
- 1 Introduction
- 2 Defining the Concept of Representation
- 3 Computability of Successor, Addition, Multiplication and Exponentiation in Representations of Natural Numbers
- 4 Conclusions
- References
- On the Differences and Sums of Strongly Computably Enumerable Real Numbers
- 1 Introduction
- 2 Differences of Strongly C.E. Reals
- 3 Sums of Strongly C.E. Reals
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.