DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.37

Quasi-Isometric Reductions Between Infinite Strings

Authors: Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Lou, Frank Stephan, and Guohua Wu

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

This paper studies the recursion-theoretic aspects of large-scale geometries of infinite strings, a subject initiated by Khoussainov and Takisaka (2017). We investigate several notions of quasi-isometric reductions between recursive infinite strings and prove various results on the equivalence classes of such reductions. The main result is the construction of two infinite recursive strings α and β such that α is strictly quasi-isometrically reducible to β, but the reduction cannot be made recursive. This answers an open problem posed by Khoussainov and Takisaka.

Cite as

Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Lou, Frank Stephan, and Guohua Wu. Quasi-Isometric Reductions Between Infinite Strings. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{celine_et_al:LIPIcs.MFCS.2024.37,
  author =	{Celine, Karen Frilya and Gao, Ziyuan and Jain, Sanjay and Lou, Ryan and Stephan, Frank and Wu, Guohua},
  title =	{{Quasi-Isometric Reductions Between Infinite Strings}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37},
  URN =		{urn:nbn:de:0030-drops-205931},
  doi =		{10.4230/LIPIcs.MFCS.2024.37},
  annote =	{Keywords: Quasi-isometry, recursion theory, infinite strings}
}

Search Results

Documents authored by Lou, Ryan

Quasi-Isometric Reductions Between Infinite Strings

Abstract

Cite as

Thanks for your feedback!

Could not send message