DROPS

Document

Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131)

Authors: Vasco Brattka, Alberto Marcone, Arno Pauly, Linda Westrick, and Kenneth Gill

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 25131 "Weihrauch Complexity: Structuring the Realm of Non-Computability". It includes an abstract of every talk given during the seminar, as well as summaries of all presentations from the sessions on open problems and new research directions. At the end is the latest version of a bibliography on Weihrauch complexity which was originally started a decade ago at the first Dagstuhl Seminar on the topic (https://doi.org/10.4230/DagRep.5.9.77).

Cite as

Vasco Brattka, Alberto Marcone, Arno Pauly, Linda Westrick, and Kenneth Gill. Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131). In Dagstuhl Reports, Volume 15, Issue 3, pp. 125-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{brattka_et_al:DagRep.15.3.125,
  author =	{Brattka, Vasco and Marcone, Alberto and Pauly, Arno and Westrick, Linda and Gill, Kenneth},
  title =	{{Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131)}},
  pages =	{125--158},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Brattka, Vasco and Marcone, Alberto and Pauly, Arno and Westrick, Linda and Gill, Kenneth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.125},
  URN =		{urn:nbn:de:0030-drops-248965},
  doi =		{10.4230/DagRep.15.3.125},
  annote =	{Keywords: combinatorial problems, computability and complexity, computable analysis, reverse and constructive mathematics, Weihrauch reducibility and related reducibilities}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.CSL.2021.4

Borel Sets in Reverse Mathematics (Invited Talk)

Authors: Linda Westrick

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

Abstract

We present what is known about the reverse mathematical strength of weak theorems involving Borel sets.

Cite as

Linda Westrick. Borel Sets in Reverse Mathematics (Invited Talk). In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{westrick:LIPIcs.CSL.2021.4,
  author =	{Westrick, Linda},
  title =	{{Borel Sets in Reverse Mathematics}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{4:1--4:2},
  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.4},
  URN =		{urn:nbn:de:0030-drops-134387},
  doi =		{10.4230/LIPIcs.CSL.2021.4},
  annote =	{Keywords: Borel sets, reverse mathematics, measure, category}
}

Search Results

Documents authored by Westrick, Linda

Weihrauch Complexity: Structuring the Realm of Non-Computability (Dagstuhl Seminar 25131)

Abstract

Cite as

Borel Sets in Reverse Mathematics (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message