Nathan Grosshans
email: nathan.grosshans@polytechnique.edu

The Power of Programs over Monoids in J

published or not. The documents may come

Introduction

In computational complexity theory, many hard still open questions concern relationships between complexity classes that are expected to be quite small in comparison to the mainstream complexity class P of tractable languages. One of the smallest such classes is NC 1 , the class of languages decided by Boolean circuits of polynomial length, logarithmic depth and bounded fan-in, a relevant and meaningful class, that has many characterisations but whose internal structure still mostly is a mystery. Indeed, among its most important subclasses, we count AC 0 , CC 0 and ACC 0 : all of them are conjectured to be different from each other and strictly within NC 1 , but despite many efforts for several decades, this could only be proved for the first of those classes.

In the late eighties, Barrington and Thérien [START_REF] Barrington | Finite monoids and the fine structure of NC 1[END_REF], building on Barrington's celebrated theorem [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1[END_REF], gave an interesting viewpoint on those conjectures, relying on algebraic automata theory. They defined the notion of a program over a monoid M : a sequence of instructions (i, f ), associating through function f some element of M to the letter at position i in the input of fixed length. In that way, the program outputs an element of M for every input word, by multiplying out the elements given by the instructions for that word; acceptance or rejection then depends on that outputted element. A language of words of arbitrary length is consequently recognised in a non-uniform fashion, by a sequence of programs over some fixed monoid, one for each possible input length; when that sequence is of polynomial length, it is said that the monoid p-recognises that language. Barrington and Thérien's discovery is that NC 1 and almost all of its significant subclasses can each be exactly characterised by p-recognition over monoids taken from some suitably chosen variety of finite monoids (a class of finite monoids closed under basic operations on monoids). For instance, NC 1 , AC 0 , CC 0 and ACC 0 correspond exactly to p-recognition by, respectively, finite monoids, finite aperiodic monoids, finite solvable groups and finite solvable monoids. Understanding the internal structure of NC 1 thus becomes a matter of understanding what finite monoids from some particular variety are able to p-recognise.

It soon became clear that regular languages play a central role in understanding p-recognition: McKenzie, Péladeau and Thérien indeed observed [START_REF] Mckenzie | NC 1 : The automata-theoretic viewpoint[END_REF] that finite monoids from a variety V and a variety W p-recognise the same languages if and only if they p-recognise the same regular languages. Otherwise stated, most conjectures about the internal structure of NC 1 can be reformulated as a statement about where one or several regular languages lie within that structure. This is why a line of previous works got interested into various notions of tameness, capturing the fact that for a given variety of finite monoids, p-recognition does not offer much more power than classical morphism-recognition when it comes to regular languages (see [START_REF] Péladeau | Classes de circuits booléens et variétés de monoïdes[END_REF][START_REF] Péladeau | Finite semigroup varieties defined by programs[END_REF][START_REF] Maciel | Programs over semigroups of dot-depth one[END_REF][START_REF] Straubing | When can one finite monoid simulate another? In Algorithmic Problems in Groups and Semigroups[END_REF][START_REF] Straubing | Languages defined with modular counting quantifiers[END_REF][START_REF] Tesson | Computational Complexity Questions Related to Finite Monoids and Semigroups[END_REF][START_REF] Lautemann | An algebraic point of view on the Crane Beach property[END_REF][START_REF] Grosshans | The power of programs over monoids in DA[END_REF]).

This paper is a contribution to an ongoing study of what regular languages can be p-recognised by monoids taken from "small" varieties, started with the author's Ph.D. thesis [START_REF] Grosshans | The limits of Nečiporuk's method and the power of programs over monoids taken from small varieties of finite monoids[END_REF]. In a previous paper by the author with McKenzie and Segoufin [START_REF] Grosshans | The power of programs over monoids in DA[END_REF], a novel notion of tameness was introduced and shown for the "small" variety of finite aperiodic monoids DA. This allowed them to characterise the class of regular languages p-recognised by monoids from DA as those recognised by so called quasi-DA morphisms and represented a first small step towards a new proof that the variety A of finite aperiodic monoids is tame. This is a statement equivalent to Furst's, Saxe's, Sipser's [START_REF] Furst | Parity, circuits, and the polynomialtime hierarchy[END_REF] and Ajtai's [1] well-known lower bound result about AC 0 . In [START_REF] Grosshans | The power of programs over monoids in DA[END_REF], the authors also observed that, while DA "behaves well" with respect to p-recognition of regular languages, the variety J, a subclass of DA, does, in contrast, "behave badly" in the sense that monoids from J do p-recognise regular languages that are not recognised by quasi-J morphisms. Now, J is a well-studied and fundamental variety in algebraic automata theory (see, e.g., [START_REF] Pin | Varieties Of Formal Languages[END_REF][START_REF] Pin | The dot-depth hierarchy, 45 years later[END_REF]), corresponding through classical morphism-recognition to the class of regular languages in which membership depends on the presence or absence of a finite set of words as subwords. This paper is a contribution to the understanding of the power of programs over monoids in J, a knowledge that certainly does not bring us closer to a new proof of the tameness of A (as we are dealing with a strict subvariety of DA), but that is motivated by the importance of J in algebraic automata theory and the unexpected power of programs over monoids in J. The results we present in this article are twofold: first, we exhibit a fine hierarchy within the class of languages p-recognised by monoids from J, depending on the length of those programs and on a parametrisation of J; second, we show that a whole class of regular languages, that form a subclass of dot-depth one languages [START_REF] Pin | The dot-depth hierarchy, 45 years later[END_REF], are p-recognised by monoids from J while, in general, they are not recognised by any quasi-J morphism. This class roughly corresponds to dot-depth one languages where detection of a given factor does work only when it does not appear too often as a subword. We actually even conjecture that this class of languages with additional positional modular counting (that is, letters can be differentiated according to their position modulo some fixed number) corresponds exactly to all those p-recognised by monoids in J, a statement that is interesting in itself for algebraic automata theory.

Organisation of the paper. Following the present introduction, Section 2 is dedicated to the necessary preliminaries. In Section 3, we present the results about the fine hierarchy and in Section 4 we expose the results concerning the regular languages p-recognised by monoids from J. Section 5 gives a short conclusion.

Note.

This article is based on unpublished parts of the author's Ph.D. thesis [START_REF] Grosshans | The limits of Nečiporuk's method and the power of programs over monoids taken from small varieties of finite monoids[END_REF].

Preliminaries

Various mathematical materials

We assume the reader is familiar with the basics of formal language theory, semigroup theory and recognition by morphisms, that we might designate by classical recognition; for those, we only specify some things and refer the reader to the two classical references of the domain by Eilenberg [START_REF] Eilenberg | Automata, Languages, and Machines, volume A[END_REF][START_REF] Eilenberg | Automata, Languages, and Machines[END_REF] and Pin [START_REF] Pin | Varieties Of Formal Languages[END_REF].

General notations and conventions. Let i, j ∈ N. We shall denote by [[i, j]] the set of all n ∈ N verifying i ≤ n ≤ j. We shall also denote by [i] the set [ [1, i]]. Given some set E, we shall denote by P(E) the powerset of E. All our alphabets and words will always be finite; the empty word will be denoted by ε.

Varieties and languages.

A variety of monoids is a class of finite monoids closed under submonoids, Cartesian product and morphic images. A variety of semigroups is defined similarly. When dealing with varieties, we consider only finite monoids and semigroups, each having an idempotent power, a smallest ω ∈ N >0 such that x ω = x 2ω for any element x. To give an example, the variety of finite aperiodic monoids, denoted by A, contains all finite monoids M such that, given ω its idempotent power, x ω = x ω+1 for all x ∈ M .

To each variety V of monoids or semigroups we associate the class L(V) of languages such that, respectively, their syntactic monoid or semigroup belongs to V. For instance, L(A) is well-known to be the class of star-free languages. Quasi V languages. If S is a semigroup we denote by S 1 the monoid S if S is already a monoid and S ∪ {1} otherwise.

The following definitions are taken from [START_REF] Pin | Some results on C-varieties[END_REF]. Let ϕ be a surjective morphism from Σ * to a finite monoid M . For all k consider the subset ϕ(Σ k ) of M (where Σ k is the set of words over Σ of length k). As M is finite there is a k such that ϕ(Σ 2k ) = ϕ(Σ k ). This implies that ϕ(Σ k ) is a semigroup. The semigroup given by the smallest such k is called the stable semigroup of ϕ. If S is the stable semigroup of ϕ, S 1 is called the stable monoid of ϕ. If V is a variety of monoids or semigroups, then we shall denote by QV the class of such surjective morphisms whose stable monoid or semigroup, respectively, is in V and by L(QV) the class of languages whose syntactic morphism is in QV.

Programs over monoids. Programs over monoids form a non-uniform model of computation, first defined by Barrington and Thérien [START_REF] Barrington | Finite monoids and the fine structure of NC 1[END_REF], extending Barrington's permutation branching program model [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1[END_REF]. Let M be a finite monoid and Σ an alphabet. A program P over M on Σ n is a finite sequence of instructions of the form (i, f ) where i ∈ [n] and f ∈ M Σ ; said otherwise, it is a word over ([n] × M Σ ). The length of P , denoted by |P |, is the number of its instructions. The program P defines a function from Σ n to M as follows. On input w ∈ Σ n , each instruction (i, f ) outputs the monoid element f (w i ). A sequence of instructions then yields a sequence of elements of M and their product is the output P (w) of the program. A language L ⊆ Σ n is consequently recognised by P whenever there exists F ⊆ M such that L = P -1 (F ).

A language L over Σ is recognised by a sequence of programs (P n ) n∈N over some finite monoid M if for each n, the program P n is on Σ n and recognises

L =n = L ∩ Σ n . We say (P n ) n∈N is of length s(n) for s : N → N whenever |P n | = s(n) for all n ∈ N and that it is of length at most s(n) whenever there exists α ∈ R >0 verifying |P n | ≤ α • s(n) for all n ∈ N.
For s : N → N and V a variety of monoids, we denote by P(V, s(n)) the class of languages recognised by sequences of programs over monoids in V of length at most s(n). The class P(V) = k∈N P V, n k is then the class of languages p-recognised by a monoid in V, i.e. recognised by sequences of programs over monoids in V of polynomial length.

The following is an important property of P(V).

Proposition 2.1 ([12, Corollary 3.5]). Let V be a variety of monoids, then P(V) is closed under Boolean operations.

Given two alphabets Σ and Γ, a Γ-program on Σ n for n ∈ N is defined just like a program over some finite monoid M on Σ n , except that instructions output letters from Γ and thus that the program outputs words over Γ. Let now L ⊆ Σ * and K ⊆ Γ * . We say that L program-reduces to K if and only if there exists a sequence (Ψ n ) n∈N of Γ-programs (the program-reduction) such that Ψ n is on Σ n and L =n = Ψ -1 n (K =|Ψn| ) for each n ∈ N. The following proposition shows closure of P(V) also under program-reductions. Proposition 2.2 ([7, Proposition 3.3.12 and Corollary 3.4.3]). Let Σ and Γ be two alphabets. Let V be a variety of monoids. Given K ⊆ Γ * in P(V, s(n)) for s : N → N and L ⊆ Σ * from which there exists a program-reduction to K of length t(n), for t : N → N, we have that L ∈ P(V, s(t(n))). In particular, when K is recognised (classically) by a monoid in V, we have that L ∈ P(V, t(n)).

Tameness and the variety J

We won't introduce any of the proposed notions of tameness but will only state that the main consequence for a variety of monoids V to be tame in the sense of [START_REF] Grosshans | The power of programs over monoids in DA[END_REF] is that P(V) ∩ Reg ⊆ L(QV). This consequence has far-reaching implications from a computational-complexity-theoretic standpoint when P(V) happens to be equal to a circuit complexity class. For instance, tameness for A implies that P(A) ∩ Reg ⊆ L(QA), which is equivalent to the fact that AC 0 does not contain the language MOD m of words over {0, 1} containing a number of 1s not divisible by m for any m ∈ N, m ≥ 2 (a central result in complexity theory [START_REF] Furst | Parity, circuits, and the polynomialtime hierarchy[END_REF]1]).

Let us now define the variety of monoids J. A finite monoid M of idempotent power ω belongs to J if and only if (xy) ω = (xy) ω x = y(xy) ω for all x, y ∈ M . It is a strict subvariety of the variety DA, containing all finite monoids M of idempotent power ω such that (xy) ω = (xy) ω x(xy) ω for all x, y ∈ M , itself a strict subvariety of A. The variety J is a "small" one, well within A.

We now give some specific definitions and results about J that we will use, based essentially on [START_REF] Klíma | Hierarchies of piecewise testable languages[END_REF], but also on [15, Chapter 4, Section 1].

For some alphabet Σ and each k ∈ N, let us define the equivalence relation ∼ k on Σ * by u ∼ k v if and only if u and v have the same set of k-subwords (subwords of length at most k), for all u, v ∈ Σ * . The relation ∼ k is a congruence of finite index on Σ * . For an alphabet Σ and a word u ∈ Σ * , we shall write u ¡ Σ * for the language of all words over Σ having u as a subword. In the following, we consider that ¡ has precedence over ∪ and ∩ (but of course not over concatenation).

We define the class of piecewise testable languages PT as the class of regular languages such that for every alphabet Σ, we associate to Σ * the set PT (Σ * ) of all languages over Σ that are Boolean combinations of languages of the form u ¡ Σ * where u ∈ Σ * . In fact, PT (Σ * ) is the set of languages over Σ equal to a union of ∼ k -classes for some k ∈ N (see [START_REF] Simon | Piecewise testable events[END_REF]). Simon showed [START_REF] Simon | Piecewise testable events[END_REF] that a language is piecewise testable if and only if its syntactic monoid is in J, i.e. PT = L(J).

We can define a hierarchy of piecewise testable languages in a natural way. For k ∈ N, let the class of k-piecewise testable languages PT k be the class of regular languages such that for every alphabet Σ, we associate to Σ * the set PT k (Σ * ) of all languages over Σ that are Boolean combinations of languages of the form u ¡ Σ * where u ∈ Σ * with |u| ≤ k. We then have that PT k (Σ * ) is the set of languages over Σ equal to a union of ∼ k -classes. Let us define J k the inclusion-wise smallest variety of monoids containing the quotients of Σ * by ∼ k for any alphabet Σ: we have that a language is k-piecewise testable if and only if its syntactic monoid belongs to J k , i.e. PT k = L(J k ). (See [9, Section 3].)

Fine Hierarchy

The first part of our investigation of the computational power of programs over monoids in J concerns the influence of the length of programs on their computational capabilities.

We say two programs over a same monoid on the same set of input words are equivalent if and only if they recognise the same languages. Tesson and Thérien proved in [START_REF] Tesson | The computing power of programs over finite monoids[END_REF] that for any monoid M in DA, there exists some k ∈ N such that for any alphabet Σ there is a constant c ∈ N >0 verifying that any program over M on Σ n for n ∈ N is equivalent to a program over M on Σ n of length at most c • n k . Since J ⊂ DA, any monoid in J does also have this property. However, this does not imply that there exists some k ∈ N working for all monoids in J, i.e. that P(J) collapses to P J, n k .

In this section, we show on the one hand that, as for DA, while P(J, s(n)) collapses to P(J) for any super-polynomial function s : N → N, there does not exist any k ∈ N such that P(J) collapses to P J, n k ; and on the other hand that P(J k ) does optimally collapse to P J k , n k/2 for each k ∈ N.

Strict hierarchy

Given k, n ∈ N, we say that σ is a k-selector over n if σ is a function of P([n]) [n] k that associates a subset of [n] to each vector in [n] k . For any sequence ∆ = (σ n ) n∈N such that σ n is a k-selector over n for each n ∈ N -a sequence we will call a sequence of k-selectors -, we set L ∆ = n∈N K n,σn , where for each n ∈ N, the language K n,σn is the set of words over {0, 1} of length (k + 1) • n that can be decomposed into k + 1 consecutive blocks u (1) , u (2) , . . . , u (k) , v of n letters where the first k blocks each contain 1 exactly once and uniquely define a vector ρ in [n] k , where for all i ∈ [k], ρ i is given by the position of the only 1 in u (i) (i.e. u (i) ρi = 1) and v is such that there exists j ∈ σ n (ρ) verifying that v j is 1. Observe that for any k-selector σ 0 over 0, we have K 0,σ0 = ∅.

We now proceed similarly to what has been done in Subsection 5.1 in [START_REF] Grosshans | The power of programs over monoids in DA[END_REF] to show, on one hand, that for all k ∈ N, there is a monoid M k in J 2k+1 such that for any sequence of k-selectors ∆, the language L ∆ is recognised by a sequence of programs over M k of length at most n k+1 ; and, on the other hand, that for all k ∈ N there is a sequence of k-selectors ∆ such that for any finite monoid M and any sequence of programs (P n ) n∈N over M of length at most n k , the language L ∆ is not recognised by (P n ) n∈N .

We obtain the following proposition; the proof can be found in Appendix A.

Proposition 3.1. For all k ∈ N, we have P J, n k ⊂ P J, n k+1 . More precisely, for all k ∈ N and d ∈ N, d ≤ k 2 -1, we have P J k , n d ⊂ P J k , n d+1 .

Collapse

Looking at Proposition 3.1, it looks at first glance rather strange that, for each k ∈ N, we can only prove strictness of the hierarchy inside P(J k ) up to exponent k 2 . We now show, in a way similar to Subsection 5.2 in [START_REF] Grosshans | The power of programs over monoids in DA[END_REF], that in fact P(J k ) does collapse to P J k , n k/2 for all k ∈ N, showing Proposition 3.1 to be optimal in some sense. Due to space constraints, we leave the proof to Appendix A. Proposition 3.2. Let k ∈ N. Let M ∈ J k and Σ be an alphabet. Then there exists a constant c ∈ N >0 such that any program over M on

Σ n for n ∈ N is equivalent to a program over M on Σ n of length at most c • n k/2 .
In particular, P(J k ) = P J k , n k/2 for all k ∈ N.

4 Regular Languages in P(J)

The second part of our investigation of the computational power of programs over monoids in J is dedicated to understanding exactly what regular languages can be p-recognised by monoids in J.

Non-tameness of J

It is shown in [START_REF] Grosshans | The power of programs over monoids in DA[END_REF] that P(J) ∩ Reg L(QJ), thus giving an example of a wellknown subvariety of A for which p-recognition allows to do unexpected things when recognising a regular language. How far does this unexpected power go?

The first thing to notice is that, though none of them is in L(QJ), all languages of the form Σ * u and uΣ * for Σ an alphabet and u ∈ Σ + are in P(J). Indeed, each of them can be recognised by a sequence of constant-length programs over the syntactic monoid of u ¡ Σ * : for every input length, just output the image, through the syntactic morphism of u ¡Σ * , of the word made of the |u| first or last letters. So, informally stated, programs over monoids in J can check for some constant-length beginning or ending of their input words.

But they can do much more. Indeed, the language (a + b) * ac + does not belong to L(QJ) (compute the stable monoid), yet it is in P(J). The crucial insight is that it can be program-reduced in linear length to the piecewise testable language of all words over {a, b, c} having ca as a subword but not the subwords cca, caa and cb by using the following trick (that we shall call "feedback-sweeping") for input length n ∈ N: read the input letters in the order 2, 1, 3, 2, 4, 3, 5, 4, . . . , n, n-1, output the letters read. This has already been observed in [8, Proposition 5]; here we give a formal proof of the following lemma, to be found in Appendix B.

Lemma 4.1. (a + b) * ac + ∈ P(J, n).
Using variants of the "feedback-sweeping" reading technique, we can prove that the phenomenon just described is not an isolated case. Hence, we are tempted to say that there are "much more" regular languages in P(J) than just those in L(QJ), even though it is not clear to us whether L(QJ) ⊆ P(J) or not. But can we show any upper bound on P(J) ∩ Reg? It turns out that we can, relying on two known results.

First, since J ⊆ DA, we have P(J) ⊆ P(DA), so Theorem 6 in [START_REF] Grosshans | The power of programs over monoids in DA[END_REF], that states P(DA) ∩ Reg = L(QDA), implies that P(J) ∩ Reg ⊆ L(QDA).

Second, let us define an important superclass of the class of piecewise testable languages. Let Σ be an alphabet and u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ); we define [u 1 , . . . , u k ] = Σ * u 1 Σ * • • • Σ * u k Σ * .
The class of dot-depth one languages is the class of Boolean combinations of languages of the form Σ * u, uΣ * and [u 1 , . . . , u k ] for Σ an alphabet, k ∈ N >0 and u, u 1 , . . . , u k ∈ Σ + . The inclusion-wise smallest variety of semigroups containing all syntactic semigroups of dot-depth one languages is denoted by J * D and verifies that L(J * D) is exactly the class of dot-depth one languages. (See [START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF][START_REF] Maciel | Programs over semigroups of dot-depth one[END_REF][START_REF] Pin | The dot-depth hierarchy, 45 years later[END_REF].) It has been shown in [START_REF] Maciel | Programs over semigroups of dot-depth one[END_REF]Corollary 8] that P(J * D) ∩ Reg = L(Q(J * D)) (if we extend the program-over-monoid formalism in the obvious way to finite semigroups). Now, we have J ⊆ J * D, so that P(J) ⊆ P(J * D) and hence P(J) ∩ Reg ⊆ L(Q(J * D)).

To summarise, we have the following.

Proposition 4.3. P(J) ∩ Reg ⊆ L(QDA) ∩ L(Q(J * D)).
In fact, we conjecture that the inverse inclusion does also hold.

Conjecture 1. P(J) ∩ Reg = L(QDA) ∩ L(Q(J * D)).
Why do we think this should be true? Though, for a given alphabet Σ, we cannot decide whether some word u ∈ Σ + of length at least 2 appears as a factor of any given word w in Σ * with programs over monoids in J (because Σ * uΣ * / ∈ L(QDA)), Lemma 4.2 and the possibilities offered by the "feedback-sweeping" technique give the impression that we can do it when we are guaranteed that u appears at most a fixed number of times in w, which seems somehow to be what dot-depth one languages become when restricted to belong to L(QDA). This intuition motivates the definition of threshold dot-depth one languages.

Threshold dot-depth one languages

The idea behind the definition of threshold dot-depth one languages is that we take the basic building blocks of dot-depth one languages, of the form [u 1 , . . . , u k ] for an alphabet Σ, for k ∈ N >0 and u 1 , . . . , u k ∈ Σ + , and restrict them so that, given l ∈ N >0 , membership of a word does really depend on the presence of a given word u i as a factor if and only if it appears less than l times as a subword. Definition 4.4. Let Σ be an alphabet. For all u ∈ Σ + and l ∈ N >0 , we define [u] l to be the language of words over Σ containing u l as a subword or u as a factor, i.e.

[u] l = Σ * uΣ * ∪ u l ¡Σ * . Then, for all u 1 , . . . , u k ∈ Σ + (k ∈ N, k ≥ 2) and l ∈ N >0 , we define [u 1 , . . . , u k ] l = [u 1 ] l • • • [u k ] l . Obviously, for each Σ an alphabet, k ∈ N >0 and u 1 , . . . , u k ∈ Σ + , the language [u 1 , . . . , u k ] 1 equals u 1 • • • u k ¡ Σ * .
Over {a, b, c}, the language [ab, c] 3 contains all words containing a letter c verifying that in the prefix up to that letter, ababab appears as a subword or ab appears as a factor. Finally, the language (a+b) * ac + over {a, b, c} of Lemma 4.

1 is equal to [c, a] 2 ∩[c, b] 2 ∩[ac] 2 .
We then define a threshold dot-depth one language as any Boolean combination of languages of the form Σ * u, uΣ * and [u 1 , . . . , u k ] l for Σ an alphabet, for k, l ∈ N >0 and u, u 1 , . . . , u k ∈ Σ + .

Confirming the intuition briefly given above, the technique of "feedbacksweeping" can indeed be pushed further to prove that the whole class of threshold dot-depth one languages is contained in P(J), and we dedicate the remainder of this section to prove it. Concerning Conjecture 1, our intuition leads us to believe that, in fact, the class of threshold dot-depth one languages with additional positional modular counting is exactly L(QDA) ∩ L(Q(J * D)). We simply refer the interested reader to Section 5.4 of the author's Ph.D. thesis [START_REF] Grosshans | The limits of Nečiporuk's method and the power of programs over monoids taken from small varieties of finite monoids[END_REF], that contains a partial result supporting this belief, too technical and long to be presented here.

Let us now move on to the proof of the following theorem.

Theorem 4.5. Every threshold dot-depth one language belongs to P(J).

As P(J) is closed under Boolean operations (Proposition 2.1), our goal is to prove, given an alphabet Σ, given l ∈ N >0 and u 1 , . . . , u k ∈ Σ + (k ∈ N >0 ), that [u 1 , . . . , u k ] l is in P(J); the case of Σ * u and uΣ * for u ∈ Σ + is easily handled (see the discussion at the beginning of Subsection 4.1). To do this, we need to put

[u 1 , . . . , u k ] l in some normal form. It is readily seen that [u 1 , . . . , u k ] l = q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k )
where the L (l) (ui,qi) 's are defined thereafter. Definition 4.6. Let Σ be an alphabet.

For all u ∈ Σ + , l ∈ N >0 and α ∈ [l], set L (l) (u,α) = Σ * uΣ * if α < l u l ¡ Σ * otherwise .
Building directly a sequence of programs over a monoid in J that decides

L (l) (u1,q1) • • • L (l) (u k ,q k )
for some alphabet Σ and q 1 , . . . , q k ∈ {1, l} seems however tricky. We need to split things further by controlling precisely how many times each u i for i ∈ [k] appears in the right place when it does less than l times. To do this, we consider, for each α ∈ [l] k , the language R α l (u 1 , . . . , u k ) defined below.

Definition 4.7. Let Σ be an alphabet.

