††thanks: Funded by a FRIA fellowship from the F.R.S.-FNRS.††thanks: Research
associate of F.R.S.-FNRS. Supported by the ARC Project Transform Fédération
Wallonie-Bruxelles and the FNRS CDR J013116F; MIS F451019F projects.††thanks:
Partly funded by the ANR projects DeLTA (ANR-16-CE40-0007) and Ticktac
(ANR-18-CE40-0015).††thanks: Partly funded by the ANR projects DeLTA
(ANR-16-CE40-0007) and Ticktac (ANR-18-CE40-0015).

# Computability of Data-Word Transductions
over Different Data Domains

Léo Exibard  Université Libre de Bruxelles, Brussels, Belgium and Aix
Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
<EMAIL_ADDRESS>Emmanuel Filiot  Université Libre de Bruxelles,
Brussels, Belgium  Nathan Lhote  Aix Marseille Univ, Université de Toulon,
CNRS, LIS, Marseille, France  Pierre-Alain Reynier  Aix Marseille Univ,
Université de Toulon, CNRS, LIS, Marseille, France

###### Abstract

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 non-
deterministic transducers equipped with registers, an extension of register
automata with outputs, to describe specifications. Being non-deterministic,
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 so-
called 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 PSpace-complete for $(\mathbb{N},<)$ and
for a large class of oligomorphic data domains, including for instance
$(\mathbb{Q},<)$.

###### keywords:

Data Words and Register Automata and Register Transducers and Functionality
and Continuity and Computability.

###### Contents

  1. 1 Data alphabet, languages and transducers
    1. 1.1 Data as logical structures
    2. 1.2 Words and data words
    3. 1.3 Functions and relations
    4. 1.4 Register transducers
  2. 2 Continuity and computability
    1. 2.1 Continuity notions
      1. 2.1.1 Continuity
      2. 2.1.2 Cauchy continuity
      3. 2.1.3 Uniform continuity
    2. 2.2 Computability notions
    3. 2.3 Computability versus continuity
      1. 2.3.1 From computability to continuity
      2. 2.3.2 From continuity to computability
  3. 3 Oligomorphic data
    1. 3.1 Characterizing functionality and continuity
      1. 3.1.1 Characterization of non-emptiness
      2. 3.1.2 Characterizing functionality
      3. 3.1.3 Characterizing continuity
    2. 3.2 Deciding functionality, continuity and computability
      1. 3.2.1 Computing the next letter
      2. 3.2.2 Deciding functionality, continuity and computability
  4. 4 A non oligomorphic case: $(\mathbb{N},\\{<,0\\})$A non oligomorphic case: (N,{¡,0})
    1. 4.1 On loop iteration
    2. 4.2 $\mathbb{Q}$-typesQ-types
    3. 4.3 Relations between machines over $\mathbb{N}$ and over $\mathbb{Q}_{+}$Relations between machines over N and Q+
    4. 4.4 Emptiness of automata
    5. 4.5 Functionality
    6. 4.6 Next-letter problem
    7. 4.7 Uniform continuity
    8. 4.8 Continuity
    9. 4.9 Transfer result
  5. A Proof of Lemma 14
  6. B Proof of Lemma 30

## Introduction

#### Synthesis

Program synthesis aims at deriving, in an automatic way, a program that
fulfils a given specification. It is very appealing when for instance the
specification describes, in some abstract formalism (an automaton or ideally a
logic), important properties that the program must satisfy. The synthesised
program is then _correct-by-construction_ with regard to those properties. It
is particularly important and desirable for the design of safety-critical
systems with hard dependability constraints, which are notoriously hard to
design correctly. In their most general forms, synthesis problems have two
parameters, a set of inputs In and a set of outputs Out, and relate two
classes $\mathcal{S}$ and $\mathcal{I}$ of specifications and implementations
respectively. A specification $S\in\mathcal{S}$ is a relation
$S\subseteq\textsf{In}\times\textsf{Out}$ and an implementation
$I\in\mathcal{I}$ is a function $I:\textsf{In}\rightarrow\textsf{Out}$. The
$(\mathcal{S},\mathcal{I})$-synthesis problem asks, given a (finite
representation of a) specification $S\in\mathcal{S}$, whether there exists
$I\in\mathcal{I}$ such that for all $u\in\textsf{In}$, $(u,I(u))\in S$. If
such $I$ exists, then the procedure must return a program implementing $I$. If
all specifications in $\mathcal{S}$ are _functional_ , in the sense that they
are the graphs of functions from In to Out, then the
$(\mathcal{S},\mathcal{I})$-synthesis is a membership problem: given
$f\in\mathcal{S}$, does $f\in\mathcal{I}$ hold?

#### Automata-theoretic approach to synthesis

In this paper, we are interested in the automata-theoretic approach to
synthesis, in the sense that specifications and implementations can be defined
by automata, or by automata extended with outputs called _transducers_. In
this approach, In and Out are sets of words over input and output alphabets
$\Sigma$ and $\Gamma$ respectively. Perhaps the most well-known decidable
instance of synthesis in this context is the celebrated result of Büchi and
Landweber [JL69]: $\mathcal{S}$ is the class of $\omega$-regular
specifications, which relates infinite input words
$i_{0}i_{1}\dots\in\Sigma^{\omega}$ to infinite output words
$o_{0}o_{1}\dots\in\Gamma^{\omega}$ through $\omega$-automata (e.g.
deterministic parity automata), in the sense that the infinite convolution
$i_{0}o_{0}i_{1}o_{1}\dots\in(\Sigma\Gamma)^{\omega}$ must be accepted by an
$\omega$-automaton defining the specification. The class of implementations
$\mathcal{I}$ is all the functions which can be defined by Mealy machines, or
equivalently, deterministic _synchronous_ transducers which, whenever they
read some input $i\in\Sigma$, produce some output $o\in\Gamma$ and possibly
change their own internal state. The seminal result of Büchi and Landweber has
recently triggered a lot of research in reactive system synthesis and game
theory, both on the theoretical and practical sides, see for instance
[CHVB18]. We identify two important limitations to the now classical setting
of $\omega$-regular reactive synthesis:

  1. $(i)$

specifications and implementations are required to be synchronous, in the
sense that a single output $o\in\Gamma$ must be produced for each input
$i\in\Sigma$, and

  2. $(ii)$

the alphabets $\Sigma$ and $\Gamma$ are assumed to be finite.

Let us argue why we believe $(i)$ and $(ii)$ are indeed limitations. First of
all, if a specification is not realizable by a synchronous transducer, then a
classical synthesis algorithm stops with a negative answer. However, the
specification could be realizable in a larger class of implementations
$\mathcal{I}$. As an example, if $S$ is the set of words $i_{0}o_{0}\dots$
such that $o_{\ell}=i_{\ell+1}$, then $S$ is not realizable synchronously
because it is impossible to produce $o_{\ell}$ before knowing $i_{\ell+1}$.
But this specification is realizable by a program which can delay its output
production by one time unit. Enlarging the class of implementations can
therefore allow one to give finer answers to the synthesis problem in cases
where the specification is not synchronously realizable. We refer to this type
of relaxations as _asynchronous_ implementations. An asynchronous
implementation can be modelled in automata-theoretic terms as a transducer
which, whenever it reads an input $i\in\Sigma$, produces none or several
outputs, i.e. a finite word $u\in\Gamma^{*}$. Generalizations of reactive
system synthesis to asynchronous implementations have been considered in
[HKT12, FLZ11, WZ20]. In these works however, the specification is still
synchronous, given by an automaton which strictly alternates between reading
input and output symbols. Here, we also assume that specifications are
asynchronous, as it gives more flexibility in the relations that can be
expressed. For instance, one can specify that some response has to be delayed,
or, when transforming of data streams, allow for erasure and/or duplication of
some data values.

The synchronicity assumption made by classical reactive synthesis is motivated
by the fact that such methods focus on the control of systems rather than on
the data, in the sense that input symbols are Boolean signals issued by some
environment, and output symbols are actions controlling the system in order to
fulfil some correctness properties. From a data-processing perpective, this is
a strong limitation. The synthesis of systems which need to process streams of
data, like a monitoring system or a system which cleans noisy data coming from
sensors, cannot be addressed using classical $\omega$-regular synthesis.
Therefore, one needs to extend specifications to asynchronous specifications,
in the sense that the specifications must describe properties of executions
which do not strictly alternate between inputs and outputs. Already on finite
words however, the synthesis problem of asynchronous specifications by
asynchronous implementations, both defined by transducers, is undecidable in
general [CL14], and decidable only in some restricted cases [FJLW16]. The
second limitation $(ii)$ is addressed in the next paragraph.

#### From finite to infinite alphabets

To address the synthesis of systems where _data_ are taken into account, one
also needs to extend synthesis methods to handle infinite alphabets. As an
example, in a system scheduling processes, the data values are process ids. In
a stream processing system, data values can be temperature or pressure
measurements for example. Not only one needs synthesis methods able to handle
infinite alphabets of data values, but where those values can be compared
through some predicates, like equality or a linear order. Recent works have
considered the synthesis of (synchronous) reactive systems processing _data
words_ whose elements can be compared for equality [KMB18, ESKG14, KK19,
EFR19] as well as comparison with a linear order on the data [EFK21]. To
handle data words, just as automata have been extended to _register automata_
, transducers have been extended to _register transducers_. Such transducers
are equipped with a finite set of registers in which they can store data
values and with which they can compare them for equality, inequality or in
general any predicate, depending on the considered data domain. When a
register transducer reads a data value, it can compare it to the values stored
in its registers, assign it to some register, and output the content of none
or several registers, i.e., a finite word $v$ of register contents. To have
more expressive power, we also allow transducers to guess an arbitrary data
value and assign it to some register. This feature, called data guessing, is
arguably a more robust notion of non-determinism notion for machines with
registers and was introduced to enhance register automata [KZ10]. We denote by
NRT the class of non-deterministic register transducers. As an example,
consider the (partial111In this paper, data word functions can be partial by
default and therefore we do not explicitly mention it in the sequel.) data
word function $g$ which takes as input any data word of the form
$u=su_{1}su_{2}\cdots\in\mathbb{N}^{\omega}$, $s$ occurs infinitely many times
in $u$, and $u_{i}\in(\mathbb{N}\setminus\\{s\\})^{+}$ for all $i\geq 1$. Now,
for all $i\geq 1$, denote by $|u_{i}|$ the length of $u_{i}$ and by $d_{i}$
the last data value occurring in $u_{i}$. The function $g$ is then defined as
$g(u)=d_{1}^{|u_{1}|}sd_{2}^{|u_{2}|}s\dots$. This function can be defined by
the NRT of Figure 1. Note that without the guessing feature, this function
could not be defined by any NRT.

$i$$f$$o$$\top\mid\downarrow{}r_{s},?r_{o},\mathrm{out}~{}\varepsilon$$\star\neq
r_{s}\mid\downarrow{}r_{c},\mathrm{out}~{}r_{o}$$\wedge\begin{array}[]{c}\star=r_{s}\\\
r_{c}=r_{o}\end{array}\mid?r_{o},\mathrm{out}~{}r_{s}$$\star\neq
r_{s}\mid\downarrow{}r_{c},\mathrm{out}~{}r_{o}$ Figure 1: An NRT defining the
data word function $g$, equipped with a Büchi condition. The current data
value denoted by $\star$ is tested with respect to the content of the
registers on the left of the bar $|$. On the right of the bar, there are
instructions such as assigning an arbitrary data value to $r$ (notation $?r$),
outputting the content of a register or nothing ($\mathrm{out}~{}r$), or
assigning the current data value to some register ($\downarrow{}r$). The Büchi
condition makes sure that the first data value, initially stored in $r_{s}$
during the first transition, occurs infinitely many times. The register
$r_{c}$ stores the last data value that has been read. $r_{o}$ is meant to
store the last data value $d_{i}$ of an input chunk $u_{i}$. It has to be
guessed whenever a new chunk $u_{i}$ is starting to be read, and on reading
again $r_{s}$, the automaton checks that the guess was right by evaluating
whether $r_{c}=r_{o}$ (at that moment, $r_{c}$ contains $d_{i}$).

Thanks to the non-determinism of NRT, in general and unlike the previous
example, there might be several accepting runs for the same input data word,
each of them producing a possibly different output data word. Thus, NRT can be
used to define binary relations of data $\omega$-words, and hence
specifications. In the works [KMB18, ESKG14, KK19, EFR19, EFK21] already
mentioned, NRT have been used as a description of specifications, however they
are assumed to be synchronous and without guessing.

#### Objective: synthesis of computable data word functions

In this paper, our goal is to define a synthesis setting where both
limitations $(i)$ and $(ii)$ are lifted. In particular, specifications are
assumed to be given by (asynchronous) non-deterministic register transducers
equipped with a Büchi condition (called NRT). To retain decidability, we
however make some hypothesis: specifications are assumed to be functional,
i.e., they already define a function from input data $\omega$-words to output
data $\omega$-words. While this a strong hypothesis, it is motivated by two
facts. First, the synthesis problem of asynchronous implementations from
asynchronous specifications given by (non-functional) NRT is undecidable in
general, already in the finite alphabet case [CL14]. Second, functional NRT
define uncomputable functions in general, and therefore they cannot be used as
machines that compute the function they specify. Since those functions are
defined over infinite inputs, let us make clear what we mean by computable
functions. A (partial) function $f$ of data $\omega$-words is computable if
there exists a Turing machine $M$ that has an infinite input
$x\in\mathrm{dom}(f)$, and produces longer and longer prefixes of the output
$f(x)$ as it reads longer and longer prefixes of the input $x$. Therefore,
such a machine produces the output $f(x)$ in the limit. As an example, the
function $g$ previously defined is computable. A Turing machine computing it
simply has to wait until it sees the last data value $d_{i}$ of a chunk
$u_{i}$ (which necessarily happens after a finite amount of time), compute the
length $\ell_{i}$ of $u_{i}$ and once it sees $d_{i}$, output
$d_{i}^{\ell_{i}}$ at once. However, consider the extension $f$ to any input
data word defined as follows: $f(u)=g(u)$ if $u$ is in the domain of $g$, and
otherwise $f(u)=s^{\omega}$ where $s$ is the first data value of $u$. Such
function is not computable. For instance, on input $x=sd^{\omega}$ (where
$d\neq s$ is an arbitrary data value), we have $f(sd^{\omega})=s^{\omega}$, as
$x$ is not in the domain of $g$. Yet, on any finite prefix $\alpha_{k}=sd^{k}$
of $sd^{\omega}$, any hypothetical machine computing $f$ cannot output
anything. Indeed, there exists a continuation of $\alpha_{k}$ which is in the
domain of $g$, and for which $f$ produces a word which starts with a different
data value than $f(\alpha_{k}d^{\omega})$: it suffices to take the
continuation $(sd)^{\omega}$, as we have
$f(\alpha_{k}(sd)^{\omega})=g(\alpha_{k}(sd)^{\omega})=d^{k}(sd)^{\omega}$.

In this paper, our goal is therefore to study the following synthesis problem:
given a functional NRT defining a function $f$ of data $\omega$-words,
generate a Turing machine which computes $f$ if one exists. In other words,
one wants to decide whether $f$ is computable, and if it is, to synthesize an
algorithm which computes it.

#### Contributions

Register transducers can be parameterized by the set of data values from which
the $\omega$-data words are built, along with the set of predicates which can
be used to test those values. We distinguish a large class of data sets for
which we obtain decidability results for the later problem, namely the class
of oligomorphic data sets [BKL14]. Briefly, oligomorphic data sets are
countable sets $D$ equipped with a finite set of predicates which satisfies
that for all $n$, $D^{n}$ can be partitioned into finitely many equivalence
classes by identifying tuples which are equal up to automorphisms (predicate-
preserving bijections). For example, any set equipped with equality is
oligomorphic, such as $(\mathbb{N},\\{=\\})$, $(\mathbb{Q},\\{<\\})$ is
oligomorphic while $(\mathbb{N},\\{<\\})$ is not. However
$(\mathbb{N},\\{<\\})$ is an interesting data set in and of itself. We also
investigate NRT over such data set, using the fact that it is a substructure
of $(\mathbb{Q},\\{<\\})$ which is oligormorphic. Our detailed contributions
are the following:

  1. 1.

We first establish a general correspondence between computability and the
classical mathematical notion of continuity (for the Cantor distance) for
functions of data $\omega$-words (Theorems 9 and 10). This correspondence
holds under a general assumption, namely the decidability of what we called
the _next-letter problem_ , which in short asks that the next data value which
can be safely outputted knowing only a finite prefix of the input data
$\omega$-word is computable, if it exists. We also show similar
correspondences for more constrained computability and continuity notions,
namely Cauchy, uniform and $m$-uniform computability and continuity. In these
correspondences, the construction of a Turing machine computing the function
is effective.

  2. 2.

We consider a general computability assumption for oligomorphic data sets,
namely that they have decidable first-order satisfiability problem [Boj19]. We
call such data sets _decidable_. We then show that functions defined by NRT
over decidable oligomorphic data sets and over $(\mathbb{N},\\{<\\})$, have
decidable next-letter problem. As a consequence (Theorems 20 and 37), we
obtain that a function of data $\omega$-words definable by an NRT over
decidable oligomorphic data sets and over $(\mathbb{N},\left\\{<\right\\})$,
is computable iff it is continuous (and likewise for all computability and
continuity notions we introduce). This is a useful mathematical
characterization of computability, which we use to obtain our main result.

  3. 3.

As explained before, an NRT may not define a function in general but a
relation, due to non-determinism. Functionality is a semantical, and not
syntactical, notion. We nevertheless show that checking whether an NRT defines
a function is decidable for decidable oligomorphic data sets (Theorem 21).
This problem is called the _functionality problem_ and is a prerequisite to
our study of computability, as we assume specifications to be functional. We
establish PSpace-completeness of the functionality problem for NRT over
$(\mathbb{N},\\{<\\})$ (Corollary 35) and for oligomorphic data sets (Theorem
21) under some additional assumptions on the data set that we call polynomial
decidability. In short, it is required that the data set has PSpace-decidable
first-order satisfiability problem.

  4. 4.

Finally, we show (again Theorem 21) that continuity of functions defined by
NRT over decidable (resp. polynomially decidable) oligomorphic data sets is
decidable (resp. PSpace-c). We also obtain PSpace-completeness in the non-
oligomorphic case $(\mathbb{N},\\{<\\})$ (Theorem 42). These results also hold
for the stronger notion of uniform continuity (see also Theorem 39). As a
result of the correspondence between computability and continuity, we also
obtain that computability and uniform computability are decidable for
functions defined by NRT over decidable oligomorphic data sets, and PSPace-c
for polynomially decidable oligomorphic data sets as well as
$(\mathbb{N},\\{<\\})$. This is our main result and it answers positively our
initial synthesis motivation.

The proof techniques we use have the following structure in common: first, we
characterize non-functionality and non-continuity by structural patterns on
NRT and establish small witness properties for the existence these patterns.
Then, based on the small witness properties, we show how to decide whether
given an NRT, such patterns are matched or not. While the proofs have some
similarities between the oligomorphic case, the case $(\mathbb{N},\\{<\\})$
and the functionality and continuity problems, there are subtle technical
differences which make them hard to factorize with reasonable amount of
additional notations and theoretical assumptions.

#### Related Work

We have already mentioned works related to the synthesis problem. We now give
references to results on computability and continuity. The notion of
continuity with regards to Cantor distance is not new, and for rational
functions over finite alphabets, it was already known to be decidable [Pri02].
The approach of Prieur is to reduce continuity to functionality by defining
from a transducer $T$ a transducer realizing its topological closure. We were
able to extend this approach to almost all the cases we considered, except for
transducers over $(\mathbb{N},\left\\{<\right\\})$ with guessing allowed, so
we chose a different proof strategy. The connection between continuity and
computability for functions of $\omega$-words over a finite alphabet has
recently been investigated in [DFKL20] for one-way and two-way transducers.
Our results lift the case of one-way transducers from [DFKL20] to data words.
Our results were partially published in conference proceedings [EFR20]. In
that publication, only the case of data sets equipped with the equality
predicate was considered. We now consider oligomorphic data sets (which
generalise the latter case), the data set $(\mathbb{N},\\{<\\})$ and new
computability notions. Despite the fact that our results are more general,
this generalisation also allows to extract the essential arguments needed to
prove this kind of results. Moreover, compared to [EFR20], we add here the
possibility for the register transducer to make non-deterministic register
assignment (data guessing), which strictly increases their expressive power.

##  1 Data alphabet, languages and transducers

###  1.1 Data as logical structures

Let $\Sigma$ be a finite signature with relation and constant symbols. Let
$\mathbb{D}=(D,\Sigma^{\mathbb{D}})$ be a logical structure over $\Sigma$ with
a countably infinite domain $D$ and an interpretation of each symbol of
$\Sigma$. Note that we often identify $\mathbb{D}$ and $D$ when the structure
considered is clear, from context.

An _automorphism_ of a structure $\mathbb{D}$ is a bijection $\mu:D\rightarrow
D$ which preserves the constants and the predicates of $\mathbb{D}$: for any
constant $c$ in $D$, $\mu(c)=c$ and for any relation of $\Sigma$, $R\subseteq
D^{r}$, we have $\forall\ \bar{x},\ R(\bar{x})\Leftrightarrow
R(\mu(\bar{x}))$, where $\mu$ is naturally extended to $D^{r}$ by applying it
pointwise. We denote by $\mathrm{Aut}(\mathbb{D})$ the set of automorphisms of
$\mathbb{D}$. Let $\bar{x}\in\mathbb{D}^{d}$, the set
$\left\\{\mu(\bar{x})\mid\ \mu\in\mathrm{Aut}(\mathbb{D})\right\\}$ is called
the _orbit_ of $\bar{x}$ under the action of $\mathrm{Aut}(\mathbb{D})$.

We will be interested in structures that have a lot of symmetry. For instance
the structures $(\mathbb{N},\left\\{0,=\right\\})$,
$(\mathbb{Z},\left\\{<\right\\})$ and $(\mathbb{Q},\left\\{<\right\\})$ fall
under our study as well as more sophisticated structures like
$(1(0+1)^{*},{\otimes})$ where $\otimes$ is the bitwise xor operation. Other
structures like $(\mathbb{Z},\left\\{+\right\\})$ will not have enough
internal symmetry to be captured by our results.

A logical structure $\mathbb{D}$ is _oligomorphic_ if for any natural number
$n$ the set $\mathbb{D}^{n}$ has finitely many orbits under the action of
$\mathrm{Aut}(\mathbb{D})$.

Oligomorphic structures can be thought of as “almost finite”. Consider
$(\mathbb{N},\left\\{=\right\\})$, then $\mathbb{N}^{2}$ only has two orbits:
the diagonal $\left\\{(x,x)\mid\ x\in\mathbb{N}\right\\}$ and its complement
$\left\\{(x,y)\in\mathbb{N}^{2}\mid\ x\neq y\right\\}$. In fact
$(\mathbb{N},\left\\{=\right\\})$ is oligomorphic, since the orbit of an
element of $\mathbb{N}^{n}$ is entirely determined by which coordinates are
equal to each other. Similarly, one can see that the dense linear order
$(\mathbb{Q},\left\\{<\right\\})$ is oligomorphic.

The automorphism group of $(\mathbb{Z},\left\\{<\right\\})$ consists of all
translations $n\mapsto n+c$ for some fixed $c\in\mathbb{Z}$. This means that
$\mathbb{Z}$ only has one orbit. However, $\mathbb{Z}^{2}$ has an infinite
number of orbits since the difference between two numbers is preserved by
translation. Hence $(\mathbb{Z},\left\\{<\right\\})$ is not oligormorphic.
However, the fact that $(\mathbb{Z},\left\\{<\right\\})$ is a substructure of
$(\mathbb{Q},\left\\{<\right\\})$ will allow us to extend our results to this
structure, with some additional work. For more details on oligomorphic
structures see [Boj19, Chap. 3].

Let $G$ be a group acting on both $X,Y$, then a function $f:X\rightarrow Y$ is
called _equivariant_ if for all $x\in X,\mu\in G$ we have
$f(\mu(x))=\mu(f(x))$.

###  1.2 Words and data words

For a (possibly infinite) set $A$, we denote by $A^{*}$ (resp. $A^{\omega}$)
the set of finite (resp. infinite) words over this alphabet, and we let
$A^{\infty}=A^{*}\cup A^{\omega}$. For a word $u=u_{1}\dots u_{n}$, we denote
$\lvert u\lvert=n$ its length, and, by convention, for $x\in A^{\omega},\lvert
x\lvert=\infty$. The empty word is denoted $\varepsilon$. For $1\leq i\leq
j\leq\lvert w\lvert$, we let $w[i{:}j]=w_{i}w_{i+1}\dots w_{j}$ and
$w[i]=w[i{:}i]$ the $i$th letter of $u$. For $u,v\in A^{\infty}$, we say that
$u$ is a prefix of $v$, written $uv$, if there exists $w\in A^{\infty}$ such
that $v=uw$. In this case, we define $u^{-1}v=w$. For $u,v\in A^{\infty}$, we
say that $u$ and $v$ _match_ if either $uv$ or $vu$, which we denote by
$u\mathrel{{\hstretch{.8}{\parallel}}}v$, and we say that they _mismatch_ ,
written $u\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}v$,
otherwise. Finally, for $u,v\in A^{\infty}$, we denote by $u\wedge v$ their
longest common prefix, i.e. the longest word $w\in A^{\infty}$ such that $wu$
and $wv$.

Let $\mathbb{D}$ be a logical structure. A word over $\mathbb{D}$ is called a
_$\mathbb{D}$ -data word_ (or just _data word_). Note that
$\mathrm{Aut}(\mathbb{D})$ naturally acts on $\mathbb{D}^{\infty}$.

###  1.3 Functions and relations

A (binary) relation between sets $X$ and $Y$ is a subset $R\subseteq X\times
Y$. We denote its domain $\mathrm{dom}(R)=\\{x\in X\mid\exists y\in Y,(x,y)\in
R\\}$. It is _functional_ if for all $x\in\mathrm{dom}(R)$, there exists
exactly one $y\in Y$ such that $(x,y)\in R$. Then, we can also represent it as
the function $f_{R}:\mathrm{dom}(R)\rightarrow Y$ such that for all
$x\in\mathrm{dom}(R)$, $f(x)=y$ such that $y\in Y$ (we know that such $y$ is
unique). $f_{R}$ can also be seen as a _partial_ function $f_{R}:X\rightarrow
Y$. In this paper, unless otherwise stated, functions of data words are
assumed to be partial, and we denote by $\mathrm{dom}(f)$ the domain of any
(partial) function $f$.

###  1.4 Register transducers

Let $\mathbb{D}$ be a logical structure, and let $R$ be a finite set of
variables. We define _$R$ -tests_ by the following grammar:

$\phi::=P(\bar{t})|\phi\wedge\phi|\phi\vee\phi|\neg\phi$

where $P$ is a symbol of arity $k$ in the signature of $\mathbb{D}$ and
$\bar{t}$ a $k$-tuple of terms. We denote by $\mathsf{Test}(R)$ the set of
$R$-tests. Terms are defined by either a constant of $\mathbb{D}$ or a
variable of $R$. In other words $R$-tests are exactly the quantifier-free
formulas over the signature of $\mathbb{D}$ using variables in $R$.

######  Remark 1.

We choose tests to be quantifier-free formulas. However we could have chosen
existential first-order formulas without affecting our results. Note that we
choose this formalism just for simplicity’s sake, and that it does not make
any difference for structures which admit quantifier elimination such as
$(\mathbb{N},\left\\{=\right\\})$ or $(\mathbb{Q},\left\\{<\right\\})$.

A _non-deterministic register transducer_ (NRT for short) over $\mathbb{D}$ is
a tuple $\left(Q,R,\Delta,q_{0},\overline{\mathsf{c}_{0}},F\right)$. Where $Q$
is a finite set of states, $R$ is a finite set of registers, $q_{0}\in Q$,
$\overline{\mathsf{c}_{0}}\in\Sigma^{R}$ is a vector of constant symbols,
$F\subseteq Q$, and $\Delta$ is a finite subset of

$\underbrace{Q}_{\text{current
state}}\times\underbrace{\mathsf{Test}(R\uplus\left\\{\mathsf{input}\right\\})}_{\text{current
registers + input data}}\times\underbrace{Q}_{\text{target
state}}\times\underbrace{\left\\{\mathsf{keep},\mathsf{set},\mathsf{guess}\right\\}^{R}}_{\text{register
operations}}\times\underbrace{R^{*}}_{\text{output word}}$

A _non-guessing_ transducer (NGRT) has a transition function which is included
in $Q\times\mathsf{Test}(R\uplus\left\\{\mathsf{input}\right\\})\times
Q\times\left\\{\mathsf{keep},\mathsf{set}\right\\}^{R}\times R^{*}$. Finally,
a _deterministic_ transducer (DRT) satisfies an even stronger condition: its
transition relation is a function of type
$\delta:Q\times\mathsf{Test}(R\uplus\left\\{\mathsf{input}\right\\})\rightarrow
Q\times\left\\{\mathsf{keep},\mathsf{set}\right\\}^{R}\times R^{*}$ where,
additionally, tests are mutually exclusive, i.e. for all
$\phi,\psi\in\mathrm{dom}(\delta)$, $\phi\wedge\psi$ is unsatisfiable.

######  Remark 2.

Note that in the definition of a transducer we require that $\mathbb{D}$
contains at least one constant symbol. This is needed for annoying technical
reasons, namely in order to initialize registers to some value.

However it is not too damaging since, given a $\Sigma$-structure $\mathbb{D}$
of domain $D$, one can always consider the
$\Sigma\uplus\left\\{\mathsf{c}_{0}\right\\}$-structure $\mathbb{D}_{\bot}$
with domain $D\uplus\left\\{\bot\right\\}$, which is just the structure
$\mathbb{D}$ with the extra constant symbol being interpreted as the new
element $\bot$, the other relations and constants are unchanged, except
naturally for the equality relation which is extended to include
$(\bot,\bot)$.

For simplicity’s sake we will sometimes talk about structures without
mentioning any constant, implicitely stating that we extend the structure to
include $\bot$. Also note that this operation of adding a fresh constant does
not affect oligomorphicity.

Let $T$ be an NRT given as above. A _configuration_ $C$ of $T$ is given by a
pair $(q,\bar{d})$ where $q\in Q$ is a state and $d\in\mathbb{D}^{R}$ is a
tuple of data values, hence the group $\mathrm{Aut}(\mathbb{D})$ naturally
acts on the configurations of $T$ by not touching the states and acting on the
content of the registers pointwise. The _initial configuration_ is the pair
$C_{0}=(q_{0},\bar{d}_{0})$ with
$\bar{d}_{0}=\overline{\mathsf{c}}_{0}^{\mathbb{D}}$ being the interpretation
of the constants in $\mathbb{D}$. A configuration is called _final_ if the
state component is in $F$. Let
$C_{1}=(q_{1},\bar{d}_{1}),C_{2}=(q_{2},\bar{d}_{2})$ be two configurations,
let $d\in\mathbb{D}$ and let
$t=(q_{1},\phi,q_{2},\mathsf{update},v)\in\Delta$. We say that $C_{2}$ is a
_successor configuration_ of $C_{1}$ by reading $d$ through $t$ and producing
$w\in\mathbb{D}^{|v|}$ if the following hold:

  * •

