Michaël Cadilhac

Olivier Carton
email: olivier.carton@irif.fr

Charles Paperman

CONTINUITY OF FUNCTIONAL TRANSDUCERS: A PROFINITE STUDY OF RATIONAL FUNCTIONS

Keywords: Transducers, rational functions, language varieties, continuity

A word-to-word function is continuous for a class of languages V if its inverse maps V-languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes.

Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages. To this end, we develop a robust theory rooted in the standard profinite analysis of regular languages.

Since previous algebraic studies of transducers have focused on the sole structure of the underlying input automaton, we also compare the two algebraic approaches. We focus on two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?

Introduction

The algebraic theory of regular languages is tightly interwoven with fundamental questions about the computing power of Boolean circuits and logics. The most famous of these braids revolves around A, the class of aperiodic or counter-free languages. Not only is it expressed using the logic FO [<], but it can be seen as the basic building block of AC 0 , the class of languages recognized by circuit families of polynomial size and constant depth. This class is in turn expressed by the logic FO [arb] (see [START_REF] Straubing | Finite Automata, Formal Logic, and Circuit Complexity[END_REF] for a lovely account). This pervasive interaction naturally suggests lifting this study to the functional level, hence to rational functions. This was started in [START_REF] Cadilhac | A circuit complexity approach to transductions[END_REF], where it was shown that a subsequential (i.e., input-deterministic) transducer computes an AC 0 function iff it preserves the regular languages of AC 0 by inverse image. Buoyed by this clean, semantic characterization, we wish to further investigate this latter property for different classes: say that a function f : A * → B * is V-continuous, for a class of languages V, if for every language L ⊆ B * of V, the language f -1 (L) is also a language of V. Our main focus will be on deciding V-continuity for rational functions; before listing our main results, we emphasize two additional motivations.

First, there has been some historical progression towards this goal. Noting, in [START_REF] Pin | Some operations and transductions that preserve rationality[END_REF], that inverse rational functions provide a uniform and compelling view of a wealth of natural operations on regular languages, Pin and Sakarovitch initiated in [START_REF] Pin | Une application de la representation matricielle des transductions[END_REF] a study of regularcontinuous functions. It was already known at the time, by a result of Choffrut (see [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]Theorem 2.7]), that regular-continuity together with some uniform continuity property characterize functions computed by subsequential transducers. This characterization was instrumental in the study of Reutenauer and Schützenberger [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF], who already noticed the peculiar link between uniform continuity for some distances on words and continuity for certain classes of languages. This link was tightened by Pin and Silva [START_REF] Pin | A topological approach to transductions[END_REF] who formalized a topological approach and generalized it to rational relations. More recently [START_REF] Pin | On profinite uniform structures defined by varieties of finite monoids[END_REF], the same authors made precise the link unveiled by Reutenauer and Schützenberger, and developed a fascinating and robust framework in which language continuity has a topological interpretation (see the beginning of Section 3, as we build upon this theory). Pin and Silva [START_REF] Pin | On uniformly continuous functions for some profinite topologies[END_REF] notably proposed thereafter a study of functions for which continuity for a class is propagated to subclasses. In addition, Daviaud et al. [START_REF] Daviaud | A generalised twinning property for minimisation of cost register automata[END_REF][START_REF] Daviaud | Degree of sequentiality of weighted automata[END_REF] recently explored continuity notions in the spirit of Choffrut's characterization to study weighted automata and cost-register automata.

Second, the interweaving between languages, circuits, and logic that was alluded to previously can in fact be formally stated (see again [START_REF] Straubing | Finite Automata, Formal Logic, and Circuit Complexity[END_REF][START_REF] Tesson | Logic meets algebra: the case of regular languages[END_REF]). A central property towards this formalization is the correspondence between "cascade products" of automata, stacking of circuits, and nesting of formulas, respectively. Strikingly, these operations can all be seen as inverse rational functions [START_REF] Tesson | Logic meets algebra: the case of regular languages[END_REF]. These operations are intrinsic in the construction of complex objects: languages, circuits, and formulas are often given as a sequence of simple objects to be composed (see, e.g., [START_REF] Schneider | Verification of Reactive Systems: Formal Methods and Algorithms[END_REF]Section 5.5]). We remark that a sufficient condition for the result of the composition to be in some given class (of languages, circuits, or logic formulas), is that each rational function be continuous for that class. Hence deciding continuity allows to give a sufficient condition for this membership question without computing the result of the composition, which is subject to combinatorial blowup.

Here, we report on three questions, the first two relating continuity to the other main algebraic approach to transducers, while allowing a more gentle introduction to the evaluation of profinite words by transducers:

• When does the transducer structure (i.e., its so-called transition monoid ) impact its continuity? The results of Reutenauer and Schützenberger [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF] can indeed be seen as the starting point of two distinct algebraic theories for rational functions; on the one hand the study of continuity, and on the other the study of the transition monoid of the transducer (disregarding the output). This latter avenue was explored by [START_REF] Filiot | First-order definability of rational transductions: An algebraic approach[END_REF]. We show in Section 4.1:

Theorem 1.1. Let V be a variety of languages among J , R, L, DA, A, COM, AB, G nil , G sol , or G.

-The statement "Any rational function structurally in V is continuous for V" holds for V ∈ {A, G sol , G} and does not otherwise; -The statement "Any rational function continuous for V is structurally in V" holds for V ∈ {G nil , G sol , G} and does not otherwise.

• What is the impact of variety inclusion on the inclusion of the related classes of continuous rational functions? When focusing on transducer structure alone, there is a natural propagation to superclasses; when is it the case for continuity? We show in Section 4.2:

Preliminaries

We assume some familiarity with the theory of automata and transducers, and concepts related to metric spaces (see, e.g., [START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Pin | Mathematical Foundations of Automata Theory[END_REF] for presentations pertaining to our topic). We first settle the notation for these prerequisites. We will use A and B for alphabets, and A * for words over A, with 1 the empty word. For each word u, there is a smallest v, called the primitive root of u, such that u = v c for some c; if c = 1, then u is itself primitive. We write |u| for the length of a word u ∈ A * and alph(u) for the set of letters that appear in u.

Let L ⊆ A * be a language. We write L c for the complement of L. For a word u ∈ A * , we write u -1 L for {v | u • v ∈ L}, and symmetrically for Lu -1 , these two operations being called the left and right quotients of L by u, respectively. We naturally extend concatenation and quotients to binary relations, in a component-wise fashion, e.g., for R ⊆ A * × A * and a pair ρ ∈ A * × A * , we may use ρ -1 R and Rρ -1 . More generally, with Id the identity relation, we will write, e.g., Id • ((x * , x * )ρ -1 ) for the pairs (ww 1 , ww 2 ) of words such that

w i ∈ x * ρ -1 i , i = 1, 2.
A variety is a mapping V which associates with each alphabet A a set V(A * ) of regular languages closed under the Boolean operations and quotient, and such that for any morphism h : A * → B * and any L ∈ V(B * ), we have that h -1 (L) ∈ V(A * ). Reg is the variety that maps every alphabet A to the set Reg(A * ) of regular languages over A.

Given two languages K, L ⊆ A * , we say that they are V-separable if there is a

S ∈ V(A * ) such that K ⊆ S and L ∩ S = ∅. Since V is closed under complement, K, L are V-separable iff L, K are. Naturally, L ∈ V(A * ) iff L is V-separable from L c .
Transducers. A transducer τ is a 9-tuple (Q, A, B, δ, I, F, λ, µ, ρ) where (Q, A, δ, I, F ) forms a nondeterministic automaton (i.e., Q is a state set, A an input alphabet, δ ⊆ Q × A × Q a transition set, I ⊆ Q a set of initial states, and F ⊆ Q a set of final states), and additionally, B is an output alphabet and λ : I → B * , µ : δ → B * , ρ : F → B * are the output functions. We write τ q,q for τ with I := {q} and F := {q }, adjusting λ and ρ to output 1 if they were undefined on these states. Similarly, τ q,• is τ with I := {q} and F unchanged, and symmetrically for τ •,q . For q ∈ Q and u ∈ A * , we write q.u for the set of states reached from q by reading u. We assume that all the transducers and automata under study have no useless state, that is, all states appear in some accepting path.

With w ∈ A * , let t 1 t 2 • • • t |w| ∈ δ * be an accepting path for w, starting in a state q ∈ I and ending in some q ∈ F . The output of this path is λ(q)µ(t 1 )µ(t 2 ) • • • µ(t n )ρ(q ), and we write τ (w) for the set of outputs of such paths. We use τ for both the transducer and its associated partial function from A * to subsets of B * . Relations of the form {(u, v) | v ∈ τ (u)} are called rational relations.

The transducer τ is unambiguous if there is at most one accepting path for each word. In that case τ q,q is also an unambiguous transducer for any states q, q . When τ is unambiguous, it realizes a (partial) word-to-word function: the set of functions computed by unambiguous transducers is the set of rational functions. Further restricting, if the underlying automaton is deterministic, we say that τ is a subsequential transducer. If τ is a finite union of subsequential transducers of disjoint domains, we say that τ is plurisubsequential.

Word distances, profinite words. For a variety V of regular languages, we define a distance between words for which, intuitively, two words are close if it is hard to separate them with V languages. Define d V (u, v), for words u, v ∈ A * , to be 2 -r where r is the size of the smallest automaton that recognizes a language of V(A * ) that separates {u} from {v}; if no such language exists, then d V (u, v) = 0. It can be shown that this distance is a pseudo-ultrametric [13, Section VII.2]; we make only implicit and innocuous use of this fact.

The complete metric space that is the completion of (A * , d Reg ) is denoted A * and is called the free profinite monoid, its elements being the profinite words, and the concatenation being naturally extended. By definition, if (u n ) n>0 is a Cauchy sequence, it should hold that for any regular language L, there is a N such that either all u n with n > N belong to L, or none does. For any x ∈ A * , define the profinite word x ω = lim x n! , and more generally, for any c > 0, x ω-c = lim x n!-c . That (x n! ) n>0 is a Cauchy sequence is a starting point of the profinite theory [START_REF] Pin | Mathematical Foundations of Automata Theory[END_REF]Proposition VI.2.10]; it is also easily checked that x c×ω = lim x c×n! is equal to x ω for any integer c ≥ 1. Given a language L ⊆ A * , we write L ⊆ A * for its closure, and we note that if L is regular, L c = L c -the complement being taken in A * in the left-hand side and in A * in the right-hand side. Furthermore, for L regular, L ∪ L = L ∪ L , and similarly for intersection (see [START_REF] Pin | Mathematical Foundations of Automata Theory[END_REF]Theorem VI.3.15]).