For all u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ), l ∈ N >0 , α ∈ [l] k , we set R α l (u 1 , . . . , u k ) =(u 1 α1 • • • u k α k ) ¡ Σ * ∩ i∈[k],αi<l (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡ Σ * .
Now, for a given α ∈ [l] k , we are interested in the words of R α l (u 1 , . . . , u k ) such that for each i ∈ [k] verifying α i < l, the word u i indeed appears as a factor in the right place. We thus introduce a last language S α l (u 1 , . . . , u k ) defined as follows.

Definition 4.8. Let Σ be an alphabet.

For all u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ), l ∈ N >0 , α ∈ [l] k , we set S α l (u 1 , . . . , u k ) = i∈[k],αi<l (u 1 α1 • • • u i-1 αi-1 )¡Σ * u i (u i+1 αi+1 • • • u k α k )¡Σ * .
We now have the normal form we were looking for to prove Theorem 4.5: [u 1 , . . . , u k ] l is equal to the union, over all α ∈ [l] k , of the intersection of R α l (u 1 , . . . , u k ) and S α l (u 1 , . . . , u k ). Though rather intuitive, the correctness of this decomposition is not so straightforward to prove and, actually, we can only prove it when for each i ∈ [k], the letters in u i are all distinct. (The tedious proof is to be found in Appendix B.) Lemma 4.9. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ) such that for each i ∈ [k], the letters in u i are all distinct. Then, q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) = α∈[l] k R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) .
Our goal now is to prove, given an alphabet Σ, given l ∈ N >0 and u 1 , . . . , u k ∈ Σ + (k ∈ N >0 ) such that for each i ∈ [k], the letters in u i are all distinct, that for any α ∈ [l] k , the language R α l (u 1 , . . . , u k )∩S α l (u 1 , . . . , u k ) is in P(J); closure of P(J) under union (Proposition 2.1) consequently entails that [u 1 , . . . , u k ] l ∈ P(J). The way R α l (u 1 , . . . , u k ) and S α l (u 1 , . . . , u k ) are defined allows us to reason as follows. For each i ∈ [k] verifying α i < l, let L i be the language of words w over Σ containing x i,1 u i αi x i,2 as a subword but not x i,1 u i αi+1 x i,2

and such that w = y 1 u i y 2 with y 1 ∈ x i,1 ¡ Σ * and y 2 ∈ x i,2 ¡ Σ * , where

x i,1 = u 1 α1 • • • u i-1 αi-1 and x i,2 = u i+1 αi+1 • • • u k α k . If we manage to prove that for each i ∈ [k] verifying α i < l we have L i ∈ P(J), we can conclude that R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) = (u 1 α1 • • • u k α k ) ¡ Σ * ∩ i∈[k],αi<l L i does
belong to P(J) by closure of P(J) under intersection, Proposition 2.1. The lemma that follows, the main lemma in the proof of Theorem 4.5, exactly shows this. The proof crucially uses the "feedback sweeping" technique, but note that we actually don't know how to prove it when we do not enforce that for each i ∈ [k], the letters in u i are all distinct.

Lemma 4.10. Let Σ be an alphabet and u ∈ Σ + such that its letters are all distinct. For all α ∈ N >0 and x 1 , x 2 ∈ Σ * , we have

(x 1 u α x 2 ) ¡ Σ * ∩ (x 1 u α+1 x 2 ) ¡ Σ * ∩ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ) ∈ P(J) .
Sketch. Let Σ be an alphabet and u ∈ Σ + such that its letters are all distinct. Let α ∈ N >0 and x 1 , x 2 ∈ Σ * . We let

L = (x 1 u α x 2 ) ¡ Σ * ∩ (x 1 u α+1 x 2 ) ¡ Σ * ∩ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ) .
If |u| = 1, the lemma follows trivially because L is piecewise testable and hence belongs to L(J), so we assume |u| > 1.

For each letter a ∈ Σ, we shall use 2 |u| -1 distinct decorated letters of the form a (i) for some i ∈ [[0, 2 |u| -2]], using the convention that a (0) = a; of course, for two distinct letters a, b ∈ Σ, we have that a (i) and b (j) are distinct for all i, j ∈ [[0, 2 |u| -2]]. We denote by A the alphabet of these decorated letters. The main idea of the proof is, for a given input length n ∈ N, to build an A-program Ψ n over Σ n such that, given an input word w ∈ Σ n , it first ouputs the |u| -1 first letters of w and then, for each i going from |u| to n, outputs w i , followed by w

(1) i-1 • • • w (|u|-1)
i-|u|+1 (a "sweep" of |u|-1 letters backwards down to position i-|u|+ 1, decorating the letters incrementally) and finally by w

(|u|) i-|u|+2 • • • w (2|u|-2) i
(a "sweep" forwards up to position i, continuing the incremental decoration of the letters). The idea behind this way of rearranging and decorating letters is that, given an input word w ∈ Σ n , as long as we make sure that w and thus Ψ n (w) do contain x 1 u α x 2 as a subword but not x 1 u α+1 x 2 , then Ψ n (w) can be decomposed as Ψ n (w) = y 1 zy 2 where y 1 ∈ x 1 ¡Σ * , y 2 ∈ x 2 ¡Σ * , and

|y 1 | , |y 2 | are minimal, with z containing u β u (1) |u|-1 • • • u (|u|-1) 1 u (|u|) 2 • • • u (2|u|-2) |u| u α-β as a subword for some β ∈ [α] if and only if w ∈ (x 1 ¡ Σ * )u(x 2 ¡ Σ * )
. This means we can check whether w ∈ L by testing whether w belongs to some fixed piecewise testable language over A.

The full proof can be found in Appendix B.

As explained before stating the previous lemma, we can now use it to prove the result we were aiming for. The detailed proof can be found in Appendix B. Proposition 4.11. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ) such that for each i ∈ [k], the letters in u i are all distinct. For all α ∈ [l] k , we have R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , .
. . , u k ) ∈ P(J). We thus derive the awaited corollary. Corollary 4.12. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . , u k ∈ Σ + (k ∈ N >0 ) such that for each i ∈ [k], the letters in u i are all distinct. Then, [u 1 , . . . , u k ] l ∈ P(J).

However, what we really want to obtain is that [u 1 , . . . , u k ] l ∈ P(J) without putting any restriction on the u i 's. But, in fact, to remove the constraint that the letters must be all distinct in each of the u i 's, we simply have to decorate each of the input letters with its position minus 1 modulo a big enough d ∈ N >0 . This finally leads to the following proposition; as usual, the proof is in Appendix B. Proposition 4.13. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . ,

u k ∈ Σ + (k ∈ N >0 ). Then [u 1 , . . . , u k ] l ∈ P(J).
This finishes to prove Theorem 4.5 by closure of P(J) under Boolean combinations (Proposition 2.1) and by the discussion at the beginning of Subsection 4.1.

Conclusion

Although P(J) is very small compared to AC 0 , we have shown that programs over monoids in J are an interesting subject of study in that they allow to do quite unexpected things. The "feedback-sweeping" technique allows one to detect presence of a factor thanks to such programs as long as this factor does not appear too often as a subword: this is the basic principle behind threshold dot-depth one languages, that our article shows to belong wholly to P(J).

Whether threshold dot-depth one languages with additional positional modular counting do correspond exactly to the languages in L(QDA)∩L(Q(J * D)) seems to be a challenging question, that we leave open. In his Ph.D. thesis [START_REF] Grosshans | The limits of Nečiporuk's method and the power of programs over monoids taken from small varieties of finite monoids[END_REF], the author proved that all strongly unambiguous monomials (the basic building blocks in L(DA)) that are imposed to belong to L(J * D) at the same time are in fact threshold dot-depth one languages. However, the proof looks much too complex and technical to be extended to, say, all languages in L(DA) ∩ L(J * D). New techniques are probably needed, and we might conclude by saying that proving (or disproving) this conjecture could be a nice research goal in algebraic automata theory.

A Missing Proofs from Section 3

A.1 Proof of Proposition 3.1