By letting $\bar{d}_{1}[\mathsf{input}\leftarrow
d]:\left\\{\begin{array}[]{l}r\in R\mapsto\bar{d}_{1}(r)\\\
\mathsf{input}\mapsto d\end{array}\right.$, we have
$\bar{d}_{1}[\mathsf{input}\leftarrow d]\models\phi$

  * •

for all $r\in R$, if $\mathsf{update}(r)=\mathsf{keep}$, then
$\bar{d}_{2}(r)=\bar{d}_{1}(r)$

  * •

for all $r\in R$, if $\mathsf{update}(r)=\mathsf{set}$, then
$\bar{d}_{2}(r)=d$

  * •

$w(i)=\bar{d}_{2}(v(i))$ for all $i\in\left\\{1,\ldots,|v|\right\\}$

Moreover, we write $C_{1}\xrightarrow{d,\phi,\mathsf{update}|w}_{T}C_{2}$ to
indicate that fact. Often we don’t mention $T$ (when clear from context), nor
$\phi$ and $\mathsf{update}$, and we simply write
$C_{1}\xrightarrow{d|w}C_{2}$. Given a sequence of successor configurations,
called a _run_ ,
$\rho=C_{1}\xrightarrow{d_{1}|w_{1}}C_{2}\xrightarrow{d_{2}|w_{2}}C_{3}\ldots
C_{n}\xrightarrow{d_{n}|w_{n}}C_{n+1}$, we write
$C_{1}\xrightarrow{d_{1}d_{2}\cdots d_{n}|w_{1}w_{2}\cdots w_{n}}C_{n+1}$. We
sometimes even don’t write the output $C\xrightarrow{u}C^{\prime}$ stating
that there is a sequence of transitions reading $u$ going from $C$ to
$C^{\prime}$.

Let $\rho=C_{1}\xrightarrow{d_{1}|v_{1}}C_{2}\ldots
C_{n}\xrightarrow{d_{n}|v_{n}}C_{n+1}\ldots$ denote a possibly infinite run.
If $C_{1}=C_{0}$, then $\rho$ is called _initial_. If an infinite number of
configurations of $\rho$ are final, we say that $\rho$ is _final_. A run which
is both initial and final is _accepting_. We say that the run $\rho$ is over
the input word $x=d_{1}\ldots d_{n}\ldots$ and produces $w=v_{1}\ldots
v_{n}\ldots$ in the output. Then the semantics of $T$ is defined as
$\llbracket T\rrbracket=\left\\{(x,w)\mid\ \rho\text{ is over $x$, produces
$y$ and is
accepting}\right\\}\subseteq\mathbb{D}^{\omega}\times\mathbb{D}^{\infty}$. An
NRT is called _functional_ if $\llbracket T\rrbracket$ is a (partial)
function. Note that in the following we will mainly consider transducers that
only produce $\omega$-words. Restricting the accepting runs of a transducer to
runs producing infinite outputs is a Büchi condition and can easily be done by
adding one bit of information to states.

##  2 Continuity and computability

###  2.1 Continuity notions

We equip the set $A^{\infty}$ with the usual distance: for $u,v\in
A^{\infty}$, $\lVert u,v\rVert=0$ if $u=v$ and $\lVert u,v\rVert=2^{-\lvert
u\wedge v\lvert}$ otherwise. A sequence of (finite or infinite) words
$(w_{n})_{n\in\mathbb{N}}$ converges to some word $w$ if for all $\epsilon>0$,
there exists $N\geq 0$ such that for all $n\geq N$, $\lVert
w_{n},w\rVert\leq\epsilon$. Given a language $L\subseteq A^{\infty}$, we
denote by $\bar{L}$ its topological closure, i.e. the set of words which can
be approached arbitrarily close by words of $L$.

######  Remark 3.

Whether the alphabet $A$ is finite or infinite substantially modifies the
properties of the metric space $A^{\infty}$. Indeed when $A$ is finite this
space is compact, but it is not when $A$ is infinite.

####  2.1.1 Continuity

[Continuity] A function $f:A^{\omega}\rightarrow B^{\omega}$ is _continuous_
at $x\in\mathrm{dom}(f)$ if (equivalently):

  1. [(a)]

  2. 1.

for all sequences of words $(x_{n})_{n\in\mathbb{N}}$ converging towards $x$,
where for all $i\in\mathbb{N}$, $x_{i}\in\mathrm{dom}(f)$, we have that
$(f(x_{n}))_{n\in\mathbb{N}}$ converges towards $f(x)$.

  3. 2.

$\forall i\geq 0,\ \exists j,\ \forall y\in\mathrm{dom}(f),\ \lvert x\wedge
y\lvert\geq j\Rightarrow\lvert f(x)\wedge f(y)\lvert\geq i$

The function $f$ is called _continuous_ if it is continuous at each
$x\in\mathrm{dom}(f)$.

####  2.1.2 Cauchy continuity

A Cauchy continuous function maps any Cauchy sequence to a Cauchy sequence.
One interesting property of Cauchy continuous functions is that they always
admit a (unique) continuous extension to the completion of their domain. Since
we deal with $A^{\infty}$ which is complete, the completion of the domain of a
function $f$, denoted $\overline{\mathrm{dom}(f)}$, is simply its closure.

[Cauchy continuity] A function $f:A^{\omega}\rightarrow A^{\omega}$ is _Cauchy
continuous_ if the image of a Cauchy sequence in $\mathrm{dom}(f)$ is a Cauchy
sequence.

######  Remark 4.

Any Cauchy continuous function $f$ can be continuously extended over
$\overline{\mathrm{dom}(f)}$ in a unique way, which we denote by $\bar{f}$.

####  2.1.3 Uniform continuity

[Uniform continuity] A function $f:A^{\omega}\rightarrow A^{\omega}$ is
_uniformly continuous_ if there exists a mapping
$m:\mathbb{N}\rightarrow\mathbb{N}$ such that:

$\forall i\geq 0,\forall x,y\in\mathrm{dom}(f),\lvert x\wedge y\lvert\geq
m(i)\Rightarrow\lvert f(x)\wedge f(y)\lvert\geq i$

Such a function $m$ is called a _modulus of continuity_ 222The usual notion of
modulus of continuity is defined with respect to distance, but here we choose
to define it with respect to longest common prefixes, for convenience. Given
$m$ a modulus of continuity in our setting we can define $\omega:x\mapsto
2^{-m\left(\left\lceil\log_{2}\left(\frac{1}{x}\right)\right\rceil\right)}$
and recover the usual notion. for $f$. We also say that $f$ is _$m$
-continuous_. Finally, a functional NRT $T$ is _uniformly continuous_ when
$\llbracket T\rrbracket$ is uniformly continuous.

######  Remark 5.

In the case of a finite alphabet, and in general for compact spaces, Cauchy
continuity is equivalent to uniform continuity, but for infinite alphabets
this does not hold anymore. Consider the following function $f$ computable by
a DRT over the data alphabet $(\mathbb{N},\left\\{0,<\right\\})$ and defined
by $u0x\mapsto x$, for $u0\in\mathbb{N}^{*}$ being a strictly decreasing
sequence. Then this function is not uniformly continuous, since two words may
be arbitrarily close yet have very different images. However one can check
that the image of a Cauchy sequence is indeed Cauchy: let
$(x_{n})_{n\in\mathbb{N}}$ be a Cauchy sequence in the domain of $f$. Let us
assume without loss of generality that all the $x_{n}$’s begin with the same
letter $i\in\mathbb{N}$. Then, after reading at most $i+1$ symbols of one of
the $x_{n}$’s, the DRT outputs something. Let $j\in\mathbb{N}$ and let $N$ be
such that for all $m,n\geq N$ we have $|x_{m}\wedge x_{n}|\geq i+j+1$. Thus we
have $|f(x_{m})\wedge f(x_{n})|\geq j$, which means that
$(f(x_{n}))_{n\in\mathbb{N}}$ is Cauchy.

We’ve seen in the previous remark that Cauchy continuity and uniform
continuity don’t coincide over infinite alphabets. However when dealing with
oligomorphic structures we recover some form of compactness, that is
compactness of $\mathbb{D}^{\infty}/{\mathrm{Aut}(\mathbb{D})}$, which ensures
that the two notions do coincide in this case.

######  Proposition 6.

Let $\mathbb{D}$ be an oligomorphic structure and let
$f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be an equivariant
function. Then $f$ is uniformly continuous if and only if it is Cauchy
continuous.

######  Proof 2.1.

It is clear that a uniformly continuous function is in particular Cauchy
continuous. Let $\mathbb{D}$ be an oligomorphic structure and let
$f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be an equivariant
function. Let us assume that $f$ is not uniformly continuous. This means that
there exists $i\in\mathbb{N}$ and a sequence $(x_{n},y_{n})_{n\in\mathbb{N}}$
such that for all $n$, $|x_{n}\wedge y_{n}|\geq n$ and $|f(x_{n})\wedge
f(y_{n})|\leq i$. Let us consider the sequence
$([x_{n}],[y_{n}])_{n\in\mathbb{N}}$ of pairs of elements in
$\mathbb{D}^{\omega}/{\mathrm{Aut}(\mathbb{D})}$, i.e. words are seen up to
automorphism. Using standard arguments, one can show that the set
$\mathbb{D}^{\omega}/{\mathrm{Aut}(\mathbb{D})}$, equipped with the distance
$d([x],[y])=\min_{u\in[x],v\in[y]}d(u,v)$, is compact (see [Exi21, Proposition
12.28] for details). As a consequence, we can extract a subsequence (which we
also call $([x_{n}],[y_{n}])_{n\in\mathbb{N}}$ for convenience) and which is
convergent. This means that there are automorphisms
$(\mu_{n})_{n\in\mathbb{N}}$ such that the sequence
$(\mu_{n}(x_{n}))_{n\in\mathbb{N}}$ (and thus
$(\mu_{n}(y_{n}))_{n\in\mathbb{N}}$) converges. Hence by interleaving
$(\mu_{n}(x_{n}))_{n\in\mathbb{N}}$ and $(\mu_{n}(y_{n}))_{n\in\mathbb{N}}$,
we obtain a converging sequence whose image is divergent, which means that $f$
is not Cauchy continuous.

######  Remark 7.

In order to refine uniform continuity one can study $m$-continuity for
particular kinds of functions $m$. For instance for $m:i\mapsto i+b$,
$m$-continuous functions are exactly $2^{b}$-Lipschitz continuous functions.
Similarly, for $m:i\mapsto ai+b$, $m$-continuous function are exactly the
$\frac{1}{a}$-Hölder continuous functions.

Note that while these notions are interesting in and of themselves, they are
very sensitive to the metric that is being used. For instance the metric
$d(x,y)=\frac{1}{|x\wedge y|}$ while defining the same topology over words,
yields different notions of Lipschitz and Hölder continuity.

###  2.2 Computability notions

Let $\mathbb{D}$ be a data set. In order to reason with computability, we
assume in the sequel that the countable set of data values $\mathbb{D}$ we are
dealing with has an effective representation, meaning that each element can be
represented in a finite way. For instance, this is the case when
$\mathbb{D}=\mathbb{N}$. Moreover, we assume that checking if a tuple of
values belongs to some relation of $\mathbb{D}$ is decidable. We say that the
structure $\mathbb{D}$ is _representable_. Formally, a structure is
representable if there exists a finite alphabet $A$ and an injective function
$\mathsf{enc}:\mathbb{D}\rightarrow A^{*}$ such that the sets
$\\{\mathsf{enc}(d)\mid d\in\mathbb{D}\\}$, $\\{\mathsf{enc}(c)\mid c\text{ is
a constant of }\mathbb{D}\\}$ and
$\left\\{\mathsf{enc}(d_{1})\sharp\cdots\sharp\mathsf{enc}(d_{k})\mid\
(d_{1},\ldots,d_{k})\in R\right\\}$ are decidable for all predicates $R$ of
$\mathbb{D}$ and $\sharp\not\in A$. Any infinite word
$d_{1}d_{2}\dots\in\mathbb{D}^{\omega}$ can be encoded as the $\omega$-word
$\mathsf{enc}(d_{1})\sharp\mathsf{enc}(d_{2})\sharp\dots\in(A^{*}\sharp)^{\omega}$.

We now define how a Turing machine can compute a function from
$\mathbb{D}^{\omega}$ to $\mathbb{D}^{\omega}$. We consider deterministic
Turing machines whose cells can contain a letter from $A\cup\\{\sharp\\}$ or a
letter from a finite working alphabet. They have three tapes: a read-only one-
way input tape on alphabet $A\cup\\{\sharp\\}$ (containing an encoding of an
infinite input data word), a two-way working tape, and a write-only one-way
output tape on alphabet $A\cup\\{\sharp\\}$ (on which they write the encoding
of the infinite output data word). Since we always work modulo encoding, for
the sake of simplicity, from now on and in the rest of the paper, we assume
that each cell of the Turing machine, on the input and output tapes, contain a
data value $d\in\mathbb{D}$, while cells of the working tape are assumed to
contain either a data value $d\in\mathbb{D}$ or a letter from the working
alphabet. So, instead of saying the input contains the encoding of a data word
$x$, we just say that it contains the input data word $x$. We discuss in
Remark 8 how the computability notions we introduce hereafter are sensitive to
encodings.

Consider such a Turing machine $M$ and some input data word
$x\in\mathbb{D}^{\omega}$. For any integer $k\in\mathbb{N}$, we let $M(x,k)$
denote the finite output data word written by $M$ on its output tape after
reaching cell number $k$ of the input tape (assuming it does). Observe that as
the output tape is write-only, the sequence of data words $(M(x,k))_{k\geq 0}$
is non-decreasing, and thus we denote by $M(x)$ the limit content of the
output tape.

[Computability] Let $\mathbb{D}$ be a representable data domain. A data word
function $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ is _computable_
if there exists a deterministic multi-tape machine $M$ such that for all
$x\in\mathrm{dom}(f)$, $M(x)=f(x)$. We say that $M$ _computes_ $f$.

[Cauchy computability] Let $\mathbb{D}$ be a representable data domain. A data
word function $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ is _Cauchy
computable_ if there exists a deterministic multi-tape machine $M$ computing
$f$ such that for all $x$ in the topological closure
$\overline{\mathrm{dom}(f)}$ of $\mathrm{dom}(f)$, the sequence
$(M(x,k))_{k\geq 0}$ converges to an infinite word. In other words a Cauchy
computable function is a function which admits a continuous extension to the
closure of its domain and which is computable. We say that $M$ _Cauchy
computes_ $f$.

[Uniform computability] Let $\mathbb{D}$ be a representable data domain. A
data word function $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ is
_uniformly computable_ if there exists a deterministic multi-tape machine $M$
and a computable mapping $m:\mathbb{N}\rightarrow\mathbb{N}$ such that $M$
computes $f$ and for all $i\geq 0$ and $x\in\mathrm{dom}(f)$, $|M(x,m(i))|\geq
i$. Such a function $m$ is called a _modulus of computability_ for $f$. In
that case $f$ is called _$m$ -computable_. We say that $M$ _uniformly
computes_ $f$, and also that $M$ _$m$ -computes_ $f$.

The function $g$ defined in the Introduction (p. From finite to infinite
alphabets), for the data domain of integers, is computable. Remind that it is
defined on all input words of the form $x=su_{1}d_{1}su_{2}d_{2}s\dots$ such
that $s$ occurs infinitely often, and for all $i$, $s$ does not occur in
$u_{i}d_{i}$, by $g(x)=d_{1}^{|u_{1}|+1}sd_{2}^{|u_{2}|+1}s\dots$. A Turing
machine just needs to read the input up to $d_{1}$, then output $d_{1}$
exactly $|u_{1}|+1$ times, and so on for the other pieces of inputs.

In Remark 5, the function $f$ is not uniformly continuous but Cauchy
continuous. It is actually not uniformly computable but Cauchy computable. As
a matter of fact, all the computability notions we define here entail the
respective continuity notions defined before. We make this formal in Section
2.3.

######  Remark 8 (Robustness to encoding).

When actually representing words over an infinite alphabet, it is not
realistic to assume that one letter takes a constant amount of space and can
be read in a constant amount of time. Then, which of the many notions
introduced above are sensitive to encoding and which ones are more robust?

Let $\mathbb{D}$ be a representable structure, and let
$\mathsf{enc}:\mathbb{D}\rightarrow A^{*}$ be its encoding function. Let
$f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be a function and let
$f_{\mathsf{enc}}:(A\uplus\sharp)^{\omega}\rightarrow(A^{*}\uplus\sharp)^{\omega}$
be defined as ${\mathsf{enc}_{\sharp}}\circ
f\circ{\mathsf{enc}_{\sharp}}^{-1}$, where $\mathsf{enc}_{\sharp}:d_{1}\cdots
d_{n}\mapsto\mathsf{enc}(d_{1})\sharp\cdots\sharp\mathsf{enc}(d_{n})$.
Continuity and computability are robust enough so that $f$ is continuous
(resp. computable) if and only if $f_{\mathsf{dec}}$ is. Cauchy continuity and
computability also fall under this category. In contrast, uniform continuity
and uniform computability are very sensitive to encoding. As an example, the
function which maps a word to the second letter in the word is _never_
uniformly continuous, since the encoding of the first letter may be
arbitrarily long. Nevertheless, uniform computability is still a relevant
notion, as it provides guarantees on the maximal number of input data values
which need to be read to produce a given number of output data values, even
though the encoding of those values can be arbitrarily large.

###  2.3 Computability versus continuity

In this section, we show that all the computability notions (computability,
Cauchy continuity, …) imply their respective continuity notions. We then give
general conditions under which the converse also holds.

####  2.3.1 From computability to continuity

######  Theorem 9.

Let $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ and let
$m:\mathbb{N}\rightarrow\mathbb{N}$, the following implications hold:

  * •

$f$ is computable $\Rightarrow$ $f$ is continuous

  * •

$f$ is Cauchy computable $\Rightarrow$ $f$ is Cauchy continuous

  * •

$f$ is uniformly computable $\Rightarrow$ $f$ is uniformly continuous

  * •

$f$ is $m$-computable $\Rightarrow$ $f$ is $m$-continuous

######  Proof 2.2.

Assume that $f$ is computable by a deterministic multi-tape Turing machine
$M$. Let $x$ be in the topological closure of $\mathrm{dom}(f)$ and
$(x_{n})_{n}$ be a sequence in $\mathrm{dom}(f)$ converging to $x$. We show
that $(f(x_{n}))_{n}$ converges to $M(x)$ if $M(x)$ is infinite, which is the
case for all $x\in\mathrm{dom}(f)$ since $f$ is computable. For all $k\geq 0$,
let $p_{k}$ the prefix of $x$ of length $k$. Since
$\lim_{n\rightarrow\infty}x_{n}=x$, for all $k$, there exists $n_{k}$ such
that for all $m\geq n_{k}$, $p_{k}\leq x_{m}$. As $M$ is a deterministic
machine, it implies that $M(x,k)\leq f(x_{m})$. So, for all $k$, $M(x,k)\leq
f(x_{m})$ for all but finitely many $m$. It follows that $(f(x_{m}))_{m}$
converges to $M(x)=\lim_{k\rightarrow\infty}M(x,k)$ if $M(x)$ is an infinite
word, which it is if $x\in\mathrm{dom}(f)$, entailing continuity of $f$. If
additionally $f$ is Cauchy computable, then it is also the case for all
$x\in\overline{\mathrm{dom}(f)}$, entailing Cauchy continuity of $f$.

It remains to show the fourth statement, which entails the third. So, let us
assume that $f$ is $m$-computable by some machine $M$. We show it is
$m$-continuous. Let $i\geq 0$, $x,y\in\mathrm{dom}(f)$ such that $|x\wedge
y|\geq m(i)$. We must show that $|f(x)\wedge f(y)|\geq i$. We have
$M(x,m(i))=M(y,m(i))$ because $M$ is deterministic and $|x\wedge y|\geq m(i)$.
By definition of $m$-computability, we also have $|M(x,m(i))|\geq i$. Since
$M(x,m(i))\leq f(x)$ and $M(y,m(i))\leq f(y)$, we get $|f(x)\wedge f(y)|\geq
i$, concluding the proof.

####  2.3.2 From continuity to computability

While, as we have seen in the last section, computability of a function $f$
implies its continuity, and respectively for all the notions of computability
and continuity we consider in this paper, the converse may not hold in
general. We give sufficient conditions under which the converse holds for $f$,
namely when it has a computable next-letter problem. This problem asks, given
as input two finite words $u,v\in\mathbb{D}^{*}$, to output, if it exists, a
data value $d\in\mathbb{D}$ such that for all $y\in\mathbb{D}^{\omega}$ such
that $uy\in\mathrm{dom}(f)$, we have $vd\leq f(uy)$. Because of the universal
quantification on $y$, note that $d$ is unique if it exists. Formally:

Next-Letter Problem for $f$:

Input | $u,v\in\mathbb{D}^{*}$
---|---
Output | $\left\\{\begin{array}[]{ll}d\in\mathbb{D}&\text{if for all }y\in\mathbb{D}^{\omega}\text{ s.t. }uy\in\mathrm{dom}(f),vd\leq f(uy)\\\ \texttt{none}&\text{otherwise}\end{array}\right.$

######  Theorem 10.

Let $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be a function with a
computable next-letter problem and let $m:\mathbb{N}\rightarrow\mathbb{N}$,
the following implications hold:

  * •

$f$ is continuous $\Rightarrow$ $f$ is computable

  * •

$f$ is Cauchy continuous $\Rightarrow$ $f$ is Cauchy computable

  * •

$f$ is uniformly continuous $\Rightarrow$ $f$ is uniformly computable

  * •

$f$ is $m$-continuous $\Rightarrow$ $f$ is $m$-computable

######  Proof 2.3.

Let us assume the existence of a procedure $\textsf{Next}_{f}(u,v)$ which
computes the next-letter problem. To show the four statements, we show the
existence of a deterministic Turing machine $M_{f}$ common to the four
statements, in the sense that $M_{f}$ computes $f$ if $f$ is continuous,
respectively Cauchy computes $f$ is f is Cauchy continuous, etc. The Turing
machine $M_{f}$ is best presented in pseudo-code as follows.

Data: $x\in\mathbb{D}^{\omega}$

1 $v:=\epsilon$;

2 for  _$i=0$ to $+\infty$_ do

3 $d:=\textsf{Next}_{f}(x[{:}i],v)$;

4 while  _$d\neq\texttt{none}$_ do

output $d$;

// write $d$ on the output tape

5 $v:=vd$;

6 $d:=\textsf{Next}_{f}(x[{:}i],v)$;

7

8 end while

/* end while loop when $d=\texttt{none}$ */

9

10 end for

Algorithm 1 Turing machine $M_{f}$ defined in pseudo-code.

Now, we show that if $f$ is continuous, then $M_{f}$ computes $f$, i.e.
$M_{f}(x)=f(x)$ for all $x\in\mathrm{dom}(f)$. First, for all $i\geq 0$, let
$v_{i}=d_{i,1}d_{i,2}\dots$ be the sequence of data values outputted at line 1
at the $i$th iteration of the for loop. Note that the $i$th iteration may not
exist when the test at line 1 is forever true. In that case, we set
$v_{i}=\epsilon$. By definition of $M_{f}(x,i)$, we have333For any
$\omega$-word $\alpha$, we let $\alpha.\epsilon=\alpha$.
$M_{f}(x,i)=v_{0}v_{1}\dots v_{i}$ for all $i\geq 0$. Moreover, by definition
of the next-letter problem, we also have $M_{f}(x,i)\leq f(x)$. Now, by
definition, $M_{f}(x)=v_{0}v_{1}v_{2}\dots$. So, if it is infinite, then
$M_{f}(x)=f(x)$. It remains to show that it is indeed true when $f$ is
continuous. Suppose it is not the case. Then there exists $i_{0}$ such that
for all $i\geq i_{0}$ the call $\textsf{Next}_{f}(x[{:}i],v_{0}\dots
v_{i_{0}})$ returns none (assume $i_{0}$ is the smallest index having this
property). Let $d$ such that $v_{0}\dots v_{i_{0}}d<f(x)$. Then, for all
$i\geq i_{0}$, there exists $\alpha_{i}\in\mathcal{D}^{\omega}$ and
$d^{\prime}\neq d$ such that $x[{:}i]\alpha_{i}\in\mathrm{dom}(f)$ and
$v_{0}\dots v_{i_{0}}d^{\prime}<f(x[{:}i]\alpha_{i})$. Clearly, the sequence
$(f(x[{:}i]\alpha_{i}))_{i}$, if it converges, does not converge to $f(x)$.
Since $(x[{:}i]\alpha_{i})_{i}$ converges to $x$, this contradicts the
continuity of $f$.

Consider now the case where $f$ is Cauchy-continuous. It implies that $f$
admits a unique continuous extension $\overline{f}$ to
$\overline{\mathrm{dom}(f)}$ (see Remark 4). By the first statement we just
proved, $M_{\overline{f}}$ computes $\overline{f}$, and by definition of
Cauchy-computability, we conclude that $M_{f}$ Cauchy-computes $f$.

We finally prove the fourth statement, which implies the third. Suppose that
$f$ is $m$-continuous for some modulus of continuity $m$. We show that $M_{f}$
$m$-computes $f$. We already proved that $M_{f}$ computes $f$ (as $f$ is
continuous). Let $i\geq 0$ and $x\in\mathrm{dom}(f)$. It remains to show that
$|M_{f}(x,m(i))|\geq i$. Let $j=m(i)$. Since the algorithm $M_{f}$ calls
$\textsf{Next}_{f}(x[{:}j],\cdot)$ until it returns none, we get that
$v_{0}v_{1}\dots v_{j}$ is the longest output which can be safely output given
only $x[{:}j]$, i.e. $v_{0}\dots v_{j}=\bigwedge\\{f(x[{:}j]\alpha)\mid
x[{:}j]\alpha\in\mathrm{dom}(f)\\}$. If $v_{j}$ is infinite, then
$|M_{f}(x,j)|=+\infty$ and we are done. Suppose $v_{j}$ is finite. Then, there
exists $\alpha\in\mathcal{D}^{\omega}$ such that
$x[{:}j]\alpha\in\mathrm{dom}(f)$ and $f(x)\wedge
f(x[{:}j]\alpha)=v_{0}v_{1}\dots v_{j}=M_{f}(x,j)$. Since $|x\wedge
x[{:}j]\alpha|\geq j=m(i)$, by $m$-continuity of $f$, we get that
$|M_{f}(x,j)|\geq i$, concluding the proof.

##  3 Oligomorphic data

In this section we consider a structure $\mathbb{D}$ which is oligomorphic. We
will show that in this case one can decide, under reasonable computability
assumptions, all the notions of continuity introduced in the previous section,
as well as compute the next-letter problem. The first step is to prove
characterizations of these properties, and then show that the
characterizations are decidable. Let
$\mathcal{R}:\mathbb{N}\rightarrow\mathbb{N}$ denote the _Ryll-Nardzewski
function_ of $\mathbb{D}$ which maps $k$ to the number of orbits of $k$-tuples
of data values, which is finite thanks to oligomorphism.

###  3.1 Characterizing functionality and continuity

The main goal of this section is to give for NRT characterizations of
functionality, continuity and uniform continuity, that consist in small
witnesses. These small witnesses are obtained by pumping arguments that rely
on the fact that there is only a finite number of configuration orbits.

We start by defining _loop removal_ , a tool which will prove useful
throughout this section. The main idea is that although no actual loop over
the same configuration can be guaranteed over infinite runs, the
oligomorphicity property guarantees that a configuration _orbit_ will be
repeated over long enough runs. A _loop_ is a run of the shape
$C\xrightarrow{u|v}D\xrightarrow{w|z}\mu(D)$ such that $\mu(C)=C$. The shorter
run $C\xrightarrow{\mu(u)|\mu(v)}\mu(D)$ is thus called the run obtained after
_removing the loop_.

######  Proposition 11 (Small run witness).

let $T$ be an NRT with $k$ registers and state space $Q$, and let
$C\xrightarrow{u|v}D$ be a run. Then there exists $u^{\prime},v^{\prime}$ with
$|u^{\prime}|\leq|Q|\cdot\mathcal{R}(2k)$ such that
$C\xrightarrow{u^{\prime}|v^{\prime}}D$.

######  Proof 3.1.

The idea behind this proposition is simple: any large enough run must contain
a loop and can thus be shortened. Let $u=a_{1}\cdots a_{n}$ with a run
$C_{1}\xrightarrow{a_{1}|v_{1}}C_{2}\xrightarrow{a_{2}|v_{2}}C_{3}\cdots
C_{n}$. Let us assume that $n>|Q|\mathcal{R}(2k)$, we want to obtain a shorter
run from $C_{1}$ to $C_{n}$. Let us consider the orbits of the pairs
$(C_{1},C_{1}),(C_{1},C_{2}),\ldots,(C_{1},C_{n})$. Since
$n>|Q|\mathcal{R}(2k)$, there must be two pairs in the same orbit, i.e. there
must be two indices $1\leq i<j\leq n$ and some automorphism $\mu$ such that
$\mu(C_{1},C_{i})=(C_{1},C_{j})$. Hence we obtain the run
$\mu(C_{1})\xrightarrow{\mu(a_{1}\cdots a_{i-1}|v_{1}\cdots
v_{i-1})}\mu(C_{i})=C_{1}\xrightarrow{\mu(a_{1}\cdots a_{i-1}|v_{1}\cdots
v_{i-1})}C_{j}$ which is strictly shorter.

####  3.1.1 Characterization of non-emptiness

Let an NRA (non deterministic register automaton) be simply an NRT without any
outputs. We give a characterization of non-emptiness in terms of small
witnesses.

######  Proposition 12.

Let $A$ be an NRA, the following are equivalent:

  1. 1.

$A$ recognizes at least one word

  2. 2.

there exist $C_{0}\xrightarrow{u_{1}}C\xrightarrow{u_{2}}\mu(C)$ with $C$
being a final configuration, and $\mu\in\mathrm{Aut}(\mathbb{D})$

  3. 3.

there exist $C_{0}\xrightarrow{u_{1}}C\xrightarrow{u_{2}}\mu(C)$ with
$|u_{1}|,|u_{2}|\leq|Q|\cdot\mathcal{R}(2k)$, $C$ being a final configuration,
and $\mu\in\mathrm{Aut}(\mathbb{D})$

######  Proof 3.2.

Let us assume (1) and let $x$ be a word accepted by $A$. Since $\mathbb{D}$ is
oligomorphic, there is only a finite number of orbits of configurations. Thus
an accepting run of $A$ over $x$ must go through some accepting configuration
orbit infinitely often, and in particular at least twice. Hence (2) holds.

Let us assume that (2) holds. To bound the size of $u_{1}$ and $u_{2}$ and
obtain (3), we apply Proposition 11 twice in $A$ (seen as a trivial NRT
producing only epsilon outputs): once to remove loops in the run
$C_{0}\xrightarrow{u_{1}\mid\epsilon}C$ and once in
$C\xrightarrow{u_{2}\mid\epsilon}\mu(C)$.

Let us assume (3), then the word $u_{1}u_{2}\mu(u_{2})\mu^{2}(u_{2})\cdots$ is
accepted by $A$.

####  3.1.2 Characterizing functionality

Characterizing functionality is slightly more complicated since we have to
care about outputs. Moreover, we need to exhibit patterns involving two runs
which makes pumping more involved.

We start with a useful yet quite technical lemma, which will allow us to
remove loops while preserving mismatches.

######  Lemma 13 (Small mismatch witness).

There exists a polynomial $P(x,y,z)$ such that the following hold.

Let $T$ be an NRT, with $k$ registers, a state space $Q$ and a maximal output
length $L$. Let $C_{1}\xrightarrow{u|u_{1}}D_{1}$ and
$C_{2}\xrightarrow{u|u_{2}}D_{2}$ be runs such that
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$. Then
there exists $u^{\prime}$ of length less than $P(\mathcal{R}(4k+2),|Q|,L)$ and
$u_{1}^{\prime},u_{2}^{\prime}$, so that
$C_{1}\xrightarrow{u^{\prime}|u_{1}^{\prime}}D_{1}$,
$C_{2}\xrightarrow{u^{\prime}|u_{2}^{\prime}}D_{2}$ with
$u_{1}^{\prime}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}^{\prime}$.

######  Proof 3.3.

Let $\rho_{1}=C_{1}\xrightarrow{u|u_{1}}D_{1}$ and
$\rho_{2}=C_{2}\xrightarrow{u|u_{2}}D_{2}$ be runs such that
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$.

Our goal is to show that either $|u|$ is smaller than some
polynomial444Technically, $5\mathcal{R}(4k+2)^{7}\cdot Q^{14}\cdot L^{5}$ is a
suitable such polynomial, although better bounds could be computed. in
$\mathcal{R}(4k+2),|Q|$ and $L$ or we can remove a synchronous loop in
$\rho_{1},\rho_{2}$ while preserving the mismatch. A synchronous loop is
defined as a loop over the same input in the product transducer $T\times T$.
Let $u_{1}=\alpha a_{1}\beta_{1}$, $u_{2}=\alpha a_{2}\beta_{2}$ with
$a_{1}\neq a_{2}$. We will only consider removing loops that do _not_ contain
the transitions producing the mismatching letters $a_{1}$ or $a_{2}$.

In order to make things more precise we introduce some useful loop vocabulary.
An _initial loop_ in $\rho=C_{1}\rightarrow C_{2}\rightarrow\cdots\rightarrow
C_{n}$ is a loop starting in $C_{1}$. A _simple loop_ is a loop $C\rightarrow
D\rightarrow\mu(D)$ so that there is no pair of configurations $B,\lambda(B)$
with $\lambda(C)=C$ which occur within the part $D\rightarrow\mu(D)$ of the
run. Similarly a _simple synchronous loop_ is a simple loop over $T\times T$.

In the following we will consider loops that are synchronous and simple. They
will be of the shape
$(C_{1},C_{2})\rightarrow(B_{1},B_{2})\rightarrow\mu(B_{1},B_{2})$ with
$\mu(C_{1},C_{2})=(C_{1},C_{2})$. Moreover, we will ask that the automorphism
satisfies $\mu(a_{1})=a_{1}$ and $\mu(a_{2})=a_{2}$, this is done to be sure
that removing or adding loops does not affect the fact that $a_{1}\neq a_{2}$
(note that it would be enough to simply ask that $\mu(a_{1})=a_{1}$). We call
such loops _nice_. With these constraints, if we have a sequence of
configuration pairs in $(\rho_{1},\rho_{2})$ of length larger than
$\mathcal{R}(4k+2)Q^{2}$, we are sure to find a nice loop that preserves
$(a_{1},a_{2})$.

We call the _effect_ of a loop on $\rho_{1}$, the length of the output factor
removed from $\alpha$, in particular the effect is $0$ if the factor removed
is in $\beta_{1}$ (and symmetrically for $\rho_{2}$). We call the _net effect_
of a synchronous loop on $\rho_{1},\rho_{2}$ the difference between the effect
in $\rho_{1}$ and the effect on $\rho_{2}$. Loops with a positive, negative
and null net effect are called positive, negative and null loops,
respectively.

If there exists a null nice loop, then removing it preserves the mismatch and
we are done. We split the proof into the two remaining cases: 1) either all
nice loops are strictly positive (without loss of generality) or 2) some nice
loops are strictly positive while others are strictly negative. In the first
case, we will show that $u$ has to be _small_. In the second case, we will
show that, after removing all nice loops, we can repump (a small number of)
positive and negative nice loops to realign the mismatch.

