5 Search Results for "Weihrauch, Klaus"


Document
Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)

Authors: Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)


Abstract
Naive computations with real numbers on computers may cause serious errors. In traditional numerical computation these errors are often neglected or, more seriously, not identified. Two approaches attack this problem and investigate its background, Reliable Computing and Computable Analysis. Methods in Reliable Computing are essentially mathematical theorems, the assumptions of which are verified on the computer. This verification is performed using the very efficient floating point arithmetic. If the verification succeeds, the assertions are true and correct error bounds have been computed; if not, a corresponding message is given. Thus the results are always mathematically correct. A specific advantage of Reliable Computing is that imprecise data are accepted; the challenge is to develop mathematical theorems the assumptions of which can be verified effectively in floating-point and to produce narrow bounds for the solution. Computable Analysis extends the traditional theory of computability on countable sets to the real numbers and more general spaces by refining continuity to computability. Numerous even basic and simple problems are not computable since they cannot be solved continuously. In many cases computability can be refined to computational complexity which is the time or space a Turing machine needs to compute a result with given precision. By treating precision as a parameter, this goes far beyond the restrictions of double precision arithmetic used in Reliable computing. For practical purposes, however, the asymptotic results from complexity theory must be refined. Software libraries provide efficient implementations for exact real computations. Both approaches are established theories with numerous important results. However, despite of their obvious close relations these two areas are developing almost independently. For exploring possibilities of closer contact we have invited experts from both areas to this seminar. For improving the mutual understanding some tutorial-like talks have been included in the program. As a result of the seminar it can be stated that interesting joint research is possible.

Cite as

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler. Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481). In Dagstuhl Reports, Volume 7, Issue 11, pp. 142-167, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Article{muller_et_al:DagRep.7.11.142,
  author =	{M\"{u}ller, Norbert T. and Rump, Siegfried M. and Weihrauch, Klaus and Ziegler, Martin},
  title =	{{ Reliable Computation and Complexity on the Reals (Dagstuhl Seminar 17481)}},
  pages =	{142--167},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{M\"{u}ller, Norbert T. and Rump, Siegfried M. and Weihrauch, Klaus and Ziegler, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.11.142},
  URN =		{urn:nbn:de:0030-drops-86826},
  doi =		{10.4230/DagRep.7.11.142},
  annote =	{Keywords: Computable Analysis, Verification Methods, Real Complexity Theory, Reliable Computing}
}
Document
Weihrauch Degrees, Omniscience Principles and Weak Computability

Authors: Vasco Brattka and Guido Gherardi

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


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-dev.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
Computable Separation in Topology, from T_0 to T_3

Authors: Klaus Weihrauch

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


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-dev.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
Computability and Complexity in Analysis (Dagstuhl Seminar 99461)

Authors: Ker-I Ko, Anil Nerode, and Klaus Weihrauch

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Ker-I Ko, Anil Nerode, and Klaus Weihrauch. Computability and Complexity in Analysis (Dagstuhl Seminar 99461). Dagstuhl Seminar Report 259, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)


Copy BibTex To Clipboard

@TechReport{ko_et_al:DagSemRep.259,
  author =	{Ko, Ker-I and Nerode, Anil and Weihrauch, Klaus},
  title =	{{Computability and Complexity in Analysis (Dagstuhl Seminar 99461)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{259},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.259},
  URN =		{urn:nbn:de:0030-drops-151448},
  doi =		{10.4230/DagSemRep.259},
}
Document
Computability and Complexity in Analysis (Dagstuhl Seminar 9717)

Authors: Ker-I Ko, Anil Nerode, and Klaus Weihrauch

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Ker-I Ko, Anil Nerode, and Klaus Weihrauch. Computability and Complexity in Analysis (Dagstuhl Seminar 9717). Dagstuhl Seminar Report 176, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)


Copy BibTex To Clipboard

@TechReport{ko_et_al:DagSemRep.176,
  author =	{Ko, Ker-I and Nerode, Anil and Weihrauch, Klaus},
  title =	{{Computability and Complexity in Analysis (Dagstuhl Seminar 9717)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{176},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.176},
  URN =		{urn:nbn:de:0030-drops-150630},
  doi =		{10.4230/DagSemRep.176},
}
  • Refine by Author
  • 4 Weihrauch, Klaus
  • 2 Ko, Ker-I
  • 2 Nerode, Anil
  • 1 Brattka, Vasco
  • 1 Gherardi, Guido
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Computable Analysis
  • 1 Computable analysis
  • 1 Computable topology
  • 1 Real Complexity Theory
  • 1 Reliable Computing
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2009
  • 1 1997
  • 1 2000
  • 1 2018

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