Computing with Foresight and Industry

Name: Computing with Foresight and Industry | 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019, Proceedings

Florin Manea Barnaby Martin Daniël Paulusma Giuseppe Primiero(Herausgeber*in)

Springer (Verlag)

Erschienen am 4. Juli 2019

XII, 323 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-22996-2 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken