[Formula: see text] Is Decidable in [Formula: see text]

We show that it is decidable whether or not a relation on the reals definable in the structure [Formula: see text] can be defined in the structure [Formula: see text]. This result is achieved by obtaining a topological characterization of [Formula: see text]-definable relations in the family of [For...

Descripción completa

Detalles Bibliográficos
Autores principales: Bès, Alexis, Choffrut, Christian
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206654/
http://dx.doi.org/10.1007/978-3-030-40608-0_8
_version_ 1783530452478328832
author Bès, Alexis
Choffrut, Christian
author_facet Bès, Alexis
Choffrut, Christian
author_sort Bès, Alexis
collection PubMed
description We show that it is decidable whether or not a relation on the reals definable in the structure [Formula: see text] can be defined in the structure [Formula: see text]. This result is achieved by obtaining a topological characterization of [Formula: see text]-definable relations in the family of [Formula: see text]-definable relations and then by following Muchnik’s approach of showing that this characterization can be expressed in the logic of [Formula: see text].
format Online
Article
Text
id pubmed-7206654
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066542020-05-08 [Formula: see text] Is Decidable in [Formula: see text] Bès, Alexis Choffrut, Christian Language and Automata Theory and Applications Article We show that it is decidable whether or not a relation on the reals definable in the structure [Formula: see text] can be defined in the structure [Formula: see text]. This result is achieved by obtaining a topological characterization of [Formula: see text]-definable relations in the family of [Formula: see text]-definable relations and then by following Muchnik’s approach of showing that this characterization can be expressed in the logic of [Formula: see text]. 2020-01-07 /pmc/articles/PMC7206654/ http://dx.doi.org/10.1007/978-3-030-40608-0_8 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Bès, Alexis
Choffrut, Christian
[Formula: see text] Is Decidable in [Formula: see text]
title [Formula: see text] Is Decidable in [Formula: see text]
title_full [Formula: see text] Is Decidable in [Formula: see text]
title_fullStr [Formula: see text] Is Decidable in [Formula: see text]
title_full_unstemmed [Formula: see text] Is Decidable in [Formula: see text]
title_short [Formula: see text] Is Decidable in [Formula: see text]
title_sort [formula: see text] is decidable in [formula: see text]
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206654/
http://dx.doi.org/10.1007/978-3-030-40608-0_8
work_keys_str_mv AT besalexis formulaseetextisdecidableinformulaseetext
AT choffrutchristian formulaseetextisdecidableinformulaseetext

Ejemplares similares