Upper bound. We start with the upper bound. Given k ∈ N, we define the alphabet Y k = {e, #} ∪ {⊥ l , l | l ∈ [k]}; we are going to prove that for all k ∈ N there exists a language Z k ∈ PT 2k+1 (Y * k ) such that for all ∆ = (σ n ) n∈N sequences of k-selectors, there exists a program-reduction from L ∆ to Z k of length at most 2 • (k + 1) -k • n k+1 . To this end, we use the following proposition and the fact that the language of words of length n ∈ N of L ∆ is exactly K n ,σ n when there exists n ∈ N verifying n = (k + 1) • n and ∅ otherwise.

Proposition A.1. For all k ∈ N there is a language Z k ∈ PT 2k+1 (Y * k ) such that ε /
∈ Z k and for all n ∈ N and all k-selectors σ n over n, we have

K n,σn = Ψ -1 (k+1)•n,σn (Z =|Ψ (k+1)•n,σn | k ) where Ψ (k+1)•n,σn is a Y k -program on {0, 1} (k+1)•n of length at most 2 • (k + 1) • n k+1 .
Proof. We first define by induction on k a family of languages

Z k over the alphabet Y k . For k = 0, set Z 0 = Y * 0 #Y * 0 .
For k ∈ N >0 , the language Z k is the set of words containing each of k and ⊥ k exactly once, the first before the latter, and verifying that the factor between the occurrence of k and the occurrence of

⊥ k belongs to Z k-1 , i.e. Z k = Y * k-1 k Z k-1 ⊥ k Y * k-1 . A simple induction on k shows that Z k for k ∈ N is defined by the expression Y * k-1 k Y * k-2 k-1 • • • Y * 1 2 Y * 0 1 Y * 0 #Y * 0 ⊥ 1 Y * 0 ⊥ 2 Y * 1 • • • ⊥ k-1 Y * k-2 ⊥ k Y * k-1 ,
hence it belongs to PT 2k+1 (Y * k ) and in particular does not contain the empty word ε.

Fix n ∈ N. If n = 0, the proposition follows trivially since for any k-selector σ 0 over 0, we have K 0,σ0 = ∅ and ε / ∈ Z k ; otherwise, we define by induction on k a Y k -program P k (d, σ) on {0, 1} (d+k+1)•n for every k-selector σ over n and every d ∈ N.

For any j ∈ [n] and σ a 0-selector over n, which is just a function in P([n]) {ε} , let h j,σ : {0, 1} → Y 0 be the function defined by h j,σ (0) = e and h j,σ (1) = # if j ∈ σ(ε) e otherwise . For all k ∈ N >0 , we also let f k and g k be the functions in

Y k {0,1} defined by f k (0) = g k (0) = e, f k (1) = k and g k (1) = ⊥ k .
Moreover, for any k-selector σ over n, the symbol σ|j for j ∈ [n] denotes the (k -1)selector over n such that for all ρ ∈ [n] k-1 , we have i ∈ σ|j(ρ ) if and only if i ∈ σ((j, ρ )).

For k ∈ N >0 , for d ∈ N and σ a k-selector over n, the Y k -program P k (d, σ) on {0, 1} (d+k+1)•n is the following sequence of instructions:

(d • n + 1, f k )P k-1 (d + 1, σ|1)(d • n + 1, g k ) • • •(d • n + n, f k )P k-1 (d + 1, σ|n)(d • n + n, g k ) .
In words, for each position

i ∈ [[d • n + 1, d • n + n]
] with a 1 in the (d + 1)-th block of n letters in the input, the program runs, between the symbols k and ⊥ k , the program P k-1 (d + 1, σ|i) obtained by induction for σ|i the (k -1)-selector over n obtained by restricting σ to all vectors in [n] k whose first coordinate is i.

For k = 0, for d ∈ N and σ a 0-selector over n, the Y 0 -program P 0 (d, σ) on {0, 1} (d+1)•n is the following sequence of instructions:

(d • n + 1, h 1,σ )(d • n + 2, h 2,σ ) • • • (d • n + n, h n,σ ) .
In words, for each position

i ∈ [[d • n + 1, d • n + n]
] with a 1 in the (d + 1)-th block of n letters in the input, the program outputs # if and only if (i -d • n) does belong to the set σ(ε).

In short, P k (d, σ) is designed so that for any w ∈ {0, 1} (d+k+1)•n , the word P k (d, σ)(w) belongs to Z k if and only if the last (k + 1) • n letters of w form a word of K n,σ .

A simple computation shows that for any k ∈ N, any d ∈ N and σ a k-selector over n, the number of instructions in

P k (d, σ) is at most 2 • (k + 1) • n k+1 .
A simple induction on k shows that for any k ∈ N and d ∈ N, when running on a word w ∈ {0, 1} (d+k+1)•n , for any σ a k-selector over n, the program P k (d, σ) returns a word in Z k if and only if when u (1) , u (2) , . . . , u (k) , v are the last k + 1 consecutive blocks of n letters of w, then u (1) , u (2) , . . . , u (k) each contain 1 exactly once and define the vector ρ in [n] k where for all i ∈ [k], the value ρ i is given by the position of the only 1 in u (i) , verifying that there exists j ∈ σ n (ρ) such that v j is 1.

Therefore, for any k ∈ N and σ n a k-selector over n, if we set

Ψ (k+1)•n,σn = P k (0, σ n ), we have K n,σn = Ψ -1 (k+1)•n,σn (Z =|Ψ (k+1)•n,σn | k ) where Ψ (k+1)•n,σn is a Y k -program on {0, 1} (k+1)•n of length at most 2 • (k + 1) • n k+1 .
Consequently, for all k ∈ N and any sequence of k-selectors ∆, since the language Z k is in PT 2k+1 (Y * k ) and thus recognised by a monoid from J 2k+1 , we have, by Proposition 2.2, that L ∆ ∈ P J 2k+1 , n k+1 . Lower bound. For the lower bound, we use the following claim, whose proof can be found in [8, Claim 10].

Claim A.2. For all i ∈ N >0 and n ∈ N, the number of languages in {0, 1} n recognised by programs over a monoid of order i on {0, 1} n , with at most l ∈ N instructions, is upper-bounded by i

i 2 2 i • (n • i 2 ) l .
If for some k ∈ N and i ∈ [α] with α ∈ N >0 , we apply this claim for all n ∈ N and l = α • ((k + 1) • n) k , we get a number µ i (n) of languages in {0, 1} (k+1)•n recognised by programs over a monoid of order i on {0, 1} (k+1)•n with at most l instructions that is in 2 O(n k log 2 (n)) , which is asymptotically strictly smaller than the number of distinct K n,σn when the k-selector σ n over n varies, which is

2 n k+1 , i.e. µ i (n) is in o(2 n k+1 ).
Hence, for all j ∈ N >0 , there exist an n j ∈ N and τ j a k-selector over n j such that no program over a monoid of order i ∈ [j] on {0, 1} (k+1)•nj and of length at most j • ((k + 1) • n j ) k recognises K nj ,τj . Moreover, we can assume without loss of generality that the sequence (n j ) j∈N>0 is increasing. Let ∆ = (σ n ) n∈N be such that σ nj = τ j for all j ∈ N >0 and σ n : [n] k → P([n]), ρ → ∅ for any n ∈ N verifying that it is not equal to any n j for j ∈ N >0 . We show that no sequence of programs over a finite monoid of length O(n k ) can recognise L ∆ . If this were the case, then let i be the order of the monoid. Let j ∈ N, j ≥ i be such that for any n ∈ N, the n-th program has length at most j • n k . But, by construction, we know that there does not exist any such program on {0, 1} (k+1)•nj recognising K nj ,τj , a contradiction. This implies that for all k ∈ N, we have P J, n k ⊂ P J, n k+1 and additionally that for all d ∈ N, d ≤ k 2 -1, we have P J k , n d ⊂ P J k , n d+1 , since any monoid from J d is also a monoid from J k .

A.2 Proof of Proposition 3.2

Actually, the equivalent shorter program we give is even a subprogram of the original one, i.e. a subsequence of the latter. For P some program over a finite monoid M , we may denote by ξ P the function that associates to each possible input word w the word in M |P | obtained by successively evaluating the instructions of P for w.

Observe that given P a program over some finite monoid M on Σ n for n ∈ N and Σ an alphabet, a subprogram P of P is equivalent to P if and only if for every language K ⊆ M * recognised by the evaluation morphism η M of M , the unique morphism from M * to M extending the identity on M , we have ξ P (w) ∈ K ⇔ ξ P (w) ∈ K for all w ∈ Σ n . Moreover, every language recognised by η M is precisely a language of PT k (M * ) when M ∈ J k for some k ∈ N.

The result is hence a consequence of the following lemma and the fact that every language in PT k (M * ) is a union of ∼ k -classes, each of those classes corresponding to all words over M having the same set of k-subwords, that is finite.

Lemma A.3. Let Σ be an alphabet and M a finite monoid.

For all k ∈ N, there exists a constant c ∈ N >0 verifying that for any program P over M on Σ n for n ∈ N and any word t ∈ M k , there exists a subprogram Q of P of length at most c • n k/2 such that for any subprogram Q of P that has Q as a subprogram, we have that t is a subword of ξ P (w) if and only if t is a subword of ξ Q (w) for all w ∈ Σ n .

Proof. A program P over M on Σ n for n ∈ N is a finite sequence (p i , f i ) of instructions where each p i is a positive natural number which is at most n and each f i is a function from Σ to M . We denote by l the number of instructions of P . For each set I ⊆ [l] we denote by P [I] the subprogram of P consisting of the subsequence of instructions of P obtained after removing all instructions whose index is not in I. When I = [[i, j]] for some i, j ∈ [l], we may write

P [i, j] instead of P [I].
We prove the lemma by induction on k, fixing the constant to be

c k = k! • |Σ| k/2
for a given k ∈ N. The intuition behind the proof for a program P on inputs of length n and some t of length at least 3 is as follows. Given l the length of P , we will select a subset I of the indices of instructions numbered from 1 to l to obtain P [I] verifying the conditions of the lemma. Consider all the indices 1 ≤ i 1 < i 2 < • • • < i s ≤ l that each correspond, for some letter a and some position p in the input, to the first instruction of P that would output the element t 1 when reading a at position p or to the last instruction of P that would output the element t k when reading a at position p. We then have that, given some w as input, t is a subword of ξ P (w) if and only if there exist 1 ≤ γ < δ ≤ s verifying that the element at position i γ of ξ P (w) is t 1 , the element at position i δ of ξ P (w)

is t k and t 2 • • • t k-1 is a subword of ξ P [iγ +1,i δ -1] (w).
The idea is then that if we set I to contain i 1 , i 2 , . . . , i s as well as all indices obtained by induction for P [i j + 1, i j+1 -1] and t α • • • t β for all 1 ≤ j ≤ s -1 and 1 < α ≤ β < k, we would have that for all w, the word t is a subword of ξ P (w) if and only if it is a subword of ξ P [I] (w), that is ξ P (w) where only the elements at indices in I have been kept. The length upper bound of the order of n k/2 would be met because the number of possible values for j is s -1, hence at most linear in n, and the number of possible values for (α, β) is quadratic in k, a constant.

The intuition behind the proof when t is of length less than 3 is essentially the same, but without induction.

Inductive step. Let k ∈ N, k ≥ 3 and assume the lemma proven for all k ∈ N, k < k. Let P be a program over M on Σ n for n ∈ N of length l ∈ N and some word t ∈ M k .

Observe that when n = 0, we necessarily have P = ε, so that the lemma is trivially proven in that case. So we now assume n > 0.

For each p ∈ [n] and each a ∈ Σ consider within the sequence of instructions of P the first instruction of the form (p, f ) with f (a) = t 1 and the last instruction of that form with f (a) = t k , if they exist. We let I (1,k) be the set of indices of these instructions for all a and p. Notice that the size of

I (1,k) is at most 2 • |Σ| • n.
Let s = I (1,k) and let us denote

I (1,k) = {i 1 , i 2 , . . . , i s } where i 1 < i 2 < • • • < i s . Given α, β ∈ [k], we also set t (α,β) = t α t α+1 • • • t β . For all α, β ∈ [k] such that 1 < α ≤ β < k and j ∈ [s -1]
, we let J j,(α,β) be the set of indices of the instructions within P [i j + 1, i j+1 -1] appearing in its subprogram obtained by induction for P [i j + 1, i j+1 -1] and t (α,β) .

We now let I be the union of I (1,k) and J j,(α,β) = {e + i j | e ∈ J j,(α,β) } for all α, β ∈ [k] such that 1 < α ≤ β < k and j ∈ [s -1] (the translation being required because the first instruction in P [i j + 1, i j+1 -1] is the (i j + 1)-th instruction in P ). We claim that Q = P [I], a subprogram of P , has the desired properties.

First notice that by induction the size of J j,(α,β) for all α, β ∈

[k] such that 1 < α ≤ β < k and j ∈ [s -1] is upper bounded by (β -α + 1)! • |Σ| (β-α+1)/2 • n (β-α+1)/2 ≤ (k -2)! • |Σ| (k-2)/2 • n (k-2)/2 .
Hence, the size of I is at most

I (1,k) + s-1 j=1 1<α≤β<k J j,(α,β) ≤2 • |Σ| • n + (2 • |Σ| • n -1) • (k -1) • (k -2) 2 • (k -2)! • |Σ| (k-2)/2 • n (k-2)/2 ≤2 • |Σ| • n + (2 • |Σ| • n -1) • k • (k -1) 2 • (k -2)! • |Σ| (k-2)/2 • n (k-2)/2 ≤k! • |Σ| k/2 • n k/2 = c k • n k/2 as {(α, β) ∈ N 2 | 1 < α ≤ β < k} = k-1 j=2 (k -j) = k-2 j=1 j = (k-1)•(k-2) 2 and 2 • |Σ| • n ≤ k! 2 • |Σ| (k-2)/2
• n (k-2)/2 since k ≥ 3, so that P [I] has at most the required length.

Let Q be a subprogram of P that has Q as a subprogram: it means that there exists some set

I ⊆ [l] containing I such that Q = P [I ].
Take w ∈ Σ n . Assume now that t is a subword of ξ P (w). It means that there exist r 1 , r 2 , . . . ,

r k ∈ [l], r 1 < r 2 < • • • < r k , such that for all j ∈ [k], we have f rj (w pr j ) = t j . By definition of I (1,k) , there exist γ, δ ∈ [s], γ < δ, such that i γ ≤ r 1 < r k ≤ i δ and f iγ (w pi γ ) = t 1 and f i δ (w pi δ ) = t k . For each j ∈ [[γ, δ -1]], let m j ∈ [[2, k]] be the smallest integer in [[2, k -1]
] such that i j ≤ r mj < i j+1 and k if it does not exist, and

M j ∈ [[1, k -1]] be the biggest integer in [[2, k -1]] such that i j ≤ r Mj < i j+1 and 1 if it does not exist. Observe that, since for each j ∈ [[γ, δ -1]], we have t (mj ,Mj ) = t (k,1) = ε if there does not exist any o ∈ [[2, k -1]] verifying i j ≤ r o < i j+1 , it holds that t (2,k-1) = δ-1 j=γ t (mj ,Mj ) . For all j ∈ [[γ, δ -1]],
we have that for any set J ⊆ [i j+1 -i j -1] containing 1<α≤β<k J j,(α,β) , the word t (mj ,Mj ) is a subword of f ij (w pi j )ξ P [ij +1,ij+1-1][J] (w) when m j < k and r mj = i j , and of ξ

P [ij +1,ij+1-1][J] (w) otherwise. Indeed, let j ∈ [[γ, δ -1]].
• If m j < k and r mj = i j , then f ij (w pi j ) = f rm j (w pr m j ) = t mj and

i j = r mj < r mj +1 < • • • < r Mj < i j+1 , so t (mj +1,Mj ) is a subword of ξ P [ij +1,ij+1-1] (w).
This implies, directly when m j = M j or by induction otherwise, that for any set J ⊆ [i j+1 -i j -1] containing 1<α≤β<k J j,(α,β) , the word

t (mj +1,Mj ) is a subword of ξ P [ij +1,ij+1-1][J] (w). This implies in turn that t (mj ,Mj ) is a subword of f ij (w pi j )ξ P [ij +1,ij+1-1][J] (w).
• Otherwise, when

m j = k, there does not exist any o ∈ [[2, k -1]] verifying i j ≤ r o < i j+1 , so t (mj ,Mj ) = ε is trivially a subword of ξ P [ij +1,ij+1-1][J] (w)
for any set J ⊆ [i j+1 -i j -1] containing 1<α≤β<k J j,(α,β) . And when m j < k but r mj = i j , it means that r mj > i j , hence i j < r mj < r mj +1 < • • • < r Mj < i j+1 , so t (mj ,Mj ) is a subword of ξ P [ij +1,ij+1-1] (w). This implies, by induction, that t (mj ,Mj ) is a subword of ξ P [ij +1,ij+1-1][J] (w) for any set J ⊆ [i j+1 -i j -1] containing 1<α≤β<k J j,(α,β) .

Therefore, using the convention that i 0 = 0 and i s+1 = l + 1, if we define, for each j ∈ [[0, s]], the set I j = {e -i j | e ∈ I , i j < e < i j+1 } as the subset of I of elements strictly between i j and i j+1 translated by -i j , we have that t (2,k-1) is a subword of

ξ P [iγ +1,iγ+1-1][I γ ] (w)f iγ+1 (w pi γ+1 )ξ P [iγ+1+1,iγ+2-1][I γ+1 ] (w) • • • f i δ-1 (w pi δ-1 )ξ P [i δ-1 +1,i δ -1][I δ-1 ] (w) (since we have r mγ ≥ r 2 > r 1 ≥ i γ ), so that, as f iγ (w pi γ ) = t 1 and f i δ (w pi δ ) = t k , we have that t = t 1 t (2,k-1) t k is a subword of ξ P [1,i1-1][I 0 ] (w)f i1 (w pi 1 )ξ P [i1+1,i2-1][I 1 ] (w) • • • f is (w pi s )ξ P [is+1,l][I s ] (w) =ξ P [I ] (w) .
Assume finally that t is a subword of ξ P [I ] (w). Then it is obviously a subword of ξ P (w), as ξ P [I ] (w) is a subword of ξ P (w).

Therefore, t is a subword of ξ P (w) if and only if t is a subword of ξ Q (w) = ξ P [I ] (w), as desired.

Base case. There are three subcases to consider.

Subcase k = 2. Let P be a program over M on Σ n for n ∈ N of length l ∈ N and some word t ∈ M 2 .

We use the same idea as in the inductive step.

Observe that when n = 0, we necessarily have P = ε, so that the lemma is trivially proven in that case. So we now assume n > 0.

For each p ∈ [n] and each a ∈ Σ consider within the sequence of instructions of P the first instruction of the form (p, f ) with f (a) = t 1 and the last instruction of that form with f (a) = t 2 , if they exist. We let I be the set of indices of these instructions for all a and p. Notice that the size of

I is at most 2 • |Σ| • n = 2! • |Σ| 2/2 • n 2/2 = c 2 • n 2/2
. We claim that Q = P [I], a subprogram of P , has the desired properties. We just showed it has at most the required length.

Let Q be a subprogram of P that has Q as a subprogram: it means that there exists some set

I ⊆ [l] containing I such that Q = P [I ].
Take w ∈ Σ n . Assume now that t is a subword of ξ P (w). It means there exist

i 1 , i 2 ∈ [l], i 1 < i 2 such that f i1 (w pi 1 ) = t 1 and f i2 (w pi 2 ) = t 2 . By definition of I, there exist i 1 , i 2 ∈ I, such that i 1 ≤ i 1 < i 2 ≤ i 2 and f i1 (w p i 1 ) = t 1 and f i2 (w p i 2 ) = t 2 . Hence, as f i1 (w p i 1 )f i2 (w p i 2 ) is a subword of ξ P [I ] (w) (because I ⊆ I ), we get that t = t 1 t 2 is a subword of ξ P [I ] (w).
Assume finally that t is a subword of ξ P [I ] (w). Then it is obviously a subword of ξ P (w), as ξ P [I ] (w) is a subword of ξ P (w).

Therefore, t is a subword of ξ P (w) if and only if t is a subword of ξ Q (w) = ξ P [I ] (w), as desired.

Subcase k = 1. Let P be a program over M on Σ n for n ∈ N of length l ∈ N and some word t ∈ M 1 .

We again use the same idea as before.

Observe that when n = 0, we necessarily have P = ε, so that the lemma is trivially proven in that case. So we now assume n > 0.

For each p ∈ [n] and each a ∈ Σ consider within the sequence of instructions of P the first instruction of the form (p, f ) with f (a) = t 1 , if it exists. We let I be the set of indices of these instructions for all a and p. Notice that the size of

I is at most |Σ| • n = 1! • |Σ| 1/2 • n 1/2 = c 1 • n 1/2
. We claim that Q = P [I], a subprogram of P , has the desired properties. We just showed it has at most the required length.

Let Q be a subprogram of P that has Q as a subprogram: it means that there exists some set

I ⊆ [l] containing I such that Q = P [I ].
Take w ∈ Σ n . Assume now that t is a subword of ξ P (w). It means there exists i ∈ [l] such that f i (w pi ) = t 1 . By definition of I, there exists i ∈ I such that i ≤ i and

f i (w p i ) = t 1 . Hence, as f i (w p i ) is a subword of ξ P [I ] (w) (because I ⊆ I), we get that t = t 1 is a subword of ξ P [I ] (w).
Assume finally that t is a subword of ξ P [I ] (w). Then it is obviously a subword of ξ P (w), as ξ P [I ] (w) is a subword of ξ P (w).

Therefore, t is a subword of ξ P (w) if and only if t is a subword of ξ Q (w) = ξ P [I ] (w), as desired.

Subcase k = 0. Let P be a program over M on Σ n for n ∈ N of length l ∈ N and some word t ∈ M 0 . of caa, cba and cca is a subword of Ψ n (w), in both cases contradicting the fact Ψ n (w) belongs to L. Hence, we indeed have j = i -1, and in particular that i ≥ 2. Now, by construction, for each t ∈ [i -2], we have that w t w i w i-1 = w t ca is a subword of Ψ n (w) ∈ L, so that w t cannot be equal to c. Similarly, for each t ∈ [[i + 1, n]], we have that w i w i-1 w t = caw t is a subword of Ψ n (w) ∈ L, so that w t must be equal to c. This means that w

1 • • • w i-2 ∈ (a + b) * and w i+1 • • • w n ∈ c * , so that w ∈ (a + b) * acc * = (a + b) * ac + . Since this is true for all w ∈ Ψ -1 n (L =s(n) ), it follows that ((a + b) * ac + ) =n ⊇ Ψ -1 n (L =s(n) ). Therefore, we have that ((a + b) * ac + ) =n = Ψ -1 n (L =s(n) ) for all n ∈ N, so (Ψ n ) n∈N is a program reduction from (a + b) * ac + to L of length s(n). So since L ∈ L(J), we can conclude that (a + b) * ac + ∈ P(J, s(n)) = P(J, n) by Proposition 2.2.

B.2 Proof of Lemma 4.9

Proof of Lemma 4.9. Let Σ be an alphabet and l ∈ N >0 . We prove it by induction on k ∈ N >0 .

Base case k = 1. Let u 1 ∈ Σ + such that the letters in u 1 are all distinct. It is clear that q1∈{1,l} L (l) (u1,q1) =(Σ * u 1 Σ * ∪ u 1 l ¡ Σ * ) = l-1 α1=1 u 1 α1 ¡ Σ * ∩ (u 1 α1+1 ¡ Σ * ) ∩ Σ * u 1 Σ * ∪ (u 1 l ¡ Σ * ) = α1∈[l] R α1 l (u 1 ) ∩ S α1 l (u 1 ) .
Induction. Let k ∈ N >0 and assume that for all u 1 , . . . , u k ∈ Σ + such that for each i ∈ [k], the letters in u i are all distinct, we have q1,...,q k ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k ,q k ) = α∈[l] k R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) . Let now u 1 , . . . , u k+1 ∈ Σ + such that for each i ∈ [k + 1], the letters in u i are all distinct. Right-to-left inclusion. Let w ∈ α∈[l] k+1 R α l (u 1 , . . . , u k+1 ) ∩ S α l (u 1 , . . . , u k+1 ) .
Let α ∈ [l] k+1 witnessing this fact. As w ∈ R α l (u 1 , . . . , u k+1 ), we can decompose it as w = xy where x ∈ (u

1 α1 • • • u k α k ) ¡ Σ * and y ∈ u k+1 α k+1 ¡ Σ * with
|y| being minimal. What we are going to do is, on the one hand, to prove that x ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) where α = (α 1 , . . . , α k ), so that we can apply the inductive hypothesis on x and get that there exist q 1 , . . . , q k ∈ {1, l}

such that x ∈ L (l) (u1,q1) • • • L (l) (u k ,q k )
; and, on the other hand, we are going to prove that there exists q k+1 ∈ {1, l} verifying y ∈ L (l) (u k+1 ,q k+1 ) . We now spell out the details.

For

each i ∈ [k], α i < l, we have x / ∈ (u 1 α1 • • • u i αi+1 • • • u k α k )¡Σ * , otherwise we would have w = xy ∈ (u 1 α1 • • • u i αi+1 • • • u k+1 α k+1 ) ¡ Σ * . Also, for all i ∈ [k], α i < l, we have that x ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * , otherwise it would mean that y = y 1 y 2 with |y 1 | > 0, that xy 1 ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * and y 2 ∈ u k+1 α k+1 ¡ Σ * , contra- dicting the minimality of |y|. So x ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k )
, which means by inductive hypothesis that there exist q 1 , . . . , q k ∈ {1, l} such that

x ∈ L (l) (u1,q1) • • • L (l) (u k ,q k ) . Remember now that the letters in u k+1 are all distinct. If α k+1 < l, since w ∈ (u 1 α1 . . . u k α k ) ¡ Σ * u k+1 Σ * , we must have y ∈ Σ * u k+1 Σ * .
Indeed, by minimality of |y|, the word y starts with the first letter of u k+1 , which has pairwise distinct letters, so that u k+1 cannot appear as a factor of xy partly in x and partly in y; so if it were the case that y does not contain u k+1 as a factor, we would have

x ∈ (u 1 α1 . . . u k α k ) ¡ Σ * u k+1 Σ * , so that xy = w ∈ (u 1 α1 . . . u k α k u k+1 α k+1 +1
) ¡ Σ * , a contradiction with the hypothesis on w.

Hence, y ∈ L (l) (u k+1 ,α k+1 ) . If α k+1 = l, then y ∈ u k+1 α k+1 ¡ Σ * = L (l) (u k+1 ,α k+1 ) .
So, if we set q k+1 = 1 if α k+1 < l l otherwise , then we get that y ∈ L

(u k+1 ,q k+1 ) .

We can conclude that

w = xy ∈ L (l) (u1,q1) • • • L (l) (u k ,q k ) L (l) (u k+1 ,q k+1 ) . Left-to-right inclusion. Let w ∈ q1,...,q k+1 ∈{1,l} L (l) (u1,q1) • • • L (l) (u k+1 ,q k+1 )
. The rough idea of our proof here is to take (u 1 , . . . , u k+1 ) by distinguishing between the case in which α k+1 = l and the case in which α k+1 < l. The first one is easy to handle, the second one is much trickier.

α k+1 ∈ [l] the biggest integer in [l] such that w ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) ) (u k+1 α k+1 ¡ Σ * )
We now spell out the details.

• Suppose we have w ∈ q1,...,q k ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k ,q k ) L (l) (u k+1 ,l) = q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 l ¡ Σ * ) .
Then w can be decomposed as w = xy where x ∈ q1,...,q k ∈{1,l} L

(l) (u1,q1) • • • L (l) (u k ,q k )
and y ∈ u k+1 l ¡Σ * with |y| being minimal. So by inductive hypothesis, there exists α ∈ [l] k such that x ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ). Observe that this means we have w ∈ (u

1 α1 • • • u k α k u k+1 l ) ¡ Σ * and for each i ∈ [k], α i < l, that w / ∈ (u 1 α1 • • • u i αi+1 • • • u k α k u k+1 l ) ¡ Σ * , other- wise it would mean that x ∈ (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡Σ * by minimality of |y|.
Similarly, for all i ∈ [k], α i < l, it is obvious that we have (u 1 , . . . , u k+1 ).

w = xy ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k u k+1 l ) ¡ Σ * as x ∈ (u 1 α1 • • • u i-1 αi-1 )¡Σ * u i (u i+1 αi+1 • • • u k α k )
• Or we have w / ∈ q1,...,q k ∈{1,l} 1) .

L (l) (u1,q1) • • • L (l) (u k ,q k ) L (l) (u k+1 ,l) = q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 l ¡ Σ * ) but w ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) L (l) (u k+1 ,
Let

α k+1 ∈ [l -1] be the biggest integer in [l -1] such that w ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 α k+1 ¡ Σ * )
which does exist by hypothesis. We can decompose w as w = xy where x ∈ q1,...,q k ∈{1,l} L (u 1 , . . . , u k+1 ) .

(l) (u1,q1) • • • L (l) (u k ,q k ) and y ∈ u k+1 α k+1 ¡ Σ * with |y|
Among the obvious things to observe is that we have w ∈ (u

1 α1 • • • u k α k u k+1 α k+1 ) ¡ Σ * and for each i ∈ [k], α i < l, that w / ∈ (u 1 α1 • • • u i αi+1 • • • u k α k u k+1 α k+1 ) ¡ Σ * , otherwise it would mean that x ∈ (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡ Σ * by min- imality of |y|.
Similarly, for all i ∈ [k], α i < l, it is obvious that we have

w = xy ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k u k+1 α k+1 ) ¡ Σ * because x ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * and y ∈ u k+1 α k+1 ¡ Σ * .
Now let us show that we have y ∈ Σ * u k+1 Σ * . Assume it weren't the case: the letters in u k+1 are pairwise distinct and moreover y starts with the first letter of u k+1 by minimality of |y|, so u k+1 cannot appear as a factor of xy partly in x and partly in y and, additionally, w ∈ q1,...,q k ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k ,q k ) L (l) (u k+1 ,1) = q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) Σ * u k+1 Σ * , so we would have x ∈ ( q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l)
(u k ,q k ) )Σ * u k+1 Σ * . But this either contradicts the maximality of α k+1 or the fact that w / ∈ q1,...,q k ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 l ¡ Σ * ) .
Thus, we have w = xy ∈ (u

1 α1 • • • u k α k ) ¡ Σ * u k+1 Σ * as x ∈ (u 1 α1 • • • u k α k ) ¡ Σ * .
Let us finish with the trickiest part, namely showing that w / ∈ (u

1 α1 • • • u k α k u k+1 α k+1 +1 ) ¡Σ * . Assume that w ∈ (u 1 α1 • • • u k α k u k+1 α k+1 +1 ) ¡Σ * .
We then have that x ∈ (u

1 α1 • • • u k α k u k+1 ) ¡ Σ * , otherwise it would mean that y = y 1 y 2 with |y 1 | > 0, with xy 1 ∈ (u 1 α1 • • • u k α k u k+1 ) ¡
Σ * and y 2 ∈ u k+1 α k+1 ¡ Σ * , contradicting the minimality of |y|. We can decompose x as x = x 1 x 2 where

x 1 ∈ (u 1 α1 • • • u k α k ) ¡ Σ * and x 2 ∈ u k+1 ¡ Σ * with |x 2 | being minimal. We claim that, actually, x 1 ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ), so that by inductive hypothesis, x 1 ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) . But since x 2 y ∈ u k+1 α k+1 +1 ¡ Σ * , this means that w = x 1 x 2 y ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 α k+1 +1 ¡ Σ * ) ,
contradicting the maximality of α k+1 or the fact that w / ∈ q1,...,q k ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k ,q k ) (u k+1 l ¡ Σ * ) .
So we can conclude that w / ∈ (u

1 α1 • • • u k α k u k+1 α k+1 +1 ) ¡ Σ * .
The claim that x 1 ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) remains to be shown. We directly see that

