5 Search Results for "Tsuiki, Hideki"


Document
Formalizing Hyperspaces for Extracting Efficient Exact Real Computation

Authors: Michal Konečný, Sewon Park, and Holger Thies

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
We propose a framework for certified computation on hyperspaces by formalizing various higher-order data types and operations in a constructive dependent type theory. Our approach builds on our previous work on axiomatization of exact real computation where we formalize nondeterministic first-order partial computations over real and complex numbers. Based on the axiomatization, we first define open, closed, compact and overt subsets in an abstract topological way that allows short and elegant proofs with computational content coinciding with standard definitions in computable analysis. From these proofs we extract programs for testing inclusion, overlapping of sets, et cetera. To improve extracted programs, our framework specializes the Euclidean space ℝ^m making use of metric properties. To define interesting operations over hyperspaces of Euclidean space, we introduce a nondeterministic version of a continuity principle valid under the standard type-2 realizability interpretation. Instead of choosing one of the usual formulations, we define it in a way similar to an interval extension operator, which often is already available in exact real computation software. We prove that the operations on subsets preserve the encoding, and thereby define a small calculus to built new subsets from given ones, including limits of converging sequences with regards to the Hausdorff metric. From the proofs, we extract programs that generate drawings of subsets of ℝ^m with any given precision efficiently. As an application we provide a function that constructs fractals, such as the Sierpinski triangle, from iterated function systems using the limit operation, resulting in certified programs that errorlessly draw such fractals up to any desired resolution.

Cite as

Michal Konečný, Sewon Park, and Holger Thies. Formalizing Hyperspaces for Extracting Efficient Exact Real Computation. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{konecny_et_al:LIPIcs.MFCS.2023.59,
  author =	{Kone\v{c}n\'{y}, Michal and Park, Sewon and Thies, Holger},
  title =	{{Formalizing Hyperspaces for Extracting Efficient Exact Real Computation}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.59},
  URN =		{urn:nbn:de:0030-drops-185935},
  doi =		{10.4230/LIPIcs.MFCS.2023.59},
  annote =	{Keywords: Computable analysis, type theory, program extraction}
}
Document
On the Complexity of Lattice Puzzles

Authors: Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
In this paper, we investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n x n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. That is, it gives us new insight of these computational complexity classes.

Cite as

Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara. On the Complexity of Lattice Puzzles. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2019.32,
  author =	{Kobayashi, Yasuaki and Suetsugu, Koki and Tsuiki, Hideki and Uehara, Ryuhei},
  title =	{{On the Complexity of Lattice Puzzles}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{32:1--32:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.32},
  URN =		{urn:nbn:de:0030-drops-115287},
  doi =		{10.4230/LIPIcs.ISAAC.2019.32},
  annote =	{Keywords: Lattice puzzle, NP-completeness, GI-completeness, FPT algorithm}
}
Document
Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)

Authors: Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki

Published in: Dagstuhl Reports, Volume 1, Issue 10 (2012)


Abstract
There is a large gap between mathematical structures and the structures computer implementations are based on. To stimulate research to overcome this---especially for infinitary structures---highly non-trivial problem the Dagstuhl Seminar 11411 ``Computing with Infinite Data: Topological and Logical Foundations'' was held. This report collects the ideas that were presented and discussed during the course of the seminar.

Cite as

Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki. Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411). In Dagstuhl Reports, Volume 1, Issue 10, pp. 14-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Article{berger_et_al:DagRep.1.10.14,
  author =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  title =	{{Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)}},
  pages =	{14--36},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{10},
  editor =	{Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.10.14},
  URN =		{urn:nbn:de:0030-drops-33721},
  doi =		{10.4230/DagRep.1.10.14},
  annote =	{Keywords: Exact real number computation, Stream computation, Infinite computations, Computability in analysis, Hierarchies, Reducibility, Topological complexity}
}
Document
Random Iteration Algorithm for Graph-Directed Sets

Authors: Yoshiki Tsujii, Takakazu Mori, Mariko Yasugi, and Hideki Tsuiki

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


Abstract
A random iteration algorithm for graph-directed sets is defined and discussed. Similarly to the Barnsley-Elton's theorem, it is shown that almost all sequences obtained by this algorithm reflect a probability measure which is invariant with respect to the system of contractions with probabilities.

Cite as

Yoshiki Tsujii, Takakazu Mori, Mariko Yasugi, and Hideki Tsuiki. Random Iteration Algorithm for Graph-Directed Sets. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 245-256, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{tsujii_et_al:OASIcs.CCA.2009.2275,
  author =	{Tsujii, Yoshiki and Mori, Takakazu and Yasugi, Mariko and Tsuiki, Hideki},
  title =	{{Random Iteration Algorithm for Graph-Directed Sets}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{245--256},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2275},
  URN =		{urn:nbn:de:0030-drops-22759},
  doi =		{10.4230/OASIcs.CCA.2009.2275},
  annote =	{Keywords: Random iteration algorithms, graph-directed sets, displaying fractals, invariant probability measures}
}
Document
Dyadic Subbases and Representations of Topological Spaces

Authors: Hideki Tsuiki

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)


Abstract
We explain topological properties of the embedding-based approach to computability on topological spaces. With this approach, he considered a special kind of embedding of a topological space into Plotkin's $T^\omega$, which is the set of infinite sequences of $T = \{0,1,\bot \}$. We show that such an embedding can also be characterized by a dyadic subbase, which is a countable subbase $S = (S_0^0, S_0^1, S_1^0, S_1^1, \ldots)$ such that $S_n^j$ $(n = 0,1,2,\ldots; j = 0,1$ are regular open and $S_n^0$ and $S_n^1$ are exteriors of each other. We survey properties of dyadic subbases which are related to efficiency properties of the representation corresponding to the embedding.

Cite as

Hideki Tsuiki. Dyadic Subbases and Representations of Topological Spaces. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{tsuiki:DagSemProc.04351.15,
  author =	{Tsuiki, Hideki},
  title =	{{Dyadic Subbases and Representations of Topological Spaces}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.15},
  URN =		{urn:nbn:de:0030-drops-1376},
  doi =		{10.4230/DagSemProc.04351.15},
  annote =	{Keywords: Dyadic subbase , embedding , computation over topological spaces , Plotkin's \$T^\backslashomega\$}
}
  • Refine by Author
  • 4 Tsuiki, Hideki
  • 1 Berger, Ulrich
  • 1 Brattka, Vasco
  • 1 Kobayashi, Yasuaki
  • 1 Konečný, Michal
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Computability in analysis
  • 1 Computable analysis
  • 1 Dyadic subbase
  • 1 Exact real number computation
  • 1 FPT algorithm
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2005
  • 1 2009
  • 1 2012
  • 1 2019
  • 1 2023

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