episciences.org_7104_20230321085607225
20230321085607225
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
18605974
07
29
2022
Volume 18, Issue 3
Computability of DataWord Transductions over Different Data Domains
Léo
Exibard
Emmanuel
Filiot
Nathan
Lhote
PierreAlain
Reynier
In this paper, we investigate the problem of synthesizing computable
functions of infinite words over an infinite alphabet (data $\omega$words).
The notion of computability is defined through Turing machines with infinite
inputs which can produce the corresponding infinite outputs in the limit. We
use nondeterministic transducers equipped with registers, an extension of
register automata with outputs, to describe specifications. Being
nondeterministic, such transducers may not define functions but more generally
relations of data $\omega$words. In order to increase the expressive power of
these machines, we even allow guessing of arbitrary data values when updating
their registers.
For functions over data $\omega$words, we identify a sufficient condition
(the possibility of determining the next letter to be outputted, which we call
next letter problem) under which computability (resp. uniform computability)
and continuity (resp. uniform continuity) coincide.
We focus on two kinds of data domains: first, the general setting of
oligomorphic data, which encompasses any data domain with equality, as well as
the setting of rational numbers with linear order; and second, the set of
natural numbers equipped with linear order. For both settings, we prove that
functionality, i.e. determining whether the relation recognized by the
transducer is actually a function, is decidable. We also show that the
socalled next letter problem is decidable, yielding equivalence between
(uniform) continuity and (uniform) computability. Last, we provide
characterizations of (uniform) continuity, which allow us to prove that these
notions, and thus also (uniform) computability, are decidable. We even show
that all these decision problems are PSpacecomplete for $(\mathbb{N},<)$ and
for a large class of oligomorphic data domains, including for instance
$(\mathbb{Q},<)$.
07
29
2022
7104
French National Research Agency (ANR)
ANR16CE400007
French National Research Agency (ANR)
ANR18CE400015
https://creativecommons.org/licenses/by/4.0
arXiv:2101.07038
10.48550/arXiv.2101.07038
https://arxiv.org/abs/2101.07038v3
https://arxiv.org/abs/2101.07038v2
https://arxiv.org/abs/2101.07038v1
10.46298/lmcs18(3:9)2022
https://lmcs.episciences.org/7104

https://lmcs.episciences.org/9861/pdf

https://lmcs.episciences.org/9861/pdf