Search Results

Documents authored by 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.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
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.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.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.dagstuhl.de/entities/document/10.4230/DagSemRep.176},
  URN =		{urn:nbn:de:0030-drops-150630},
  doi =		{10.4230/DagSemRep.176},
}
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