Equations. For u, v ∈ A * , a language L ⊆ A * satisfies the (profinite) equation u = v if for any words s, t

∈ A * , [s • u • t ∈ L ⇔ s • v • t ∈ L].
Similarly, a class of languages satisfies an equation if all the languages of the class satisfy it. For a variety V, we write u = V v, and say that

u is equal to v in V, if V(A * ) satisfies u = v. For a partial function f , f (u) = V f (v)
means that either both f (u) and f (v) are undefined, or they are both defined and equal in V.

Given a set E of equations over A * , the class of languages defined by E is the class of languages over A * that satisfy all the equations of E. Reiterman's theorem shows in particular that for any variety V and any alphabet A, V(A * ) is defined by a set of equations (the precise form of which being studied in [START_REF] Gehrke | Duality and Equational Theory of Regular Languages[END_REF]).

More on varieties. Borrowing from Almeida and Costa [START_REF] Almeida | Equidivisible pseudovarieties of semigroups[END_REF], we say that a variety V is supercancellative when for any alphabet A, any u, v ∈ A * and x, y

∈ A, if u • x = V v • y or x • u = V y • v, then u = V v
and x = y. This implies in particular that for any word w ∈ A * , both w • A * and A * • w are in V(A * ). We further say that a variety V separates words if for any s, t ∈ A * , {s} and {t} are V-separable.

Our main applications revolve around some classical varieties, that we define over any possible alphabet A as follows, where x, y range over all of A * , and a, b over A: The varieties included in A are called aperiodic varieties and those in G are called group varieties. Precise definitions, in particular for the group varieties, can be found in [START_REF] Straubing | Finite Automata, Formal Logic, and Circuit Complexity[END_REF][START_REF] Pin | Profinite semigroups, Mal'cev products and identities[END_REF]; we simply note that in group varieties, x ω equals 1 for all x ∈ A * . All these varieties except for AB and COM separate words, and only DA and A are supercancellative. They satisfy:

J = R ∩ L R L DA A AB = G ∩ COM G nil G sol G COM
On transducers and profinite words. For a profinite word u and a state q of an unambiguous transducer τ , the set q.u is well defined; indeed, with u = lim u n , the set q.u n is eventually constant, as otherwise for some state q , the domain of τ q,q would be a regular language that separates infinitely many u n 's.

A transducer τ : A * → B * is a V-transducer, 1 for a variety V, if for some set of equations E defining V(A * ), for all (u = v) ∈ E and all states q of τ , the equality q.u = q.v holds. A rational function is V-realizable if it is realizable by a V-transducer.

Continuity. For a variety V, a function f : A * → B * is V-continuous 2 iff for any L ∈ V(B * ), f -1 (L) ∈ V(A * ).
We mostly restrict our attention to rational functions. Since they are computed by transducers, there are countably many such functions. We note that many more Reg-continuous functions exist, in particular uncomputable ones: Proposition 2.1. There are uncountably many Reg-continuous functions.

Proof. Consider a strictly increasing function g :

N → N. Define f : {a} * → {a} * by f (a n ) = a g(n)! .
Recall that any regular language over a unary alphabet is a finite union of languages of the form a i (a j ) * . Moreover, we have that f -1 (a i (a j ) * ) is finite when i ≡ 0 mod j, and cofinite otherwise, thus f is Reg-continuous. There are however uncountably many increasing functions g, hence uncountably many Reg-continuous functions f .

Continuity is a formal notion of "functions being compatible with a class of languages." An equally valid notion could be to consider classes of functions that contain the characteristic functions of the languages, and closed under composition; it turns out that the largest such class coincides with the class of continuous functions. Indeed, writing χ L : A * → {0, 1} for the characteristic function of a language L ⊆ A * : Proposition 2.2. Let V be a variety such that {1} ∈ V({0, 1} * ). Let F be the largest class of functions such that:

(1) For any alphabet A, F ∩ {0,

1} A * = {χ L | L ∈ V(A * )}; (2) F is closed under composition.
The class F is well defined and it coincides with the class of V-continuous functions.

Proof. We say that a class of functions is good if it satisfies properties (1) and ( 2). We show that the V-continuous functions form a good class, and that any good class is included in the V-continuous functions. This implies that there is a largest good class, and that it coincides with the class of V-continuous functions, as claimed.

(Continuous functions form a good class.) Clearly, the class of V-continuous functions is closed under composition. Now consider a V-continuous function f :

A * → {0, 1}. By continuity, L = f -1 ({1}) is in V(A * ), since by hypothesis {1} ∈ V({0, 1} * ). Hence f = χ L for some L ∈ V(A * ), concluding this step.
1 The usual definition of V-transducer is based on the so-called transition monoid of τ , see, e.g., [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF]; the definition here is easily seen to be equivalent by [1, Lemma 3.2] and [5, Lemma 1].

2 A note on terminology: There has been some fluctuation on the use of the term "continuous" in the literature, mostly when a possible incompatibility arises with topology. In [START_REF] Pin | On uniformly continuous functions for some profinite topologies[END_REF], the authors use the term "preserving" in the more general context of functions from monoids to monoids. In our study, we focus on word to word functions, in which the natural topological context provides a solid basis for the use of "continuous," as used in [START_REF] Pin | A topological approach to transductions[END_REF][START_REF] Cadilhac | A circuit complexity approach to transductions[END_REF].

(Functions in good classes are continuous.) Let f : A * → B * be in a good class, and let L ∈ V(B * ); we ought to show that f -1 (L) is in V(A * ). We have:

f -1 (L) = f -1 (χ -1 L (1)) = (χ L • f ) -1 (1) = g -1 (1) . (with g = χ L • f )
Note that χ L is by hypothesis in the good class, and it being closed under composition, g also belongs to the good class. Since g ∈ {0, 1} A * , there is a L ∈ V(A * ) such that g = χ L . This implies that f -1 (L) = L , and it thus belongs to V(A * ).

Continuity: The profinite approach

We build upon the work of Pin and Silva [START_REF] Pin | A topological approach to transductions[END_REF] and develop tools specialized to rational functions. In Section 3.1, we present a lemma asserting the equivalence between V-continuity and the "preservation" of the defining equations for V. In the sections thereafter, we specialize this approach to rational functions. As noted in [START_REF] Pin | A topological approach to transductions[END_REF], it often occurs that results about rational functions can be readily applied to the larger class of Reg-continuous functions; here, this is in particular the case for the Preservation Lemma of Section 3.1.

The connection to the classical notion of continuity is given by the next Theorem.

Theorem 3.1 [17, Theorem 4.1]. Let f : A * → B * . It holds that f is V-continuous iff f is uniformly continuous for the distance d V .
Consequently, if f is Reg-continuous then it has a unique continuous extension to the free profinite monoid with domain f -1 (B * ), written f : A * → B * . The salient property of this mapping is that it is continuous in the topological sense (see, e.g., [START_REF] Pin | Mathematical Foundations of Automata Theory[END_REF]). For our specific needs, we simply mention that it implies that for any regular language L, we have that f -1 (L) is closed (that is, it is the closure of some set).

3.1. The Preservation Lemma: Continuity is equivalent to preserving equations. The Preservation Lemma gives us a key characterization in our study: it ties together continuity and some notion of preservation of equations. This can be seen as a generalization for functions of the notion of equation satisfaction for languages. We will need the following technical lemma that extends [13, Proposition VI.3.17] from morphisms to arbitrary Reg-continuous functions; interestingly, this relies on a quite different proof. Lemma 3.2. Let f : A * → B * be a Reg-continuous function and L a regular language. The equality f -1 (L) = f -1 (L) holds.

Proof. First note that f -1 (L) ⊆ f -1 (L), and that the right-hand side of this inclusion is closed. Hence f -1 (L) ⊆ f -1 (L).

For the converse inclusion, first write D = f -1 (B * ), a regular language by hypothesis. We have that f

-1 (L) = ( f -1 (L c )) c ∩ D, and similarly, f -1 (L) = (f -1 (L c )) c ∩ D. This latter equality implies that f -1 (L) = f -1 (L c ) c ∩ D, since f -1 (L c
) and D are regular.

