5 Search Results for "Kihara, Takayuki"

Document
DOI: 10.4230/LIPIcs.STACS.2026.75
Effective Versions of Strong Measure Zero

Authors: Matthew Rayman

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Effective versions of strong measure zero sets are developed for various levels of complexity and computability. It is shown that the sets can be equivalently defined using a generalization of supermartingales called odds supermartingales, success rates on supermartingales, predictors, and coverings. We show Borel’s conjecture that a set has strong measure zero if and only if it is countable holds in the time and space bounded setting. At the level of computability this does not hold. We show the computable level contains sequences at arbitrary levels of the hyperarithmetical hierarchy. This is done by proving a correspondence principle yielding a condition for the sets of computable strong measure zero to agree with the classical sets of strong measure zero. An algorithmic version of strong measure zero using lower semicomputability is defined. We show that this notion is equivalent to the set of NCR reals studied by Reimann and Slaman, thereby giving new characterizations of this set. Effective strong packing dimension zero is investigated by requiring success with respect to the limit inferior instead of the limit superior. It is proven that every sequence in the corresponding algorithmic class is decidable. At the level of computability, the sets coincide with a notion of weak countability that we define.
Cite as

Matthew Rayman. Effective Versions of Strong Measure Zero. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rayman:LIPIcs.STACS.2026.75,
  author =	{Rayman, Matthew},
  title =	{{Effective Versions of Strong Measure Zero}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.75},
  URN =		{urn:nbn:de:0030-drops-255648},
  doi =		{10.4230/LIPIcs.STACS.2026.75},
  annote =	{Keywords: Strong measure zero, NCR, Effective fractal dimensions, Borel’s Conjecture, Hausdorff dimension, Packing dimension}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.139
Minimality and Computability of Languages of G-Shifts

Authors: Djamel Eddine Amir and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.
Cite as

Djamel Eddine Amir and Benjamin Hellouin de Menibus. Minimality and Computability of Languages of G-Shifts. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2025.139,
  author =	{Amir, Djamel Eddine and Hellouin de Menibus, Benjamin},
  title =	{{Minimality and Computability of Languages of G-Shifts}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.139},
  URN =		{urn:nbn:de:0030-drops-235161},
  doi =		{10.4230/LIPIcs.ICALP.2025.139},
  annote =	{Keywords: shifts, subshifts, minimal shifts, computable language, computability, strong computable type, descriptive complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2024.42
Local Operators in Topos Theory and Separation of Semi-Classical Axioms in Intuitionistic Arithmetic

Authors: Satoshi Nakata

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
There has been work on the strength of semi-classical axioms over Heyting arithmetic such as Σ_n-DNE (double negation elimination) and Π_n-LEM (law of excluded middle). Among other things, Akama et al. show that Σ_n-DNE does not imply Π_n-LEM for any n ≥ 1 by using Kleene realizability relativized to Turing degrees. These realizability notions are expressed by subtoposes of the effective topos ℰff and thus by corresponding local operators (a.k.a. Lawvere-Tierney topologies). Our purpose is to provide a topos-theoretic explanation for separation of semi-classical axioms. It consists of determining the least dense local operator of a given axiom φ in a topos ℰ, which completely characterizes the dense subtoposes of ℰ satisfying φ. This idea is motivated by Caramello’s study of intermediate propositional logics and van Oosten’s study of Lifschitz realizability. We first investigate sufficient conditions for an arithmetical formula to have a least dense operator. In particular, we show that each semi-classical axiom has a least dense operator in every elementary topos with natural number object. This is a generalization of van Oosten’s result for Π₁∨Π₁-DNE in ℰff. We next determine least dense operators of semi-classical axioms in ℰff in terms of (generalized) Turing degrees. Not only does it immediately imply some separation results of Akama et al. but also explain that realizability notions they used are optimal in the sense of minimality. We finally point out a negative consequence that Π_n-LEM, Σ_n-LEM and Σ_{n+1}-DNE are never separable by any subtopos of ℰff for any n ≥ 0.
Cite as

Satoshi Nakata. Local Operators in Topos Theory and Separation of Semi-Classical Axioms in Intuitionistic Arithmetic. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nakata:LIPIcs.CSL.2024.42,
  author =	{Nakata, Satoshi},
  title =	{{Local Operators in Topos Theory and Separation of Semi-Classical Axioms in Intuitionistic Arithmetic}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{42:1--42:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.42},
  URN =		{urn:nbn:de:0030-drops-196859},
  doi =		{10.4230/LIPIcs.CSL.2024.42},
  annote =	{Keywords: local operator, elementary topos, effective topos, realizability, intuitionistic arithmetic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.8
Descriptive Complexity on Non-Polish Spaces

Authors: Antonin Callard and Mathieu Hoyrup

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.
Cite as

Antonin Callard and Mathieu Hoyrup. Descriptive Complexity on Non-Polish Spaces. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2020.8,
  author =	{Callard, Antonin and Hoyrup, Mathieu},
  title =	{{Descriptive Complexity on Non-Polish Spaces}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.8},
  URN =		{urn:nbn:de:0030-drops-118694},
  doi =		{10.4230/LIPIcs.STACS.2020.8},
  annote =	{Keywords: Represented space, Computable analysis, Descriptive set theory, CoPolish spaces}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.58
Dividing by Zero - How Bad Is It, Really?

Authors: Takayuki Kihara and Arno Pauly

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way. In this note we investigate the strength of the computational problem Robust division: Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility. As application for Robust division, we show that it suffices to execute Gaussian elimination.
Cite as

Takayuki Kihara and Arno Pauly. Dividing by Zero - How Bad Is It, Really?. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kihara_et_al:LIPIcs.MFCS.2016.58,
  author =	{Kihara, Takayuki and Pauly, Arno},
  title =	{{Dividing by Zero - How Bad Is It, Really?}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.58},
  URN =		{urn:nbn:de:0030-drops-64702},
  doi =		{10.4230/LIPIcs.MFCS.2016.58},
  annote =	{Keywords: computable analysis, Weihrauch reducibility, recursion theory, linear algebra}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2024
  • 1 2020
  • 1 2016

  • Refine by Author
  • 1 Amir, Djamel Eddine
  • 1 Callard, Antonin
  • 1 Hellouin de Menibus, Benjamin
  • 1 Hoyrup, Mathieu
  • 1 Kihara, Takayuki
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Point-set topology
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Constructive mathematics
  • Show More...

  • Refine by Keyword
  • 1 Borel’s Conjecture
  • 1 CoPolish spaces
  • 1 Computable analysis
  • 1 Descriptive set theory
  • 1 Effective fractal dimensions
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact