Quasi-Isometric Reductions Between Infinite Strings
<|reference_start|>Quasi-Isometric Reductions Between Infinite Strings: 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 $\alpha$ and $\beta$ such that $\alpha$ is strictly quasi-isometrically reducible to $\beta$, but the reduction cannot be made recursive. This answers an open problem posed by Khoussainov and Takisaka.<|reference_end|>
@article{celine2024quasi-isometric,
    title={Quasi-Isometric Reductions Between Infinite Strings},
    author={Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Lou, Frank Stephan
  and Guohua Wu},
    journal={arXiv preprint arXiv:2407.14105},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.14105},
    primaryClass={cs.FL cs.LO}
}