|
" Computing with foresight and industry : "
Florin Manea, Barnaby Martin, Daniel Paulusma, Giuseppe Primiero, (eds.).
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
862475
|
| Main Entry
|
:
|
Conference on Computability in Europe(15th :2019 :, Durham, England)
|
| Title & Author
|
:
|
Computing with foresight and industry : : 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019 : proceedings /\ Florin Manea, Barnaby Martin, Daniel Paulusma, Giuseppe Primiero, (eds.).
|
| Publication Statement
|
:
|
Cham, Switzerland :: Springer,, [2019]
|
| Series Statement
|
:
|
Lecture notes in computer science,; 11558
|
|
|
:
|
LNCS Sublibrary: SL1 - Theoretical computer science and general issues
|
| Page. NO
|
:
|
1 online resource
|
| ISBN
|
:
|
3030229963
|
|
|
:
|
: 3030229971
|
|
|
:
|
: 9783030229962
|
|
|
:
|
: 9783030229979
|
|
|
:
|
3030229955
|
|
|
:
|
9783030229955
|
| Bibliographies/Indexes
|
:
|
Includes bibliographical references and author index.
|
| Contents
|
:
|
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 A Simple Heuristic and Some of Its Properties4 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
|
|
|
:
|
3 Generalising Infinite Time BSSMs4 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
|
|
|
:
|
4.1 Characterization of Triviality via Lowness4.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 Pairs6 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
|
| Abstract
|
:
|
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.
|
| Subject
|
:
|
Computable functions, Congresses.
|
| Subject
|
:
|
Computer science-- Mathematics, Congresses.
|
| Subject
|
:
|
Computable functions.
|
| Subject
|
:
|
Computer science-- Mathematics.
|
| Dewey Classification
|
:
|
511.3/52
|
| LC Classification
|
:
|
QA9.59.C67 2019
|
| Added Entry
|
:
|
Manea, Florin
|
|
|
:
|
Martin, Barnaby
|
|
|
:
|
Paulusma, Daniël
|
|
|
:
|
Primiero, Giuseppe
|
| Parallel Title
|
:
|
CiE 2019
|
| |