Hence the inclusion to be shown, that is,

f -1 (L) ⊆ f -1 (L), is equivalent to: ( f -1 (L c )) c ∩ D ⊆ f -1 (L c ) c ∩ D ,
or equivalently,

f -1 (L c ) ∪ D c ⊆ f -1 (L c ) ∪ D c .
The inclusion to be shown is thus implied by

f -1 (L c ) ⊆ f -1 (L c ), that is, since L is regular, by f -1 (L c ) ⊆ f -1 (L c ).
As in the proof of the converse inclusion, the right-hand side being closed, this inclusion holds.

Lemma 3.3 (Preservation Lemma). Let f : A * → B * be a Reg-continuous function and E a set of equations that defines V(A * ). The function f is V-continuous iff for all (u = v) ∈ E and words s, t ∈ A * , f (s • u • t) = V f (s • v • t). Proof. (Only if.) Suppose f is V-continuous. Let u, v ∈ A * such that u = V v, and s, t ∈ A * . Since by V-continuity f -1 (B * ) ∈ V(A * ), either both s • u • t and s • v • t belong
to the closure of this language, or they both do not. The latter case readily yields the result, hence suppose we are in the former case. By definition, u = lim u n and v = lim v n for some Cauchy sequences of words

(u n ) n>0 and (v n ) n>0 . Since s • u • t = V s • v • t, the hypothesis yields that d V (s • u n • t, s • v n • t) tends to 0. By Theorem 3.1, f is uniformly continuous for d V , hence d V (f (s • u n • t), f (s • v n • t)) also tends to 0 (note that both f (s • u n • t) and f (s • v n • t) are defined for all n big enough). This shows that f (s • u • t) = V f (s • v • t).
(If.) Suppose that f preserves the equations of E as in the statement. Let L ∈ V(B * ), we wish to verify that L = f -1 (L) ∈ V(A * ), or equivalently by definition, that L satisfies all the equations of E. Let (u = v) ∈ E be one such equation, and s, t ∈ A * ; we must show that s

• u • t ∈ L ⇔ s • v • t ∈ L . By Lemma 3.2, since f is Reg-continuous, f (L ) = f ( f -1 (L)) ⊆ L. Now let s • u • t ∈ L , we thus have that f (s • u • t) ∈ L (observe that f (s • u • t) is indeed defined). By hypothesis, f (s • u • t) = V f (s • v • t); now since L ∈ V(B * ), it must hold that f (s • v • t) ∈ L.
Taking the inverse image of f on both sides, it thus holds that s•v•t ∈ f -1 (L), and Lemma 3.2 then shows that s • v • t ∈ L . As the argument works both ways, this shows that s

• u • t ∈ L ⇔ s • v • t ∈ L , concluding the proof.
Continuity can be seen as preserving membership in V (by inverse image); this is where the nomenclature "V-preserving function" of [START_REF] Pin | On uniformly continuous functions for some profinite topologies[END_REF] stems from. Strikingly, this could also be worded as preserving nonmembership in V:

Proposition 3.4. A Reg-continuous total 3 function f : A * → B * is V-continuous iff for all L ⊆ A * that do not belong to V(A * ), f (L) and f (L c ) are not V-separable.
Proof. We rely on a characterization due to Almeida [1, Lemma 3.2]: two languages K and L are V-separable iff for all u ∈ K, v ∈ L, we have that u = V v.

(Only if.) Suppose f is V-continuous, and let L ⊆ A * be a language outside V(A * ). There must be two profinite words u, v ∈ A * such that u = V v, u ∈ L and v ∈ L c . By V-continuity and the Preservation Lemma, f (u) = V f (v), and moreover,

f (u) ∈ f (L) and f (v) ∈ f (L c ).
The characterization above thus implies that f (L) and f (L c ) are not V-separable.

(If.) Assume that for all L ⊆ A * , if f (L) and f (L c ) are V-separable, then L ∈ V(A * ). For all K ∈ V(B * ), we show that L = f -1 (K) ∈ V(A * ). Now f (L) ⊆ K, and f (L c ) = f (f -1 (K) c ) = f (f -1 (K c )) ⊆ K c . Since K ∈ V(B *
), it is V-separable from its complement, hence f (L) and f (L c ) are V-separable, and our assumption implies that L ∈ V(A * ).

3.2.

The profinite extension of rational functions. The Preservation Lemma already hints at our intention to see transducers as computing functions from and to the free profinite monoids. Naturally, if τ is a rational function, its being Reg-continuous allows us to do so (by Theorem 3.1). For u = lim u n a profinite word, we will write τ (u) for τ (u), i.e., the limit lim τ (u n ), which exists by continuity. In this section, we develop a slightly more combinatorial approach to the evaluation of τ , and address two classes of profinite words: those expressed as s • u • t for s, t words and u a profinite word, and those expressed as x ω for x a word. Let τ be an unambiguous transducer. Recall that for any state q of τ and any profinite word u, q.u is well defined. As a consequence, if s and t are words, then there is at most one initial state q 0 , one q ∈ q 0 .s and one q ∈ q.u such that q .t is final, and these states exist iff τ (s • u • f ) is defined. Thus: Lemma 3.5. Let τ be an unambiguous transducer from A * to B * , s, t ∈ A * and u ∈ A * . Suppose τ (s • u • t) is defined, and let q 0 , q, q be the unique states such that q 0 is initial, q ∈ q 0 .s, q ∈ q.u, and q .t is final. The following holds:

τ (s • u • t) = τ •,q (s) • τ q,q (u) • τ q ,• (t) .
Let us now turn to the evaluation of ω-terms: Lemma 3.6. Let τ be an unambiguous transducer from A * to B * and x ∈ A * . If τ (x ω ) is defined, then there are words s, y, t ∈ B * such that:

τ (x ω ) = s • y ω-1 • t .
Proof. Consider a large value n; we study the behavior of x n! on τ . There is an initial state q 0 , a state q, and a final state q 1 such that x n! is accepted by a path going from q 0 to q reading x i , from q to q reading x k with k < n, and from q to q 1 reading x j . Thus the accepting path for any word of the form x m! , m > n is similar to the one for x n! : from q 0 to q, looping (m! -n!)/k + 1 times on q, and then from q to q 1 . Let thus s = τ q 0 ,q (x i ), z = τ q,q (x k ), and t = τ q,q 1 (x j ). It then holds that τ ((

x k ) m! ) = s • z m!-(n!/k)+1 • t. Letting c = n!/k -1, this shows that τ ((x k ) ω ) = s • z ω-c • t. Now on the one hand, (x k ) ω =
x ω , and on the other hand, we similarly have that z ω-c = y ω-1 by letting y = z c . We thus obtain that τ

(x ω ) = s • y ω-1 • t.
These constitute our main ways to effectively evaluate the image of profinite words through transducers. Since they are ubiquitous in our study, we will frequently apply these lemmas without explicitly citing them.

3.3.

The Syncing Lemma: Preservation Lemma applied to transducers. We apply the Preservation Lemma on transducers and deduce a slightly more combinatorial characterization of transducers describing continuous functions. This does not provide an immediate decidable criterion, but our decidability results will often rely on it. The goal of the forthcoming lemma is to decouple, when evaluating s • u • t (with the notations of the Preservation Lemma), the behavior of the u part and that of the s, t part. This latter part will be tested against an equalizer set: Definition 3.7 (Equalizer set). Let u, v ∈ A * . The equalizer set of u and v in V is:

Equ V (u, v) = {(s, s , t, t ) ∈ (A * ) 4 | s • u • t = V s • v • t } .
Remark 3.8. The complexity of equalizer sets can be surprisingly high. For instance, letting V be the class of languages defined by {x 2 = x 3 | x ∈ A * }, there is a profinite word u for which Equ V (u, u) is undecidable (this relies on the existence of arbitrarily long square-free words). On the other hand, equalizer sets quickly become less complex for common varieties; for instance, Lemma 3.12 will provide a simple form for the equalizer sets of aperiodic supercancellative varieties.

= {(u, v) | (∃s)[(s, u) ∈ R ∧ (s, v) ∈ S]} = S • R -1 ) .
Naturally, the input synchronization of two rational functions is a rational relation. Lemma 3.10 (Syncing Lemma). Let τ be an unambiguous transducer from A * to B * and E a set of equations that defines V(A * ). The function τ is V-continuous iff:

(1) τ -1 (B * ) ∈ V(A * ), and (2) For any (u = v) ∈ E, any states p, q, any p ∈ p.u, and any q ∈ q.v, and letting u = τ p,p (u) and v = τ q,q (v):

(τ •,p τ •,q ) × (τ p ,• τ q ,• ) ⊆ Equ V (u , v ) .
Proof. We rely on the Preservation Lemma, since τ is Reg-continuous.

(Only if.) Suppose that τ is V-continuous, the first point is immediate. For the second, we use the notation of the statement. Let (s, s , t, t ) ∈ (τ •,p τ •,q ) × (τ p ,• τ q ,• ). This implies that there are words x, y ∈ A * such that:

