Search Results

Documents authored by de Brecht, Matthew

Document
DOI: 10.4230/LIPIcs.CSL.2022.9
Constructing the Space of Valuations of a Quasi-Polish Space as a Space of Ideals

Authors: Matthew de Brecht

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We construct the space of valuations on a quasi-Polish space in terms of the characterization of quasi-Polish spaces as spaces of ideals of a countable transitive relation. Our construction is closely related to domain theoretical work on the probabilistic powerdomain, and helps illustrate the connections between domain theory and quasi-Polish spaces. Our approach is consistent with previous work on computable measures, and can be formalized within weak formal systems, such as subsystems of second order arithmetic.
Cite as

Matthew de Brecht. Constructing the Space of Valuations of a Quasi-Polish Space as a Space of Ideals. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{debrecht:LIPIcs.CSL.2022.9,
  author =	{de Brecht, Matthew},
  title =	{{Constructing the Space of Valuations of a Quasi-Polish Space as a Space of Ideals}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{9:1--9:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.9},
  URN =		{urn:nbn:de:0030-drops-157293},
  doi =		{10.4230/LIPIcs.CSL.2022.9},
  annote =	{Keywords: Quasi-Polish spaces, space of valuations, domain theory, measure theory}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.16
Noetherian Quasi-Polish spaces

Authors: Matthew de Brecht and Arno Pauly

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
In the presence of suitable power spaces, compactness of X can be characterized as the singleton {X} being open in the space O(X) of open subsets of X. Equivalently, this means that universal quantification over a compact space preserves open predicates. Using the language of represented spaces, one can make sense of notions such as a Sigma^0_2-subset of the space of Sigma^0_2-subsets of a given space. This suggests higher-order analogues to compactness: We can, e.g., investigate the spaces X where {X} is a Delta^0_2-subset of the space of Delta^0_2-subsets of X. Call this notion nabla-compactness. As Delta^0_2 is self-dual, we find that both universal and existential quantifier over nabla-compact spaces preserve Delta^0_2 predicates. Recall that a space is called Noetherian iff every subset is compact. Within the setting of Quasi-Polish spaces, we can fully characterize the nabla-compact spaces: A Quasi-Polish space is Noetherian iff it is nabla-compact. Note that the restriction to Quasi-Polish spaces is sufficiently general to include plenty of examples.
Cite as

Matthew de Brecht and Arno Pauly. Noetherian Quasi-Polish spaces. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{debrecht_et_al:LIPIcs.CSL.2017.16,
  author =	{de Brecht, Matthew and Pauly, Arno},
  title =	{{Noetherian Quasi-Polish spaces}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.16},
  URN =		{urn:nbn:de:0030-drops-76988},
  doi =		{10.4230/LIPIcs.CSL.2017.16},
  annote =	{Keywords: Descriptive set theory, synthetic topology, well-quasi orders, Noetherian spaces, compactness}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.CCA.2009.2264
Sigma^0_alpha - Admissible Representations (Extended Abstract)

Authors: Matthew de Brecht and Akihiro Yamamoto

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

Abstract
We investigate a hierarchy of representations of topological spaces by measurable functions that extends the traditional notion of admissible representations common to computable analysis. Specific instances of these representations already occur in the literature (for example, the naive Cauchy representation of the reals and the ``jump'' of a representation), and have been used in investigating the computational properties of discontinuous functions. Our main contribution is the integration of a recently developing descriptive set theory for non-metrizable spaces that allows many previous results to generalize to arbitrary countably based $T_0$ topological spaces. In addition, for a class of topological spaces that include the reals (with the Euclidean topology) and the power set of $\omega$ (with the Scott-topology), we give a complete characterization of the functions that are (topologically) realizable with respect to the level of the representations of the domain and codomain spaces.
Cite as

Matthew de Brecht and Akihiro Yamamoto. Sigma^0_alpha - Admissible Representations (Extended Abstract). In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 119-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{debrecht_et_al:OASIcs.CCA.2009.2264,
  author =	{de Brecht, Matthew and Yamamoto, Akihiro},
  title =	{{Sigma^0\underlinealpha - Admissible Representations}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{119--130},
  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.2264},
  URN =		{urn:nbn:de:0030-drops-22649},
  doi =		{10.4230/OASIcs.CCA.2009.2264},
  annote =	{Keywords: Admissible representations, Borel measurable functions, computable analysis, descriptive set theory}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact