15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15-19, 2019 : proceedings /
First Statement of Responsibility
Florin Manea, Barnaby Martin, Daniel Paulusma, Giuseppe Primiero, (eds.).
.PUBLICATION, DISTRIBUTION, ETC
Place of Publication, Distribution, etc.
Cham, Switzerland :
Name of Publisher, Distributor, etc.
Springer,
Date of Publication, Distribution, etc.
[2019]
PHYSICAL DESCRIPTION
Specific Material Designation and Extent of Item
1 online resource
SERIES
Series Title
Lecture notes in computer science,
Series Title
LNCS Sublibrary: SL1 - Theoretical computer science and general issues
Volume Designation
11558
ISSN of Series
0302-9743 ;
INTERNAL BIBLIOGRAPHIES/INDEXES NOTE
Text of Note
Includes bibliographical references and author index.
CONTENTS NOTE
Text of Note
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
Text of Note
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
Text of Note
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
Text of Note
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
Text of Note
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
0
8
8
8
8
SUMMARY OR ABSTRACT
Text of Note
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.
ACQUISITION INFORMATION NOTE
Source for Acquisition/Subscription Address
Springer Nature
Stock Number
com.springer.onix.9783030229962
OTHER EDITION IN ANOTHER MEDIUM
Title
Computing with foresight and industry.
International Standard Book Number
9783030229955
PARALLEL TITLE PROPER
Parallel Title
CiE 2019
TOPICAL NAME USED AS SUBJECT
Computable functions, Congresses.
Computer science-- Mathematics, Congresses.
Computable functions.
Computer science-- Mathematics.
(SUBJECT CATEGORY (Provisional
COM051300
UMB
UMB
DEWEY DECIMAL CLASSIFICATION
Number
511
.
3/52
Edition
23
LIBRARY OF CONGRESS CLASSIFICATION
Class number
QA9
.
59
Book number
.
C67
2019
PERSONAL NAME - ALTERNATIVE RESPONSIBILITY
Manea, Florin
Martin, Barnaby
Paulusma, Daniël
Primiero, Giuseppe
CORPORATE BODY NAME - PRIMARY RESPONSIBILITY
Conference on Computability in Europe(15th :2019 :, Durham, England)