• s = τ •,p (x), s = τ •,q (x); • t = τ p ,• (y), t = τ q ,• (y). By Lemma 3.5, we have that τ (x • u • y) = s • u • t and τ (x • v • y) = s • v • t . The Preservation Lemma then asserts that s • u • t = V s • v • t , showing that (s, s , t, t ) ∈ Equ V (u , v ). (If.) Let (u = v) ∈ E and x, y ∈ A * . We must show that τ (x • u • y) = V τ (x • v • y). Since τ -1 (B * ) ∈ V(A * )
, either τ is defined on both x • u • y and x • v • y, or on neither; in this latter case, the equality is satisfied by definition. We thus suppose that both values are defined. This implies that there are states p, q, p , q as in the statement, and using the same notation, letting s, s , t, t just as above, the hypothesis yields that s

• u • t = V s • v • t , showing the claim.

3.4.

A profinite toolbox for the aperiodic setting. In this section, we provide a few lemmas pertaining to our study of aperiodic continuity. We show that the equalizer sets of aperiodic supercancellative varieties are well behaved. Intuitively, the larger the varieties are, the more their nonempty equalizer sets will be similar to the identity. For instance, if s • x ω = A x ω , for words s and x, it should hold that s and x have the same primitive root. We first note the following easy fact that will only be used in this section; it is reminiscent of the notion of equidivisibility, studied in the profinite context by Almeida and Costa [START_REF] Almeida | Equidivisible pseudovarieties of semigroups[END_REF]. Lemma 3.11. Let u, v be profinite words over an alphabet A and V be a supercancellative variety. Suppose that there are s, t

∈ A * such that u • t = V s • v, then there is a w ∈ A * such that u = V s • w and v = V w • t. If moreover u = v and V is aperiodic, then u = V s • u • t. Proof. Let u = lim u n ; if (u n ) n>0 is ultimately constant, then this is immediate, so we assume that |u n | is unbounded. From u • t = V s • v,
and the fact that s • A * ∈ V(A * ) by supercancellativity, we obtain that for n large enough, u n • t ∈ s • A * . Since u is nonfinite, |u n | > |s| for n large enough, in which case u n = s • w n for some sequence (w n ) n>0 . Let w ∈ A * be a limit point of this sequence, that exists by compactness (this is an essential property of the free profinite monoid, see, e.g., [START_REF] Pin | Mathematical Foundations of Automata Theory[END_REF]Theorem VI.2.5]). It holds that u = s • w. Replacing u by this value in the equation of the hypothesis, we thus have that s

• w • t = V s • v, and since V is supercancellative, that v = V w • t.
For the last point, with u = v, we iterate the previous construction on w, since in that case,

u = V w • t = V s • w. This provides a sequence w = w 1 , w 2 , w 3 , . . . such that u = V s n • w n = V w n • t n . Taking a limit point x of (w n ) n>0 , it thus holds that u = V s ω • x = V x • t ω , showing, by aperiodicity, that u = V s • u = V u • t.
Lemma 3.12. Let u, v be profinite words over an alphabet A and V be an aperiodic supercancellative variety. Suppose Equ V (u, v) is nonempty. There are words x, y ∈ A * and two pairs ρ 1 , ρ 2 ∈ (A * ) 2 such that:

Equ V (u, v) = Id • (x * , x * )ρ -1 1 × ρ -1 2 (y * , y * ) • Id . Proof.
Let us first establish the property for u = v. Assume that there are nonempty primitive words x, y such that x • u • y = V u; we show the statement of the lemma with these x and y, and ρ 1 = ρ 2 = (1, 1). Note that x ω • u • y ω = V u, hence, since x ω+1 = x ω and similarly for y, we have that x • u = V u • y = V u. This and the fact that V is supercancellative show the right-to-left inclusion.

For the left-to-right inclusion, let s, s , t, t be such that s

• u • t = V s • u • t .
Since V is supercancellative, this implies that the equation also holds if common prefixes of s and s and common suffixes of t and t are removed. We may thus assume that we are in two possible situations, by symmetry: (1) Suppose s = t = 1, that is, s • u • t = V u, and that s, t are nonempty. By the same token as above, this shows that s

• u = V u • t = V u.
In particular, this implies that:

s |x| • u • t |y| = V x |s| • u • y |t| ,
which implies, since V is supercancellative, that s |x| = x |s| and t |y| = y |t| . As x and y are primitive, this shows that s ∈ x * and t ∈ y * . (Note that this holds even if one of s or t is empty.) (2) Suppose s = t = 1, that is, u • t = V s • u, and that s , t are nonempty. By Lemma 3.11, we have that u = V s • u • t, and we can appeal to the previous situation, showing that s ∈ x * and t ∈ y * .

(The cases where one of s, t is empty, in the first point, or one of s , t is empty, in the second, are treated similarly. Note that it is not possible for both s and s to be nonempty, since that would imply that they start with different letters, falsifying the assumed equation by supercancellativity.) We assumed that the x, y existed, we ought to show the other cases satisfy the claim. The two situations above show that if Equ V (u, u) is nonempty, then such x, y exist, although without the guarantee that they be nonempty. Now if x • u = V u and there are no nonempty y such that x • u • y = V u, this implies that there are no nonempty y such that u • y = V u. Consequently, in the above case, t = t = 1, and the analysis stands. This concludes the proof for the case u = v.

We will reduce the case u = v to this one. Indeed, suppose that s

• u • v = s • v • t .
Again, by stripping away common prefixes and suffixes, we are faced with two cases:

(1) Suppose

s = t = 1, that is, s • u • t = V v. We have that Equ V (u, v) = Equ V (u, s • u • t), hence (m, m , n, n ) ∈ Equ V (u, v) iff (m, m • s, n, t • n ) ∈ Equ V (u, u)
, and the result follows.

(2) Suppose

s = t = 1, that is, u • t = V s • v. By Lemma 3.11, there is a profinite word w such that u = V s • w and v = V w • t, hence (m, m , n, n ) ∈ Equ V (u, v) iff (m • s , m , n, t • n ) ∈ Equ V (w, w), concluding the proof.
Lemma 3.13. Let x, y be words. For every aperiodic supercancellative variety V, the equality

Equ V (x ω , y ω ) = Equ A (x ω , y ω ) holds.
Proof. The inclusion from right to left is clear, since all equations true in A hold in V.

In the other direction, let us write u = x |y| and v = y |x| ; we have that u ω = x ω and v ω = y ω . Suppose s • u ω t = V s • v ω • t . In particular, since V is supercancellative, this means that s • u n is a prefix of s • v n , or vice-versa, depending on whether |s| > |s | or the opposite. This implies that u • u p = v s • v for some prefix u p of u and suffix v s of v. Hence (by, e.g., [START_REF] Lothaire | Combinatorics on Words[END_REF]Proposition 1.3.4]) u and v are conjugate. Their respective primitive roots are thus conjugate (by [START_REF] Lothaire | Combinatorics on Words[END_REF]Proposition 1.3.3]); writing z • z and z • z for them, we have that

u ω = (z • z ) ω and v ω = (z • z) ω .
Thus the equation above reads: s

• (z • z ) ω • t = V s • (z • z) ω • t .
As in the proof of Lemma 3.12, removing the common prefixes and suffixes (which we can do both in V and A), we are left with two possibilities:

• Suppose s = t = 1, that is, s•(z • z ) ω •t = V (z • z) ω .
The same argument as in Lemma 3.12 shows that s ∈ z • (z • z ) * and t ∈ (z • z ) * • z, and hence the equation holds in A too;

• Suppose s = t = 1, that is, (z • z ) ω • t = V s • (z • z) ω . Similarly, as V is supercancellative
and aperiodic, this shows that s ∈ z • (z • z) * and t ∈ (z • z ) * • z, and the equation holds in A too, concluding the proof.

Remark 3.14. For two aperiodic supercancellative varieties V and W, we could further show that if both Equ V (u, v) and Equ W (u, v) are nonempty, then they are equal, for any profinite words u, v. It may however happen that one equalizer set is empty while the other is not; for instance, with u = (ab) ω and v = (ab) ω • a • (ab) ω , the equalizer set of u and v in DA is nonempty, while it is empty in A.

Intermezzos

We present a few facts of independent interest on continuous rational functions. Through this, we develop a few examples, showing in particular how the Preservation and Syncing Lemmas can be used to show (non)continuity. In a first part, we study when the structure of the transducer is relevant to continuity, and in a second, when the (non)inclusion of variety relates to (non)inclusion of the class of continuous rational functions.

4.1.

Transducer structure and continuity. As noted by Reutenauer and Schützenberger [20, p. 231], there exist numerous natural varieties V for which any V-realizable rational function is V-continuous. Indeed:

Proposition 4.1. Let V be a variety of languages closed under inverse V-realizable rational function. Any V-realizable rational function is V-continuous. This holds in particular for the varieties A, G sol , and G.

Proof. This is due to a classical result of Sakarovitch [START_REF] Sakarovitch | Sur la définition du produit en couronne[END_REF] (see also [START_REF] Pin | Une application de la representation matricielle des transductions[END_REF]), stating, in modern parlance, that a variety V is closed under block product iff it is closed under inverse V-realizable rational functions (note that there has been some fluctuation on vocabulary, since wreath product was used at some point to mean block product). That A, G sol , and G are closed under block product is folklore.

This naturally fails for all our other varieties, since they are not closed under inverse V-realizable rational functions. For completeness, we give explicit constructions in the proof of the following Proposition. Proposition 4.2. For V ∈ {J , L, R, DA, AB, G nil , COM}, there are V-realizable rational functions that are not V-continuous.