x 1 / ∈ (u 1 α1 • • • u i αi+1 • • • u k α k )¡Σ * for all i ∈ [k], α i < l, otherwise it would mean that x ∈ (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡ Σ * . Let now i ∈ [k], α i < l, and assume that x 1 / ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * . We can decompose x 1 as x 1 = x 1,1 x 1,2 where x 1,1 ∈ (u 1 α1 • • • u i αi ) ¡ Σ * and x 1,2 ∈ (u i+1 αi+1 • • • u k α k ) ¡ Σ * with |x 1,1 |
being minimal. By hypothesis, we have

x 1,1 / ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡
Σ * u i Σ * , otherwise we would have

x 1 = x 1,1 x 1,2 ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * .
As previously, the letters in u i are pairwise distinct, and x 1,1 ends with the last letter of u i by minimality of |x 1,1 |, so u i cannot appear as a factor of x partly in x 1,1 and partly in x 1,2 x 2 . Thus, we have that

x 1,2 x 2 ∈ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * because we know that x ∈ (u 1 α1 • • • u i-1 αi-1 )¡Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * . But this means that x = x 1,1 x 1,2 x 2 ∈ (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡
Σ * , a contradiction. Hence, we can deduce that for all i ∈

[k], α i < l, we have x 1 ∈ (u 1 α1 • • • u i-1 αi-1 ) ¡Σ * u i (u i+1 αi+1 • • • u k α k ) ¡Σ * . This finishes to show that x 1 ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) .
Putting all together, we indeed also have that

w ∈ R (α1,...,α k+1 ) l (u 1 , . . . , u k+1 ) ∩ S (α1,...,α k+1 ) l (u 1 , . . . , u k+1 )
in the present case.

In conclusion, in both cases,

w ∈ α∈[l] k+1 R α l (u 1 , . . . , u k+1 ) ∩ S α l (u 1 , . . . , u k+1 ) .
So we can finally conclude that q1,...,q k+1 ∈{1,l}

L (l) (u1,q1) • • • L (l) (u k+1 ,q k+1 ) = α∈[l] k+1 R α l (u 1 , . . . , u k+1 ) ∩ S α l (u 1 , . . . , u k+1 ) .
This concludes the proof of the lemma.

B.3 Proof of Lemma 4.10

Before proving Lemma 4.10, we need a useful decomposition lemma, that is straightforward to prove.

Lemma B.1. Let Σ be an alphabet and u ∈ Σ + . Then, for all α ∈ N >0 , each

w ∈ u α ¡ Σ * ∩ (u α+1 ¡ Σ * ) verifies w = α i=1 |u| j=1 (v i,j u j ) y
where v i,j ∈ (Σ \ {u j }) * for all i ∈ [α] and j ∈ [|u|], and y ∈

|u| i=1 i-1 j=1 (Σ \ {u j }) * u j (Σ \ {u i }) * .
Proof. Let Σ be an alphabet and u ∈ Σ + . Take α ∈ N >0 and w ∈ u α ¡ Σ * ∩ (u α+1 ¡ Σ * ) . As w ∈ u α ¡ Σ * , the word w can be decomposed as w = xy where x ∈ u α ¡ Σ * and |x| is minimal. Then, it is clearly necessarily the case that

x = α i=1 |u| j=1 (v i,j u j ) with v i,j ∈ (Σ \ {u j }) * for all i ∈ [α] and j ∈ [|u|]. Moreover, as xy / ∈ u α+1 ¡ Σ * , we necessarily have that y / ∈ u ¡ Σ * , so that there exists some i ∈ [|u|] verifying that u 1 • • • u i-1 is a subword of y but not u 1 • • • u i . Thus, we have that y ∈ i-1 j=1 (Σ \ {u j }) * u j (Σ \ {u i }) * . This concludes the proof.
We can now prove Lemma 4.10.

Proof of Lemma 4.10. Let Σ be an alphabet and u ∈ Σ + such that its letters are all distinct. Let α ∈ N >0 and x 1 , x 2 ∈ Σ * . We let

L = (x 1 u α x 2 ) ¡ Σ * ∩ (x 1 u α+1 x 2 ) ¡ Σ * ∩ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ) .
If |u| = 1, the lemma follows trivially because L is piecewise testable and hence belongs to L(J), so we assume |u| > 1.

For each letter a ∈ Σ, we shall use 2 |u| -1 distinct decorated letters of the form a (i) for some i ∈ [[0, 2 |u| -2]], using the convention that a (0) = a; of course, for two distinct letters a, b ∈ Σ, we have that a (i) and b (j) are distinct for all i, j ∈ [[0, 2 |u| -2]]. We denote by A the alphabet of these decorated letters.

For each

i ∈ [[0, 2 |u| -2]], let f (i) : Σ → A a → a (i)
.

For all i ∈ N, i ≥ |u|, we define

Φ i = (i, f (0) ) |u|-1 j=1 (i -j, f (j) ) |u| j=2 (i -|u| + j, f (|u|+j-2) ) .
For all n ∈ N, n < |u|, we define Ψ n = ε. For all n ∈ N, n ≥ |u|, we define

Ψ n = |u|-1 i=1 (i, f (0) ) n i=|u| Φ i .
Finally, let K be the language of words over A having

ζ β = x 1 u β-1 u |u|-1 j=1 u (j) |u|-j |u| j=2 u (|u|+j-2) j u α-β x 2
for some β ∈ [α] as a subword but not x 1 u α+1 x 2 .

Claim B.2. The sequence (Ψ n ) n∈N of A-programs is a program-reduction from L to K.

Let

s : N → N n → 0 if n < |u| |u| -1 + (n -|u| + 1) • (2 |u| -1) otherwise . It is direct to see that s(n) = |Ψ n | ≤ (2 |u| -1) • n for all n ∈ N.
Therefore, using this claim, (Ψ n ) n∈N is a program-reduction from L to K of length s(n), so since K is piecewise testable and hence is recognised (classically) by some monoid from J, Proposition 2.2 tells us that L ∈ P(J, s(n)) = P(J, n).

Proof of claim. Let n ∈ N. If n < |u|, then it is obvious that for all w ∈ Σ n , we have w / ∈ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ) so w / ∈ L =n and also Ψ n (w) = ε / ∈ K =s(n) , hence L =n = ∅ = Ψ -1 n (K =s(n) ). Otherwise, n ≥ |u|. We are going to show that L =n = Ψ -1 n (K =s(n) ).
Left-to-right inclusion. Let w ∈ L =n . We want to show that Ψ n (w) ∈ K =s(n) . We are first going to show that there exists some β ∈ [α] such that ζ β is a subword of Ψ n (w). The fact that w ∈ L =n means in particular that w ∈ j=1 (Σ \ {u j }) * u j (Σ \ {u i }) * . We know the letters in u are all distinct, so this means that there is no β ∈ [α -1] such that u is a factor of z partly in |u| j=1 (v β,j u j ) and partly in |u| j=1 (v β+1,j u j ), and that u cannot appear as a factor of z partly in |u| j=1 (v α,j u j ) and partly in y either. Hence, since z ∈ Σ * uΣ * , by the way we decomposed z, there necessarily exists β ∈

[α] such that |u| j=1 (v β,j u j ) ∈ Σ * uΣ * . Let γ, δ ∈ [n] such that w γ • • • w δ = |u| j=1 (v β,j u j ), w 1 • • • w γ-1 = y 1 β-1 i=1 |u| j=1 (v i,j u j ) and w δ+1 • • • w n = α i=β+1 |u| j=1 (v i,j u j ) yy 2 .
By the way β is defined, we have w δ-|u|+1 • • • w δ = u, because δ is the first and only position in w with the letter

u |u| within the interval [[γ, δ]] verifying that w γ • • • w δ-1 contains u 1 • • • u |u|-1
as a subword, and we observe additionally that δ ≥ γ + |u| -1 ≥ |u|. This means that

Φ δ (w) =f (0) (w δ )f (1) (w δ-1 ) • • • f (|u|-1) (w δ-|u|+1 )f (|u|) (w δ-|u|+2 ) • • • f (2|u|-2) (w δ ) =u |u| |u|-1 j=1 u (j) |u|-j |u| j=2 u (|u|+j-2) j . Moreover, γ-1 i=1 f (0) (w i ) = w 1 • • • w γ-1 = y 1 β-1 i=1 |u| j=1 (v i,j u j ) , δ-1 i=δ-|u|+1 f (0) (w i ) = w δ-|u|+1 • • • w δ-1 = u 1 • • • u |u|-1 and n i=δ+1 f (0) (w i ) = w δ+1 • • • w n = α i=β+1 |u| j=1 (v i,j u j ) yy 2 .

So as

γ-1 i=1 (i, f (0) ) δ-1 i=δ-|u|+1 (i, f (0) )Φ δ n i=δ+1 (i, f (0)
) is a subword of Ψ n , we have that

ζ β = x 1 u β-1 u |u|-1 j=1 u (j) |u|-j |u| j=2 u (|u|+j-2) j u α-β x 2
is a subword of Ψ n (w).

We secondly show that x 1 u α+1 x 2 cannot be a subword of Ψ n (w). But this is direct by construction of Ψ n , otherwise we would have that x 1 u α+1 x 2 is a subword of w, contradicting the fact that w ∈ L =n . Hence, Ψ n (w) ∈ K =s(n) , and since this is true for all w ∈ L =n , we have L =n ⊆ Ψ -1 n (K =s(n) ).

Right-to-left inclusion. We are going to prove the "contrapositive inclusion". Let w ∈ Σ n \ L =n . We want to show that Ψ n (w) / ∈ K =s(n) . Let us start with the easy cases. If we have w / ∈ (x 1 u α x 2 ) ¡ Σ * , then it means that x 1 u α x 2 is not a subword of w and hence, by construction of Ψ n , not a subword of Ψ n (w) either, so that there does not exist any β ∈ [α] such that ζ β is a subword of Ψ n (w). Similarly, if we have w ∈ (x 1 u α+1 x 2 ) ¡ Σ * , then it means that x 1 u α+1 x 2 is a subword of w and hence, by construction of Ψ n , a subword of Ψ n (w).

We now assume that w ∈ (x 1 u α x 2 ) ¡ Σ * ∩ (x 1 u α+1 x 2 ) ¡ Σ * while w / ∈ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ). We want to show that in this case, there does not exist any β ∈ [α] such that ζ β is a subword of Ψ n (w). Suppose for a contradiction that such a β exists; our goal is to show, through a careful observation of what this implies on the letters in w by examining how Ψ n decorates the letters, that this contradictingly entails x 1 u α+1 x 2 is a subword of w.

Since ζ β is a subword of Ψ n (w), it is not too difficult to see there exist

)(q 1 , f (0) ) • • • (q |u| , f (0) ) (q |u|+1 , f (1) ) • • • (q 2|u|-1 , f (|u|-1) )(q 2|u| , f (|u|) ) • • • (q 3|u|-2 , f (2|u|-2) ) (r 1 , f (0) ) • • • (r (α-β)•|u|+|x2| , f (0) )
is a subword of Ψ n . By construction of Ψ n , we have

p 1 < • • • < p |x1|+(β-1)•|u| < q 1 < • • • < q |u| < r 1 < • • • < r (α-β)•|u|+|x2|
, so this implies that w can be decomposed as w = y 1 zy 2 where y 1 ∈ x 1 ¡ Σ * , where z ∈ u α ¡ Σ * and y 2 ∈ x 2 ¡ Σ * , the positions p 1 , . . . , p |x1| corresponding to letters in y 1 , the positions p |x1|+1 , . . . , p |x1|+(β-1)•|u| , q 1 , . . . , q |u| , r 1 , . . . , r (α-β)•|u| corresponding to letters in z and the positions r (α-β)•|u|+1 , . . . , r (α-β)•|u|+|x2| corresponding to letters in y 2 .

We are now going to show that, in fact, q |u| < q 2|u|-1 < q 2|u| < • • • < q 3|u|-2 < r 1 , which implies z ∈ u α+1 ¡ Σ * and thus the contradiction we are aiming for. Since w / ∈ (x 1 ¡ Σ * )u(x 2 ¡ Σ * ), we have z / ∈ Σ * uΣ * , hence as w q |u| = u |u| and |u| > 1, there must exist j ∈ [|u| -1] such that w q |u| -j = u |u|-j and w q |u| -ι = u |u|-ι for all ι ∈ [[0, j -1]]. By construction of Ψ n , we know that q |u|+j ≥ q |u| -j (because the instructions with f (j) after an instruction with f (0) querying position p ∈ [n] all query a position at least equal to p -j), but since u |u|-j = w q |u| -j and u |u|-j = u |u|-ι = w q |u| -ι for all ι ∈ [[0, j -1]] as the letters in u are all distinct, we get that q |u|+j > q |u| . By (backward) induction, we can show that for all ι ∈ [[j + 1, |u| -1]], we have q |u|+ι > q |u| . Indeed, given ι ∈ [[j + 1, |u| -1]], we have q |u|+ι-1 > q |u| , either by inductive hypothesis or directly in the base case ι = j + 1 by what we have just seen. So by construction of Ψ n , we know that q |u|+ι ≥ q |u| (because the instructions with f (ι) after an instruction with f (ι-1) querying position p ∈ [n] all query a position at least equal to p -1), but since u |u|-ι = u |u| = w q |u| as the letters in u are all distinct, it follows that q |u|+ι > q |u| . Therefore, we have that q 2|u|-1 > q |u| . Moreover, by construction of Ψ n , we also have q 2|u|-1 < q 2|u| < • • • < q 3|u|-2 < r 1 (because for each ι ∈ [[0, |u| -2]], the instructions with f (|u|+ι) after an instruction with f (|u|+ι-1) querying position p ∈ [n] all query a position at least equal to p + 1 and similarly for the instructions with f (0) after an instruction with f (2|u|-2) ). So, to conclude, we have

