Synthesis of Computable Regular Functions of Infinite Words
Regular functions from infinite words to infinite words can be equivalently
specified by MSO-transducers, streaming $\omega$-string transducers as well as
deterministic two-way transducers with look-ahead. In their one-way
restriction, the latter transducers define the class of rational functions.
Even though regular functions are robustly characterised by several
finite-state devices, even the subclass of rational functions may contain
functions which are not computable (by a Turing machine with infinite input).
This paper proposes a decision procedure for the following synthesis problem:
given a regular function $f$ (equivalently specified by one of the
aforementioned transducer model), is $f$ computable and if it is, synthesize a
Turing machine computing it.
 For regular functions, we show that computability is equivalent to
continuity, and therefore the problem boils down to deciding continuity. We
establish a generic characterisation of continuity for functions preserving
regular languages under inverse image (such as regular functions). We exploit
this characterisation to show the decidability of continuity (and hence
computability) of rational and regular functions. For rational functions, we
show that this can be done in $\mathsf{NLogSpace}$ (it was already known to be
in $\mathsf{PTime}$ by Prieur). In a similar fashion, we also effectively
characterise uniform continuity of regular functions, and relate it to the
notion of uniform computability, which offers stronger efficiency guarantees.