Proof. We devise simple counter examples with A = {a, b}.

(The J , R and COM cases.) Recall that A * a / ∈ R(A * ) ∪ COM(A * ). The minimal unambiguous two-state transducer τ that erases all of its input except for the last letter is a (J ∩ COM)-transducer; indeed, a acts in the same way as b and they are idempotent on the transducer. However, τ -1 (a) = A * a.

(The R and DA cases.) Consider the Dyck language D over A; this is the (nonregular) language of well-parenthesized expressions where a is the opening and b the closing parenthesis. Write D (k) for the Dyck language where parentheses are nested at most k times, for instance

D (0) = 1, D (1) = (ab) * and D (2) = (a(ab) * b)
* . These languages have great importance in algebraic language theory, as they separate each level of the dot-depth hierarchy [START_REF] Janusz | The dot-depth hierarchy of star-free languages is infinite[END_REF]. It holds in particular that D (1) / ∈ DA(A * ). Let τ be the rational function that removes the first letter of each block of a's and each block of b's; naturally, τ is L-realizable. However, τ -1 (D k-1 ) = D k , showing not only that τ is not continuous for DA, but also not continuous for any level of the dot-depth hierarchy.

(The G nil and AB cases.) Consider the two-state transducer τ where a loops on both states, and a b on one state goes to the other. When a is read on the first state, it produces a x, while all the other productions are the identity. This is an AB-transducer. However, τ (aba) = xba = baa = τ (baa), hence it is not AB-continuous by the Preservation Lemma, since aba = AB baa. For G nil , let L be the language over {a, b, x} with a number of x congruent to 0 modulo 3. It can be shown that τ -1 (L) / ∈ G nil (A * ), intuitively since this language needs to differentiate between those a's that are an even number of b's away from the beginning of the word, and those which are not.

The converse concern, that is, whether all V-continuous rational functions are V-realizable, was mentioned by Reutenauer and Schützenberger [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF] for V = A. Proposition 4.3. For V ∈ {J , L, R, DA, A, AB, COM}, there are V-continuous rational functions that are not V-realizable.

Proof. (The aperiodic cases.) Let A = {a}, a unary alphabet. Consider the transducer τ that removes every second a: its minimal transducer not being a A-transducer, it is not A-realizable (this is a property of subsequential transducers [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF]). However, all the unary languages of V are either finite or co-finite, and hence for any L ∈ V(A * ), τ -1 (L) is either finite or co-finite, hence belongs to V(A * ).

(The AB and COM cases.) Over A = {a, b}, define τ to map words w in aA * to (ab) |w| , and words w in bA * to (ba) |w| . Clearly, a and b cannot act commutatively on the transducer. Now τ (ab) = COM τ (ba), and moreover τ (x ω ) = AB (ab) ω = AB 1 = τ (1), hence τ is continuous for both AB and COM by the Preservation Lemma.

We delay the positive answers to that question, namely for G nil , G sol , G, to Corollary 5.8 as they constitute our main lever towards the decidability of continuity for these classes.

Variety inclusion and inclusion of classes of continuous functions.

In this section, we study the consequence of variety (non)inclusion on the inclusion of the related classes of continuous rational functions. This is reminiscent of the notion of heredity studied by [START_REF] Pin | On profinite uniform structures defined by varieties of finite monoids[END_REF], where a function is V-hereditarily continuous if it is W-continuous for each subvariety W of V. Variety noninclusion provides the simplest study case here: Proposition 4.4. Let V and W be two varieties. If V ⊆ W then there are V-continuous rational functions that are not W-continuous.

Proof. Let L ∈ V(A * ) be such that L / ∈ W(A * ). Define f : A * → A * as the identity function with domain L. Clearly, as

f -1 (K) = K ∩ L, the function f is V-continuous. However, f -1 (A * ) = L / ∈ W(A * ) and A * ∈ W(A * ), thus f is not W-continuous.
The remainder of this section focuses on a dual statement: Proof. It remains to show the case V = AB. This is in fact the same example as in the proof of Proposition 4.3, to wit, over A = {a, b}, the rational function τ that maps w ∈ aA * to (ab) |w| , and words w ∈ bA * to (ba) |w| . Indeed, we saw that this function is continuous for AB, but we have that τ (a) = ab on the one hand, and τ (b ω a) = (ba) ω ba = W ba, but ab = W ba.

If V W,
The Preservation Lemma then shows that τ is not continuous for W.

Proposition 4.6. All AB-continuous rational functions are COM-continuous.

Proof. Indeed, if u = AB v with u, v words, then u = COM v, since these varieties separate the same words. As COM is defined using equations on words, this directly shows the claim by the Preservation Lemma.

4.2.2. The aperiodic cases. We now turn to aperiodic varieties. For less expressive varieties, the property fails:

Proposition 4.7. For V ∈ {J , L, R} and W ∈ {L, R, DA, A} with V W, there are V-continuous rational functions that are not W-continuous.

Proof. Define τ : {a} * → {a, b} * to be the rational function that changes every other a to b; that is, τ (a 2n ) = (ab) n , and τ (a 2n+1 ) = (ab) n • a. Note that naturally, over a single letter, a • (aa) ω = (aa) ω • a = a ω+1 . Now τ (a ω ) = (ab) ω and τ (a ω+1 ) = (ab) ω • a, and since these two profinite words are equal in J and R, the Preservation Lemma shows that τ is continuous for both J and R. However, these two profinite words are not equal in L, DA, and A, showing that τ is continuous for none of those varieties.

The remaining case, that is, showing the existence of a J -continuous rational function that is not R-continuous is done symmetrically, with the function mapping a 2n to (ab) n and a 2n+1 to b • (ab) n . Proposition 4.8. Any DA-continuous rational function is A-continuous.

Proof. First note that both DA and A satisfy the hypotheses of Lemma 3.12. Consider a DA-continuous rational function τ : A * → B * . By the Syncing Lemma, to show that it is A-continuous, it is enough to show that 1. τ -1 (B * ) ∈ A(A * ), and 2. That some input synchronizations of τ , based on equations of the form x ω = A x ω+1 , belong to an equalizer set of the form (by Lemma 3.6):

Equ A (α • y ω • β, α • z ω • β ) = {(s, s , t, t ) | (s • α, s • α , β • t, β • t ) ∈ Equ A (y ω , z ω )} .
Applying the Syncing Lemma on τ for the variety DA, we get that point 1 is true, since τ -1 (B * ) ∈ DA(A * ). Similarly, point 2 is true since x ω = x ω+1 is an equation of DA, and Lemma 3.13 implies that the equalizer set of the equation above is the same in DA and A.

However, this property does not hold beyond rational functions: Proposition 4.9. There are nonrational functions that are continuous for both DA and Reg but are not A-continuous.

Proof. Define f : {a} * → {a, b} * by f (a 2n ) = (ab) n and f (a 2n+1 ) = (ab) n • a • (ab) n . We first have to check that f is indeed Reg-continuous. Given a regular language L, we define a pushdown automaton over {a} * that recognizes f -1 (L); since all unary context-free languages are regular, by Parikh's theorem, this shows the claim. If the input is of the form a 2n , then the pushdown automaton may check that (ab) n ∈ L, by simulating the automaton for L. If the input is of the form a 2n+1 , then the pushdown automaton can guess the middle position of the input, and accordingly check that (ab) n • a • (ab) n ∈ L, again using the automaton for L. This concludes the construction.

The function f being Reg-continuous, consider its extension f . As in Proposition 4.7, checking that f is DA-continuous amounts to checking that f (a ω ) = DA f (a ω+1 ). The lefthand side being (ab) ω while the right-hand side is (ab) ω • a • (ab) ω , this holds. However, these two profinite words are equal in DA but not in A, hence this function is not A-continuous, again appealing to the Preservation Lemma.

5. Deciding continuity for transducers 5.1. Deciding continuity for group varieties. Reutenauer and Schützenberger showed in [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF] that a rational function is G-continuous iff it is G-realizable. Since this is proven effectively, it leads to the decidability of G-continuity. In Proposition 4.1, we saw that the right-to-left statement also holds for G sol ; we now show that the left-to-right statement holds for all group varieties V that contain G nil -this odd-looking condition on V is here to ensure that the free group is embedded, in a precise sense, in V [21, § 6.1.9]. As in [START_REF] Reutenaeur | Variétés et fonctions rationnelles[END_REF], but with sensibly different techniques, we show that V-continuous transducers are plurisubsequential. The Syncing Lemma will then imply that such transducers are V-transducers. Both properties rely on an omnibus normal form which uses the three following notions: Definition 5.1. • A transducer τ is utilitarian if for any two states p, q:

(∃x, y) ∅ = (τ p,• τ q,• ) ⊆ (x, y) • Id ⇒ p = q .

• Within a transducer, a pan is a triplet (q, q , p) of the form: p q q a a a * This is regardless of the outputs. The pan is proper if q = q . • Within a transducer, and for a letter a, a state q is a-recurrent if p.a ω = {p}. The transducer itself is said to be a-recurrent if all of its states are, and recurrent if it is a-recurrent for all letters.

Lemma 5.2. Let τ be a transducer. There is a utilitarian transducer τ computing the same function. Additionally:

• If τ is V-continuous for some group variety that contains G nil , then τ has no proper pan;

• For any letter a, if τ is a-recurrent, so is τ .

Proof. We start with the utilitarianism, then focus on the first of the "additionally" parts.