p 1 < • • • < p |x1|+(β-1)•|u| < q 1 < • • • < q |u| < q 2|u|-1 < q 2|u| < • • • < q 3|u|-2 < r 1 < • • • < r (α-β)•|u|+|x2| and w p1 • • • w p |x 1 |+(β-1)•|u| w q1 • • • w q |u| w q 2|u|-1 w q 2|u| • • • w q 3|u|-2 w r1 • • • w r (α-β)•|u|+|x 2 | =x 1 u β-1 uu 1 u 2 • • • u |u| u α-β x 2 = x 1 u α+1 x 2 .
This implies that w ∈ (x 1 u α+1 x 2 ) ¡Σ * , a contradiction. So there does not exist

β ∈ [α] such that ζ β is a subword of Ψ(w).
Therefore, in every case Ψ n (w) / ∈ K =s(n) , and since this is true for all w ∈ Σ n \ L =n , we have Σ n \ L =n ⊆ Ψ -1 n (A s(n) \ K =s(n) ), which is equivalent to

L =n ⊇ Ψ -1 n (K =s(n) ).
This concludes the proof of the claim.

And the one of the lemma.

B.4 Proof of Proposition 4.11

Proof of Proposition 4.11. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . , u k ∈ Σ + (k ∈ N >0 ) such that for each i ∈ [k], the letters in u i are all distinct. Let α ∈ [l] k . For each i ∈ [k] verifying α i < l, we define

L i =(u 1 α1 • • • u k α k ) ¡ Σ * ∩ (u 1 α1 • • • u i αi+1 • • • u k α k ) ¡ Σ * ∩ (u 1 α1 • • • u i-1 αi-1 ) ¡ Σ * u i (u i+1 αi+1 • • • u k α k ) ¡ Σ * .
It is immediate to show that R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) = (u

1 α1 • • • u k α k ) ¡ Σ * ∩ i∈[k],αi<l L i .
By Lemma 4.10, L i ∈ P(J) for each i ∈ [k] verifying α i < l. Moreover, since (u 1 α1 • • • u k α k ) ¡ Σ * obviously is a piecewise testable language, it belongs to P(J). Thus, we can conclude that R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) belongs to P(J) by closure of P(J) ∩ Reg under intersection, Proposition 2.1.

Lemma 4 . 2 .

 42 The languages (a + b) * ac + , (a + b) * ac + a(a + b) * , c + a(a + b) * ac + , (a + b) * bac + and (a + b) * ac + (a + b) * ac + do all belong to P(J) \ L(QJ).

  and decompose w as w = xy where x ∈ q1,...,q k ∈{1,l} L (l) (u1,q1) • • • L (l) (u k ,q k ) and y ∈ u k+1 α k+1 ¡ Σ * with |y| being minimal. By inductive hypothesis, we know there exists α ∈ [l] k such that x ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ) and we then prove that xy ∈ R (α1,...,α k+1 ) l (u 1 , . . . , u k+1 ) ∩ S (α1,...,α k+1 ) l

  ¡Σ * and y ∈ u k+1 l ¡Σ * . Hence, w ∈ R (α1,...,α k+1 ) l (u 1 , . . . , u k+1 ) ∩ S (α1,...,α k+1 ) l

  being minimal. So by inductive hypothesis, there exists α ∈ [l] k such that x ∈ R α l (u 1 , . . . , u k ) ∩ S α l (u 1 , . . . , u k ). We are now going to prove that w = xy ∈ R (α1,...,α k+1 ) l (u 1 , . . . , u k+1 ) ∩ S (α1,...,α k+1 ) l

(x 1 ¡

 1 Σ * )u(x 2 ¡ Σ * ) and we can hence decompose w as w = y 1 zy 2 where y 1 ∈ (x 1 ¡ Σ * ) and y 2 ∈ (x 2 ¡ Σ * ) with |y 1 | and |y 2 | being minimal. It follows necessarily that z ∈ u α ¡ Σ * ∩ (u α+1 ¡ Σ * ) ∩ Σ * uΣ * by minimality of |y 1 | and |y 2 |. By Lemma B.1, we have z = α i=1 |u| j=1 (v i,j u j ) y where v i,j ∈ (Σ\{u j }) * for all i ∈ [α] and j ∈ [|u|], and y ∈ |u| i=1 i-1

p 1 ,w

 1 . . . , p |x1|+(β-1)•|u| , q 1 , . . . , q 3|u|-2 , r 1 , . . . , r (α-β)•|u|+|x2| ∈ [n] verifying that w p1 • • • w p |x 1 |+(β-1)•|u| = x 1 u β-1 , w q1 • • • w q 3|u|-2 = u r1 • • • w r (α-β)•|u|+|x 2 | = u α-β x 2 and (p 1 , f (0) ) • • • (p |x1|+(β-1)•|u| , f(0)

Acknowledgements The author thanks the anonymous referees for their helpful comments and suggestions.

We claim that Q = ε, a subprogram of P , has the desired properties. First notice that the length of Q is 0 ≤ 0! • |Σ| 0/2 • n 0/2 = c 0 • n 0/2 , at most the required length.

Let Q be a subprogram of P that has Q as a subprogram. As t ∈ M 0 , we necessarily have that t = ε, which is a subword of any word in M * . Therefore, we immediately get that for all w ∈ Σ n , the word t is a subword of ξ P (w) if and only if t is a subword of ξ Q (w), as desired. Let

B Missing

be the language of all words over Σ having ca as a subword but not the subwords cca, caa and cb, that by construction is piecewise testable, i.e. belongs to L(J).

We are now going to build a program-reduction from (a + b)

We therefore have

Since this means that Ψ n (w) ∈ L =s(n) , we necessarily have n ≥ 2 as it must contain ca as a subword, so that

Let i, j ∈ [n] verifying that w i = c, that w j = a and w i w j is a subword of Ψ n (w). This means that j ≥ i-1, and we will now show that, actually, j = i-1. Assume that j ≥ i+2; by construction, this would mean that w i w j w j = caa is a subword of Ψ n (w), a contradiction to the fact it belongs to L. Assume otherwise that j = i + 1; by construction, this would either mean that w i w i-1 w i+1 w i is a subword of Ψ n (w), which would imply one of caa, cba and cca is a subword of Ψ n (w), or that w i+1 w i w i+2 w i+1 is a subword of Ψ n (w), which would imply one

B.5 Proof of Proposition 4.13

Proof of Proposition 4.13. Let Σ be an alphabet, l ∈ N >0 and u 1 , . . . ,

, then the result is straightforward because the language [u 1 , . . . , u k ] l then belongs to L(J), so now we assume d ≥ 2. We let Σ d = Σ × Z/d Z and for all w ∈ Σ * , for all i ∈ Z/d Z, we define w i = |w| j=1 (w j , (j + i -1) mod d). We also let w = w 0 for all w ∈ Σ * .

For all v ∈ Σ + , |v| ≤ d, we define µ(v, 1) = v and

a language over Σ d , that does belong to P(J) by Corollary 4.12 and closure of P(J) ∩ Reg under finite union (Proposition 2.1), because since

, each v i j for j ∈ Z/d Z has all distinct letters. This implies that for all q 1 , . . . , q k ∈ {1, l}, we have that [µ(u 1 , q 1 ), . . . , µ(u k , q k )] l,d does belong to P(J), so that q1,...,q k ∈{1,l} [µ(u 1 , q 1 ), . . . , µ(u k , q k )] l,d is a language over Σ d belonging to P(J). Now, it is not so difficult to see that

[µ(u 1 , q 1 ), . . . , µ(u k , q k )] l,d , which allows us to conclude that the sequence (Ψ n ) n∈N of Σ d -programs such that Ψ n (w) = w for all n ∈ N and w ∈ Σ n is a program-reduction from [u 1 , . . . , u k ] l to q1,...,q k ∈{1,l} [µ(u 1 , q 1 ), . . . , µ(u k , q k )] l,d of length n. Hence, [u 1 , . . . , u k ] l does also belong to P(J) by Proposition 2.2.


Jean-François Berret
email: jean-francois.berret@univ-paris-diderot.fr

Microrheology of viscoelastic solutions studied by magnetic rotational spectroscopy

Keywords: magnetic wires, microrheology, Maxwell fluid, Magnetic rotational spectroscopy, wormlike micelles

Magnetic rotational spectroscopy is based on the use of magnetic micron-size wires for viscosity measurements. Submitted to a rotational magnetic field with increasing frequency, the wires undergo a hydrodynamic instability between a synchronous and an asynchronous regime. From a comparison between predictions and experiments, the static shear viscosity and elastic modulus of wormlike micellar solutions are here determined. The values agree with the determination by cone-and-plate rheometry.

Introduction

Rheology is the study of how complex materials flow and deform under stress. Traditional rheometers measure the frequency-dependent linear viscoelastic relationship between strain and stress on milliliter-scale samples. Microrheology in contrast measures these quantities using colloidal probes embedded in a fluid [START_REF] Squires | Fluid Mechanics of Microrheology[END_REF]. Fluids produced in tiny amounts or confined in small volumes, down to 1 picoliter can be examined only with this technique. The past 20 years have seen increasingly rapid advances in this research field, both theoretically and experimentally [START_REF] Tierno | Recent advances in anisotropic magnetic colloids: realization, assembly and applications[END_REF]. In microrheology, the objective is to translate the motion of a probe particle into the relevant fluid rheological quantities, such as the static viscosity or the high frequency elastic modulus. Following the pioneer work by Crick and Hughes some 60 years ago [START_REF] Crick | The Physical Properties of Cytoplasm -A Study by Means of the Magnetic Particle Method[END_REF], recent studies have shown that microrheology based on the tracking of anisotropic probes, such as rods, wires and ellipsoids could bring significant advances to the field. It has been proposed that the static viscosity can be determined from the motion of a micro-actuator submitted to a rotating electric or magnetic field. These techniques are described as electric or magnetic rotational spectroscopy [START_REF] Tokarev | Magnetic Rotational Spectroscopy with Nanorods to Probe Time-Dependent Rheology of Microdroplets[END_REF]. Here, we propose an innovative method that goes beyond the previous analysis and that is able to deal with complex fluids showing both viscosity and elasticity effects. The method is based on the tracking of magnetic wires submitted to a rotational magnetic field at increasing frequencies, and on their temporal trajectory analysis. In this work, the method is implemented on a surfactant wormlike micellar solution that behaves as an ideal Maxwell fluid. It is shown that the viscosities between 1 and 10 5 times the water viscosity (10 -3 Pa s -10 2 Pa s) can be measured.

Materials and Methods

Iron oxide nanoparticles were synthesized by co-precipitation of iron(II) and iron(III) salts in aqueous media and by further oxidation of the magnetite (Fe 3 O 4 ) into maghemite (γ-Fe 2 O 3 ) [START_REF] Berret | Stable oxide nanoparticle clusters obtained by complexation[END_REF][START_REF] Chanteau | Electrosteric Enhanced Stability of Functional Sub-10 nm Cerium and Iron Oxide Particles in Cell Culture Medium[END_REF]. The particle size and dispersity were determined from transmission electron microscopy (𝐷𝐷 !"# = 13.2 nm, 𝑠𝑠 !"# = 0.23), whereas the structure was assessed by electron beam diffraction. Light scattering was used to measure the weight-average molecular weight (𝑀𝑀 ! = 12×10 6 g mol -1 ) and the hydrodynamic diameter (𝐷𝐷 ! = 27 nm) of the uncoated particles [START_REF] Berret | Stable oxide nanoparticle clusters obtained by complexation[END_REF][START_REF] Safi | Interactions between sub-10-nm iron and cerium oxide nanoparticles and 3T3 fibroblasts: the role of the coating and aggregation state[END_REF]. The wires were made according to a bottom-up coassembly process using poly(acrylic) acid coated particles together with cationic polymers [START_REF] Fresnais | Universal scattering behavior of coassembled nanoparticle-polymer clusters[END_REF][START_REF] Yan | Growth mechanism of nanostructured superparamagnetic rods obtained by electrostatic co-assembly[END_REF]. The polymer used was poly(diallyldimethylammonium chloride) of molecular weight < 100000 g mol -1 . The wires obtained were characterized by a median length of 10 µm and a median diameter of 0.7 µm. The wires dispersion was autoclaved at 120 °C and atmospheric pressure to prevent bacterial contamination and stored at 4 °C. Bright field microscopy was used to monitor the wire actuation as a function of time.

Stacks of images were acquired on an IX73 inverted microscope (Olympus) equipped with a 100× objective. 65 µl of a fluid to be studied were deposited on a glass plate and sealed into to a Gene Frame ® (Abgene/Advanced Biotech) dual adhesive system. To prevent wire rotation coupling and interaction, experiments were performed in infinite dilution, corresponding to wire concentrations of 1 pM. The glass plate was introduced into a homemade device generating a rotational magnetic field, thanks to two coil pairs working with a 90°-phase shift (Fig. 1a). An electronic set-up allowed measurements in the frequency range 10 -3 -10 rad s -1 and at magnetic fields B = 0 -20 mTesla [START_REF] Chevry | Magnetic wire-based sensors for the microrheology of complex fluids[END_REF]. Fig. 1b displays the magnetic field distributions between the electromagnetic coil poles in the X-and Y-directions. The image acquisition system consisted of an EXi Blue CCD camera (QImaging) working with Metaview (Universal Imaging). Images of wires were digitized and treated by the ImageJ software and plugins. Fig. 1c shows snapshots of a rotating 10 µm wire at fixed time interval during a 180° spin.

Results and Discussion

Newtonian liquid -For a viscous liquid of viscosity 𝜂𝜂, a wire submitted to a rotating field experiences a restoring torque that slows down its rotation. As a result, the wire motion undergoes a transition between a synchronous and an asynchronous rotation. In the first regime, the wire rotates at the same frequency as the field, whereas in the second regime it is animated of periodic back-and-forth motions. Because wires are superparamagnetic, the oscillation frequency above the instability is twice that of the excitation. The critical frequency 𝜔𝜔 ! between these two regimes reads [START_REF] Chevry | Magnetic wire-based sensors for the microrheology of complex fluids[END_REF][START_REF] Helgesen | Nonlinear phenomena in systems of magnetic holes[END_REF][START_REF] Frka-Petesic | Dynamics of paramagnetic nanostructured rods under rotating field[END_REF]:

𝜔𝜔 ! = 3 8 𝜇𝜇 ! Δ𝜒𝜒 𝜂𝜂 ! 𝑔𝑔 𝐿𝐿 𝐷𝐷 𝐷𝐷 ! 𝐿𝐿 ! 𝐻𝐻 ! (1)
where 𝜇𝜇 ! is the permeability in vacuum, 𝐿𝐿 and 𝐷𝐷 the length and diameter of the wire, 𝐻𝐻 the magnetic excitation amplitude and 𝑔𝑔 𝐿𝐿/𝐷𝐷 = 𝐿𝐿𝐿𝐿 𝐿𝐿/𝐷𝐷 -0.662 + 0.917𝐷𝐷/𝐿𝐿 -0.050 𝐷𝐷/𝐿𝐿 ! is a dimensionless function of the anisotropy ratio. In Eq. 1, Δ𝜒𝜒 = 𝜒𝜒 ! (2 + 𝜒𝜒) where 𝜒𝜒 denotes the magnetic susceptibility. In the synchronous and asynchronous regimes, the wire motion is analyzed with respect to their rotation angle 𝜃𝜃(𝑡𝑡). Examples of 𝜃𝜃 𝑡𝑡 -traces obtained are illustrated in Fig. 2. For the analysis, the 𝜃𝜃 𝑡𝑡 -traces are translated into a set of two parameters: the average rotation velocity Ω ω and the oscillation amplitude 𝜃𝜃 ! ω in the asynchronous regime [START_REF] Chevry | Magnetic wire-based sensors for the microrheology of complex fluids[END_REF]. The average angular velocity Ω(ω) in the two regimes expresses as:

ω ≤ 𝜔𝜔 ! Ω ω = ω ω ≥ 𝜔𝜔 ! Ω ω = ω -ω ! -𝜔𝜔 ! ! (2)
With increasing frequency, the average velocity increases linearly, passes through a cusplike maximum at the critical frequency and decreases. The transition between the synchronous and asynchronous regimes was used to calibrate the wire-rheometer and determine the susceptibility parameter Δ𝜒𝜒 in Eqs. 1. For the calibration, experiments were performed on a 85 wt. % water-glycerol mixture of static viscosity 𝜂𝜂 = 0.062 Pa s -1 . In a purely viscous fluid, the critical frequency is found to decrease as 𝑔𝑔 ! ! 𝐿𝐿 !! in agreement with Eq. 1. For wires made from 13.2 nm particles and PADADMAC, we found Δ𝜒𝜒 = 2.1 ± 0.4, and a magnetic susceptibility 𝜒𝜒 = 3.4 ± 0.4.

Maxwell fluid -In continuum mechanics, a Maxwell fluid is described by a spring and dashpot in series. An actuated wire immersed in such a medium experiences a viscous and an elastic torque that both oppose the applied magnetic torque. The differential equation describing the wire motion has been derived and solved, leading to the following predictions [START_REF] Chevry | Magnetic wire-based sensors for the microrheology of complex fluids[END_REF]. With increasing ω, the wire undergoes the same type of transition as the one described previously and the critical frequency 𝜔𝜔 ! expresses as in Eq. 1. The static viscosity 𝜂𝜂 in Eq. 1 is however replaced by the product 𝐺𝐺𝐺𝐺, where 𝐺𝐺 and 𝜏𝜏 denote the shear elastic modulus and the fluid relaxation time. The set of equations in Eq. 2 is also identical to that of a Newtonian fluid. From the oscillation amplitude 𝜃𝜃 ! 𝜔𝜔 in the asynchronous regime, it is possible to determine the shear elastic modulus 𝐺𝐺 using [START_REF] Chevry | Magnetic wire-based sensors for the microrheology of complex fluids[END_REF]:

lim !→! 𝜃𝜃 ! (𝜔𝜔) = 3 4 𝜇𝜇 ! Δ𝜒𝜒 𝐺𝐺 𝑔𝑔( 𝐿𝐿 𝐷𝐷 ) 𝐷𝐷 ! 𝐿𝐿 ! 𝐻𝐻 ! (3)
Comparison between cone-and-plate and wire-based rheology -To assess the validity of the wire-based microrheology approach, magnetic wires were tested on a surfactant solution made of cetylpyridinium chloride and sodium salicylate, abbreviated as CPCl/NaSal. CPCl and NaSal are known to self-assemble spontaneously into micrometer long wormlike micelles, which then build a semi-dilute entangled network above a certain concentration [START_REF] Berret | Metastable versus unstable transients at the onset of a shearinduced phase transition[END_REF][START_REF] Walker | Macroscopic response of wormlike micelles to elongational flow[END_REF]. This network confers to the solution a Maxwell-type viscoelastic behavior. At the concentration of 2 wt.%, the network mesh size is of the order of 30 nm, i.e. much smaller than the wire diameter. Surfactant wormlike micelles are sometimes called equilibrium polymers.

In Fig. 2, a 15 mT rotating magnetic field was applied a 8 µm nanowire immersed in the CPCl/NaSal solution at increasing frequencies: a) 𝜔𝜔 = 0.85 rad s -1 ; b) 𝜔𝜔 = 1.2 rad s -1 and c) 𝜔𝜔 = 7 rad s -1 . The wire motion was monitored by optical microscopy, and the time dependence of their orientation was derived. At low frequency, the wire rotates with the field and 𝜃𝜃 𝑡𝑡 = 𝜔𝜔𝜔𝜔. Above the critical frequency (here 𝜔𝜔 ! = 0.90 rad s !! ), the wire is animated of back-and-forth motion characteristic of the asynchronous regime. In this range, 𝜃𝜃 𝑡𝑡 displays oscillations. The green straight lines in the figure represent the average angular velocity Ω(𝜔𝜔) introduced in Eq. 2. With increasing frequency, Ω(𝜔𝜔) increases, passes through a maximum at the critical frequency and decreases. The Ω(𝜔𝜔)-data were adjusted using Eq. 2 and a value of the static viscosity of 𝜂𝜂 = 1.3 ± 0.3 Pa s, in good agreement with the cone-and-plate rotational rheometry value. From the oscillation amplitudes in the regime 𝜔𝜔𝜏𝜏 ≫ 1 (Eq.

3), a modulus of 9.4 ± 2 Pa was derived. Experiments performed with wires of different lengths and in various magnetic field conditions confirmed the good agreement with cone-and-plate rheometry, and demonstrates the ability of the technique to measure the linear viscoelasticity of a Maxwell fluid (Table 1).

