2 Search Results for "Gaßner, Christine"


Document
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
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}
}
  • Refine by Author
  • 2 Gaßner, Christine
  • 1 Pauly, Arno
  • 1 Steinberg, Florian

  • Refine by Classification
  • 1 Mathematics of computing → Integral calculus
  • 1 Mathematics of computing → Point-set topology
  • 1 Theory of computation → Abstract machines
  • 1 Theory of computation → Turing machines

  • Refine by Keyword
  • 1 BSS machines
  • 1 BSS-machine
  • 1 Lebesgue measure
  • 1 P-DNP problem
  • 1 Weihrauch reducibility
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2009
  • 1 2021

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