DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2021.22

Computing Measure as a Primitive Operation in Real Number Computation

Authors: Christine Gaßner, Arno Pauly, and Florian Steinberg

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Abstract

We study the power of BSS-machines enhanced with abilities such as computing the measure of a BSS-decidable set or computing limits of BSS-computable converging sequences. Our variations coalesce into just two equivalence classes, each of which also can be described as a lower cone in the Weihrauch degrees. We then classify computational tasks such as computing the measure of Δ⁰₂-set of reals, integrating piece-wise continuous functions and recovering a continuous function from an L₁([0, 1])-description. All these share the Weihrauch degree lim.

Cite as

Christine Gaßner, Arno Pauly, and Florian Steinberg. Computing Measure as a Primitive Operation in Real Number Computation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganer_et_al:LIPIcs.CSL.2021.22,
  author =	{Ga{\ss}ner, Christine and Pauly, Arno and Steinberg, Florian},
  title =	{{Computing Measure as a Primitive Operation in Real Number Computation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.22},
  URN =		{urn:nbn:de:0030-drops-134564},
  doi =		{10.4230/LIPIcs.CSL.2021.22},
  annote =	{Keywords: BSS-machine, Weihrauch reducibility, integrable function, Lebesgue measure, computable analysis}
}

Document

DOI: 10.4230/OASIcs.CCA.2009.2266

Relativizations of the P =? DNP Question for the BSS Model

Authors: Christine Gaßner

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

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}
}

Search Results

Documents authored by Gaßner, Christine

Computing Measure as a Primitive Operation in Real Number Computation

Abstract

Cite as

Relativizations of the P =? DNP Question for the BSS Model

Abstract

Cite as

Thanks for your feedback!

Could not send message