The second point therein is easily satisfied by construction. Utilitarianism is shown in three steps.

(Step 1.) Define τ to be the Cartesian product of τ with the powerset automaton of its reversal. By construction, we get the following fact, writing R p for the language of words accepted from p, that is {w | p.w ∩ F = ∅}: Fact 5.6. Any recurrent transducer is plurisubsequential.

Fact 5.7. Any V-continuous utilitarian plurisubsequential transducer is a V-transducer.

These facts together naturally imply the lemma.

Proof of Fact 5.5. We first apply Lemma 5.2 on τ . We turn the resulting transducer-which we call τ again-into a recurrent transducer one letter at a time. After each letter, we apply again Lemma 5.2, thus obtaining at the end of the process a utilitarian and recurrent transducer equivalent to τ . In the following, for any state q, we write L q for {w | q ∈ I.w} and R q for {w | q.w ∩ F = ∅}. The preimage of τ is denoted by L = τ -1 (B * ). Since τ is V-continuous, then L is in V. Finally, we say that a state p is weakly a-recurrent if p ∈ p.a w .

Let a be a letter. We first perform the direct product of the automaton with an automaton remembering the last weakly a-recurrent state seen. Let p be a non weakly a-recurrent state. Now τ is V-continuous and has no proper pan, hence for any u, v such that u ∈ L p and v ∈ R p , there exist q, q such that:

I u -→ q a ω -→ q a n -→ q v -→ F .
By the same argument used in showing the absence of proper pan in Lemma 5.2, it holds that p = q . Since p is connected to some weakly a-recurrent state, there is some k > 0 such that the above path can be decomposed as follows:

I u -→ q a ω -→ q a ω-k -→ q a k -→ p v -→ F .
Since p contains the information of the last weakly a-recurrent state seen, the choice of q is independent from u and v. Hence the choice of q too is independent from both u and v. In particular, this shows that L p ⊆ L q . Furthermore, for any word in u ∈ L q and any word v ∈ R q , we have ua ω v ∈ L, and thus uv ∈ L as well. Hence there exists a state r such that:

I u -→ r v -→ F .
By the same argument as above, we necessary have r = p, proving that L p = L q .

We now merge together all states p, q satisfying the property that L p = L q . Since, by Lemma 5.2, Fact 5.3 we have either R p ∩ R q = ∅ or R p = R q , merging p and q will not change the function computed. After these merges, all states are a-recurrent.

We now ensure that merging these states preserves that states were recurrent for other letters. Assume that the transducer was b-recurrent. Consider p and q to be merged; since L p = L q , they are both in a cycle of b's of the exact same length, say n. Let p ∈ p.b k and q ∈ q.b k . We finish this proof by showing that L p = L q , which implies that p and q are also merged during the process.

For any u ∈ L p , we have ub n-k ∈ L p = L q . Hence, ub n is in L q . Since the transducer is b-recurrent, then necessarily the unique state that can reach q by reading n letters b backwards is itself, proving that u ∈ L q and so L p ⊆ L q . Symmetrically, L q ⊆ L p , entailing L p = L q and concluding the proof.

of Fact 5.5.

Proof of Fact 5.6. Let a be some letter and q be a state of the transducer. Consider two states p, p in q.a. Since q.a ω = {q}, it holds that p.a ω-1 = {q}, and thus that p ∈ p.a ω . Hence p = p , since p is a-recurrent. of Fact 5.6.

•

  J , def. by (xy) ω • x = y • (xy) ω = (xy) ω • R, def. by (xy) ω • x = (xy) ω • L, def. by y • (xy) ω = (xy) ω • DA, def. by x ω • z • x ω = x ω for all z ∈ alph(x) * • A, def. by x ω+1 = x ω • COM, def. by ab = ba • AB, def. by ab = ba and a ω = 1 • G nil , the languages rec. by nilpotent groups • G sol , the languages rec. by solvable groups • G, the languages rec. by groups

Definition 3 . 9 (

 39 Input synchronization). Let R, S ⊆ A * × B * . The input synchronization of R and S is defined as the relation over B * ×B * obtained by synchronizing the first component of R and S: R S

  are all V-continuous rational functions W-continuous? Proposition 4.5. For V, W ∈ {G nil , G sol , G} with V W, all V-continuous rational functions are W-continuous. This however fails for V = AB and for any W ∈ {G nil , G sol , G}. 24:15

	4.2.1. The group cases. We first focus on group varieties. Naturally, if 1. V-continuous
	rational functions are V-realizable and 2. W-realizable rational functions are W-continuous,
	this holds. Appealing to the forthcoming Corollary 5.8 for point 1 and Proposition 4.1 for
	point 2, we then get:

In all the varieties we are interested in, one can easily modify any partial function into a total function while preserving its continuity properties.

Acknowledgment. We are deeply indebted to Shaull Almagor, Jorge Almeida (in particular for the Remark on page 10), Luc Dartois, Bruno Guillon (in particular for the Remark on page 23), Ismaël Jecker, and Jean-Éric Pin for their insightful comments and kind help.

The first and third authors are partly funded by the DFG Emmy Noether program (KR 4042/2); the second author is funded by the DeLTA project (ANR-16-CE40-0007).

Vol. 16:1 CONTINUITY OF FUNCTIONAL TRANSDUCERS 24:17

Fact 5.3. For any states p, p of τ , R p ∩ R p = ∅ ⇒ R p = R p .

(Step 2.) Write simply τ for the result of Step 1. In this step, we make sure that outputs are produced "as soon as possible", a process known as normalization (e.g., [12, Section 1.5.2]) that we sketch for completeness. For every state q, write π q for the longest string such that τ q,• (A * ) ⊆ π q • B * . Now define the new output function (λ , µ , ρ ) by letting:

µ (1, q) = µ(1, q) • π q , µ (q, a, q ) = π -1 q µ(q, a, q ) • π q , µ (q, 1) = π -1 q µ(q, 1) . Write τ for τ equipped with the output function µ . For no state q there is a letter b ∈ B * such that τ q,• (A * ) ⊆ b • B * .

(Step 3.) Write again τ for the result of the previous step. Naturally, τ still satisfies Fact 5.3. Consider two states p, q such that there are x, y ∈ B * satisfying ∅ = (τ p,• τ q,• ) ⊆ (x, y) • Id. The first part of this assumption implies that R p ∩ R q = ∅, and thus, by Fact 5.3, R p = R q . In other words, τ p,• and τ q,• have the same domain. The second part of the assumption thus indicates that every production of p (resp. of q) starts with x (resp. with y), and Step 2 asserts that x = y = 1. Hence τ p,• and τ q,• actually compute the same function. We can thus merge them into a single state without changing the function realized. Repeating this operation results in a transducer τ that is utilitarian.

(No proper pans.) Consider a pan (q, q , p) on a in τ . As p can be reached from both q and q reading a, the product P = τ q,• τ q ,• is nonempty. Write x = τ q ,p (a), y = τ p,q (a n ), z = τ q,p (a), for some n such that y is defined. We let h be the longest common suffix of x and z, and x = x • h and z = z • h.

As τ is G-continuous, let us apply point 2 of the Syncing Lemma on τ , the equation (a ω = 1), from the pair of states (q , q ) to (q, q ). With Z = τ •,q τ •,q , a nonempty subset of the identity, we have that Z × P ⊆ Equ V (x(yz) ω-1 y, 1). We write, in the following, ν -1 for ν ω-1 , to convey the fact that ν -1 is the inverse of ν in V; that is: ν • ν -1 = V 1 (this analogy naturally carries further, since for instance, (νη) -1 = V η -1 • ν -1 ). Let (s, s, u, u ) ∈ Z × P , then:

(By the Syncing Lemma)

Since u is a word and x and z do not share a common suffix, there is a word w such that u = z • w (this is true in the free group, which is embedded, in a precise sense, in V [21, § 6.1.9]). This implies that u = V x • w and shows that P ⊆ (z , x ) • Id, hence that q = q by the main property of this lemma, and the pan is not proper. of Lemma 5.2.

Lemma 5.4. Let V be a variety of group languages that contains G nil . For any V-continuous unambiguous transducer, there is an equivalent plurisubsequential V-transducer.

Proof. Let τ be a V-continuous unambiguous transducer. The proof is split in three facts:

Fact 5.5. There is a utilitarian recurrent transducer τ that defines the same function as τ .

Vol. 16:1

CONTINUITY OF FUNCTIONAL TRANSDUCERS 24:19

Proof of Fact 5.7. Let τ be a V-continuous utilitarian plurisubsequential transducer. Consider an equation u = V v, a state q of τ , and let p = q.u and p = q.v. We show that p = p , concluding this point. We rely on the Syncing Lemma, since τ is V-continuous; it ensures in particular that:

Let (s, s, t 1 , t 2 ) be in the left-hand side. We have that s

(here and in the following, we derive equivalent equations by appealing to the fact that the free group is embedded, in a precise sense, in V [21, § 6.1.9]). Now consider another tuple (s , s , t 1 , t 2 ) again in the left-hand side of Equation (5.1). It also holds that

This is in turn equal in V to some α • β -1 such that α and β are words that do not share the same last letter. This shows that t 1 = α • t and t 2 = β • t for some word t, and similarly for t 1 and t 2 . More generally: (τ p,• τ p ,• ) ⊆ (α, β) • Id, and since τ is utilitarian, p = p .

