| Description |
1 online resource |
| Series |
Lecture notes in computer science, 0302-9743 ; 11558 |
|
LNCS Sublibrary: SL1 - Theoretical computer science and general issues |
|
Lecture notes in computer science ; 11558.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| 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 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 |
|
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 |
|
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 |
| Summary |
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 |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource; title from digital title page (viewed on July 30, 2019) |
| In |
Springer eBooks |
| Subject |
Computable functions -- Congresses
|
|
Computer science -- Mathematics -- Congresses
|
|
Software
|
|
Electronic Data Processing
|
|
software.
|
|
Computable functions
|
|
Computer science -- Mathematics
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Manea, Florin, editor.
|
|
Martin, Barnaby, editor.
|
|
Paulusma, Daniël, editor.
|
|
Primiero, Giuseppe, editor.
|
| ISBN |
9783030229962 |
|
3030229963 |
|
9783030229979 |
|
3030229971 |
|