Let us consider a configuration $(B_{1},B_{2})$ in $(\rho_{1},\rho_{2})$. The
_effects_ of $(B_{1},B_{2})$ is the set of effects of nice loops starting in
$(C_{1},C_{2})$ ending in $(B_{1},B_{2})$ (note that we consider any nice
loop, not just the ones occurring in $(\rho_{1},\rho_{2})$). Then we say that
$(B_{1},B_{2})$ is _positive_ (resp.  _negative_) if all its effect are
positive (resp.  _negative_).

We consider two cases, 1) either $(\rho_{1},\rho_{2})$ only has strictly
positive configurations (without loss of generality) or 2) it has
configurations with positive and negative effects (possibly different
configurations).

Let us start with the first case, we observe two simple facts: the effect of a
nice loop is bounded by $\mathcal{R}(4k+2)|Q|^{2}L$ and, similarly, the output
length of a run without nice loops is bounded by $\mathcal{R}(4k+2)|Q|^{2}L$.
Let us denote by $\Delta_{0}$ the difference of output lengths
$|u_{2}|-|u_{1}|$. Since there are no nice loops having $0$ effect on
$\rho_{1}$ this means that $|\beta_{1}|\leq\mathcal{R}(4k+2)|Q|^{2}L$, and
thus $\Delta_{0}\geq-\mathcal{R}(4k+2)|Q|^{2}L$. We denote by $\Delta_{1}$ the
difference of output length after removing one nice loop from
$(\rho_{1},\rho_{2})$. We observe that
$-\mathcal{R}(4k+2)|Q|^{2}L\leq\Delta_{0}<\Delta_{1}$ since all nice loops
must be strictly positive. We carry on removing nice loops until there are
none left. Note that removing nice loops cannot introduce configurations with
new effects: some configurations are erased, and to some an automorphism $\mu$
satisfying $\mu(C_{1},C_{2},a_{1},a_{2})=(C_{1},C_{2},a_{1},a_{2})$ is
applied, which preserves the effect set. We thus obtain
$-\mathcal{R}(4k+2)|Q|^{2}L\leq\Delta_{0}<\Delta_{1}<\ldots<\Delta_{l}\leq\mathcal{R}(4k+2)|Q|^{2}L$
after removing $l$ nice loops and obtaining a run without nice loops. Hence we
get that $l\leq 2\mathcal{R}(4k+2)|Q|^{2}L$. This means that the runs
$\rho_{1},\rho_{2}$ could not have been very large. In fact we have
$|\rho_{1}|\leq(l+1)\times\mathcal{R}(4k+2)|Q|^{2}\leq
3\mathcal{R}(4k+2)^{2}|Q|^{4}L$.

We only have left to consider the second case, that is, $(\rho_{1},\rho_{2})$
has configurations with positive and negative effects. Note that the effects
of configurations belong to the interval
$[-\mathcal{R}(4k+2)|Q|^{2}L,\mathcal{R}(4k+2)|Q|^{2}L]$. Let $d$ denote in
the following the $\gcd$ of all effects of configurations in
$(\rho_{1},\rho_{2})$. Let
$(B_{1}^{1},B_{2}^{1}),\ldots,(B_{1}^{l},B_{2}^{l})$ be configurations so that
the $\gcd$ of their collective effects is $d$, and with at least one positive
and one negative effect. We can assume that $l\leq\mathcal{R}(4k+2)|Q|^{2}L$.
We remove nice loops without deleting these configurations. Note that removing
loops may mean applying an automorphism to some of these configurations.
However, the automorphisms always preserve $(C_{1},C_{2},a_{1},a_{2})$ so the
effect set of the configuration is left unchanged. Also note that the effects
of such loops are all multiples of $d$. After removing all these loops we are
left with runs that are small ($\leq(l+1)\mathcal{R}(4k+2)|Q|^{2}$) but the
outputs $a_{1}$, $a_{2}$ may very well be misaligned (by a factor of $d$). The
idea is to use the configurations
$(B_{1}^{1},B_{2}^{1}),\ldots,(B_{1}^{k},B_{2}^{k})$ to pump simple loops into
the run to realign the two mismatching outputs. Let us explain how these nice
loops can be pumped into the runs: Let
$\alpha:(C_{1},C_{2})\xrightarrow{(u_{1},u_{2})|(v_{1},v_{2})}(B_{1},B_{2})$
be a run and let
$\beta:(C_{1},C_{2})\xrightarrow{(x_{1},x_{2})|(y_{1},y_{2})}(B_{1},B_{2})\xrightarrow{(z_{1},z_{2})|(w_{1},w_{2})}\mu(B_{1},B_{2})$
be a nice loop. By applying $\mu^{-1}$ to $\alpha$ and the second part of
$\beta$ we obtain a run of the shape:
$(C_{1},C_{2})\xrightarrow{\mu^{-1}(u_{1},u_{2})|\mu^{-1}(v_{1},v_{2})}\mu^{-1}(B_{1},B_{2})\xrightarrow{\mu^{-1}(z_{1},z_{2})|\mu^{-1}(w_{1},w_{2})}(B_{1},B_{2})$,
with the added effect of $\beta$.

Note that we have chosen the configurations carefully so that we can change
the alignment by any multiple of $d$.

######  Lemma 14 (Signed generalized Bézout identity).

Let $p_{1},\ldots,p_{k}\in\mathbb{Z}{\setminus}{\left\\{0\right\\}}$ be non-
zero integers, such that at least two have different signs. Then there exist
natural numbers $n_{1},\ldots,n_{k}\leq\max(|p_{1}|^{3},\ldots,|p_{k}|^{3})$
such that:

$n_{1}p_{1}+\ldots+n_{k}p_{k}=\gcd(p_{1},\ldots,p_{k})$

Using the previous lemma (see Appendix A for the proof), we can change the
alignment by $d$ using only a polynomial number of times each loop (at most
$(\mathcal{R}(4k+2)|Q|^{2}L)^{3}$ for each loop). Since the runs are small,
the misalignment is also small (at most $(l+1)\mathcal{R}(4k+2)|Q|^{2}L$) and
we only need to repeat this operation a polynomial number of times. Finally
since we have chosen automorphisms that preserve $a_{1},a_{2}$, we are sure to
obtain a mismatch.

######  Proposition 15 (Functionality).

There exists a polynomial $P(x,y,z)$ such that the following holds.

Let $R\subseteq\mathbb{D}^{\omega}\times\mathbb{D}^{\omega}$ be given by an
NRT $T$ with $k$ registers, a state space $Q$ and a maximum output length $L$.
The following are equivalent:

  1. 1.

$R$ is not functional

  2. 2.

there exist
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}D_{1}\xrightarrow{w|w_{1}}\mu(C_{1})$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}D_{2}\xrightarrow{w|w_{2}}\mu(C_{2})$
with $C_{1},D_{2}$ final, $\mu\in\mathrm{Aut}(\mathbb{D})$ such that
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$

  3. 3.

there exist
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}D_{1}\xrightarrow{w|w_{1}}\mu(C_{1})$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}D_{2}\xrightarrow{w|w_{2}}\mu(C_{2})$
with $C_{1},D_{2}$ final and $|u|,|v|,|w|\leq P(\mathcal{R}(4k),|Q|,L)$,
$\mu\in\mathrm{Aut}(\mathbb{D})$ such that
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$

######  Proof 3.4.

Let us assume that (1) holds, meaning that $T$ has two accepting runs
$\rho_{1},\rho_{2}$ over some word $x\in\mathbb{D}^{\omega}$ which produce
different outputs. Let $C_{0},C_{1},C_{2}\ldots$ denote the configurations of
$\rho_{1}$ and $C_{0},C_{1}^{\prime},C_{2}^{\prime}\ldots$ the ones of
$\rho_{2}$. Let us consider the orbits of pairs of configurations
$C_{i},C_{i}^{\prime}$. We know that there is a finite number of such orbits.
We also know that an infinite number of such pairs is accepting in the first
component and an infinite number is accepting in the second component. Thus we
can see $(\rho_{1},\rho_{2})$ as a sequence of the following shape, with $C$
and $D^{\prime}$ final:

$(C_{0},C_{0})\xrightarrow{u_{0}}(C,C^{\prime})\xrightarrow{v_{0}}(D,D^{\prime})\xrightarrow{u_{1}}{\mu_{1}(C,C^{\prime})}\xrightarrow{v_{1}}\nu_{1}(D,D^{\prime})\xrightarrow{u_{2}}\cdots$

Since the outputs are different and infinite then they mismatch at some
position $i$. Then, there exists $n$ such that $u=u_{0}v_{0}\cdots u_{n}v_{n}$
has produced at least $i$ symbols, both for $\rho_{1}$ and $\rho_{2}$. Hence
we have shown that
$C_{0}\xrightarrow{u|\alpha_{1}}\mu_{n}(C)\xrightarrow{u_{n+1}|\beta_{1}}\nu_{n+1}(D)\xrightarrow{v_{n+1}|\gamma_{1}}\mu_{n+1}(C)$,
$C_{0}\xrightarrow{u|\alpha_{2}}\mu_{n}(C^{\prime})\xrightarrow{u_{n+1}|\beta_{2}}\nu_{n+1}(D^{\prime})\xrightarrow{v_{n+1}|\gamma_{2}}\mu_{n+1}(C^{\prime})$,
and by assumption $|\alpha_{1}|,|\alpha_{2}|\geq i$, and thus
$\alpha_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}\alpha_{2}$.
Hence we have shown that (2) holds.

Let us assume that (2) holds: i.e. we have
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}D_{1}\xrightarrow{w|w_{1}}\mu(C_{1})$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}D_{2}\xrightarrow{w|w_{2}}\mu(C_{2})$
with $C_{1},D_{2}$ final, $\mu\in\mathrm{Aut}(\mathbb{D})$ such that
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$. We use
Lemma 13 (small mismatch witness) to obtain that
$C_{0}\xrightarrow{u^{\prime}|u_{1}^{\prime}}C_{1}$,
$C_{0}\xrightarrow{u^{\prime}|u_{2}^{\prime}}C_{2}$ with
$u_{1}^{\prime}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}^{\prime}$
and $|u^{\prime}|$ small. We get
$C_{0}\xrightarrow{u^{\prime}|u_{1}^{\prime}}C_{1}\xrightarrow{v|v_{1}}D_{1}\xrightarrow{w|w_{1}}\mu(C_{1})$,
$C_{0}\xrightarrow{u^{\prime}|u_{2}^{\prime}}C_{2}\xrightarrow{v|v_{2}}D_{2}\xrightarrow{w|w_{2}}\mu(C_{2})$.
We now only have to use some loop removal on $v$ and $w$, just as in
Proposition 12, in order to obtain words smaller than
$|Q|^{2}\mathcal{R}(4k)$.

Showing that (3) implies (1) is the easiest part since the pattern clearly
causes non-functionality over the word $uvw\mu(vw)\mu^{2}(vw)\cdots$.

####  3.1.3 Characterizing continuity

Here we characterize continuity and uniform continuity using patterns similar
to the one of functionality. Before doing so we introduce two properties of
configuration. A configuration is _co-reachable_ if there is a final run from
it.

For this we define a notion of _critical pattern_. Let $T$ be an NRT. We
associate to it the set of critical patterns, denoted
$\mathsf{Critical}_{T}(u,v,w,z,C_{1},\mu(C_{1}),D_{1},C_{2},\mu(C_{2}),D_{2})$
($T$ is omitted when clear from context), given by the runs
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})\xrightarrow{w|w_{1}}D_{1}$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})\xrightarrow{z|w_{2}}D_{2}$
so that $D_{1}$, $D_{2}$ are co-reachable and one of the following holds:

  1. [a)]

  2. 1.

$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$, or

  3. 2.

$v_{i}=\epsilon$ and
$u_{j}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{i}w_{i}$
for $\left\\{i,j\right\\}=\left\\{1,2\right\\}$, or

  4. 3.

$v_{1}=v_{2}=\epsilon$ and
$u_{1}w_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}w_{2}$

Before characterizing continuity and uniform continuity, we show a small
critical pattern property. [Small critical pattern] There exists a polynomial
$P^{\prime}(x,y,z)$ such that the following holds.

Let $T$ be an NRT, with $k$ registers, a state space $Q$ and a maximal output
length $L$. Let
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})\xrightarrow{w|w_{1}}D_{1}$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})\xrightarrow{z|w_{2}}D_{2}$
be a critical pattern. Then there exists
$u^{\prime},v^{\prime},w^{\prime},z^{\prime}$ of length less than
$P^{\prime}(\mathcal{R}(4k),|Q|,L)$ and
$u_{1}^{\prime},v_{1}^{\prime},w_{1}^{\prime},u_{2}^{\prime},v_{2}^{\prime},w_{2}^{\prime}$,
so that
$C_{0}\xrightarrow{u^{\prime}|u_{1}^{\prime}}C_{1}\xrightarrow{v^{\prime}|v_{1}^{\prime}}\mu(C_{1})\xrightarrow{w^{\prime}|w_{1}^{\prime}}D_{1}$,
$C_{0}\xrightarrow{u^{\prime}|u_{2}^{\prime}}C_{2}\xrightarrow{v^{\prime}|v_{2}^{\prime}}\mu(C_{2})\xrightarrow{z^{\prime}|w_{2}^{\prime}}D_{2}$
is a critical pattern.

######  Proof 3.5.

We want to remove loops in $u,v,w,z$ without affecting the mismatches. The
idea is to see such a critical pattern as a pair of runs which mismatch and
leverage Lemma 13. In order to make sure that the loops which are removed do
not interfere with the intermediate configurations, we color the states of the
transducer. We consider runs which start with red configurations, then the
middle parts $C_{1}\xrightarrow{v|v_{1}}\mu(C_{1})$ and
$C_{2}\xrightarrow{v|v_{2}}\mu(C_{2})$ are colored in blue and the final parts
are colored in green. Using Lemma 13, we obtain runs smaller than
$P(\mathcal{R}(4k),3|Q|,L)$ (the $3$ factor comes from the coloring). Since
the loops have to be removed in the monochromatic parts, we obtain the desired
result.

Let us give a characterization of continuity and uniform continuity for
functions given by an NRT.

######  Proposition 16 (Continuity/uniform continuity).

There exists a polynomial $P^{\prime}(x,y,z)$ such that the following holds.
Let $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be given by an NRT
$T$ with $k$ registers, a state space $Q$ and a maximum output length $L$. The
following are equivalent:

  1. 1.

$f$ is not uniformly continuous (resp. continuous)

  2. 2.

there exists a critical pattern in
$\mathsf{Critical}(u,v,w,z,C_{1},\mu(C_{1}),D_{1},C_{2},\mu(C_{2}),D_{2})$
(resp. with $C_{1}$ final).

  3. 3.

there exists a critical pattern in
$\mathsf{Critical}(u,v,w,z,C_{1},\mu(C_{1}),D_{1},C_{2},\mu(C_{2}),D_{2})$
such that $|u|,|v|,|w|,|z|\leq P^{\prime}(\mathcal{R}(4k),|Q|,L)$ (resp. with
$C_{1}$ final).

######  Proof 3.6.

Let us assume that (1) holds, meaning that $f$ is not uniformly continuous
(resp. not continuous) at some point $x\in\mathbb{D}^{\omega}$. This means
that there exists $i$ such that for any $n$, there are two accepting runs
$\rho_{1},\rho_{2}$ over $x_{1},x_{2}$ and producing $y_{1},y_{2}$
respectively such that $|x\wedge x_{1}\wedge x_{2}|>n$ and $|y_{1}\wedge
y_{2}|<i-1$. Moreover, if $f$ is not continuous, we can even assume that
$x_{1}=x$ and $\rho_{1}=\rho$, some accepting run over $x$. Let us consider
some $n>2i\cdot|Q|^{2}\cdot\mathcal{R}(2k)$. Let $u=x\wedge x_{1}\wedge
x_{2}$, since $u$ is large enough we have that some pair of configurations in
$\rho_{1},\rho_{2}$ has to repeat at least $2i$ times, up to automorphism. If
$f$ is not continuous, we choose $n$ large enough so that a final
configuration appears at least $2i\cdot|Q|^{2}\cdot\mathcal{R}(2k)$ times in
the first $n$ transitions of $\rho$. That way we can ensure that some pair of
configuration in $\rho,\rho_{2}$ repeats at least $2i$ times, up to
automorphism, with the configuration of $\rho$ being accepting.

Thus we obtain two sequences:
$C_{0}\xrightarrow{u_{0}|v_{0}}C\xrightarrow{u_{1}|v_{1}}\mu_{1}(C)\cdots\mu_{{2i-1}}(C)\xrightarrow{u_{2i}|v_{2i}}\mu_{2i}(C)$
and
$C_{0}\xrightarrow{u_{0}|w_{0}}D\xrightarrow{u_{1}|w_{1}}\mu_{1}(D)\cdots\mu_{{2i-1}}(D)\xrightarrow{u_{2i}|w_{2i}}\mu_{2i}(D)$.
Moreover, let $x_{1}=ux_{1}^{\prime}$, $x_{2}=ux_{2}^{\prime}$, let
$y_{1}=v_{0}\cdots v_{2i}y_{1}^{\prime}$ and $y_{2}=w_{0}\cdots
w_{2i}y_{2}^{\prime}$. We do a case analysis; note that the cases are not
necessarily mutually exclusive.

Case 1) let us first assume that there is some index
$j\in\left\\{1,\ldots,2i\right\\}$ so that
$\mu_{j}(C)\xrightarrow{u_{j}|\epsilon}\mu_{j}(C)$ and
$\mu_{j-1}(D)\xrightarrow{u_{i}|\epsilon}\mu_{j}(D)$. Since the outputs
$y_{1},y_{2}$ mismatch, we have some prefixes of $\rho_{1},\rho_{2}$ of the
shape $C_{0}\xrightarrow{u_{0}\cdots u_{j-1}|v_{0}\cdots
v_{j-1}}\mu_{j}(C)\xrightarrow{u_{j}|\epsilon}\mu_{j}(C)\xrightarrow{x_{1}^{\prime\prime}|y_{1}^{\prime\prime}}E$
and $C_{0}\xrightarrow{u_{0}\cdots u_{j-1}|w_{0}\cdots
w_{j-1}}\mu_{j}(D)\xrightarrow{u_{j}|\epsilon}\mu_{j}(D)\xrightarrow{x_{2}^{\prime\prime}|y_{2}^{\prime\prime}}F$
with $v_{0}\cdots
v_{j-1}y_{1}^{\prime\prime}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}w_{0}\cdots
w_{j-1}y_{2}^{\prime\prime}$. Hence we obtain a critical pattern of shape c).

Case 2) we assume that there are at least $i$ indices
$j\in\left\\{1,\ldots,2i\right\\}$ such that $v_{j}\neq\epsilon$ and at least
$i$ indices such that $w_{j}\neq\epsilon$. Then we have that $v_{0}\cdots
v_{2i}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}w_{0}\cdots
w_{2i}$ and thus we get a critical pattern of shape a).

Case 3), let us assume (without loss of generality) that there strictly fewer
than $i$ indices such that $w_{j}\neq\epsilon$. This means that ther must be
at least $i$ indices such that $v_{j}\neq\epsilon$, otherwise we refer back to
case 1). Let us consider a prefix of $\rho_{2}$ $C_{0}\xrightarrow{u_{0}\cdots
u_{2i}|w_{0}\cdots
w_{2i}}\mu_{2i}D\xrightarrow{x_{2}^{\prime\prime}|y_{2}^{\prime\prime}}$ such
that $v_{0}\cdots
v_{2i}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}w_{0}\cdots
w_{2i}y_{2}^{\prime\prime}$. Let $j$ be such that $w_{j}=\epsilon$, then we
add the loop corresponding to index $j$ after the configuration
$(\mu_{2i}(C),\mu_{2i}(D))$. Doing this may modify the mismatching letter of
$y_{2}^{\prime\prime}$ as to cancelling the mismatch, however if it is the
case, we can simply add the loop twice, which guarantees that the mismatch is
preserved. Thus we obtain a critical pattern of shape b).

If we assume that (2) holds then Claim 3.1.3 gives us (3).

Let us assume that (3) holds. Then $f$ is discontinuous at
$x=uv\mu(v)\mu^{2}(v)\cdots\in\overline{\mathrm{dom}(f)}$ and is thus not
uniformly continuous. Moreover, if $C_{1}$ is final we have that $f$ is
discontinuous at $x\in\mathrm{dom}(f)$, and hence $f$ is not continuous.

###  3.2 Deciding functionality, continuity and computability

We use a key property of oligomorphic structures, namely that orbits can be
defined by first order formulas.

Let $\mathbb{D}=(D,\Sigma^{\mathbb{D}})$ be an oligomorphic structure. We
denote by $\textsf{FO}[\Sigma]$ the set of first-order formulas over signature
$\Sigma$, and just FO if $\Sigma$ is clear from the context.

######  Proposition 17 ([Boj19, Lemma 4.11]).

Let $\mathbb{D}$ be an oligomorphic structure and let $k$ be a natural number.
Any orbit of an element of $\mathbb{D}^{k}$ is first-order definable.

We say that $\mathbb{D}$ is _decidable_ if its Ryll-Nardzewski function is
computable and $\textsf{FO}[\Sigma]$ has decidable satisfiability problem over
$\mathbb{D}$. Moreover, we say that $\mathbb{D}$ is _polynomially decidable_
if an orbit of $\mathbb{D}^{k}$ can be expressed by an FO formula of
polynomial size in $k$ and the FO satisfiability problem is decidable in
PSpace. One (but not us) could easily define a similar notion of exponentially
decidable, or $f$-decidable for some fixed complexity function $f$.

Roughly speaking the main automata problems which we will consider (emptiness,
functionality, continuity, etc) will be PSpace (resp. decidable) whenever the
structure $\mathbb{D}$ is polynomially decidable (resp. decidable).

####  3.2.1 Computing the next letter

In this section, we show how to compute the next letter problem for NRT over a
decidable representable oligomorphic structure $\mathbb{D}$. By Theorems 10
and 9, this entails that continuity and computability coincide for functions
defined by transducers over decidable representable oligomorphic structures,
as stated in Theorem 20 below.

Before tackling the next letter problem, we consider the emptiness problem of
register automata.

######  Theorem 18.

Let $\mathbb{D}$ be a decidable (resp. polynomially decidable) oligomorphic
structure. The emptiness problem for NRA is decidable (resp. in PSpace).

######  Proof 3.7.

We show the result in case of a polynomially decidable structure, the more
general case can be obtained by forgetting about complexity. Let $\mathbb{D}$
be a polynomially decidable oligomorphic structure and let $T$ be an NRA with
$k$ registers and state space $Q$. Since $\mathbb{D}$ is polynomially
decidable, any orbit of $\mathbb{D}^{k}$ can be represented by a formula of
size polynomial in $k$. This means that $\mathcal{R}(k)$ is exponential. Using
the non-emptiness characterization from Proposition 12, we only need to find a
run of length polynomial in $Q$ and $\mathcal{R}(k)$. The idea is to use a
counter bounded by this polynomial, using space in $\log(|Q|\mathcal{R}(k))$,
and execute an NPSpace algorithm which will guess a run of the automaton and
update the type of configurations in space polynomial in $k$ and $\log(|Q|)$.
Simulating the run goes like this: first the type of the configuration is
initialized to $q_{0},(d_{0},\ldots,d_{0})$. Then a new type
$\phi(y_{1},\ldots,y_{k})$ is guessed, as well as a transition which we see as
given by a state $q$ and a formula
$\psi(x_{1},\ldots,x_{k},y_{1},\ldots,y_{k})$. We check that the transition is
valid by deciding the satisfiability of $\exists y_{1},\ldots,y_{k}\
\psi(d_{0},\ldots,d_{0},y_{1},\ldots,y_{k})\wedge\phi(y_{1},\ldots,y_{k})$
which can be done in PSpace, by assumption. We thus move to the new
configuration type given by $q,\phi$ and we continue the simulation. At some
point when $q$ is final, we keep the configuration type in memory and guess
that we will see it again.

######  Lemma 19.

Let $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be a function
defined by an NRT over a decidable representable oligomorphic structure
$\mathbb{D}$. Then, its next letter problem is computable.

######  Proof 3.8.

In the next letter problem we get as input two words $u,v\in\mathbb{D}^{*}$.
Our first goal is to decide whether there exists $d\in D$ such that
$f(u\mathbb{D}^{\omega})\subseteq vd\mathbb{D}^{\omega}$. We check the
negation of this property, i.e. we try to exhibit two runs
$C_{0}\xrightarrow{u|u_{1}}C_{1}\xrightarrow{w|w_{1}}D_{1}$,
$C_{0}\xrightarrow{u|u_{2}}C_{2}\xrightarrow{w|w_{2}}D_{2}$ such that
$|u_{1}w_{1}|,|u_{2}w_{2}|>|v|$ and either $|u_{1}w_{1}\wedge v|<|v|$ or
$|u_{1}w_{1}\wedge u_{2}w_{2}|\leq|v|$. The non-existence of such runs only
depends on the type of $u,v$, hence we can define an automaton which simulates
$T$ and starts by reading some input of the type of $u$ and checks whether
there is a mismatch occurring before the $|v|$ outputs, which can be done by
adding one register to store the mismatch, and two $|v|$-bounded counters in
memory (recall that $v$ is given as input). It finally checks that the reached
configurations are co-reachable by guessing some continuation for each and
simulating $T$ over it. Thus we reduce the non-existence of a next letter to
the non-emptiness of an automaton, which is decidable.

Once we know that such a next letter exists, we only have to simulate any run
of $T$ over $uw$ for an arbitrary $w\in\mathbb{D}^{\omega}$ such that
$uw\in\mathrm{dom}(T)$, and see what the $|v|+1^{\text{th}}$ output is (note
that we can avoid $\epsilon$-producing loops, so this data value will be
output in a finite number of steps). To be able to simulate $T$ over $uw$, we
use the fact that $\mathbb{D}$ is representable and decidable. For every
transition that we want to take, from decidability we can check whether the
transition is possible. Then, once we know the transition is possible, we can
enumerate the representations of elements of $\mathbb{D}$ and check that they
satisfy the transition formula.

As a direct corollary of Lemma 19, Theorem 10 and Theorem 9, we obtain:

######  Theorem 20.

Let $f:\mathbb{D}^{\omega}\rightarrow\mathbb{D}^{\omega}$ be a function
defined by an NRT over a decidable oligomorphic structure $\mathbb{D}$, and
let $m:\mathbb{N}\rightarrow\mathbb{N}$ be a total function. Then,

  1. 1.

$f$ is computable iff $f$ is continuous

  2. 2.

$f$ is uniformly computable iff $f$ is uniformly continuous

  3. 3.

$f$ is $m$-computable iff $f$ is $m$-continuous

####  3.2.2 Deciding functionality, continuity and computability

######  Theorem 21.

Given a decidable (resp. polynomially decidable) oligomorphic structure
$\mathbb{D}$ functionality, continuity and uniform continuity are decidable
(resp. PSpace-c) for functions given by NRT. As a consequence, if $\mathbb{D}$
is representable, then computability and uniform computability are decidable
(resp. PSpace-c).

######  Proof 3.9.

The proofs are very similar, whether we consider functionality, continuity or
uniform continuity. Let us show the result for functionality. Moreover we
assume that $\mathbb{D}$ is polynomially decidable, the argument in the more
general case can easily be obtained just by forgetting about complexity.

Let us consider an NRT $T$ with $k$ registers, state space $Q$ and maximum
output length $L$. We want to show that we can decide the existence of two
runs with a mismatch. From the characterization given in Proposition 15, we
know that the pattern we are looking for is small. We consider a counter
bounded by the value $3P(\mathcal{R}(4k),|Q|,L)$, which can be represented
using polynomial space because $\mathcal{R}(4k)$ is exponential in $k$
($\mathbb{D}$ is polynomially decidable). Our goal is to simulate $T$ and
exhibit a pattern of length bounded by that counter. As we have seen before,
we can easily simulate runs of $T$ in PSpace. The additional difficulty here
is that at some point we have to check that two output positions mismatch. We
use two additional counters which will ensure that the two mismatching outputs
correspond to the same position. Let us now describe how the algorithm goes,
in a high-level manner. We start by initializing two runs in parallel, as well
as our counters. We keep in memory the $2k$-type of the two configurations,
which can be done in polynomial space since $\mathbb{D}$ is polynomially
decidable. We keep guessing in parallel two transitions for our runs and
updating the $2k$-type using the fact that satisfiability of FO is in PSpace.
Every time a run outputs some letter, its counter is incremented. At some
point we may guess that we output the mismatching value in one of the runs, in
which case we stop the counter corresponding to that run. We crucially also
need to be able to check later that the value output mismatches. In order to
do this we keep in memory a $2k+1$-type, always keeping the value which we
output. At some point we output the second mismatching position, we check that
the counters coincide and that the outputs are indeed different, which is
given by the $2k+1$-type. In parallel, we also have to check that we reach
some final configurations and that some configuration repeats. To do this we
need to keep one or two additional $2k$-type in memory, which again can easily
be done in PSpace.

The approach for continuity and uniform continuity is exactly the same except
that the patterns of Proposition 16 are slightly more involved. Moreover we
also need to decide on the fly that the configurations reached are co-
reachable. This can be done exactly like for non-emptiness of automata in
PSpace.

Finally, the PSpace lower bound is obtained by reducing from emptiness of
register automata over $(\mathbb{N},\\{=\\})$, which is PSpace-c [DL09]. Since
the data domains are countable, they can always simulate
$(\mathbb{N},\\{=\\})$, and the proofs of [EFR20] can easily be adapted: given
a NRA $A$ over $(\mathbb{N},\\{=\\})$, define a relation associating words of
the form $w\\#x$ with $w\in L(A)$ and $x\in\mathcal{D}^{\omega}$ to all
elements of $\mathcal{D}^{\omega}$; it is functional if and only if its domain
is empty. Similarly, given some non-continuous function $g$ defined by some
NRT, define the function $w\\#x\mapsto g(x)$ for all $w\in L(A)$ and
$x\in\mathcal{D}^{\omega}$. Again, it is continuous iff it is empty; similarly
for uniform continuity.

Thus, given a specification represented as a NRT over a representable and
decidable domain, one can examine whether it can be implemented (provided it
is functional, which is then decidable) by checking whether it is computable.
Indeed, computability is the most liberal criterium for being realisable. The
notion of uniform computability then allows to refine this check, as for
functions that are uniformly computable, one can focus on implementations that
have a bounded lookahead. In the case of $(\mathbb{Q},\left\\{<\right\\})$, we
further get that both problems are PSpace-complete:

######  Theorem 22.

For relations given by NRT over $(\mathbb{Q},\left\\{<\right\\})$ deciding
functionality, continuity/computability and uniform continuity/uniform
computability are PSpace-complete.

######  Proof 3.10.

We only need to argue that $(\mathbb{Q},\left\\{<\right\\})$ is representable
and polynomially decidable. Clearly rational numbers are representable.
Moreover, since $(\mathbb{Q},\left\\{<\right\\})$ is homogeneous, it admits
quantifier elimination, which means that any $k$-type can be defined by a
formula polynomial in $k$ (actually linear). Indeed a type is just given by
the linear order between the free variables. Moreover, satisfiability of
first-order logic over $(\mathbb{Q},\left\\{<\right\\})$ is in PSpace.

Note that the same reasoning applies for $(\mathbb{N},\left\\{=\right\\})$;
the case of $(\mathbb{N},\left\\{=\right\\})$ can also be obtained by encoding
it in $(\mathbb{Q},\left\\{<\right\\})$.

##  4 A non oligomorphic case: $(\mathbb{N},\\{<,0\\})$A non oligomorphic
case: (N,{¡,0})

We now turn to the study of the case of natural numbers equipped with the
usual order. This domain is not oligomorphic (cf Example 1.1), so there might
not exist loops in the transducer, as there are infinitely many orbits of
configurations. For simplicity, in the rest of this section,
$(\mathbb{N},\\{<,0\\})$ and $(\mathbb{Q}_{+},\\{<,0\\})$ (where
$\mathbb{Q}_{+}$ is the set of rational numbers which are greater than or
equal to $0$) are respectively denoted $\mathbb{N}$ and $\mathbb{Q}_{+}$. We
thus need to study more precisely which paths are iterable, i.e. can be
repeated unboundedly or infinitely many times. We show that such property only
depends on the relative order between the registers, i.e. on the type of the
configurations, seen as belonging to $\mathbb{Q}_{+}$, where the type of a
configuration is an FO-formula describing its orbit (cf Proposition 17 and
Section 4.2). More generally, the fact that $\mathbb{N}$ is a subdomain of
$\mathbb{Q}_{+}$, along with the property that any finite run in
$\mathbb{Q}_{+}$ corresponds to a run in $\mathbb{N}$ (by multiplying all
involved data values by the product of their denominator), allows us to
provide a characterisation of continuity and uniform continuity which yields a
PSpace decision procedure for those properties.

###  4.1 On loop iteration

$0$$1$$\top,\downarrow{}r$$*<r,\downarrow{}r$

$0$$1$$?r_{M}$$r<*<r_{M},\downarrow{}r$

The NRA of Example 4.1 is non-empty in $\mathbb{Q}_{+}$, since it accepts e.g.
the word $1\cdot\dfrac{1}{2}\cdots\dfrac{1}{n}\cdots$. However, it is empty in
$\mathbb{N}$. Indeed, any data word compatible with its only infinite run
necessarily forms an infinite descending chain, which is impossible in
$\mathbb{N}$. Similarly, in Example 4.1, the NRA initially guesses some upper
bound $B$ which it stores in $r_{M}$, and then asks to see an infinite
increasing chain which is bounded from above by $B$. This is possible in
$\mathbb{Q}_{+}$, but not in $\mathbb{N}$.

That is why we need to study more closely what makes a given path _$\omega$
-iterable_, i.e. that can be taken an infinite number of times. To
characterise continuity, we will also need the weaker notion of _iterable_
path, i.e. of a path that can be taken arbitarily many times over finite
inputs which are increasing for the prefix order. For instance, the loop in
Example 4.1 is not iterable: the first letter in the input sets a bound on the
number of times it can be taken. The loop in Example 4.1 is iterable: it
suffices to guess bigger and bigger values of the initial upper bound.
However, there can be no infinite run which contains infinitely many
occurrences of such loop, as the value that is initially guessed for a given
run sets a bound on the number of times the loop can be taken, so it is not
$\omega$-iterable.

We show that the notions of iterability and $\omega$-iterability are both
characterised by properties on the order between registers of a pair of
configurations, which can be summed up into a type, hence opening the way to
deciding such properties.

###  4.2 $\mathbb{Q}$-typesQ-types

In our study, the relative order between registers plays a key role. Such
information is summed up by the type of the configuration, interpreted as a
configuration in $\mathbb{Q}_{+}$.

Since we will need to manipulate different types of copies of some set of
registers, we adopt the following convention: In the following, we assume that
for a set of registers $R$, $R_{1}$ and $R_{2}$ are two disjoint copies of
$R$, whose elements are respectively $r_{1}$ and $r_{2}$ for $r\in R$.
Similarly, $R^{\prime}$ is a primed copy of $R$, whose elements are
$r^{\prime}$ for $r\in R$. Note that the two can be combined to get
$R_{1}^{\prime},R_{2}^{\prime}$. Note also that primes and indices are also
used as usual notations, but no ambiguity should arise.

For a register valuation $\bar{d}:R\rightarrow\mathbb{N}$, we define
$\tau(\bar{d})$ as $\tau_{\mathbb{Q}_{+}}(\bar{d})$ the type of the valuation
in $\mathbb{Q}_{+}$, i.e. an FO-formula describing its orbit (such an FO-
formula exists by Proposition 17 since $\mathbb{Q}_{+}$ is oligomorphic). Note
that such type can be represented e.g. by the formula
$\bigwedge_{\bowtie\in\\{<,>,=\\}}\bigwedge_{r,r^{\prime}\in
R\mid\bar{d}(r)\bowtie\bar{d}(r^{\prime})}r\bowtie
r^{\prime}\wedge\bigwedge_{r\in R\mid\bar{d}(r)=0}r=0$. We extend the notion
to configurations $(p,\bar{d})\in Q\times\mathbb{N}^{R}$ by letting
$\tau((p,\bar{d}))=(p,\tau(\bar{d}))$. Thus, the type specifies the current
state, and summarises the information of the order between registers, as well
as whether they are equal to $0$ or not.

We will also need to have access to the relative order between registers of
two configurations. Thus, for two register valuations
$\bar{d}_{1},\bar{d}_{2}:R\rightarrow\mathbb{N}$, we define
$\sigma(\bar{d}_{1},\bar{d}_{2})=\tau_{\mathbb{Q}_{+}}(\bar{d}_{1}\uplus\bar{d}_{2}^{\prime})$,
where $\bar{d}_{1}\uplus\bar{d}_{2}^{\prime}$ is the disjoint union of
$\bar{d}_{1}$ and of a primed copy of $\bar{d}_{2}$, so that the registers of
$\bar{d}_{2}$ can be distinguished from those of $\bar{d}_{1}$. We then have,
for all registers $r,s\in R$ and all relations $\bowtie\in\\{<,>,=\\}$ that
$\sigma(\bar{d}_{1},\bar{d}_{2})\Rightarrow r\bowtie s^{\prime}$ if and only
if $\bar{d}_{1}(r)\bowtie\bar{d}_{2}(s)$. Again, the definition is naturally
lifted to configurations by letting
$\sigma((p,\bar{d}_{1}),(q,\bar{d}_{2}))=(p,q,\sigma(\bar{d}_{1},\bar{d}_{2}))$.

######  Remark 23.

Recall that by definition of an orbit, we have that for any register
valuations $\bar{d}_{1}$ and $\bar{d}_{2}$ such that
$\tau(\bar{d}_{1})=\tau(\bar{d}_{2})$, there exists an automorphism
$\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$ such that $\mu(\bar{d}_{1})=\bar{d}_{2}$.

The core property is the following:

Let $R$ be a set of registers, and let $\sigma$ be a $\mathbb{Q}$-type defined
over $R\uplus R^{\prime}$, where $R^{\prime}$ is a primed copy of $R$. We say
that $\sigma$ has the property $\star$ for the set of registers $X\subseteq R$
if:

  * •

for all $r\in X$, $\sigma\Rightarrow r\leq r^{\prime}$

  * •

for all $r,s\in X$, if $\sigma\Rightarrow s=s^{\prime}$ and $\sigma\Rightarrow
r\leq s$, then $\sigma\Rightarrow r=r^{\prime}$

By extension, for two configurations $C$ and $C^{\prime}$ over $R$, we say
that $C$ and $C^{\prime}$ have the property $\star$ for the set of registers
$X\subseteq R$ if $\sigma(C,C^{\prime})$ has the $\star$ property for $X$.

Finally, when $X=R$, we simply state that $\sigma$ has the $\star$ property.

Such property ensures, for the considered subset of registers, that they
cannot induce infinite descending chains nor infinite bounded increasing
chains (as both are not feasible in $\mathbb{N}$), if a run loops over
configurations whose pairwise type is $\sigma$.

###  4.3 Relations between machines over $\mathbb{N}$ and over
$\mathbb{Q}_{+}$Relations between machines over N and Q+

There is a tight relation between machines operating over $\mathbb{N}$ and
over $\mathbb{Q}_{+}$. First, since $\mathbb{N}$ is a subdomain of
$\mathbb{Q}_{+}$, runs in $\mathbb{N}$ are also runs in $\mathbb{Q}_{+}$. Over
finite runs, by multiplying all data values by the product of their
denominators, we can get the converse property.

######  Proposition 24.

Let $X\subset_{f}\mathbb{Q}_{+}$ be a finite subset of $\mathbb{Q}_{+}$. There
exists an automorphism $\lambda\in\mathrm{Aut}(\mathbb{Q}_{+})$ such that
$\lambda(X)\subset\mathbb{N}$, $\lambda(\mathbb{N})\subseteq\mathbb{N}$ and
$\lambda$ is non-contracting, i.e. for all $x,y\in\mathbb{Q}_{+}$,
$\lvert\lambda(x)-\lambda(y)\rvert\geq\lvert x-y\rvert$.

######  Proof 4.1.

By writing $X=\left\\{\frac{p_{1}}{q_{1}},\dots,\frac{p_{n}}{q_{n}}\right\\}$,
let $K=\prod_{i}q_{i}$. Then $\lambda:d\mapsto Kd$ is an automorphism
satisfying the required properties.

