53 Search Results for "Hertling, Peter"

Volume

OASIcs, Volume 11

6th International Conference on Computability and Complexity in Analysis (CCA'09)

CCA 2009, August 18-22, 2009, Ljubljana, Slovenia

Editors: Andrej Bauer, Peter Hertling, and Ker-I Ko

Document
DOI: 10.4230/LIPIcs.MFCS.2024.62
Randomness Versus Superspeedability

Authors: Rupert Hölzl, Philip Janicki, Wolfgang Merkle, and Frank Stephan

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Speedable numbers are real numbers which are algorithmically approximable from below and whose approximations can be accelerated nonuniformly. We begin this article by answering a question of Barmpalias by separating a strict subclass that we will refer to as superspeedable from the speedable numbers; for elements of this subclass, acceleration is possible uniformly and to an even higher degree. This new type of benign left-approximation of numbers then integrates itself into a hierarchy of other such notions studied in a growing body of recent work. We add a new perspective to this study by juxtaposing this hierachy with the well-studied hierachy of algorithmic randomness notions.
Cite as

Rupert Hölzl, Philip Janicki, Wolfgang Merkle, and Frank Stephan. Randomness Versus Superspeedability. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{holzl_et_al:LIPIcs.MFCS.2024.62,
  author =	{H\"{o}lzl, Rupert and Janicki, Philip and Merkle, Wolfgang and Stephan, Frank},
  title =	{{Randomness Versus Superspeedability}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.62},
  URN =		{urn:nbn:de:0030-drops-206187},
  doi =		{10.4230/LIPIcs.MFCS.2024.62},
  annote =	{Keywords: superspeedable numbers, speedable numbers, regainingly approximable numbers, regular numbers, left-computable numbers}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.129
The Complexity of Computing in Continuous Time: Space Complexity Is Precision

Authors: Manon Blanc and Olivier Bournez

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Models of computations over the integers are equivalent from a computability and complexity theory point of view by the (effective) Church-Turing thesis. It is not possible to unify discrete-time models over the reals. The situation is unclear but simpler for continuous-time models, as there is a unifying mathematical model, provided by ordinary differential equations (ODEs). Each model corresponds to a particular class of ODEs. For example, the General Purpose Analog Computer model of Claude Shannon, introduced as a mathematical model of analogue machines (Differential Analyzers), is known to correspond to polynomial ODEs. However, the question of a robust complexity theory for such models and its relations to classical (discrete) computation theory is an old problem. There was some recent significant progress: it has been proved that (classical) time complexity corresponds to the length of the involved curves, i.e. to the length of the solutions of the corresponding polynomial ODEs. The question of whether there is a simple and robust way to measure space complexity remains. We argue that space complexity corresponds to precision and conversely. Concretely, we propose and prove an algebraic characterisation of FPSPACE, using continuous ODEs. Recent papers proposed algebraic characterisations of polynomial-time and polynomial-space complexity classes over the reals, but with a discrete-time: those algebras rely on discrete ODE schemes. Here, we use classical (continuous) ODEs, with the classic definition of derivation and hence with the more natural context of continuous-time associated with ODEs. We characterise both the case of polynomial space functions over the integers and the reals. This is done by proving two inclusions. The first is obtained using some original polynomial space method for solving ODEs. For the other, we prove that Turing machines, with a proper representation of real numbers, can be simulated by continuous ODEs and not just discrete ODEs. A major consequence is that the associated space complexity is provably related to the numerical stability of involved schemas and the associated required precision. We obtain that a problem can be solved in polynomial space if and only if it can be simulated by some numerically stable ODE, using a polynomial precision.
Cite as

Manon Blanc and Olivier Bournez. The Complexity of Computing in Continuous Time: Space Complexity Is Precision. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 129:1-129:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.ICALP.2024.129,
  author =	{Blanc, Manon and Bournez, Olivier},
  title =	{{The Complexity of Computing in Continuous Time: Space Complexity Is Precision}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{129:1--129:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.129},
  URN =		{urn:nbn:de:0030-drops-202722},
  doi =		{10.4230/LIPIcs.ICALP.2024.129},
  annote =	{Keywords: Models of computation, Ordinary differential equations, Real computations, Analog computations, Complexity theory, Implicit complexity, Recursion scheme}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.CCA.2009
OASIcs, Volume 11, CCA'09, Complete Volume

Authors: Andrej Bauer, Peter Hertling, and Ker-I Ko

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
OASIcs, Volume 11, CCA'09, Complete Volume
Cite as

6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{bauer_et_al:OASIcs.CCA.2009,
  title =	{{OASIcs, Volume 11, CCA'09, Complete Volume}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009},
  URN =		{urn:nbn:de:0030-drops-35738},
  doi =		{10.4230/OASIcs.CCA.2009},
  annote =	{Keywords: Mathematics of Computing, Analysis of Algorithms and Problem Complexity}
}
Document
Front Matter
DOI: 10.4230/OASIcs.CCA.2009.2248
CCA 2009 Front Matter - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis

Authors: Andrej Bauer, Peter Hertling, and Ker-I Ko

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
The Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, took place on August 18 to 22, 2009, in Ljubljana, Slovenia. The conference is concerned with Computable Analysis, the theory of computability and complexity over real-valued data. The conference program consisted of 4 invited talks, 2 tutorials of three talks each, and 24 contributed talks. These proceedings contain the abstracts or extended abstracts of the invited talks, tutorials, and a selection of 22 contributed articles.
Cite as

6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. i-ii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.CCA.2009.2248,
  author =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  title =	{{CCA 2009 Front Matter - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{i--ii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2248},
  URN =		{urn:nbn:de:0030-drops-22486},
  doi =		{10.4230/OASIcs.CCA.2009.2248},
  annote =	{Keywords: Computable analysis, computability, complexity, Turing machine, constructive mathematics, real number computation, computer arithmetic, exact real ari}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2249
CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis

Authors: Andrej Bauer, Peter Hertling, and Ker-I Ko

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
The Sixth International Conference on Computability and Complexity in Analysis, CCA 2009, took place on August 18 to 22, 2009, in Ljubljana, Slovenia. The conference is concerned with Computable Analysis, the theory of computability and complexity over real-valued data. The conference program consisted of 4 invited talks, 2 tutorials of three talks each, and 24 contributed talks. These proceedings contain the abstracts or extended abstracts of the invited talks, tutorials, and a selection of 22 contributed articles.
Cite as

Andrej Bauer, Peter Hertling, and Ker-I Ko. CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.CCA.2009.2249,
  author =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  title =	{{CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{1--1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2249},
  URN =		{urn:nbn:de:0030-drops-22492},
  doi =		{10.4230/OASIcs.CCA.2009.2249},
  annote =	{Keywords: Computable analysis, computability, complexity, Turing machine, constructive mathematics, real number computation, computer arithmetic, exact real ari}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.CCA.2009.2250
Computability and Complexity of Julia Sets (Invited Talk)

Authors: Mark Braverman

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
Studying dynamical systems is key to understanding a wide range of phenomena ranging from planetary movement to climate patterns to market dynamics. Various numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. In fact, little is known about computability of even the most natural problems arising from dynamical systems. In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal. I will present both positive and negative results on the computability and complexity of Julia sets. In conclusion of the talk I will discuss possible future directions and challenges in the study of the computability and complexity of dynamical systems.
Cite as

Mark Braverman. Computability and Complexity of Julia Sets (Invited Talk). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{braverman:OASIcs.CCA.2009.2250,
  author =	{Braverman, Mark},
  title =	{{Computability and Complexity of Julia Sets}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{3--3},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2250},
  URN =		{urn:nbn:de:0030-drops-22508},
  doi =		{10.4230/OASIcs.CCA.2009.2250},
  annote =	{Keywords: Computability, computable analysis, dynamical systems, complex dynamics, Julia sets Computability, computable analysis, dynamical systems, complex dynamics, Julia sets}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.CCA.2009.2251
From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval and p-Box Uncertainty (Invited Talk)

Authors: Vladik Kreinovich

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
Interval computations estimate the uncertainty of the result of data processing in situations in which we only know the upper bounds $\Delta$ on the measurement errors. In this case, based on the measurement result $\widetilde x$, we can only conclude that the actual (unknown) value $x$ of the desired quantity is in the interval $[\widetilde x-\Delta,\widetilde x+\Delta]$. In interval computations, at each intermediate stage of the computation, we have intervals of possible values of the corresponding quantities. As a result, we often have bounds with excess width. To remedy this problem, in our previous papers, we proposed an extension of interval technique to {\it set computations}, where on each stage, in addition to intervals of possible values of the quantities, we also keep sets of possible values of pairs (triples, etc.). In this paper, we show that in several practical problems, such as estimating statistics (variance, correlation, etc.) and solutions to ordinary differential equations (ODEs) with given accuracy, this new formalism enables us to find estimates in feasible (polynomial) time.
Cite as

Vladik Kreinovich. From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval and p-Box Uncertainty (Invited Talk). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 5-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kreinovich:OASIcs.CCA.2009.2251,
  author =	{Kreinovich, Vladik},
  title =	{{From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval and p-Box Uncertainty}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{5--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2251},
  URN =		{urn:nbn:de:0030-drops-22516},
  doi =		{10.4230/OASIcs.CCA.2009.2251},
  annote =	{Keywords: Interval computations, set computations, probability boxes, uncertainty, efficient algorithms}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.CCA.2009.2252
Semilattices, Domains, and Computability (Invited Talk)

Authors: Dana Scott

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
As everyone knows, one popular notion of Scott domain is defined as a bounded complete algebraic cpo. These are closely related to algebraic lattices: (i) A Scott domain becomes an algebraic lattice with the adjunction of an (isolated) top element. (ii) Every non-empty Scott-closed subset of an algebraic lattice is a Scott domain. Moreover, the isolated ($=$ compact) elements of an algebraic lattice form a semilattice (under join). This semilattice has a zero element, and, provided the top element is isolated, it also has a unit element. The algebraic lattice itself may be regarded as the ideal completion of the semilattice of isolated elements. This is all well known. What is not so clear that is that there is an easy-to-construct domain of countable semilattices giving isomorphic copies of all countably based domains. This approach seems to have advantages over both ``information systems'' or more abstract lattice formulations, and it makes definitions of solutions to domain equations very elementary to justify. The ``domain of domains'' also has an immediate computable structure.
Cite as

Dana Scott. Semilattices, Domains, and Computability (Invited Talk). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{scott:OASIcs.CCA.2009.2252,
  author =	{Scott, Dana},
  title =	{{Semilattices, Domains, and Computability}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{17--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2252},
  URN =		{urn:nbn:de:0030-drops-22525},
  doi =		{10.4230/OASIcs.CCA.2009.2252},
  annote =	{Keywords: Semilattices, domains, computability}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.CCA.2009.2253
Computable Analysis of Differential Equations (Invited Talk)

Authors: Ning Zhong

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
In this talk, we discuss some algorithmic aspects of the local and global existence theory for various ordinary and partial differential equations. We will present a sample of results and give some idea of the motivation and general philosophy underlying these results.
Cite as

Ning Zhong. Computable Analysis of Differential Equations (Invited Talk). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{zhong:OASIcs.CCA.2009.2253,
  author =	{Zhong, Ning},
  title =	{{Computable Analysis of Differential Equations}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{19--19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2253},
  URN =		{urn:nbn:de:0030-drops-22535},
  doi =		{10.4230/OASIcs.CCA.2009.2253},
  annote =	{Keywords: Computable analysis, differential equations}
}
Document
Tutorial
DOI: 10.4230/OASIcs.CCA.2009.2254
Theory and Practice of Higher-type Computation (Tutorial)

Authors: Martin Escardó

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
In higher-type computation, established by Kleene and Kreisel in the late 1950's (independently), one works with the data types obtained from the discrete natural numbers by closing under finite products and function spaces. For the theory of higher-type programming languages, it is natural to work with a corresponding hierarchy, or type structure, of domains, identified by Ershov and Scott in the late 1960's (again independently). The Kleene-Kreisel and Ershov-Scott hierarchies account for total and partial computation respectively. In this tutorial I'll explain the theory and practice of higher-type computation and programming languages, and develop old and new applications. From a theoretical point of view, I'll present Kleene-Kreisel spaces and Ershov-Scott domains, and relate the two. Moreover, I'll discuss common generalizations, chiefly QCB spaces and equilogical spaces, which admit further useful closure properties, and their relationship to TTE (Schroeder, Simpson. Scott, Bauer, Weihrauch and many others). I'll also present a natural higher-type model of computation/programming language, namely PCF (Platek, Scott, Plotkin). From a practical point of view, I'll introduce a fragment of the language Haskell as a faithful implementation of PCF. Moreover, I'll develop and run several examples (and prove theorems about them), pertaining to (i) exhaustive search of infinite sets in finite time in particular Ulrich Berger's algorithm and generalizations), and (ii) computation with real numbers (in particular Alex Simpson's integration algorithm and generalizations).
Cite as

Martin Escardó. Theory and Practice of Higher-type Computation (Tutorial). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{escardo:OASIcs.CCA.2009.2254,
  author =	{Escard\'{o}, Martin},
  title =	{{Theory and Practice of Higher-type Computation}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{21--21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2254},
  URN =		{urn:nbn:de:0030-drops-22540},
  doi =		{10.4230/OASIcs.CCA.2009.2254},
  annote =	{Keywords: Higher-type computation, domain theory, Kleene-Kreisel spaces, Ershov-Scott domains, QCB spaces, equilogical spaces, PCF}
}
Document
Tutorial
DOI: 10.4230/OASIcs.CCA.2009.2255
Computer Verified Exact Analysis (Tutorial)

Authors: Bas Spitters and Russell O'Connor

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
This tutorial will illustrate how to use the Coq proof assistant to implement effective and provably correct computation for analysis. Coq provides a dependently typed functional programming language that allows users to specify both programs and formal proofs. We will introduce dependent type theory and show how it can be used to develop both mathematics and programming. We will show how to use dependent type theory to implement constructive analysis. Specifically we will cover how to implement effective real numbers and effective integration. This work will be done using the Coq proof assistant. The tutorial will cover how to use the Coq proof assistant. Attendees are encouraged to download and install Coq 8.2 from {\tt http://coq.inria.fr/download} and also download and make the full system of C-CoRN from {\tt http://c-corn.cs.ru.nl/download.html} beforehand.
Cite as

Bas Spitters and Russell O'Connor. Computer Verified Exact Analysis (Tutorial). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, p. 23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{spitters_et_al:OASIcs.CCA.2009.2255,
  author =	{Spitters, Bas and O'Connor, Russell},
  title =	{{Computer Verified Exact Analysis}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{23--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2255},
  URN =		{urn:nbn:de:0030-drops-22554},
  doi =		{10.4230/OASIcs.CCA.2009.2255},
  annote =	{Keywords: Proof assistant, dependent type theory, constructive analysis}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2256
Computing Conformal Maps onto Canonical Slit Domains

Authors: Valentin V. Andreev and Timothy H. McNicholl

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We extend the results of (Andreev, Daniel, McNicholl preprint) by computing conformal maps onto the canonical slit domains in (Nehari 1975). Along the way, we demonstrate the computability of solutions to Neuman problems.
Cite as

Valentin V. Andreev and Timothy H. McNicholl. Computing Conformal Maps onto Canonical Slit Domains. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:OASIcs.CCA.2009.2256,
  author =	{Andreev, Valentin V. and McNicholl, Timothy H.},
  title =	{{Computing Conformal Maps onto Canonical Slit Domains}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{25--36},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2256},
  URN =		{urn:nbn:de:0030-drops-22561},
  doi =		{10.4230/OASIcs.CCA.2009.2256},
  annote =	{Keywords: Computable analysis, conformal mapping}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2257
Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions

Authors: Andrej Bauer and Jens Blanck

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We prove general theorems about unique existence of effective subalgebras of classical algebras. The theorems are consequences of standard facts about completions of metric spaces within the framework of constructive mathematics, suitably interpreted in realizability models. We work with general realizability models rather than with a particular model of computation. Consequently, all the results are applicable in various established schools of computability, such as type 1 and type 2 effectivity, domain representations, equilogical spaces, and others.
Cite as

Andrej Bauer and Jens Blanck. Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 37-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.CCA.2009.2257,
  author =	{Bauer, Andrej and Blanck, Jens},
  title =	{{Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{37--48},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2257},
  URN =		{urn:nbn:de:0030-drops-22579},
  doi =		{10.4230/OASIcs.CCA.2009.2257},
  annote =	{Keywords: Effective algebras, realizability, constructive metric spaces}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2258
Realisability and Adequacy for (Co)induction

Authors: Ulrich Berger

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We prove the correctness of a formalised realisability interpretation of extensions of first-order theories by inductive and coinductive definitions in an untyped $\lambda$-calculus with fixed-points. We illustrate the use of this interpretation for program extraction by some simple examples in the area of exact real number computation and hint at further non-trivial applications in computable analysis.
Cite as

Ulrich Berger. Realisability and Adequacy for (Co)induction. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 49-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{berger:OASIcs.CCA.2009.2258,
  author =	{Berger, Ulrich},
  title =	{{Realisability and Adequacy for (Co)induction}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{49--60},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2258},
  URN =		{urn:nbn:de:0030-drops-22581},
  doi =		{10.4230/OASIcs.CCA.2009.2258},
  annote =	{Keywords: Constructive Analysis, realisability, program extraction, semantics}
}
  • Refine by Author
  • 8 Hertling, Peter
  • 4 Bauer, Andrej
  • 3 Brattka, Vasco
  • 3 Ko, Ker-I
  • 3 Wadge, William W.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computability
  • 1 Mathematics of computing → Ordinary differential equations
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 8 Computable analysis
  • 4 constructive analysis
  • 3 complexity
  • 3 computability
  • 3 computable analysis
  • Show More...

  • Refine by Type
  • 52 document
  • 1 volume

  • Refine by Publication Year
  • 31 2009
  • 11 2006
  • 7 2008
  • 2 2024
  • 1 2002
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact