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(Editor)

Springer (Publisher)

Published on 4. July 2019

XII, 323 pages

E-Book

PDF with digital watermarking

System requirements

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

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other 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

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Computing with Foresight and Industry

Description

More details

Other editions

Additional editions

Content

System requirements