Volume
OASIcs, Volume 11
6th International Conference on Computability and Complexity in Analysis (CCA'09)
- Part of: Series: Open Access Series in Informatics (OASIcs)
Event
CCA 2009, August 18-22, 2009, Ljubljana, SloveniaEditors
Publication Details
- published at: 2009-11-25
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-939897-12-5
- DBLP: db/conf/cca/cca2009
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 11, CCA'09, Complete Volume
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
CCA 2009 Front Matter - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis
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
CCA 2009 Preface - Proceedings of the Sixth International Conference on Computability and Complexity in Analysis
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
Computability and Complexity of Julia Sets (Invited Talk)
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
From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs under Interval and p-Box Uncertainty (Invited Talk)
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
Semilattices, Domains, and Computability (Invited Talk)
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
Computable Analysis of Differential Equations (Invited Talk)
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
Theory and Practice of Higher-type Computation (Tutorial)
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
Computer Verified Exact Analysis (Tutorial)
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
Computing Conformal Maps onto Canonical Slit Domains
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
Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions
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
Realisability and Adequacy for (Co)induction
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}
}
Document
A Constructive Study of Landau's Summability Theorem
Abstract
A summability theorem of Landau, which classically is a simple consequence of the uniform boundedness theorem, is examined constructively.
Cite as
Josef Berger and Douglas Bridges. A Constructive Study of Landau's Summability Theorem. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 61-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{berger_et_al:OASIcs.CCA.2009.2259,
author = {Berger, Josef and Bridges, Douglas},
title = {{A Constructive Study of Landau's Summability Theorem}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {61--70},
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.2259},
URN = {urn:nbn:de:0030-drops-22595},
doi = {10.4230/OASIcs.CCA.2009.2259},
annote = {Keywords: Constructive analysis, Landau's theorem, uniform boundedness theorem Constructive analysis, Landau's theorem, uniform boundedness theorem}
}
Document
Separations of Non-monotonic Randomness Notions
Abstract
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"of randomness
and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-L\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural.
Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question.
In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from Martin-L\"of randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.
Cite as
Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260,
author = {Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang},
title = {{Separations of Non-monotonic Randomness Notions}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {71--82},
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.2260},
URN = {urn:nbn:de:0030-drops-22601},
doi = {10.4230/OASIcs.CCA.2009.2260},
annote = {Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies}
}
Document
Weihrauch Degrees, Omniscience Principles and Weak Computability
Abstract
In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension of this reducibility for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice with the disjoint union of multi-valued functions as greatest lower bound operation. We show that parallelization is a closure operator for this semi-lattice and the parallelized Weihrauch degrees even form a lattice with the product of multi-valued functions as greatest lower bound operation. We show that the Medvedev lattice and hence the Turing upper semi-lattice can both be embedded into the parallelized Weihrauch lattice in a natural way. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. This allows a new purely topological or computational approach to metamathematics that sheds new light on the nature of theorems. As crucial corner points of this classification scheme we study the limited principle of omniscience $\LPO$, the lesser limited principle of omniscience $\LLPO$ and their parallelizations. We show that parallelized $\LLPO$ is equivalent to Weak König's Lemma and hence to the Hahn-Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized $\LLPO$ and we present a new proof that the class of weakly computable operations is closed under composition. This proof is based on a computational version of Kleene's ternary logic. Moreover, we characterize weakly computable operations on computable metric spaces as operations that admit upper semi-computable compact-valued selectors and we show that any single-valued weakly computable operation is already computable in the ordinary sense.
Cite as
Vasco Brattka and Guido Gherardi. Weihrauch Degrees, Omniscience Principles and Weak Computability. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 83-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{brattka_et_al:OASIcs.CCA.2009.2261,
author = {Brattka, Vasco and Gherardi, Guido},
title = {{Weihrauch Degrees, Omniscience Principles and Weak Computability}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {83--94},
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.2261},
URN = {urn:nbn:de:0030-drops-22617},
doi = {10.4230/OASIcs.CCA.2009.2261},
annote = {Keywords: Computable analysis, constructive analysis, reverse mathematics, effective descriptive set theory}
}
Document
Effective Choice and Boundedness Principles in Computable Analysis
Abstract
In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice principles on closed sets which are cornerstones among Weihrauch degrees and it turns out that certain core theorems in analysis can be classified naturally in this structure. In particular, we study theorems such as the Intermediate Value Theorem, the Baire Category Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the Uniform Boundedness Theorem. Well-known omniscience principles from constructive mathematics such as $\LPO$ and $\LLPO$ can naturally be considered as Weihrauch degrees and they play an important role in our classification. Our classification scheme does not require any particular logical framework or axiomatic setting, but it can be carried out in the framework of classical mathematics using tools of topology, computability theory and computable analysis. Finally, we present a number of metatheorems that allow to derive upper bounds for the classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed Point Theorem as an example.
Cite as
Vasco Brattka and Guido Gherardi. Effective Choice and Boundedness Principles in Computable Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 95-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{brattka_et_al:OASIcs.CCA.2009.2262,
author = {Brattka, Vasco and Gherardi, Guido},
title = {{Effective Choice and Boundedness Principles in Computable Analysis}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {95--106},
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.2262},
URN = {urn:nbn:de:0030-drops-22629},
doi = {10.4230/OASIcs.CCA.2009.2262},
annote = {Keywords: Computable analysis, constructive analysis, reverse mathematics, effective descriptive set theory}
}
Document
Computability of Homology for Compact Absolute Neighbourhood Retracts
Abstract
In this note we discuss the information needed to compute the homology groups of a topological space. We argue that the natural class of spaces to consider are the compact absolute neighbourhood retracts, since for these spaces the homology groups are finite. We show that we need to specify both a function which defines a retraction from a neighbourhood of the space in the Hilbert cube to the space itself, and a sufficiently fine over-approximation of the set. However, neither the retraction itself, nor a description of an approximation of the set in the Hausdorff metric, is sufficient to compute the homology groups. We express the conditions in the language of computable analysis, which is a powerful framework for studying computability in topology and geometry, and use cubical homology to perform the computations.
Cite as
Pieter Collins. Computability of Homology for Compact Absolute Neighbourhood Retracts. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 107-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{collins:OASIcs.CCA.2009.2263,
author = {Collins, Pieter},
title = {{Computability of Homology for Compact Absolute Neighbourhood Retracts}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {107--118},
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.2263},
URN = {urn:nbn:de:0030-drops-22635},
doi = {10.4230/OASIcs.CCA.2009.2263},
annote = {Keywords: Computability, homology, compact absolute neighbourhood retract}
}
Document
Extended Abstract
Sigma^0_alpha - Admissible Representations (Extended Abstract)
Abstract
We investigate a hierarchy of representations of topological spaces by measurable functions that extends the traditional notion of admissible representations common to computable analysis. Specific instances of these representations already occur in the literature (for example, the naive Cauchy representation of the reals and the ``jump'' of a representation), and have been used in investigating the computational properties of discontinuous functions. Our main contribution is the integration of a recently developing descriptive set theory for non-metrizable spaces that allows many previous results to generalize to arbitrary countably based $T_0$ topological spaces. In addition, for a class of topological spaces that include the reals (with the Euclidean topology) and the power set of $\omega$ (with the Scott-topology), we give a complete characterization of the functions that are (topologically) realizable with respect to the level of the representations of the domain and codomain spaces.
Cite as
Matthew de Brecht and Akihiro Yamamoto. Sigma^0_alpha - Admissible Representations (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 119-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{debrecht_et_al:OASIcs.CCA.2009.2264,
author = {de Brecht, Matthew and Yamamoto, Akihiro},
title = {{Sigma^0\underlinealpha - Admissible Representations}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {119--130},
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.2264},
URN = {urn:nbn:de:0030-drops-22649},
doi = {10.4230/OASIcs.CCA.2009.2264},
annote = {Keywords: Admissible representations, Borel measurable functions, computable analysis, descriptive set theory}
}
Document
Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis
Abstract
We extract a quantitative variant of uniqueness from the usual hypotheses of the implicit functions theorem. This leads not only to an a priori proof of continuity, but also to an alternative, fully constructive existence proof.
Cite as
Hannes Diener and Peter Schuster. Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 131-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{diener_et_al:OASIcs.CCA.2009.2265,
author = {Diener, Hannes and Schuster, Peter},
title = {{Uniqueness, Continuity, and Existence of Implicit Functions in Constructive Analysis}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {131--140},
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.2265},
URN = {urn:nbn:de:0030-drops-22651},
doi = {10.4230/OASIcs.CCA.2009.2265},
annote = {Keywords: Implicit function, uniqueness, continuity, constructive analysis, countable choice}
}
Document
Relativizations of the P =? DNP Question for the BSS Model
Abstract
We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form $x\geq 0$. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set ${\cal O}$ or not. We construct oracles such that the classes P and DNP relative to these oracles are equal or not equal.
Cite as
Christine Gaßner. Relativizations of the P =? DNP Question for the BSS Model. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 141-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{ganer:OASIcs.CCA.2009.2266,
author = {Ga{\ss}ner, Christine},
title = {{Relativizations of the P =? DNP Question for the BSS Model}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {141--148},
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.2266},
URN = {urn:nbn:de:0030-drops-22667},
doi = {10.4230/OASIcs.CCA.2009.2266},
annote = {Keywords: BSS machines, oracle machines, relativizations, P-DNP problem, real knapsack problem}
}
Document
Curves That Must Be Retraced
Abstract
We exhibit a polynomial time computable plane curve ${\bf \Gamma}$ that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization $f$ of ${\bf\Gamma}$ and every positive integer $m$, there is some positive-length subcurve of ${\bf\Gamma}$ that $f$ retraces at least $m$ times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.
Cite as
Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Curves That Must Be Retraced. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 149-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{gu_et_al:OASIcs.CCA.2009.2267,
author = {Gu, Xiaoyang and Lutz, Jack H. and Mayordomo, Elvira},
title = {{Curves That Must Be Retraced}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {149--160},
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.2267},
URN = {urn:nbn:de:0030-drops-22674},
doi = {10.4230/OASIcs.CCA.2009.2267},
annote = {Keywords: Computable analysis, computable curve, computational complexity, Hausdorff measure, rectifiable curve}
}
Document
Effective Dispersion in Computable Metric Spaces
Abstract
We investigate the relationship between computable metric spaces $(X,d,\alpha )$ and $(X,d,\beta ),$ where $(X,d)$ is a given metric space. In the case of Euclidean space, $\alpha $ and $\beta $ are equivalent up to isometry, which does not hold in general. We introduce the notion of effectively dispersed metric space. This notion is essential in the proof of the main result of this paper: $(X,d,\alpha )$ is effectively totally bounded if and only if $(X,d,\beta )$ is effectively totally bounded, i.e. the property that a computable metric space is effectively totally bounded (and in particular effectively compact) depends only on the underlying metric space.
Cite as
Zvonko Iljazovic. Effective Dispersion in Computable Metric Spaces. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 161-172, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{iljazovic:OASIcs.CCA.2009.2268,
author = {Iljazovic, Zvonko},
title = {{Effective Dispersion in Computable Metric Spaces}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {161--172},
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.2268},
URN = {urn:nbn:de:0030-drops-22685},
doi = {10.4230/OASIcs.CCA.2009.2268},
annote = {Keywords: Computable metric space, effective separating sequence, computability structure, effectively totally bounded computable metric space, effectively disp}
}
Document
On Oscillation-free epsilon-random Sequences II
Abstract
It has been shown (see (Staiger, 2008)), that there are strongly \textsc{Martin-L\"of}-$\varepsilon$-random $\omega$-words that behave in terms of complexity like random $\omega$-words. That is, in particular, the \emph{a priori} complexity of these $\varepsilon$-random $\omega$-words is bounded from below and above by linear functions with the same slope $\varepsilon$. In this paper we will study the set of these $\omega$-words in terms of \textsc{Hausdorff} measure and dimension.
Additionally we find upper bounds on \emph{a priori} complexity, monotone and simple complexity for a certain class of $\omega$-power languages.
Cite as
Jöran Mielke and Ludwig Staiger. On Oscillation-free epsilon-random Sequences II. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 173-184, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{mielke_et_al:OASIcs.CCA.2009.2269,
author = {Mielke, J\"{o}ran and Staiger, Ludwig},
title = {{On Oscillation-free epsilon-random Sequences II}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {173--184},
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.2269},
URN = {urn:nbn:de:0030-drops-22698},
doi = {10.4230/OASIcs.CCA.2009.2269},
annote = {Keywords: Omega-words, partial randomness, a priori complexity, monotone complexity}
}
Document
Computability of Probability Distributions and Distribution Functions
Abstract
We define the computability of probability distributions on the real line as well as that of distribution functions. Mutual relationships between the computability notion of a probability distribution and that of the corresponding distribution function are discussed. It is carried out through attempts to effectivize some classical fundamental theorems concerning probability distributions. We then define the effective convergence of probability distributions as an effectivization of the classical vague convergence. For distribution functions, computability and effective convergence are naturally defined as real functions. A weaker effective convergence is also defined as an effectivization of pointwise convergence.
Cite as
Takakazu Mori, Yoshiki Tsujii, and Mariko Yasugi. Computability of Probability Distributions and Distribution Functions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 185-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{mori_et_al:OASIcs.CCA.2009.2270,
author = {Mori, Takakazu and Tsujii, Yoshiki and Yasugi, Mariko},
title = {{Computability of Probability Distributions and Distribution Functions}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {185--196},
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.2270},
URN = {urn:nbn:de:0030-drops-22704},
doi = {10.4230/OASIcs.CCA.2009.2270},
annote = {Keywords: Computable probability distribution, computable probability distribution function, effective convergence of probability distributions}
}
Document
Extended Abstract
How Discontinuous is Computing Nash Equilibria? (Extended Abstract)
Abstract
We investigate the degree of discontinuity of several solution concepts from non-cooperative game theory. While the consideration of Nash equilibria forms the core of our work, also pure and correlated equilibria are dealt with. Formally, we restrict the treatment to two player games, but results and proofs extend to the $n$-player case. As a side result, the degree of discontinuity of solving systems of linear inequalities is settled.
Cite as
Arno Pauly. How Discontinuous is Computing Nash Equilibria? (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 197-208, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{pauly:OASIcs.CCA.2009.2271,
author = {Pauly, Arno},
title = {{How Discontinuous is Computing Nash Equilibria?}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {197--208},
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.2271},
URN = {urn:nbn:de:0030-drops-22719},
doi = {10.4230/OASIcs.CCA.2009.2271},
annote = {Keywords: Game Theory, computable analysis, Nash equilibrium, discontinuity}
}
Document
Extended Abstract
Towards the Complexity of Riemann Mappings (Extended Abstract)
Abstract
We show that under reasonable assumptions there exist Riemann mappings which are as hard as tally $\sharp$-P even in the non-uniform case. More precisely, we show that under a widely accepted conjecture from numerical mathematics there exist single domains with simple, i.e. polynomial time computable, smooth boundary whose Riemann mapping is polynomial time computable if and only if tally $\sharp$-P equals P. Additionally, we give similar results without any assumptions using tally $UP$ instead of $\sharp$-P and show that Riemann mappings of domains with polynomial time computable analytic boundaries are polynomial time computable.
Cite as
Robert Rettinger. Towards the Complexity of Riemann Mappings (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 209-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{rettinger:OASIcs.CCA.2009.2272,
author = {Rettinger, Robert},
title = {{Towards the Complexity of Riemann Mappings}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {209--220},
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.2272},
URN = {urn:nbn:de:0030-drops-22724},
doi = {10.4230/OASIcs.CCA.2009.2272},
annote = {Keywords: Riemann mapping, complexity, polynomial time}
}
Document
Extended Abstract
On the Computability of Rectifiable Simple Curve (Extended Abstract)
Abstract
In mathematics curves are defined as the images of continuous real functions defined on closed intervals and these continuous functions are called parameterizations of the corresponding curves. If only simple curves of finite lengths are considered, then parameterizations can be restricted to the injective continuous functions or even to the continuous length-normalized parameterizations. In addition, a plane curve can also be considered as a connected one-dimensional compact subset of points. By corresponding effectivizations, we will introduce in this paper four versions of computable curves and show that they are all different. More interestingly, we show also that four classes of computable curves cover even different sets of points.
Cite as
Robert Rettinger and Xizhong Zheng. On the Computability of Rectifiable Simple Curve (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 221-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{rettinger_et_al:OASIcs.CCA.2009.2273,
author = {Rettinger, Robert and Zheng, Xizhong},
title = {{On the Computability of Rectifiable Simple Curve}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {221--232},
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.2273},
URN = {urn:nbn:de:0030-drops-22736},
doi = {10.4230/OASIcs.CCA.2009.2273},
annote = {Keywords: Computable curve, simple curve, rectifiable curve, point separability}
}
Document
Extended Abstract
A Note on Closed Subsets in Quasi-zero-dimensional Qcb-spaces (Extended Abstract)
Abstract
We introduce the notion of quasi-zero-dimensionality as a substitute for the notion of zero-dimensionality, motivated by the fact that the latter behaves badly in the realm of qcb-spaces. We prove that the category $\QZ$ of quasi-zero-dimensional qcb$_0$-spaces is cartesian closed. Prominent examples of spaces in $\QZ$ are the spaces in the sequential hierarchy of the Kleene-Kreisel continuous functionals. Moreover, we characterise some types of closed subsets of $\QZ$-spaces in terms of their ability to allow extendability of continuous functions. These results are related to an open problem in Computable Analysis.
Cite as
Matthias Schröder. A Note on Closed Subsets in Quasi-zero-dimensional Qcb-spaces (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 233-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{schroder:OASIcs.CCA.2009.2274,
author = {Schr\"{o}der, Matthias},
title = {{A Note on Closed Subsets in Quasi-zero-dimensional Qcb-spaces}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {233--244},
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.2274},
URN = {urn:nbn:de:0030-drops-22748},
doi = {10.4230/OASIcs.CCA.2009.2274},
annote = {Keywords: Computable analysis, Qcb-spaces, extendability}
}
Document
Random Iteration Algorithm for Graph-Directed Sets
Abstract
A random iteration algorithm for graph-directed sets is defined and discussed. Similarly to the Barnsley-Elton's theorem, it is shown that almost all sequences obtained by this algorithm reflect a probability measure which is invariant with respect to the system of contractions with probabilities.
Cite as
Yoshiki Tsujii, Takakazu Mori, Mariko Yasugi, and Hideki Tsuiki. Random Iteration Algorithm for Graph-Directed Sets. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 245-256, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{tsujii_et_al:OASIcs.CCA.2009.2275,
author = {Tsujii, Yoshiki and Mori, Takakazu and Yasugi, Mariko and Tsuiki, Hideki},
title = {{Random Iteration Algorithm for Graph-Directed Sets}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {245--256},
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.2275},
URN = {urn:nbn:de:0030-drops-22759},
doi = {10.4230/OASIcs.CCA.2009.2275},
annote = {Keywords: Random iteration algorithms, graph-directed sets, displaying fractals, invariant probability measures}
}
Document
Computable Separation in Topology, from T_0 to T_3
Abstract
This article continues the study of computable elementary topology started in (Weihrauch, Grubba 2009). We introduce a number of computable versions of the topological $T_0$ to $T_3$ separation axioms and solve their logical relation completely. In particular, it turns out that computable $T_1$ is equivalent to computable $T_2$. The strongest axiom $SCT_3$ is used in (Grubba, Schroeder, Weihrauch 2007) to construct a computable metric.
Cite as
Klaus Weihrauch. Computable Separation in Topology, from T_0 to T_3. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 257-268, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{weihrauch:OASIcs.CCA.2009.2276,
author = {Weihrauch, Klaus},
title = {{Computable Separation in Topology, from T\underline0 to T\underline3}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {257--268},
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.2276},
URN = {urn:nbn:de:0030-drops-22764},
doi = {10.4230/OASIcs.CCA.2009.2276},
annote = {Keywords: Computable topology, computable separation}
}
Document
Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability
Abstract
It is folklore particularly in numerical and computer sciences that, instead of solving some general problem $f:A\to B$, additional structural information about the input $x\in A$ (that is any kind of promise that $x$ belongs to a certain subset $A'\subseteq A$) should be taken advantage of. Some examples from real number computation show that such discrete advice can even make the difference between computability and uncomputability. We turn this into a both topological and combinatorial complexity theory of information, investigating for several practical problem show much advice is necessary and sufficient to render them computable.
Specifically, finding a nontrivial solution to a homogeneous linear equation $A\cdot\vec x=0$ for a given singular real $n\times n$-matrix $A$ is possible when knowing $\rank(A)\in\{0,1,\ldots,n-1\}$; and we show this to be best possible. Similarly, diagonalizing (i.e. finding a basis of eigenvectors of) a given real symmetric $n\times n$-matrix $A$ is possible when knowing the number of distinct eigenvalues: an integer between $1$ and $n$ (the latter corresponding to the nondegenerate case). And again we show that $n$--fold (i.e. roughly $\log n$ bits of) additional information is indeed necessary in order to render this problem (continuous and) computable; whereas finding \emph{some single} eigenvector of $A$ requires and suffices with $\Theta(\log n)$--fold advice.
Cite as
Martin Ziegler. Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Copy BibTex To Clipboard
@InProceedings{ziegler:OASIcs.CCA.2009.2277,
author = {Ziegler, Martin},
title = {{Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability}},
booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)},
pages = {269--280},
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.2277},
URN = {urn:nbn:de:0030-drops-22770},
doi = {10.4230/OASIcs.CCA.2009.2277},
annote = {Keywords: Nonuniform computability, recursive analysis, topological complexity, linear algebra}
}