Quasi-Isometric Reductions Between Infinite Strings Article Swipe

View

Karen Frilya Celine , Ziyuan Gao , Sanjay Jain , Ryan Chun Kit Lou , Frank Stephan , Guohua Wu ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.4230/lipics.mfcs.2024.37

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.

Related Topics

Concepts

Isometric exercise Mathematics Physical therapy Medicine

Metadata

Type: preprint
Language: en
Landing Page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4403617646

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4403617646

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/lipics.mfcs.2024.37

Digital Object Identifier
Title: Quasi-Isometric Reductions Between Infinite Strings

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-01-01

Full publication date if available
Authors: Karen Frilya Celine, Ziyuan Gao, Sanjay Jain, Ryan Chun Kit Lou, Frank Stephan, Guohua Wu

List of authors in order
Landing page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37

Direct OA link when available
Concepts: Isometric exercise, Mathematics, Physical therapy, Medicine

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4403617646
doi	https://doi.org/10.4230/lipics.mfcs.2024.37
ids.doi	https://doi.org/10.4230/lipics.mfcs.2024.37
ids.openalex	https://openalex.org/W4403617646
fwci	0.0
type	preprint
title	Quasi-Isometric Reductions Between Infinite Strings
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11269
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9830999970436096
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Algorithms and Data Compression
topics[1].id	https://openalex.org/T12029
topics[1].field.id	https://openalex.org/fields/13
topics[1].field.display_name	Biochemistry, Genetics and Molecular Biology
topics[1].score	0.9786999821662903
topics[1].domain.id	https://openalex.org/domains/1
topics[1].domain.display_name	Life Sciences
topics[1].subfield.id	https://openalex.org/subfields/1312
topics[1].subfield.display_name	Molecular Biology
topics[1].display_name	DNA and Biological Computing
topics[2].id	https://openalex.org/T11567
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9498000144958496
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	semigroups and automata theory
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C103486182
concepts[0].level	2
concepts[0].score	0.9455928802490234
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1216236
concepts[0].display_name	Isometric exercise
concepts[1].id	https://openalex.org/C33923547
concepts[1].level	0
concepts[1].score	0.4768696427345276
concepts[1].wikidata	https://www.wikidata.org/wiki/Q395
concepts[1].display_name	Mathematics
concepts[2].id	https://openalex.org/C1862650
concepts[2].level	1
concepts[2].score	0.09941539168357849
concepts[2].wikidata	https://www.wikidata.org/wiki/Q186005
concepts[2].display_name	Physical therapy
concepts[3].id	https://openalex.org/C71924100
concepts[3].level	0
concepts[3].score	0.08401858806610107
concepts[3].wikidata	https://www.wikidata.org/wiki/Q11190
concepts[3].display_name	Medicine
keywords[0].id	https://openalex.org/keywords/isometric-exercise
keywords[0].score	0.9455928802490234
keywords[0].display_name	Isometric exercise
keywords[1].id	https://openalex.org/keywords/mathematics
keywords[1].score	0.4768696427345276
keywords[1].display_name	Mathematics
keywords[2].id	https://openalex.org/keywords/physical-therapy
keywords[2].score	0.09941539168357849
keywords[2].display_name	Physical therapy
keywords[3].id	https://openalex.org/keywords/medicine
keywords[3].score	0.08401858806610107
keywords[3].display_name	Medicine
language	en
locations[0].id	pmh:oai:drops-oai.dagstuhl.de:20593
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402524
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
locations[0].source.host_organization	https://openalex.org/I2799853480
locations[0].source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
locations[0].source.host_organization_lineage	https://openalex.org/I2799853480
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	InProceedings
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name
locations[0].landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37
locations[1].id	pmh:oai:arXiv.org:2407.14105
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url	https://arxiv.org/pdf/2407.14105
locations[1].version	submittedVersion
locations[1].raw_type	text
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name
locations[1].landing_page_url	http://arxiv.org/abs/2407.14105
locations[2].id	doi:10.48550/arxiv.2407.14105
locations[2].is_oa	True
locations[2].source.id	https://openalex.org/S4306400194
locations[2].source.issn
locations[2].source.type	repository
locations[2].source.is_oa	True
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	arXiv (Cornell University)
locations[2].source.host_organization	https://openalex.org/I205783295
locations[2].source.host_organization_name	Cornell University
locations[2].source.host_organization_lineage	https://openalex.org/I205783295
locations[2].license
locations[2].pdf_url
locations[2].version
locations[2].raw_type	article
locations[2].license_id
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name
locations[2].landing_page_url	https://doi.org/10.48550/arxiv.2407.14105
locations[3].id	doi:10.4230/lipics.mfcs.2024.37
locations[3].is_oa	True
locations[3].source.id	https://openalex.org/S7407052059
locations[3].source.type	repository
locations[3].source.is_oa	False
locations[3].source.issn_l
locations[3].source.is_core	False
locations[3].source.is_in_doaj	False
locations[3].source.display_name	Dagstuhl Research Online Publication Server
locations[3].source.host_organization
locations[3].source.host_organization_name
locations[3].license	cc-by
locations[3].pdf_url
locations[3].version
locations[3].raw_type
locations[3].license_id	https://openalex.org/licenses/cc-by
locations[3].is_accepted	False
locations[3].is_published
locations[3].raw_source_name
locations[3].landing_page_url	https://doi.org/10.4230/lipics.mfcs.2024.37
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5009030201
authorships[0].author.orcid	https://orcid.org/0000-0002-7078-5582
authorships[0].author.display_name	Karen Frilya Celine
authorships[0].author_position	first
authorships[0].raw_author_name	Celine, Karen Frilya
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5091758218
authorships[1].author.orcid	https://orcid.org/0000-0002-4184-1418
authorships[1].author.display_name	Ziyuan Gao
authorships[1].author_position	middle
authorships[1].raw_author_name	Gao, Ziyuan
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5101627589
authorships[2].author.orcid	https://orcid.org/0000-0001-6798-8330
authorships[2].author.display_name	Sanjay Jain
authorships[2].author_position	middle
authorships[2].raw_author_name	Jain, Sanjay
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5114352448
authorships[3].author.orcid
authorships[3].author.display_name	Ryan Chun Kit Lou
authorships[3].author_position	middle
authorships[3].raw_author_name	Lou, Ryan
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5085103227
authorships[4].author.orcid	https://orcid.org/0000-0001-9152-1706
authorships[4].author.display_name	Frank Stephan
authorships[4].author_position	middle
authorships[4].raw_author_name	Stephan, Frank
authorships[4].is_corresponding	False
authorships[5].author.id	https://openalex.org/A5030897972
authorships[5].author.orcid	https://orcid.org/0000-0003-1552-9620
authorships[5].author.display_name	Guohua Wu
authorships[5].author_position	last
authorships[5].raw_author_name	Wu, Guohua
authorships[5].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-10-22T00:00:00
display_name	Quasi-Isometric Reductions Between Infinite Strings
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11269
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9830999970436096
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Algorithms and Data Compression
related_works	https://openalex.org/W4391375266, https://openalex.org/W2340005245, https://openalex.org/W1547508840, https://openalex.org/W2052773812, https://openalex.org/W2428872210, https://openalex.org/W2181360123, https://openalex.org/W3029411384, https://openalex.org/W2136279810, https://openalex.org/W2264056257, https://openalex.org/W3179139799
cited_by_count	0
locations_count	4
best_oa_location.id	pmh:oai:drops-oai.dagstuhl.de:20593
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402524
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
best_oa_location.source.host_organization	https://openalex.org/I2799853480
best_oa_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
best_oa_location.source.host_organization_lineage	https://openalex.org/I2799853480
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	InProceedings
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37
primary_location.id	pmh:oai:drops-oai.dagstuhl.de:20593
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402524
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
primary_location.source.host_organization	https://openalex.org/I2799853480
primary_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
primary_location.source.host_organization_lineage	https://openalex.org/I2799853480
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	InProceedings
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name
primary_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.37
publication_date	2024-01-01
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	12
abstract_inverted_index.We	20
abstract_inverted_index.an	74
abstract_inverted_index.be	69
abstract_inverted_index.by	15, 78
abstract_inverted_index.is	45, 59
abstract_inverted_index.of	6, 9, 24, 39, 48
abstract_inverted_index.on	35
abstract_inverted_index.to	63
abstract_inverted_index.α	53, 58
abstract_inverted_index.β	55
abstract_inverted_index.The	42
abstract_inverted_index.and	17, 31, 54, 80
abstract_inverted_index.but	65
abstract_inverted_index.the	3, 36, 46, 66
abstract_inverted_index.two	49
abstract_inverted_index.β,	64
abstract_inverted_index.This	0, 72
abstract_inverted_index.made	70
abstract_inverted_index.main	43
abstract_inverted_index.open	75
abstract_inverted_index.such	40, 56
abstract_inverted_index.that	57
abstract_inverted_index.paper	1
abstract_inverted_index.posed	77
abstract_inverted_index.prove	32
abstract_inverted_index.cannot	68
abstract_inverted_index.result	44
abstract_inverted_index.(2017).	19
abstract_inverted_index.answers	73
abstract_inverted_index.aspects	5
abstract_inverted_index.between	27
abstract_inverted_index.classes	38
abstract_inverted_index.notions	23
abstract_inverted_index.problem	76
abstract_inverted_index.results	34
abstract_inverted_index.several	22
abstract_inverted_index.strings	30, 52
abstract_inverted_index.studies	2
abstract_inverted_index.subject	13
abstract_inverted_index.various	33
abstract_inverted_index.Takisaka	18
abstract_inverted_index.infinite	10, 29, 50
abstract_inverted_index.strictly	60
abstract_inverted_index.strings,	11
abstract_inverted_index.Takisaka.	81
abstract_inverted_index.initiated	14
abstract_inverted_index.recursive	28, 51
abstract_inverted_index.reducible	62
abstract_inverted_index.reduction	67
abstract_inverted_index.geometries	8
abstract_inverted_index.recursive.	71
abstract_inverted_index.reductions	26
abstract_inverted_index.Khoussainov	16, 79
abstract_inverted_index.equivalence	37
abstract_inverted_index.investigate	21
abstract_inverted_index.large-scale	7
abstract_inverted_index.reductions.	41
abstract_inverted_index.construction	47
abstract_inverted_index.quasi-isometric	25
abstract_inverted_index.quasi-isometrically	61
abstract_inverted_index.recursion-theoretic	4
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	6
citation_normalized_percentile.value	0.20005901
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False