of Fact 5.7 and Lemma 5.4.

As an immediate corollary:

Corollary 5.8. For V ∈ {G nil , G sol , G}, any V-continuous rational function is V-realizable.

Theorem 5.9. Let V be a decidable variety of group languages that includes G nil and that is closed under inverse V-realizable rational functions. It is decidable, given an unambiguous transducer, whether it realizes a V-continuous function. This holds in particular for G sol and G.

Proof. Lemma 5.4 together with Proposition 4.1 shows that a transducer is V-continuous iff its equivalent transducer effectively computed by Lemma 5.4 is a V-transducer. This latter property being testable, the result follows.

5.2. Deciding continuity for aperiodic varieties. We saw in Section 4.1 that the approach of the previous section cannot work: there is no correspondence between continuity and realizability for aperiodic varieties. Herein, we use the Syncing Lemma to decide continuity in two main steps. First, note that all of our aperiodic varieties are defined by an infinite number of equations for each alphabet. The Syncing Lemma would thus have us check an infinite number of conditions; our first step is to reduce this to a finite number, which we stress through the forthcoming notion of "pertaining triplet" of states. Second, we have to show that the inclusion of the second point of the Syncing Lemma can effectively be checked. This will be done by simplifying this condition, and showing a decidability property on rational relations. We will need the following technical result in combinatorics on words in the proof of the forthcoming Lemma 5.12: Lemma 5.10. Let u, v, x, y, s, t ∈ A * be words satisfying:

(3) s and t are primitive. There exist z, z ∈ A * such that:

and since z • z is primitive, we have that t = z • z. We can do the same with x and y, letting x = s ċ • ż and y = ż • s ċ , with s = ż • ż . The same reasoning then shows that t = ż • ż. Since s has precisely |s| conjugates (by [START_REF] Lothaire | Combinatorics on Words[END_REF]Proposition 1.3.2]), we have that ż = z and ż = z , and the properties of the Lemma follow. Definition 5.11. A triplet of states (p, q, q ) is pertaining if there are words s, u, t and an integer n such that:

where • means "any word." Further, a pertaining triplet is empty if, in the above picture, β = β β = 1 and full if both words are nonempty; it is degenerate if only one of β or β β is empty.

It is called "pertaining" as the second point of the Syncing Lemma elaborates on properties of such a triplet, in particular, since u ω = u ω+1 is an equation of A. The following characterization of A-continuity is then made without appeal to equations or profinite words: Lemma 5.12. A transducer τ : A * → B * is A-continuous iff all of the following hold:

(1) τ -1 (B * ) ∈ A(A * );

(2) For all full pertaining triplets (p, q, q ), there exist x, y ∈ B * and

) For all empty pertaining triplets (p, q, q ), we have that

Proof. (Only if.) Suppose τ is A -continuous, and let us appeal to the Syncing Lemma. Point 1 is then immediate. Point 2 is a direct consequence of the second point of the Syncing Lemma and of Lemma 5.12.

We shall now check point 3, by contradiction. Let (p, q, q ) be an empty pertaining triplet; we use the notations of Definition 5.11. Then by functionality of τ , we have that

By the Preservation Lemma, and since

Point 4 is proven using similar ideas as point 3: with (p, q, q ) a degenerate pertaining tuple, and using the same notations as above, either the production of s • u ω • t going through p is a not a finite word while the production of s • u ω+1 • t through q, q is, or vice-versa. In both cases, it is not possible for these productions to be equal in A, hence if such a case happens, τ cannot be A-continuous.

(If.) We again rely on the Syncing Lemma, the first point of which being satisfied by hypothesis. Let u ω = u ω+1 be an equation of A with u a word; the set of such equations defines A(A * ). Let p, q, p , q be states such that p ∈ p.u ω and q ∈ q.u ω+1 , and let s, t be words with p, q ∈ q 0 .s and p .t, q .t ∈ F . To conclude and apply the Syncing Lemma, we need to show that:

(This is a direct consequence of the way profinite words are evaluated in a transducer, as per Lemma 3.5.) Consider a large number N = n!, so that p ∈ p.u N and q ∈ q.u N +1 . With a large enough N , there must be two states P and Q, and integers i, j with i + j = N , such that: • P ∈ p.u i , p ∈ P.u j , and P ∈ P.u N (i.e., P is "between" p and p , and belongs to a loop);

(That such a pair exists can easily be seen on the product automaton of τ by itself: The path from (p, q) to (p , q ) with q ∈ q .u reading u N must go twice through the same pair of states (P, Q), and this pair respects the above requirements.)

Now define the following words:

Using the same reasoning as Lemma 3.6, and the unambiguity of τ , Equation (5.2) is equivalent to:

and similarly for the right-hand side, Equation (5.2) is equivalent to:

To make use of the hypotheses of the present Lemma, define Q to be in Q.u and such that Q ∈ Q .u N -1 : (P, Q, Q ) is thus pertaining. The situation is then:

Since by hypothesis this triplet cannot be degenerate, either both of β and β are empty, or none are. Suppose they are both empty, then the hypothesis on empty triplets shows that:

the right-hand side evaluates to α • γ , and Equation (5.2) is thus satisfied.

Let us thus suppose that both β and β are nonempty. We divide

). Now let x, y ∈ B * and ρ 1 , ρ 2 ∈ (B * ) 2 be the (pairs of) words provided by point 2 for the triplet

2 (y * , y * ) • Id. For any k ≥ 1, and letting η = s • u i+k×N and η = u k×N +j • t, it holds by hypothesis that:

(b) Let us first emphasize an easy property of L and R:

Proof. We only show this for L, the case for R being similar.

For the first part of the statement, the hypothesis ensures the existence of a word z, integers n , n , and two prefixes x , x of x such that w

If w is a prefix of z, the property is easy to verify. In the other cases, w = z • x n • χ for some integer n < n , n (strictness coming from the hypothesis) and x = χχ . Hence w = χ • x n -n-1 • x and w = χ • x n -n-1 • x , and thus both belong to L. The case of R is similar.

For the second part of the statement, w and w start with a common word z, then some repetitions of x, and a prefix of x. Clearly, one has to be a prefix of the other. of Fact 5.13.

We first focus on the consequences of (a). First, since either α • β k is a prefix of α • β k or vice-versa, we have that either α is a prefix of α • β k , or α a prefix of α • β k , for some k. Suppose for instance that α = α • β c • β p , with β = β p • β s ; the other case will be treated later. Appealing to Fact 5.13, for k big enough, factoring out α yields that ((β s β p ) k-c-1 β s , β k ) ∈ L. Hence (β s β p ) * and β * share common prefixes of unbounded length, implying that β s β p and β are powers of a same primitive word z 1 (by, e.g., [START_REF] Lothaire | Combinatorics on Words[END_REF]Proposition 1.3.5]). Now similarly focusing on (b), we obtain that γ is a suffix of β k • γ or γ is a suffix of β k • γ, for some k. Suppose for instance that γ = β s • β c • γ , with β = β p • β s , again delaying the other case. It follows, just as above, that β and β s β p are powers of a same primitive word z 2 . Noting that (η c ) ω = η ω , for any η, Equation (5.2) is thus equivalent to:

By eliminating α and γ we thus obtain that there are some integers

(Remaining cases.) We made two suppositions: α is a prefix of α, and γ is a suffix of γ . The case where α is a prefix of α and γ a suffix of γ is entirely symmetric. Let us keep our supposition on α and assume that γ is a suffix of γ; the last remaining case is similar to this one.

Let us thus write γ = βs • β c • γ, with β = βp • βs . We then obtain, factoring out γ this time, that (β k-c-1 βp , β k ) ∈ R. This implies that ( βs βp ) and β are powers of the same primitive word, which can only be z 1 . Writing z 2 for the primitive root of β, Lemma 5.10 shows the existence of words z, z such that

By eliminating α and γ, we similarly obtain that Equation (5.2) is equivalent, for some

2

. Then both sides evaluate to z ω 2 , hence Equation (5.2) holds.

of Lemma 5.12.

Vol. 16:1 CONTINUITY OF FUNCTIONAL TRANSDUCERS 24:23

Example 5.14. We show that the transducer of Proposition 4.3 is A-continuous. Let τ be:

First, the function is total, hence the first point of Lemma 5.12 is satisfied. Second, there are no empty nor degenerate pertaining triplets, hence the third and fourth points are satisfied. Now the full pertaining triplets are (p, p, p), (p, p, q), (q, q, q), and (q, q, p). We check that the pertaining triplet (p, p, q) satisfies the second condition of Lemma 5.12, the other cases being similar or clear. The first half of the condition is immediate. Now τ p,• τ q,• = {(a n+1/2 , a n/2 ) | n ≥ 0} which satisfies the condition.

We now show that the property of Lemma 5.12 is indeed decidable: Proposition 5.15. It is decidable, given a rational relation R ⊆ A * × A * , whether there is a word x ∈ A * and a pair ρ ∈ (A * ) 2 , such that R ⊆ Id • (x * , x * )ρ -1 ).

Proof. We rely on the classical result that it is decidable whether a rational relation is included in the identity [23, p. 650].