We then get the following:

######  Proposition 25.

Let $A$ be a NRA over $\mathbb{Q}_{+}$, and let $\nu$ and $\nu^{\prime}$ be
$\mathbb{Q}$-types.

If there exist two configurations
$C=(p,\bar{d}),C^{\prime}=(q,\bar{d}^{\prime})$ where
$\bar{d},\bar{d}^{\prime}:R\rightarrow\mathbb{Q}_{+}$ are such that
$\tau(\bar{d})=\nu$, $\tau(\bar{d}^{\prime})=\nu^{\prime}$ and if there exists
a data word $v\in\mathbb{Q}_{+}^{*}$ such that $C\xrightarrow{u}C^{\prime}$,
then there also exist two configurations $D=(p,\bar{e})$,
$D^{\prime}=(q,\bar{e}^{\prime})$ and a data word $w$ which satisfy the same
properties, i.e. $\tau(D)=\nu$, $\tau(D^{\prime})=\nu^{\prime}$ and
$D\xrightarrow{w}D^{\prime}$; and which belong to $\mathbb{N}$, i.e. such that
$\bar{e},\bar{e}^{\prime}:R\rightarrow\mathbb{N}$ and $w\in\mathbb{N}^{*}$.

######  Proof 4.2.

Let $A$ be a NRA over $\mathbb{Q}_{+}$, and assume that
$C\xrightarrow{u}C^{\prime}$. By applying Proposition 24 to $X=C(R)\cup
C^{\prime}(R)\cup\mathsf{data(u)}$ (states do not play a role here), we get
that $\lambda(C)\xrightarrow{\lambda(u)}\lambda(C^{\prime})$ is also a run of
$A$, and $D=\lambda(C)$, $D^{\prime}=\lambda(C^{\prime})$ and $w=\lambda(u)$
satisfy the required properties.

######  Remark 26.

As a corollary, we obtain that for any NRA $A$ over finite words,
$L_{\mathbb{N}}(A)\neq\varnothing$ if and only if
$L_{\mathbb{Q}_{+}}(A)\neq\varnothing$.

Note that such property does not hold over infinite runs, as witnessed by
Examples 4.1 and 4.1. The property $\star$ ensures that a loop can be iterated
in $\mathbb{N}$, as shown in the next key proposition:

######  Proposition 27.

Let $T$ be an NRT and assume that $B\xrightarrow{u}B^{\prime}$ following some
sequence of transitions $\pi$, where $\tau(B)=\tau(B^{\prime})$,
$u\in\mathbb{Q}_{+}^{*}$ and $B$ and $B^{\prime}$ have the property $\star$.
Then there exists an infinite run $D\xrightarrow{x}$ over the sequence of
transitions $\pi^{\omega}$, with $x\in\mathbb{N}^{\omega}$ and
$\tau(D)=\tau(B)$.

Before showing this proposition, let us introduce some intermediate notions:
Let $\bar{d},\bar{d}^{\prime}$ be two register valuations over
$\mathbb{Q}_{+}$ such that $\tau(\bar{d})=\tau(\bar{d}^{\prime})$. We say that
$\bar{d}^{\prime}$ is _wider_ than $\bar{d}$ whenever for any $r,s\in R$, we
have:

  * •

$\lvert\bar{d}^{\prime}(s)-\bar{d}^{\prime}(r)\rvert\geq\lvert\bar{d}(s)-\bar{d}(r)\rvert$

  * •

$\bar{d}^{\prime}(r)\geq\bar{d}(r)$

Note that the second item of the definition is required to ensure that the
interval between $\bar{d}^{\prime}(r)$ and $0$ is also wider than the interval
between $\bar{d}(r)$ and $0$.

The notion is extended to configurations by saying that
$C^{\prime}=(p^{\prime},\bar{d}^{\prime})$ is wider than $C=(p,\bar{d})$ if
$\bar{d}^{\prime}$ is wider than $\bar{d}$. In the following, we only apply
this notion to configurations $C$ and $C^{\prime}$ that have the same state,
i.e. $p=p^{\prime}$.

######  Proposition 28.

Let $\sigma$ be a type over $R\uplus R^{\prime}$ such that $\sigma_{\mid
R}=\sigma_{\mid R^{\prime}}$. If $\sigma$ has the $\star$ property, then there
exist two register valuations $\bar{d}$ and $\bar{d}^{\prime}$ in $\mathbb{N}$
such that $\sigma(\bar{d},\bar{d}^{\prime})=\sigma$ and such that
$\bar{d}^{\prime}$ is wider than $\bar{d}$.

######  Proof 4.3.

First, assume that there exists some register $r_{0}\in R$ such that
$\sigma\Rightarrow r_{0}=0$ (thus $\sigma\Rightarrow r_{0}^{\prime}=0$, since
we assumed that $\sigma_{\mid R}=\sigma_{\mid R^{\prime}}$). If this is not
the case, consider instead the type $\sigma_{0}=\sigma\wedge r_{0}=0\wedge
r^{\prime}_{0}=0$ over $R\uplus\\{r_{0}\\}$. Indeed, if $\bar{d}$ and
$\bar{d}^{\prime}$ are two valuations in $\mathbb{N}$ such that
$\sigma(\bar{d},\bar{d}^{\prime})=\sigma_{0}$ and $\bar{d}^{\prime}$ is wider
than $\bar{d}^{\prime}$, then $\bar{d}_{\mid R}$ and $\bar{d}^{\prime}_{\mid
R}$ are two valuations in $\mathbb{N}$ such that
$\sigma(\bar{d},\bar{d}^{\prime})=\sigma$ and $\bar{d}^{\prime}_{\mid R}$ is
wider than $\bar{d}_{\mid R}$.

Now, for a pair of valuations $(\bar{d},\bar{d}^{\prime})$, define its
shrinking intervals:
$S(\bar{d},\bar{d}^{\prime})=\\{(r,s)\mid\lvert\bar{d}^{\prime}(s)-\bar{d}^{\prime}(r)\rvert<\lvert\bar{d}(s)-\bar{d}(r)\rvert\\}$,
and say that $(\bar{d},\bar{d}^{\prime})$ has $k=\lvert
S(\bar{d},\bar{d}^{\prime})\rvert$ shrinking intervals. We need to show that
given a pair of valuations $\bar{e}$ and $\bar{e}^{\prime}$ such that
$\sigma(\bar{e},\bar{e}^{\prime})=\sigma$, if they have $k>0$ intervals that
shrink, we can exhibit a pair of valuations $\bar{d}$ and $\bar{d}^{\prime}$
such that $\sigma(\bar{d},\bar{d}^{\prime})=\sigma$ and which has $l<k$
intervals that shrink.

Thus, let $\bar{e}$ and $\bar{e}^{\prime}$ be two valuations such that
$\sigma(\bar{e},\bar{e}^{\prime})=\sigma$ and which have $k>0$ shrinking
intervals. Then, let $(r,s)\in S(\bar{e},\bar{e}^{\prime})$; w.l.o.g. assume
that $\bar{e}^{\prime}(s)\geq\bar{e}^{\prime}(r)$. As $\bar{e}$ and
$\bar{e}^{\prime}$ have the same type, we get $\bar{e}(s)\geq\bar{e}(r)$.
Moreover, as $(r,s)\in S$, $\bar{e}(s)\neq\bar{e}(r)$, so
$\bar{e}(s)>\bar{e}(r)$, which implies
$\bar{e}^{\prime}(s)>\bar{e}^{\prime}(r)$. Finally, we have that
$\bar{e}^{\prime}(s)>\bar{e}(s)$. Indeed, since $\sigma$ has the $\star$
property, we have that $\bar{e}^{\prime}(s)\geq\bar{e}(s)$, and moreover if we
had $\bar{e}^{\prime}(s)=\bar{e}(s)$, we would get that
$\bar{e}(r)=\bar{e}^{\prime}(r)$ as $\bar{e}(r)\leq\bar{e}(s)$, which would
mean that $(r,s)\notin S(\bar{e},\bar{e}^{\prime})$.

Finally, let $M=\max\left(\\{\bar{e}(t)\mid t\in
R,\bar{e}(t)<\bar{e}^{\prime}(s)\\}\cup\\{\bar{e}^{\prime}(t)\mid t\in
R,\bar{e}^{\prime}(t)<\bar{e}^{\prime}(s)\\}\right)$ be the maximum value seen
in $\bar{e}$ and $\bar{e}^{\prime}$ which is lower than $\bar{e}^{\prime}(s)$.
Note that we have $M\geq\bar{e}(r)$, $M\geq\bar{e}^{\prime}(r)$ and
$M\geq\bar{e}(s)$.