-Conclusion

We have shown here that micron-size wires with magnetic properties can be used as probes for active µ-rheology. The magnetic rotational spectroscopy studies the transition between a synchronous and an asynchronous regime of rotation observed with increasing frequency. The instability resembles that observed on laboratory benches when a viscous solution is actuated with a magnetic bar. Tested here on a Maxwell fluid, viscoelastic parameters 𝜂𝜂, 𝐺𝐺 and 𝜏𝜏 of the fluid can be derived. The technique can be extended in principle to any kind of complex fluids.

Figure 1 a

 1 Figure 1 a) Top and side views of the rotating field device used this work. b) Magnetic field distributions are shown along the four-coil device X and Y-directions. In the center, the magnetic field is constant over a 1×1 mm 2 area. c) Snapshots of a 10 µm rotating wire. The time scale between two images is 46 ms.

Figure 2

 2 Figure 2 Rotation angle 𝜃𝜃 𝑡𝑡 of a 8.1 µm wire as a function of the time at various frequencies: a) 𝜔𝜔 = 0.8 rad s -1 ; b) 𝜔𝜔 = 1.2 rad s -1 and c) 𝜔𝜔 = 7 rad s -1 . The behaviour in a) corresponds to the synchronous regime. The green straight lines in b) and c) represent the average angular velocity Ω = 𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 in the asynchronous regime.

Fig. 3a displays

  Fig.3adisplays the frequency dependence of the elastic and loss moduli 𝐺𝐺 ! 𝜔𝜔 and 𝐺𝐺 !! 𝜔𝜔 obtained on the 2 wt.% CPCl/NaSal solution. Data were obtained on a CSL 100 rheometer from TA Instruments with a cone-and-plate device (inset). At 𝑇𝑇 = 27 °C, this wormlike micellar fluid was characterized by the static viscosity 𝜂𝜂 = 1.0 Pa s, a relaxation time 𝜏𝜏 = 0.14 s and an elastic modulus 𝐺𝐺 = 7.1 Pa, in agreement with earlier literature[START_REF] Berret | Metastable versus unstable transients at the onset of a shearinduced phase transition[END_REF][START_REF] Walker | Macroscopic response of wormlike micelles to elongational flow[END_REF]. In Fig.3a, the 𝐺𝐺 ! 𝜔𝜔 and 𝐺𝐺 !! 𝜔𝜔 data were normalized with respect to the elastic modulus and the frequency with respect to the relaxation time. The continuous lines are the predictions for a Maxwell fluid: 𝐺𝐺′(𝑋𝑋)/𝐺𝐺 = 𝑋𝑋 ! (1 + 𝑋𝑋 ! ) and 𝐺𝐺 !! 𝜔𝜔 /𝐺𝐺 = 𝑋𝑋 (1 + 𝑋𝑋 ! ), where 𝑋𝑋 = 𝜔𝜔𝜔𝜔. The agreement between the data and predictions is excellent.

Figure 3 a

 3 Figure 3 a) Cone-and-plate geometry used in rheometry. 𝐺𝐺 ! 𝜔𝜔 /𝐺𝐺 and 𝐺𝐺 !! 𝜔𝜔 /𝐺𝐺 versus frequency for a wormlike micellar fluid. The continuous lines are Maxwell predictions. Inset: cone-and-plate device used in rheometry. b) Average angular velocity Ω(𝜔𝜔) as a function of the frequency. The solid line corresponds to the best fit using Eq. 1. Inset in b): image of the 8.1 µm wire by phase contrast microscopy (60×, scale bar 5 µm).

Fig. 3b displays

  Fig.3bdisplays the average angular velocity Ω(𝜔𝜔) versus ω obtained for a 8.1 µm wire. With increasing frequency, Ω(𝜔𝜔) increases, passes through a maximum at the critical frequency and decreases. The Ω(𝜔𝜔)-data were adjusted using Eq. 2 and a value of the static viscosity of 𝜂𝜂 = 1.3 ± 0.3 Pa s, in good agreement with the cone-and-plate rotational rheometry value. From the oscillation amplitudes in the regime 𝜔𝜔𝜏𝜏 ≫ 1 (Eq. 3), a modulus of 9.4 ± 2 Pa was derived. Experiments performed with wires of different lengths and in various magnetic field conditions confirmed the good agreement with cone-and-plate rheometry, and demonstrates the ability of the technique to measure the linear viscoelasticity of a Maxwell fluid (Table1).

Table 1

 1 Viscoelastic

	Wire	#1	#2	#3	#4	#5	#6	#7	#8	#9
	𝜂𝜂 (𝑃𝑃𝑃𝑃 𝑠𝑠)	1.11 1.21 1.45 1.32 0.97 1.49 1.08 1.37 1.72
	𝜏𝜏 (𝑠𝑠)	0.15 0.13 0.16 0.14 0.12 0.14 0.12 0.17 0.15
	𝐺𝐺 (𝑃𝑃𝑃𝑃)	7.6 9.5 9.2 9.7 7.9 10.3 9.1 7.9 11.2

parameters of a CPCl/NaSal wormlike micellar solution at 2 wt. % using magnetic rotational spectroscopy. 𝐿𝐿 (µμ𝑚𝑚) 8.2 14.8 8.1 8.1 12.5 5.0 3.3 6.3 3.0 𝐵𝐵 (𝑚𝑚𝑚𝑚) 10.4 10.4 10.4 15.3 7.3 14.8 14.8 10.4 14.8 𝜔𝜔 ! (𝑟𝑟𝑟𝑟𝑟𝑟 𝑠𝑠 !! ) 1.44 0.55 0.38 0.88 0.41 1.6 4.0 0.80 2.1

Acknowledgements

I am grateful to L. Chevry, A. Cebers, M.-A. Fardin and A. Hallou for fruitful discussions. The master students who participated to this research, C. Leverrier, A. Conte-Daban, C. Lixi, L. Carvhalo and R. Chan are also acknowledged.