We first tackle a related, simpler decision problem: Given a rational relation R ⊆ (A * × A * ) and a word x ∈ A * , check whether R ⊆ Id • (x * , x * ). Write f : A * → A * for the function that removes the longest suffix in x * of its argument, and note that f is a rational function. Closure under inverse and composition of rational relations implies that R = {(f (u), f (v)) | (u, v) ∈ R} is a rational relation computable from R. We have that R ⊆ Id if and only if R ⊆ Id • (x * , x * ), hence the decision problem at hand is equivalent to checking whether R ⊆ Id, which is decidable.

We now reduce the main decision problem to the previous one. First, we note that if a solution (x, ρ) exists, then there is another solution ( ẋ, ρ) with one component of ρ empty. Indeed, write x = xρ -1

1 , x = xρ -1 2 . Assume x is also a prefix of x (the symmetric case being similar). We may thus write x = x y and x = x z, and have that R ⊆ Id • (yx ) * , (yx ) * z , showing that ẋ := yx and ρ := (1, z -1 yx ) fit the requirements.

We thus task ourselves with finding a solution (x, ρ) with ρ 2 empty (the symmetric case being similar). We first check that R ⊆ Id. If this is not the case, we can compute a pair (u, v) ∈ R \ Id (again by [23, p. 650]). All the suffixes of u are candidates for xρ -1 1 ; we go through all these candidates x (including the empty word). We say that x is a valid choice if it stems from a valid solution (x, ρ).

Next, we verify that all pairs (u, v) ∈ R are such that u ends with x (this is decidable, e.g., since R ∩

). If this is not the case, then x is not a valid choice. Otherwise, let us write R = R • (x , 1) -1 , a rational relation.

We now check again that R ⊆ Id; if it is the case, we are done and values of (x, ρ) can be deduced. Otherwise, we are given a pair (u, v) ∈ R \ Id. Now if x is a valid choice, then either u is a prefix of v, or vice-versa. In the former case, write v = u • z; if x is a valid choice, then z ∈ x * , and this provides us with candidates for x: all the possible roots z of z. We may now test that one such z starts with x , and check whether R ⊆ Id • (z * , z * ) using the above decision problem. If this holds, then there do exist an x and a ρ satisfying R ⊆ Id • (x * , x * )ρ -1 . Moreover, if such words exist, this procedure will find them. Remark 5.16. In general, the problem of deciding, given a rational relation R and a recognizable relation K, whether R ⊆ Id • K, is undecidable. Indeed, testing R ∩ Id = ∅ is undecidable [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], and equivalent to testing:

the right-hand side being of the form Id • K.

Theorem 5.17. It is decidable, given an unambiguous transducer, whether it realizes an A-continuous function.

Proof. This is a consequence of Lemma 5.12: Given a transducer, one can list all its pertaining triplets, and whether they are empty, full, or degenerate. For full pertaining triplets, the property of Lemma 5.12 is checked with Proposition 5.15 and the same Proposition applied on the reverse of the transducer. The property for empty triplets can be checked since the inclusion of a rational relation in Id is decidable.

The rest of this section focuses on conditions à la Lemma 5.12 for J , R, L, and DA. In each of these cases, we define the proper notion of "pertaining" and rewrite the conditions of Lemma 5.12 to match the defining equations. Since the proofs are simple variants of that of Lemma 5.12, we omit them; we note that in each case, the conditions are effectively verifiable.

5.2.1.

The case of J . We use a different set of equations to define J , that can easily be proved to be equivalent to the one given in the Preliminaries. Specifically, J is defined over any alphabet A by the set of equations x ω = y • x ω • z, with y, z ∈ alph(x). The definition of "pertaining" then reads as follows: Definition 5.18. For two alphabets C, D, a quadruplet of states (p, q, q , q ) is (C, D)-pertaining if there are words s, u, t with alph(u) = C, words z, z ∈ C * , and an integer n such that: (2) For all full (C, D)-pertaining quadruplets (p, q, q , q ):

(3) For all empty (C, D)-pertaining quadruplets (p, q, q , q ):

(4) No pertaining quadruplet is degenerate.

5.2.2.

The case of R. Again, we slightly diverge from the usual equations for R, as presented in the Preliminaries. Indeed, R is also defined, over any alphabet A, by x ω = x ω • y with y ∈ alph(x). We turn to the definition of "pertaining:" Definition 5.20. For an alphabet C, a triplet of states (p, q, q ) is C-pertaining if there are words s, u, t with alph(u) = C, words z ∈ C * , and an integer n such that:

The pertaining triplet is empty if, in the above picture, β = β = 1; it is full if none of β, β is empty, and degenerate otherwise. Lemma 5.21. A transducer τ : A * → B * is R-continuous iff all of the following hold:

(1) τ -1 (B * ) ∈ R(A * );

(2) For all full C-pertaining triplets (p, q, q ), there exist x ∈ B * and ρ ∈ (B * ) 2 such that both inclusions hold:

(3) For all empty C-pertaining triplets (p, q, q ):

(4) No pertaining triplet is degenerate.

Note that the x of Proposition 5.15 can be effectively found. The case of L can be simply seen as the reversal of the previous case. Indeed, DA is also defined, over any alphabet A, by x ω = x ω • y • x ω with y ∈ alph(x). The definition of "pertaining" reflects these equations:

Definition 5.22. For an alphabet C, a triplet of states (p, q, q ) is C-pertaining if there are words s, u, t with alph(u) = C, a word z ∈ C * , and an integer n such that:

Further, a pertaining triplet is empty if, in the above picture, β = β = β = 1; it is left-empty if only β is empty, right-empty if only β is empty, full if none of β, β , β is empty, and degenerate in the other cases. (2) For all full C-pertaining triplets (p, q, q ), there exist x, y ∈ B * and ρ 1 , ρ 2 ∈ (B * ) 2 such that these three inclusions hold:

(3) For all empty C-pertaining triplets (p, q, q ):

) For all right-empty C-pertaining triplets (p, q, q ), there exist x, y ∈ B * and ρ 1 , ρ 2 ∈ (B * ) 2 such that:

) For all left-empty C-pertaining triplets (p, q, q ), there exist x, y ∈ B * and ρ 1 , ρ 2 ∈ (B * ) 2 such that: 5.3. Deciding Com-and Ab-continuity. The case of COM and AB is comparatively much simpler, in particular because these varieties are defined using a finite number of equations for each alphabet. However, the argument relies on different ideas:

Theorem 5.24. For V = COM, AB, it is decidable, given an unambiguous transducer, whether it realizes a V-continuous function.

Proof. We apply the Syncing Lemma. Its first point is clearly decidable. We reduce its second point to decidable properties about semilinear sets (see, e.g., [START_REF] Ginsburg | The Mathematical Theory of Context-Free Languages[END_REF]). We also rely on the notion of Parikh image, that is, the mapping Pkh : A * → N A such that Pkh(w) maps a ∈ A to the number of a's in the word w.

Since every AB-continuous function is COM-continuous (Proposition 4.6), the conditions to test for AB-continuity are included in those for COM-continuity-this can also be seen as a consequence of the fact that if u, v are words, Equ AB (u, v) = Equ COM (u, v).

Let τ : A * → B * be a given transducer. Consider an equation ab = ba and four states p, p , q, q of τ . Write u = τ p,p (ab) and v = τ q,q (ba). We ought to check, by the Syncing Lemma, the inclusion in

and is thus defined by a simple semilinear property. The input synchronizations themselves, e.g., τ •,p τ •,q , are rational relations, and their component-wise Parikh image is thus a semilinear set. Since the inclusion of semilinear sets is decidable, the inclusion of the second point of the Syncing Lemma is also decidable.

For AB, we should additionally check the equations a ω = 1. The reasoning is similar. Consider three states (p, p , q), and write x • u ω-1 • y for τ p,p (a ω ). By commutativity and the fact that u ω-1 acts as an inverse of u in the equations holding in AB, we have that (s, s , t, t ) ∈ Equ AB (x • u ω-1 • y, 1) iff s • t = AB s • u • t . This again reduces the inclusion of the second point of the Syncing Lemma to a decidable semilinear property.

Discussion

We presented a study of continuity in functional transducers, on the one hand focused on general statements (Section 3), on the other hand on continuity for classical varieties. The heart of this contribution resides in decidability properties (Section 5), although we also addressed natural and related questions in a systematic way (Section 4). We single out two main research directions.

First, there is a sharp contrast between the genericity of the Preservation and Syncing Lemma and the technicality of the actual proofs of decidability of continuity. To which extent can these be unified and generalized? We know of two immediate extensions: 1. the generic results of Section 3 readily apply to Boolean algebras of languages closed under quotient, a relaxation of the conditions imposed on varieties, and 2. Proposition 4.1 and Lemma 5.4 can be shown to also hold for the varieties G p of languages recognized by p-groups, hence G p -continuity is decidable for transducers. Beyond these two points, we do not know how to show decidability for G nil (which is the join of the G p ), and the surprising complexity of the equalizer sets for some Burnside varieties (e.g., the one defined by x 2 = x 3 , see the Remark on page 10) leads us to conjecture that continuity may be undecidable in that case, hence that no unified way to show the decidability of continuity exists.

Second, the notion of continuity may be extended to more general settings. For instance, departing from regular languages, it can be noted that every recursive function is continuous for the class of recursive languages. Another natural generalization consists in studying (V, W)-continuity, that is, the property for a function to map W-languages to V-languages by inverse image. This would provide more flexibility for a sufficient condition for cascades of languages (or stackings of circuits, or nestings of formulas) to be in a given variety.