Now, let
$c=\big{(}\bar{e}(s)-\bar{e}(r)\big{)}-\big{(}\bar{e}^{\prime}(s)-\bar{e}^{\prime}(r)\big{)}$.
As $(r,s)\in S$, $c>0$. Then, consider the automorphism
$\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$ defined as
$\left\\{\begin{array}[]{l}x\in[0;M]\mapsto x\\\
x\in]M;\bar{e}^{\prime}(s)]\mapsto
M+\frac{\bar{e}^{\prime}(s)+c-M}{\bar{e}^{\prime}(s)-M}(x-M)\\\
x\in]\bar{e}^{\prime}(s);+\infty[\mapsto x+c\end{array}\right.$

It can be checked that for all $x,y\in\mathbb{Q}_{+}$,
$\lvert\mu(y)-\mu(x)\rvert\geq\lvert y-x\rvert$, so $\lvert
S(\mu(\bar{e}),\mu(\bar{e}^{\prime}))\rvert\leq\lvert
S(\bar{e},\bar{e}^{\prime})\rvert$. Now, we have that $(r,s)\notin
S(\mu(\bar{e}),\mu(\bar{e}^{\prime}))$. Indeed, $\mu(\bar{e}(s))=\bar{e}(s)$,
$\mu(\bar{e}(r))=\bar{e}(r)$ and
$\mu(\bar{e}^{\prime}(r))=\bar{e}^{\prime}(r)$ since
$\bar{e}(s),\bar{e}(r),\bar{e}^{\prime}(r)\in[0;M]$. Finally,
$\mu(\bar{e}^{\prime}(s))=\bar{e}^{\prime}(s)+c$. Overall, we get that
$\big{(}\mu(\bar{e}(s))-\mu(\bar{e}(r))\big{)}-\big{(}\mu(\bar{e}^{\prime}(s))-\mu(\bar{e}^{\prime}(r))\big{)}=\big{(}\bar{e}(s)-\bar{e}(r)\big{)}-\big{(}\bar{e}^{\prime}(s)+c-\bar{e}^{\prime}(r)\big{)}=c-c=0$,
which means that
$\lvert\bar{e}^{\prime}(s)-\bar{e}^{\prime}(r)\rvert=\lvert\bar{e}(s)-\bar{e}(r)\rvert$,
so $(r,s)\notin S(\mu(\bar{e}),\mu(\bar{e}^{\prime}))$: $\lvert
S(\mu(\bar{e}),\mu(\bar{e}^{\prime}))\rvert<\lvert
S(\bar{e},\bar{e}^{\prime})\rvert$.

Since $\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$, we get that
$(\mu(\bar{e}),\mu(\bar{e}^{\prime}))$ is such that
$\sigma(\mu(\bar{e}),\mu(\bar{e}^{\prime}))=\sigma$, so we exhibited a pair of
valuations which has $l<k$ intervals that shrink.

By iteratively applying this process to $(\bar{e},\bar{e}^{\prime})$ until no
shrinking intervals remain, we get a pair $(\bar{d},\bar{d}^{\prime})$ which
is such that $\sigma(\bar{d},\bar{d}^{\prime})=\sigma$ and $\bar{d}^{\prime}$
is wider than $\bar{d}$. Now, by multiplying all data values in $\bar{d}$ and
$\bar{d}^{\prime}$ by the product of their denominators, we get two valuations
$\bar{f}$ and $\bar{f}^{\prime}$ which are in $\mathbb{N}$ such that
$\sigma(\bar{f},\bar{f}^{\prime})=\sigma$ and $\bar{f}^{\prime}$ is wider than
$\bar{f}$.

We finally need the following technical result:

######  Proposition 29.

Let $\bar{d}$ and $\bar{d}^{\prime}$ be two configurations in $\mathbb{N}$
such that $\bar{d}^{\prime}$ is wider than $\bar{d}$. Then, there exists some
automorphism $\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$ such that
$\bar{d}^{\prime}=\mu(\bar{d})$ and $\mu(\mathbb{N})\subseteq\mathbb{N}$.

######  Proof 4.4.

Let $\\{a_{0},\dots,a_{k}\\}=\bar{d}(R)\cup\\{0\\}$ and
$\\{a^{\prime}_{0},\dots,a^{\prime}_{k}\\}=\bar{d}^{\prime}(R)\cup\\{0\\}$,
with $0=a_{0}<\dots<a_{k}$ and $a^{\prime}_{0}<\dots<a^{\prime}_{k}$. Note
that since $\tau(\bar{d})=\tau(\bar{d}^{\prime})$, we indeed have that
$\lvert\bar{d}(R)\cup\\{0\\}\rvert=\lvert\bar{d}^{\prime}(R)\cup\\{0\\}\rvert$;
moreover, since $\bar{d}^{\prime}$ is wider than $\bar{d}$, we have that for
all $0\leq i<k$, $a^{\prime}_{i+1}-a^{\prime}_{i}>a_{i+1}-a_{i}$. Consider the
following easy lemma (the proof is in Appendix B for completeness):

######  Lemma 30.

Let $a,b,c,d\in\mathbb{N}$ be such that $a<b$, $c<d$ and $d-c\geq b-a$. Then,
there exists a function $f:[a;b]\rightarrow[c;d]$ which is increasing and
bijective, and such that $f([a;b]\cap\mathbb{N})\subseteq\mathbb{N}$.

Then, apply it to each interval $[a_{i};a_{i+1}]$ to get a family of
increasing and bijective functions $(\mu_{i})_{0\leq i<k}$ which are such that
$\mu_{i}([a_{i};a_{i+1}])=[a^{\prime}_{i};a^{\prime}_{i+1}]$ and
$\mu([a_{i};a_{i+1}]\cap\mathbb{N})\subseteq\mathbb{N}$. Then, let
$\mu_{k}:x\in[a_{k};+\infty[\mapsto x+a^{\prime}_{k}-a_{k}$. We get that
$\mu=\cup_{0\leq i\leq k}\mu_{i}\in\mathrm{Aut}(\mathbb{Q}_{+})$ is such that
$\bar{d}^{\prime}=\mu(\bar{d})$ and satisfies
$\mu(\mathbb{N})\subseteq\mathbb{N}$.

We are now ready to prove Proposition 27:

######  Proof 4.5 (Proof of Proposition 27).

Let $T$ be an NRT and assume that $B\xrightarrow[\pi]{u}B^{\prime}$ following
some sequence of transitions $\pi$, where $\tau(B)=\tau(B^{\prime})$,
$u\in\mathbb{Q}_{+}^{*}$ and $B$ and $B^{\prime}$ have the property $\star$.

Let $\sigma=\sigma(B,B^{\prime})$. By Proposition 28, we know that there exist
two configurations $C$ and $C^{\prime}$ in $\mathbb{N}$ such that
$\sigma(C,C^{\prime})=\sigma$ and $C^{\prime}$ is wider than $C$. Let
$\nu\in\mathrm{Aut}(\mathbb{Q}_{+})$ be some automorphism such that $\nu(B)=C$
and $\nu(B^{\prime})=C^{\prime}$ (such an automorphism exists since
$\sigma(B,B^{\prime})=\sigma(C,C^{\prime})$). Then, we have that
$C\xrightarrow[\pi]{\nu(u)}C^{\prime}$. By multiplying all involved data
values by their common denominator (cf Propostion 24), we get two
configurations $D$ and $D^{\prime}$, along with some data word $v$, all
belonging to $\mathbb{N}$, such that $D\xrightarrow[\pi]{v}D^{\prime}$, and
such that $D^{\prime}$ is wider than $D$. By Proposition 29, there exists an
automorphism $\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$ such that
$\mu(D)=D^{\prime}$ and $\mu(\mathbb{N})\subseteq\mathbb{N}$. Thus, by letting
$x=v\mu(v)\mu^{2}(v)\dots$, we get that
$D\xrightarrow[\pi]{v}\mu(D)\xrightarrow[\pi]{\mu(v)}\mu^{2}(D)\dots$ is a run
over $x\in\mathbb{N}^{\omega}$ over the sequence of transitions
$\pi^{\omega}$, and $\tau(D)=\tau(B)$.

A last important property is the following:

######  Proposition 31.

Let $A$ be a NRA over $\mathbb{Q}_{+}$, and assume that
$C\xrightarrow{u}C^{\prime}$ and that $C^{\prime\prime}\xrightarrow{v}$, where
$\tau(C^{\prime})=\tau(C^{\prime\prime})$, $u\in\mathbb{Q}_{+}^{*}$ and
$v\in\mathbb{N}^{\omega}$. Then there exist $w\in\mathbb{N}^{*}$,
$x\in\mathbb{N}^{\omega}$ and two configurations $D,D^{\prime}$ whose
valuations take their values in $\mathbb{N}$ such that
$D\xrightarrow{w}D^{\prime}\xrightarrow{x}$, $\tau(C)=\tau(D)$ and
$\tau(C^{\prime})=\tau(D^{\prime})$.

######  Proof 4.6.

Since $\tau(C^{\prime})=\tau(C^{\prime\prime})$, there exists some
$\mu\in\mathrm{Aut}(\mathbb{Q}_{+})$ such that
$\mu(C^{\prime})=C^{\prime\prime}$, thus
$\mu(C)\xrightarrow{\mu(u)}C^{\prime\prime}$. Now, by applying Proposition 24
to $X=(\mu(C))(R)\cup C^{\prime\prime}(R)\cup\mathsf{data}(\mu(u))$, we get
that
$\lambda(\mu(C))\xrightarrow{\lambda(\mu(u))}\lambda(C^{\prime\prime})\xrightarrow{\lambda(v)}$
satisfies the required property.

###  4.4 Emptiness of automata

######  Proposition 32 (Non-emptiness).

Let $A$ be an NRA over $\mathbb{N}^{\omega}$. The following are equivalent:

  1. 1.

$L(A)$ is non-empty

  2. 2.

there exist two runs whose input words belong to $\mathbb{Q}_{+}^{*}$, which
are as follows:

    1. (a)

$C_{0}\xrightarrow{u}C$

    2. (b)

$D\xrightarrow{v}D^{\prime}$ with $\tau(D)=\tau(D^{\prime})=\tau(C)$, $D$ is a
final configuration, and $\sigma=\sigma(D,D^{\prime})$ satisfies $\star$
property.

######  Proof 4.7.

Assume $(2)$ holds. The result easily follows from Propositions 25, 27 and 31.

Assume now that $L(A)$ is non-empty. Let
$\rho=C_{0}\xrightarrow{d_{0}}C_{1}\xrightarrow{d_{1}}C_{2}\dots$ be an
accepting run over input $x=d_{0}d_{1}\dots$ in $A$ (where
$C_{0}=(q_{0},\overline{0})$). For each $i\geq 0$, let $\nu_{i}=\tau(C_{i})$.
As $\rho$ is acccepting and there are only finitely many types, we get that
there exists some type $\nu$ such that the state is accepting and
$(q_{i},\nu_{i})=(q,\nu)$ for infinitely many $i\in\mathbb{N}$. Let
$(C_{j})_{j\in\mathbb{N}}$ be an infinite subsequence of $C_{i}$ such that for
all $j$, $\tau(C_{j})=\nu$. Now, colour the set of unordered pairs as follows:
$c\left(\left\\{\tau(C_{j}),\tau(C_{k})\right\\}\right)=\sigma(C_{j},C_{k})$
(where we assume w.l.o.g. that $j<k$). By Ramsey’s theorem, there is an
infinite subset such that all pairs have the same colour $\sigma$. Let
$(C_{k})_{k\in\mathbb{N}}$ be an infinite subsequence such that for all $j<k$,
$\sigma(C_{j},C_{k})=\sigma$. Now, assume that $\sigma$ breaks the $\star$
property. There are two cases:

  * •

There exists some $r$ such that $\sigma\Rightarrow r>r^{\prime}$. Then, it
means that for all $j<k$, $C_{j}(r)>C_{k}(r)$. In particular, this means that
$C_{0}(r)>C_{1}(r)>\dots>C_{n}(r)\dots$, which yields an infinite descending
chain in $\mathbb{N}$, and leads to a contradiction.

  * •

There exists some $s$ such that $\sigma\Rightarrow s=s^{\prime}$ and some $r$
which satisfies $\sigma\Rightarrow r<s$ and $\sigma\not\Rightarrow
r=r^{\prime}$. If $\sigma\Rightarrow r>r^{\prime}$, we are back to the first
case. Otherwise, it means $\sigma\Rightarrow r<r^{\prime}$. Then, on the one
hand, $C_{0}(r)<C_{1}(r)<\dots<C_{n}(r)<\dots$. On the other hand,
$C_{0}(s)=C_{1}(s)=\dots=C_{n}(s)=\dots$. But we also have that for all
$k\in\mathbb{N},C_{k}(r)<C_{k}(s)=C_{0}(s)$. Overall, we get an infinite
increasing chain which is bounded from above by $C_{0}(s)$, which again leads
to a contradiction.

Thus, $\sigma$ satisfies the $\star$ property. So, this is in particular the
case for some pair of configurations $C=D=C_{k}$ and
$D^{\prime}=C_{k^{\prime}}$ for some $k<k^{\prime}$ taken from the last
extracted subsequence. Such configurations are such that (recall that the
$C_{k}$ are configurations of an accepting run over some input, which is in
particular initial):

  1. [(a)]

  2. 1.

$C_{0}\xrightarrow{u}C$

  3. 2.

$D\xrightarrow{v}D^{\prime}$.

Moreover, $\tau(D)=\tau(D^{\prime})=\tau(C)$ and $D$ is final, by definition
of $(C_{k})_{k\in\mathbb{N}}$.

######  Corollary 33.

Emptiness for NRA over $\mathbb{N}^{\omega}$ is decidable in PSpace.

######  Proof 4.8.

The algorithm is similar to the one for deciding non-emptiness for NRA over
oligomorphic domains. Indeed, the sought witness lies in $\mathbb{Q}_{+}$,
which is oligomorphic; it suffices to additionally check that the pairwise
type of $D$ and $D^{\prime}$ satisfies the star property. Thus, the algorithm
initially guesses $\tau(C)$ and $\sigma$. Then, checking that there indeed
exists a configuration whose type is $\tau(C)$ and that can be reached from
$C_{0}$ (item 2a of Propostion 32) can be done in the same way as for Theorem
21, by simulating symbolically (i.e. over $\mathbb{Q}$-types) a run of the
automaton. Now, for item 2b, the algorithm again symbolically simulates a run
from $D$, by keeping track of the type of the current configuration
$\tau(D^{\prime})$, and additionally of the pairwise type
$\sigma(D,D^{\prime})$. Since $\sigma(D,D^{\prime})$ is a $\mathbb{Q}$-type
over $2\lvert R\rvert$ registers, it can be stored in polynomial space;
moreover, given a transition test $\phi$, it can also be updated in polynomial
space.

###  4.5 Functionality

Following the study of the relationships between $\mathbb{N}$ and
$\mathbb{Q}$, we are now ready to provide a characterization of non
functionality over $\mathbb{N}$. Intuitively, it amounts to finding two pairs
of runs whose inputs are in $\mathbb{Q}$: first, a prefix witnessing a
mismatch, and second, an accepting loop satisfying the $\star$ property to
ensure its iterability over $\mathbb{N}$.

######  Proposition 34 (Functionality).

Let $R\subseteq\mathbb{N}^{\omega}\times\mathbb{N}^{\omega}$ be given by an
NRT $T$. The following are equivalent:

  1. 1.

$R$ is not functional

  2. 2.

there exist two pairs of runs whose input words belong to
$\mathbb{Q}_{+}^{*}$, which are as follows:

    1. (a)

$C_{0}\xrightarrow{u|u_{1}}C_{1}$ and $C_{0}\xrightarrow{u|u_{2}}C_{2}$ with
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$,

    2. (b)

$D_{1}\xrightarrow{v}D^{\prime}_{1}$ and $D_{2}\xrightarrow{v}D^{\prime}_{2}$
with $\tau(D_{1}\uplus D_{2})=\tau(D^{\prime}_{1}\uplus
D_{2})=\tau(C_{1}\uplus C_{2})$, both runs visit a final state of $T$, and
$\sigma_{i}=\tau((D_{1}\uplus D_{2})\uplus(D^{\prime}_{1}\uplus
D^{\prime}_{2}))$ satisfies property $\star$.

######  Proof 4.9.

First, assume that (2) holds. By applying Proposition 27 to the product
transducer $T\times T$, there exist two configurations $E_{1}$ and $E_{2}$ and
an infinite data word $x\in\mathbb{N}^{\omega}$ such that
$E_{1}\xrightarrow{x\mid y_{1}}$ and $E_{2}\xrightarrow{x\mid y_{2}}$.
Moreover, both runs are accepting as each finite run is required to visit a
final state of $T$.

Now, since $\tau(E_{1}\uplus E_{2})=\tau(D_{1}\uplus D_{2})=\tau(C_{1}\uplus
C_{2})$, we can apply Proposition 31 to get two runs
$C_{0}\xrightarrow{u^{\prime}\mid
u^{\prime}_{1}}F_{1}\xrightarrow{x^{\prime}\mid y_{1}^{\prime}}$ and
$C_{0}\xrightarrow{u^{\prime}\mid
u^{\prime}_{2}}F_{2}\xrightarrow{x^{\prime}\mid y_{2}^{\prime}}$. Moreover,
since automorphisms preserve mismatches, we know that
$u^{\prime}_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u^{\prime}_{2}$.
Thus, we obtained a witness of non-functionality, since we have
$(u^{\prime}x,u^{\prime}_{1}y_{1}^{\prime}),(u^{\prime}x,u^{\prime}_{2}y_{2}^{\prime})\in
T$, with $u^{\prime}_{1}y_{1}^{\prime}\neq u^{\prime}_{2}y_{2}^{\prime}$ since
$u^{\prime}_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u^{\prime}_{2}$.

We now assume that $R$ is not functional. By definition, and as we assume $R$
only contains infinite output words, there are two runs on some input word $x$
whose outputs mismatch. By splitting both runs after the first mismatch, we
get two runs $C_{0}\xrightarrow{t\mid t_{1}}B_{1}\xrightarrow{w\mid y}$ and
$C_{0}\xrightarrow{t\mid t_{2}}B_{2}\xrightarrow{w\mid z}$ with
$t_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}t_{2}$ (note
that we do not necessarily have that $y=z$). Now, from the product transducer
$T\times T$, one can define an NRA $A$ with registers $R\uplus R^{\prime}$
recognising the language $L(A)=\left\\{w^{\prime}\mid
E_{1}\xrightarrow[T]{w^{\prime}\mid
y^{\prime}},E_{2}\xrightarrow[T]{w^{\prime}\mid z^{\prime}}\text{ and
}\tau(E_{1}\uplus E_{2})=\tau(B_{1}\uplus B_{2})\right\\}$ which starts by
guessing some configuration $E_{1}\uplus E_{2}$ and checks that
$\tau(E_{1}\uplus E_{2})=\tau(B_{1}\uplus B_{2})$, then simulates $T\times T$.
Such language is non-empty, since it at least contains $w$. By Proposition 32,
we get that there exist runs whose input words belong to $\mathbb{Q}_{+}^{*}$
which are $C_{0}\uplus C_{0}\xrightarrow{u^{\prime}}C_{1}\uplus C_{2}$ and
$D_{1}\uplus D_{2}\xrightarrow{v}D^{\prime}_{1}\uplus D^{\prime}_{2}$ with
$\tau(D_{1}\uplus D_{2})=\tau(D^{\prime}_{1}\uplus
D^{\prime}_{2})=\tau(C_{1}\uplus C_{2})$, $D_{1}$ and $D^{\prime}_{1}$ final
and $\sigma(D_{1}\uplus D_{2},D^{\prime}_{1}\uplus D^{\prime}_{2})$ satisfies
the $\star$ property, which immediately yields item 2b.

Since $C_{0}\uplus C_{0}\xrightarrow{u^{\prime}}C_{1}\uplus C_{2}$, by
definition of the considered NRA, we have that
$E_{1}\xrightarrow[T]{u^{\prime}\mid u^{\prime}_{1}}C_{1}$ and
$E_{2}\xrightarrow[T]{u^{\prime}\mid u^{\prime}_{2}}C_{2}$, with
$\tau(E_{1}\uplus E_{2})=\tau(B_{1}\uplus B_{2})$. Thus, by applying an
automorphism $\mu$ such that $\mu(B_{1})=E_{1}$, $\mu(B_{2})=E_{2}$, such runs
can be glued with the runs $C_{0}\xrightarrow{t\mid t_{1}}B_{1}$ and
$C_{0}\xrightarrow{t\mid t_{2}}B_{2}$ to yield two runs
$C_{0}\xrightarrow{u\mid u_{1}}C_{1}$ and $C_{0}\xrightarrow{u\mid
u_{2}}C_{2}$, with $u=\mu(t)u^{\prime}$ and $u_{1}=\mu(t_{1})u^{\prime}_{1}$,
$u_{2}=\mu(t_{2})u^{\prime}_{2}$, with
$u_{1}\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}u_{2}$ since
$\mu(t_{1})\mathrel{\centernot{\mathrel{{\hstretch{.8}{\parallel}}}}}\mu(t_{2})$
(recall that automorphisms preserve mismatches, since they are bijective), so
we get item 2a.

######  Corollary 35.

Functionality for relations over
$\mathbb{N}^{\omega}\times\mathbb{N}^{\omega}$ given by NRT is decidable in
PSpace.

######  Proof 4.10.

By Lemma 13, if item 2a holds, then we can assume that the length of $u$ is
bounded by $P(\mathcal{R}(4k),\lvert Q\rvert,L)$, where $\mathcal{R}$ denotes
the Ryll-Nardzewski function of $\mathbb{Q}_{+}$, which is exponential. Thus,
the existence of $u$ can be checked with a counter that is polynomially
bounded. Then, item 2b can be checked in polynomial space, since it reduces to
checking emptiness of the NRA $A$ that we described in the above proof.

###  4.6 Next-letter problem

We now show that for any function definable by an NRT over $\mathbb{N}$, the
next-letter problem is computable.

######  Lemma 36.

Let $f:\mathbb{N}^{\omega}\rightarrow\mathbb{N}^{\omega}$ be a function
defined by an NRT over $\mathbb{N}$. Then, its next-letter problem is
computable.

######  Proof 4.11.

The algorithm is in two phases:

  1. 1.

decide whether there exists a next letter

  2. 2.

if there exists a next letter, compute it

Recall that as input to the next-letter problem, there are two finite data
words $u,v\in\mathbb{N}^{*}$ and the goal is to decide whether there exists
some $d\in\mathbb{N}$ such that for all $uy\in\mathrm{dom}(f)$, $v\leq f(uy)$
implies $vd\leq f(uy)$. Let us assume that $f$ is defined by some NRT
$T=\left(Q,R,\Delta,q_{0},\overline{\mathsf{c}_{0}},F\right)$. Let us explain
how to algorithmically realize the two latter steps.

1\. To decide the existence of such a $d$, we reduce the problem to a
functionality problem for an NRT $T_{uv}$. First, let us define the
convolution $x_{1}\otimes x_{2}$ of two data words
$x_{1}=d_{1}d_{2}\dots,x_{2}=d^{\prime}_{1}d^{\prime}_{2}\dots\in\mathbb{N}^{\omega}$
as the data word $d_{1}d^{\prime}_{1}d_{2}d^{\prime}_{2}\dots$. The intuitive
idea is to construct $T_{uv}$ in such a way that it defines the relation
$R_{uv}=R_{uv}^{1}\cup R_{uv}^{2}$ defined by $R_{uv}^{i}=\\{(ux_{1}\otimes
ux_{2},vd^{\omega})\mid ux_{1},ux_{2}\in\mathrm{dom}(f),vd\preceq
f(ux_{i})\\}$. It is not difficult to see that $R_{uv}$ is a function iff the
next-letter has a positive answer for $u$ and $v$. Once $T_{uv}$ is
constructed, checking its functionality is possible thanks to Corollary 35.
Let us now explain how to construct $T_{uv}$. It is the union of two
transducers $T_{uv}^{1}$ and $T_{uv}^{2}$ defining $R_{uv}^{1}$ and
$R_{uv}^{2}$ respectively. The constructions are similar for both:
$T_{uv}^{1}$ ignores the even position of the input word after $u$ has been
read while $T_{uv}^{2}$ ignores the odd position after $u$ has been read, but
they otherwise are defined in the same way. Let us explain how to construct
$T_{uv}^{1}$. First, $T_{uv}^{1}$ makes sure that its input
$\alpha\otimes\beta$ is such that $u\leq\alpha$ and $u\leq\beta$, or
equivalently that $\alpha\otimes\beta=(u\otimes u)(x\otimes y)$ for some
$x,y$. This is possible by hardcoding $u$ in the transitions of $T$. Likewise,
$T_{uv}^{1}$ also makes sure that $v$ is a prefix of $f(ux)$. It is also
possible by hardcoding in $T$ the output $v$ (to check for instance that a run
of $T$ output the $i$th data value $d_{i}$ of $v$, it suffices when $T$
outputs a register $r$ on its transitions, to add the test $r=d_{i}$). So,
$T_{uv}^{1}$ simulates a run of $T$ on $ux$ (the odd positions of
$\alpha\otimes\beta$) and a run of $T$ on $uy$ (the even positions of
$\alpha\otimes\beta$). Once $v$ has been consumed by the simulated run on
$ux$, the first time this simulated run outputs something, the data value is
kept in a special register and outputted all the time by $T_{uv}^{1}$.

2\. If we know that there exists a next letter $d$, the only thing that
remains to be done is to compute it. To do so, we can again construct a
transducer $T^{\prime}_{uv}$ which simulates $T$ but makes sure to accept only
input words that start with $u$, accepted by runs which outputs words starting
with $v$. This can again be done by hardcoding $u$ and $v$ in $T$. Then, to
compute a data value $d$, it suffices to execute $T^{\prime}_{uv}$ by
computing, at any point $i$, all the configurations reached by
$T^{\prime}_{uv}$, and by keeping only those which are co-reachable. Testing
whether a configuration is co-reachable can be done by testing the non-
emptiness of an NRA starting in this initial configuration. Doing so, the
algorithm computes all prefixes of accepting runs. Eventually, since there
exists a next letter $d$, one of the run will output it.

As a direct corollary of Lemma 36, Theorem 10 and Theorem 9, we obtain:

######  Theorem 37.

Let $f:\mathbb{N}^{\omega}\rightarrow\mathbb{N}^{\omega}$ be a function
defined by an NRT over $\mathbb{N}$, and let
$m:\mathbb{N}\rightarrow\mathbb{N}$ be a total function. Then,

  1. 1.

$f$ is computable iff $f$ is continuous

  2. 2.

$f$ is uniformly computable iff $f$ is uniformly continuous

  3. 3.

$f$ is $m$-computable iff $f$ is $m$-continuous

###  4.7 Uniform continuity

We now turn to uniform continuity over $\mathbb{N}$, and show that it is
enough to consider uniform continuity over $\mathbb{Q}_{+}$ and restrict our
attention to configurations that are co-reachable w.r.t. data words over
$\mathbb{N}$.

Given a configuration $\mathbb{Q}$-type $\tau$, we say that it is co-reachable
in $\mathbb{N}$ if there is an actual configuration $C$ of type $\tau$ which