Michel Latteux
email: michel.latteux@univ-lille1.fr

Yves Roos
email: yves.roos@univ-lille1.fr

On Prefixal One-Rule String Rewrite Systems

Keywords:

Prefixal one-rule string rewrite systems are one-rule string rewrite systems for which the left-hand side of the rule is a prefix of the right-hand side of the rule. String rewrite systems induce a transformation over languages: from a starting word, one can associate all its descendants. We prove, in this work, that the transformation induced by a prefixal one-rule rewrite system always transforms a finite language into a context-free language, a property that is surprisingly not satisfied by arbitrary one-rule rewrite systems. We also give here a decidable characterization of the prefixal one-rule rewrite systems whose induced transformation is a rational transduction.

Introduction

String rewrite systems are of primordial interest for computational problems. Mainly, the problems that are investigated for rewrite systems are the accessibility problem, the common descendant problem, the confluence problem, the termination and uniform termination problem. For several years they have been intensively studied and several deep results have been obtained. However some intriguing decidability problems remain open even for very simple rewrite systems 1 . The most known among these problems is certainly the decidability of the termination of one-rule rewrite systems, a question that remains open for more than thirty years.

Other problems consider rewrite systems as transformation operations on languages: given a rewrite system S and a word w, S * (w) is the set of all the descendants of w in the rewrite system S. Thus S induces a transformation relation S * over languages and, from there, one can wonder how these transformations on languages can interact with the classical families of formal languages ( [START_REF] Sénizergues | Some decision problems about controlled rewriting systems[END_REF][START_REF] Sénizergues | Formal languages & word-rewriting[END_REF]). In particular, a natural question is the following: given two classes of languages C 1 and C 2 , and a family of rewrite systems F, is it true that, for every system S in F and for every language L in C 1 , it holds that S * (L) is in C 2 . If the property is satisfied then rewrite systems in F are said to be C 1 /C 2 and, in the case when C 1 = C 2 , we rather say that rewrite systems in F preserve C 1 .

In this context, some families of rewrite systems have been identified as preserving rational languages (C 1 = C 2 = RAT) like k-period expanding systems ( [START_REF] Leupold | On regularity-preservation by string-rewriting systems[END_REF]), deleting systems ( [START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF]) and match-bounded systems ( [START_REF] Geser | Matchbounded string rewriting systems[END_REF]) or preserving context-free languages (C 1 = C 2 = CF) like systems with inhibitor ( [START_REF] Mcnaughton | Semi-thue systems with an inhibitor[END_REF])and inverse match-bounded systems ( [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF]).

Even for very simple rewrite systems, the question whether these systems are C 1 /C 2 for some given classes of languages C 1 and C 2 is not always so easy to answer. One-rule rewrite systems are among the simplest rewriting systems since they are defined by only two words u, v over an alphabet A. Clearly, one-rule rewrite systems do not always preserve regular languages: the simplest example of such a one-rule (length-preserving) rewrite system is the system S = {ba -→ ab} but it has been proved RAT/CF in [START_REF] Clerbout | Semi-commutations and algebraic languages[END_REF] , in the context of a particular class of rewrite systems called semi-commutations. From this, one could think that one-rule rewrite systems are at least FIN/CF where FIN is the class of finite languages, but, rather surprisingly, it is not the case: for the one-rule rewrite system S = {ba → a 2 b 2 } it has been proved that S(b 2 a 2 ) is not a context-free language([LR12]). Since then, one-rule grid rewrite systems, introduced in [START_REF] Geser | Decidability of termination of grid string rewriting rules[END_REF] have been proved FIN/CF in [START_REF] Latteux | On one-rule grid semi-thue systems[END_REF].

In this paper, we consider prefixal one-rule rewrite systems that are systems in the form S = {u → uf } for some word u and some non empty word f , with respect to the FIN/CF property and to the preserving of RAT. More precisely, after technical preliminaries given in Section 3, we prove that every prefixal onerule rewrite system S is FIN/CF by defining, for every word w, an appropriate context-free grammar that depends on S and w and that generates S * (w). Then, in section 5, we give a new example, different from the one given in [START_REF] Latteux | On one-rule grid semi-thue systems[END_REF], of a one-rule rewrite system that is not FIN/CF and we prove that these two examples are the simplest examples of non FIN/CF one-rule rewrite systems. In Section 6, we give a decidable characterization of prefixal one-rule rewrite systems S = {u → uf } for which S * is a rational relation. In particular we prove that it is the case if and only if S * (u) is a rational language.

Preliminaries and Notations

Let A be a finite alphabet, A * will denote the free monoid over A and ε the empty word in A * . For a word w ∈ A * , |w| denotes the length of the word w and, for any letter a ∈ A, |w| a denotes the number of occurrences of the letter a in w.

A word w is a factor of a word w if there exist two words w 1 and w 2 such that w = w 1 w w 2 and we denote by F(w) the set of the factors of the word w. We denote by RF(w) (respectively LF(w)) the set of suffixes (respectively prefixes) of the word w, that is:

RF(w) = {w ∈ A * | ∃w ∈ A * , w = w w }, LF(w) = {w ∈ A * | ∃w ∈ A * , w = w w }.
For two words w and w , we denote w ∧ l w the largest word in LF(w) ∩ LF(w ) and we denote w ∧ r w the largest word, in RF(w) ∩ RF(w ).

A word u ∈ A + is said to be primitive if it is not a power of another word, that is, u = v n with v ∈ A * implies n = 1 and v = u. The root of a word u ∈ A + is the unique primitive word ρ such that u = ρ n for some natural number n. A nonempty set X ⊆ A * is called a code if every equation u 1 u 2 . . . u m = v 1 v 2 . . . v n with u i , v j ∈ X for all i and j implies n = m and u i = v i for all i.

We denote FIN the family of finite languages, RAT the family of rational languages and CF the family of context-free languages.

A rewrite system over an alphabet A is a subset S ⊆ A * × A * . Members of S are denoted u → v. We shall denote S -1 the system obtained from the system S by reversing the rules of S, that is Among the different derivations starting from a word w, some of them play a central role in this paper: a leftmost derivation from a word w is, like for leftmost derivations in context-free grammars, a derivation where the rewriting is applied, at each step, to the leftmost possible position in the current word. Symmetrically, we will also consider rightmost derivations.

u → v ∈ S iff v → u ∈ S -1 . One-step derivation, denoted - →,
We say that a string rewrite system S is rational if the relation {(w, w ) | w ∈ S * (w)} is a rational relation and we say that S is FIN/CF, if for every finite language L, S * (L) ∈ CF. If S = {u → v} is a one-rule string rewrite system, we say that S is prefixal if v = uf for some non-empty word f ; symmetrically S is suffixal if v = f u for some word f . In the following sections, a lot of definitions and claims have symmetric counterparts that are not explicitly stated for the sake of clarity.

The languages R S

Considering an arbitrary string rewrite system S and two words w and w with w ∈ S * (w), it may happen that, for all derivation from w to w , the right edges of some words that are involved in the derivation are necessarily reached: more precisely, we say that a word w is right-complete with respect to a word w if w ∈ S + (w) and there does not exist some words w 1 , w 1 and w 2 = ε such that w = w 1 w 2 , w = w 1 w 2 and w 1 ∈ S + (w 1 ). We get the following obvious property that will often be used in the forthcoming proofs.

Property 1. Let S be an arbitrary string rewrite system and w, w be two words with w ∈ S + (w).

1. if w is right-complete with respect to w then all derivation w + -→ w can be factorized in w * -→ zl and zr * -→ w for some word z and some l → r ∈ S 2. there exist words w 2 , w 1 and w 1 such that w = w 1 w 2 , w = w 1 w 2 and w 1 is right-complete with respect to w 1 .

This property motivates the following definition in the case when S = {u → v} is a one-rule rewrite system:

R S = S * -1 (A * u) = {w ∈ A * | ∃w ∈ A * , w * -→ w u}.
From the above general property, it follows for every one-rule rewrite system S and for every word w that S * (w) = S * (w 1 )w 2 where w = w 1 w 2 with w 1 being the longest prefix of w that belongs to R S .

As for the termination problem (see for instance [START_REF] Geser | Termination of string rewriting rules that have one pair of overlaps[END_REF]) and the confluence problem ([Wra90]), a lot of properties of a one-rule string rewrite system S = {u → v}, in relation with context-free preserving, depends on the existence of overlaps between the left-hand side u and the right-hand side v of the rewriting rule. For every one-rule rewrite system S = {u → v}, we denote:

X = LF(u) ∩ RF(v) ∩ A + , Z = RF(u) ∩ LF(v) ∩ A + , U = uZ -1 = {u ∈ A * | u ∈ u Z}, U = X -1 u, V = vX -1 V = Z -1 v as depicted in Figure 1.
Note that if |u| > |v| then S terminates so S * preserves FIN. In the case when |u| = |v|, either u = v and S * is the identity function, or u = v and S terminates so S * preserves FIN. Nevertheless, some non trivial results stated later hold in the case |u| = |v|, so, in the rest of the paper, we consider only one-rule string rewrite system S = {u → v} with |v| ≥ |u| and u = v. For such systems, one observe that all the derivations from a word w to a word w have the same length. Indeed, it is clearly true when |v| > |u| and it has been proved in [START_REF] Latteux | One-rule length-preserving rewrite systems and rational transductions[END_REF] in the case |u| = |v|.

In this section, we study how to compute the set R S . While the definition of this set is very simple, its construction is not so easy. As a matter of fact, this language need not be rational as shown in the following example:

v u U ′ Z V ′′ v u V ′ X U ′′ Figure 1: The sets X, Z, U , U , V and V Example 1. Let S = {aab → aba}, then R S = A * Lb where L = {w | |w| a = |w| b +2}, so R S is a context-free language and it is not rational since R S ∩a * b * = {a n b p | n > p}.
Let us prove the equality R S = A * Lb.

• R S ⊆ A * Lb: let w ∈ R S and l be the length of a shortest derivation from w to some word of A * u, say w u. We make an induction on l.

If l = 0, we get w ∈ A * Lb since A * aab ⊆ A * Lb. If l > 0, we get w = w 1 aabw 2 - → w 1 abaw 2 l-1
--→ w u. From the inductive hypothesis, w 1 abaw 2 ∈ A * Lb. We can distinguish four cases that all imply w 1 aabw 2 ∈ A * Lb:

(i) w 2 ∈ A * Lb, (ii) aw 2 ∈ Lb that implies aabw 2 ∈ Lb, (
iii) baw 2 ∈ Lb, that implies w 2 ∈ Lb (iv) w 1 abaw 2 ∈ Lb for some w 1 ∈ RF(w 1 ).

• A * Lb ⊆ R S : let w ∈ L, we shall prove that wb ∈ R S by induction on |w|, the length of the word w. One can assume that w ∈ A + L. Since w ∈ L, we get |w| ≥ 2. If |w| = 2 then w = aa and wb ∈ R S . If |w| > 2, then w = a i bw for some word w and some integer i ≥ 2. Since a i b * -→ aba i-1 , it follows w * -→ aba i-1 w that implies a i-1 w ∈ L. Now, from the inductive hypothesis, we get a i-1 w b ∈ R S so wb ∈ R S .

We do not know whether there exists some one-rule rewrite system S such that R S is not a context-free set; we do not even know whether the set R S is effectively recursive or not. Proposition 3 will give some general bounds for R S but we can also identify some cases where it is easily seen that this set is rational: for instance, if u ∈ RF(v) it clearly follows R S = A * u but this condition is not necessary. More precisely, we get:

Proposition 1. R S = A * u if and only if X ⊆ RF(u).
Proof. Assume first that X ⊆ RF(u); it follows that there exist some words x, u and v such that u = xu , v = v x and x ∈ RF(xu ). That implies u = xu ∈ RF(xu u ) and we get uu ∈ A * u whereas uu -

→ vu = v xu = v u = uv .
Conversely, assume X ⊆ RF(u) and consider w ∈ R S . Then w * -→ w u for some word w . We prove that w ∈ A * u by induction on the length of the derivation w * -→ w u. If w = w u, we are done else w = αuβ -→ αvβ * -→ w u for some words α and β. From the inductive hypothesis, αvβ = α u for some word α .

If |β| ≥ |u| then w ∈ A * u. Else v = v v with u = v β and v = ε (recall that |u| ≤ |v|). So v ∈ X ⊆ RF(u), and it follows v β = u ∈ RF(uβ) so w ∈ A * u.
Observe that Proposition 1 does not hold in the case when |u| > |v|: Let S = {aab → a}. Since Z = ∅, we have Z ⊆ LF(u) but aaabb -→ u and aaabb ∈ uA * . Proposition 3 will use the following set in order to give some bounds for R S :

D = {u ∈ RF(u) | |vu ∧ r u| > |uu ∧ r u|}.
Why this definition? Consider one step of derivation w = u uu -→ w = u vu in a derivation from a word of R S to a word of A * u. This step "goes in the good direction" if |w ∧ r u| > |w ∧ r u| that gives |vu ∧ r u| > |uu ∧ r u|.

We observe that ε is never in D and it is also easily seen that uD ∩ A * u = ∅. Moreover, when u ∈ RF(v), there exists a letter b, distinct from letter a, such that u ∈ A * bd. In this case, we have dD ⊆ A * bd: indeed let u ∈ D, then du ∈ RF(u) and |du | ≥ |bd| so bd ∈ RF(du ). That implies dD + ⊆ A * bd.

Proposition 2. D = ∅ if and only if RF(v) ∩ F(u) ⊆ RF(u).
Lemma 1. The three following statements are equivalent:

1. u ∈ RF(v) 2. A * v ⊆ R S 3. A * v ∩ R S = ∅ Proof. Since v ∈ A * ad, we have S * (A * v) ⊆ S * (A * ad) ⊆ A * ad. It follows that if u ∈ RF(v) then S * (A * v) ∩ A * u = ∅ so A * v ∩ R S = ∅. That proves 3 =⇒ 1. Conversely, when u ∈ RF(v), we get A * v ⊆ A * u ⊆ R S that implies A * v∩R S = ∅.
That proves 1 =⇒ 2 =⇒ 3.

Using this lemma together with Proposition 1 and Proposition 2, we get the following diagram:

A * v ⊆ R S =⇒ D = ∅ =⇒ R S = A * u u ∈ RF(v) =⇒ RF(v) ∩ F(u) ⊆ RF(u) =⇒ X ⊆ RF(u)
Conversely, R S = A * u does not imply D = ∅: for S = {babb → baab}, we have

X = {b} ⊆ RF(u) so R S = A * u while D = {b} = ∅.
We can now give some bounds for R S :

Proposition 3. A * uU * ⊆ R S ⊆ A * uD * ⊆ A * d.

Proof. For the inclusion

A * uU * ⊆ R S it
= α 0 uβ 0 - → α 0 vβ 0 = α 1 uβ 1 * -→ α n vβ n = zu with α i ∈ A * and β i ∈ A + for all i ∈ [0, n].
Let k be such that β k is of minimal length then, for all i ∈ [0, n] there exists some word β i such that β i = β i β k . It follows w = w β k for some word w with w * -→ α k u. From the inductive hypothesis, we get w ∈ A * uD * .

We also have α k v * -→ α n vβ n and, since clearly S * (A * v) ⊆ A * ad, it follows α n vβ n = w ad for some word w . Moreover u ∈ RF(α k uβ k ) since the derivation w * -→ zu is of minimal length; that implies u ∈ RF(dβ k ). On the other hand, w adβ k = zu and we get

adβ k ∈ RF(u) so β k ∈ D and w = w β k ∈ A * uD * . Remark 1. If D is included in U , Proposition 3 directly implies R S = A * uD * = A * uU * .
This gives a second case where the language R S is an effective rational set (as a matter of fact, it generalizes the first case: R S = A * u when u ∈ RF(v)). Nevertheless R S = A * uD * does not imply that D is included in U as for S = {u → v} with u = aab and v = aaba. In this case, U = {ab}, D = {ab, b} and, since aabab -→ aabaab and aabb -→ aabab -→ aabaab, we get that uD ⊆ R S so R S = A * uD * . We also observe that, for S = {aab → aba} that was used in Example 1 where U = {ab} and D = {ab, b}, the two inclusions A * uU * ⊆ R S ⊆ A * uD * are strict since R S is not rational in this case. Symmetrically, U is not always included in D: if u ∈ RF(v), we get ε ∈ U and D = ∅ so U need not be a code, unlike D.

From the above remark, we shall now identify when the inclusions A * uU * ⊆ R S and R S ⊆ A * uD * are strict or not; for this, we need to study the different possible relations between D and U . We first observe that dU ⊆ A * d where

d = u ∧ r v, that implies dU * ⊆ A * d.
Lemma 2. If u ∈ A * bd and v ∈ A * ad for some distinct letters a and b and some word d then, for every word w ∈ U , the four following statements are equivalent:

1. w ∈ D 2. uw ∈ A * u 3. u ∈ RF(dw) 4. |w| ≥ |u| -|d|
Proof. Clearly 3 implies directly 2 and 2 implies 1 from Proposition 4. On the other hand, 3 clearly implies 4 and 4 implies 1 since w ∈ D implies adw ∈ RF(u).

To finish the proof of the lemma, it is sufficient to prove that 1 implies 3: let

w ∈ U \ D; since u ∈ A * bd and v ∈ A * ad, it follows u ∈ RF(v) that implies ε ∈ U so w = ε. Since w ∈ U , it follows vw ∈ A * u. Moreover, since v ∈ A * ad and adw ∈ RF(u), we get |dw| ≥ |u| so u ∈ RF(dw).
The three following statements have been proved in [START_REF] Latteux | A canonical automaton for one-rule length-preserving string rewrite systems[END_REF] for one-rule lengthpreserving string rewrite systems. They respectively correspond to Lemma 12, Lemma 9 and Lemma 10 in [START_REF] Latteux | A canonical automaton for one-rule length-preserving string rewrite systems[END_REF]. Although the proofs have been made in a context where |u| = |v|, they never use this equality and hold for the more general case |v| ≥ |u| since they only depend on the definition of D. Remark 2. From Proposition 4 it follows that for all w ∈ A * uD * , there is a unique w ∈ D * such that uw ∈ RF(w). Moreover, it follows from Lemma 3 that D is a code and, because D is a code, there is a unique sequence α 1 , . . . , α k such that w = α 1 . . . α k and α i ∈ D for each i ∈ {1, . . . , k}.

Lemma 4. If bu bd ∈ RF(u) for some word u , then A * uD * ∩ A * au bdD * = ∅.
This lemma is useful in order to obtain the following relations between U and D:

Lemma 5.

uU

* ⊆ A * u(D ∩ U ) * 2. A * uU * = A * u(D ∩ U ) * 3. A * uD * ∩ A * uU * = A * u(D ∩ U ) * 4. D * ∩ U * = (D ∩ U ) * 5. D * \ U * = D * (D \ U )D * Proof.
Clearly, 1 implies 2 that implies 3 and 4 implies 5. Let us prove that 3 implies 4. The inclusion

(D ∩ U ) * ⊆ D * ∩ U * is obvious. Conversely, let w ∈ D * ∩ U * . Then uw ∈ A * uD * ∩ A * uU * = A * u(D ∩ U ) * by 3. Proposition 4 yields uw ∩ A + uA * = ∅, so uw ∈ u(D ∩ U ) * , and so w ∈ (D ∩ U ) * . It now remains to prove 1 : let w ∈ uU * . If w = u then w ∈ A * u(D ∩ U ) * otherwise w = uw 1 w 2 .
. . w p for some words w 1 . . . w p ∈ U with p > 0. If for every 1 ≤ i ≤ p it holds that w i ∈ D, we are done, else let us consider the biggest i such that w i ∈ D. We get w i+1 . . .

w p ∈ (D ∩ U ) * and uw 1 . . . w i-1 ∈ A * d since uU * ⊆ A * d. It follows uw 1 . . . w i ∈ A * dw i and, from Lemma 2, uw 1 . . . w i ∈ A * u that implies w ∈ A * u(D ∩ U ) * .
We shall now prove a key lemma (Lemma 7) that will be particularly useful in the next section. We first need the following corollary of Proposition 4, Lemma 4 and Proposition 3: Corollary 1. Let S = {u → v} be a one-rule rewrite system with |u| ≤ |v|. For all words w, α, α ∈ A * and x ∈ D * , the two following properties are satisfied:

1. if αu - → w * -→ α u then w ∈ A * u, 2. if αux - → w * -→ α u then w = αvx or w ∈ A * ux.
Proof. Observe that 1 is a consequence of 2 in the case when x = ε: indeed from 2 we get that if αu -→ w * -→ α u then w = αv or w ∈ A * u. Since we have seen that A * v ∩ R S = ∅ if and only if u ∈ RF(v), we always have w ∈ A * u. It remains to prove 2.

Since αux -→ w, we have αux = w uw and w = w vw for some words w and w . From Proposition 4, it follows |w | ≥ |x|. We have to consider three cases:

(i) |w | = |x|. In this case, w = αvx, (ii) |w | ≥ |ux| -|d|. In this case, w ∈ A * ux. (iii) |x| < |w | < |ux| -|d|.
In this case, w uw = w u bu bdx for some words u and u with bu bd ∈ RF(u) and w = w v au bdx for some word v . It follows from Lemma 4 that w ∈ A * uD * , a contradiction since w ∈ R S and R S ⊆ A * uD * from Proposition 3.

We also need the following lemma:

Lemma 6. A * dD * D 2 ∩ A * u = ∅.
Proof. This is clearly true if D = ∅. Else, u ∈ A * bd and v ∈ A * ad for some distinct letters a and b. Moreover, since dD

* ⊆ A * d it is sufficient to prove A * dD 2 ∩ A * u = ∅. Assume A * dD 2 ∩ A * u = ∅. So, there exist two words u 1 , u 2 ∈ D with A * du 1 u 2 ∩ A * u = ∅. By u 2 ∈ D, we have adu 2 ∈ RF(u) so A * du 1 u 2 ∩ A * u ⊆ A * du 1 u 2 ∩ A * adu 2 . It follows A * du 1 u 2 ∩ A * adu 2 = ∅ that implies A * du 1 ∩A * ad = ∅, a contradiction since adu 1 ∈ RF(u) and u ∈ A * bd.
This allows us to state the following key lemma:

Lemma 7. For all w ∈ A * , x ∈ D * and y ∈ D + , if wuxy * -→ zu for some word z then there exists a word w ∈ A * such that: It remains the case: wuxy -→ wvxy * -→ zu. First observe that, if x = ε, we can take w = w so we assume x = ε. Since wvxy ∈ R S , it follows from Proposition 3 that wvxy = αuβ for some words α ∈ A * and β ∈ D * . Moreover, from Lemma 6, β = ε. Since u ∈ RF(v) we have |β| < |xy| or |β| > |xy|. We shall distinguish these two cases:

1. wux * -→ w u, 2. w vy * -→ zu.
• |β| < |xy|. From Proposition 4, it follows u ∈ RF(dD * ) so |uβ| > |dxy|.
It follows xy = gβ for some words g with dg ∈ RF(u). That implies adg ∈ RF(u) so g ∈ D. Since D is a code, it follows x = gx 1 with x 1 ∈ D * and we get αux 1 y * -→ zu. From the inductive hypothesis, we get that there exists a word w such that αux 1 * -→ w u and w vy *

-→ zu. Finally, wux = wugx 1 - → wvgx 1 = αux 1 * -→ w u. w v x y α u β a d g x 1 • |β| > |xy|.
In this case, β = gxy for some word g. One can observe that it follows from Lemma 7 that wuxy ∈ R S with x, y ∈ D * implies wux ∈ R S . We are now able to characterize when R S = A * uU * :

Proposition 5. R S = A * uU * if and only if A * v(D \ U ) ∩ A * uU * = ∅.
Proof. For the only if part assume wvw ∈ A * uU * for some words w ∈ A * and w ∈ D\U . Since wvw ∈ A * uU * ⊆ R S , it follows that wuw ∈ R S . Moreover, since it does not exist w ∈ D * with w = w such that uw ∈ RF(wuw ), it follows that wuw ∈ A * u(D ∩ U ) * that implies, from Item 2 of Lemma 5, that wuw ∈ A * uU * . Conversely, we assume R S \ A * uU * = ∅, and we shall prove that To finish this section, we state that, in the case when u ∈ F(v), we obtain a new case where R S is effective rational set. We need the following result The construction also needs the set E = {x ∈ D | ux ∈ R S } that will also be used in the following section. First we prove that E is effectively computable in order to get a decidable property: ---→ zu since there is only one occurrence of u in ux and x = ε.

A * v(D \ U ) ∩ A * uU * = ∅ by considering a shortest derivation w * -→ βu from some w ∈ R S \ A * uU * to some word βu ∈ A * u. Since w ∈ A * u,
Proposition 7. If u ∈ F(v) then ∀w, w ∈ A * , wuw ∈ R S =⇒ uw ∈ R S .
Lemma 8. If u ∈ F(v) then the set E = {x ∈ D | ux ∈ R S } is an effectively computable set. Proof. Let D 1 = {x ∈ D | vx ∈ A * u} and, for all integer i > 1, D i = {x ∈ D | vx ∈ A * uD * i-1 } ∪ D i-1 . Let D = i≥1 D i .
If n = 1, it follows vx = zu so x ∈ D 1 ⊆ D . Else vx = αuβ n-1 ---→ zu with β ∈ D + and, from Proposition 7, uβ ∈ R S . Now, from Lemma 7, we get αuβ = αuβ 1 . . . β k m -→ β 1 uβ 2 . . . β k p -→ zu.
Moreover, since all the derivations from a word to another word have the same length, it follows m + p = n -1 so m < n and p < n. By induction, we get β j ∈ D for 1 ≥ j ≥ k. Let i be the greatest integer such that β j ∈ D i for 1 ≥ j ≥ k, we get vx = uβ 1 . . .

β k ∈ A * uD * i so x ∈ D i+1 ⊆ D .
And we get as a corollary:

Proposition 8. If u ∈ F(v) then R S = A * uE * so R S is an effective computable rational set. Proof. Since u ∈ R S and uE ⊆ R S , we get A * uE * ⊆ R S .
Conversely, let wuw ∈ R S with w ∈ D n for some n ≥ 0. From Proposition 7, it follows uw ∈ R S . We shall prove by induction over n that w ∈ E * .

• If n = 0 then w = ε ∈ E * .
• Else w = xy with x ∈ D n-1 and y ∈ D. From Lemma 7 and Proposition 7, it follows ux ∈ R S and uy ∈ R S so y ∈ E and, from the inductive hypothesis, x ∈ E * so w = xy ∈ E * that finishes the proof of the equality R S = A * uE * .

Prefixal one-rule systems are FIN/CF

In this section, we shall prove that the image of all word w by a prefixal one-rule rewrite system S = {u → v} is always context-free by defining a context-free grammar G w such that L(G w ) = S * (w). If S = {u → v} is a prefixal one-rule rewrite system then S clearly satisfies the following property P R : for all words α and α , if αu -→ α u then αv -→ α v. Symmetrically, all suffixal one-rule rewrite system satisfies the property P L : for all words α and α , if uα -→ uα then vα -→ vα . Although property P R does not give a characterization of prefixal systems, for all one-rule rewrite system that satisfies it, we shall prove the following nice property: if a word w belongs to R S \ A * u then a shortest derivation from w to a word in A * u can be obtained by applying each rewriting step on the rightmost occurence of u. The following lemma shows that properties P R and P L are decidable.

Lemma 9. Let S = {u → v} be a one-rule rewrite system with |u| ≤ |v|. The three following statements are equivalent:

1. (RF(u) \ {u}) ∩ X ⊆ Z. 2. S satisfies the P R property. 3. ∀α, α ∈ A * , if αu * -→ α u then αv * -→ α v.
Proof. 1 =⇒ 2: Let us consider one step of derivation αu -→ α u for some words α and α . If α -→ α then αv -→ α v. Else u = u 1 u 2 = u 2 u 3 and v = v 1 u 2 for some words u 1 , u 2 , u 3 , v 1 with u 2 = ε and α = xu 1 , α = xv 1 for some word x. If u 1 = ε then α u = αv 1 u = αv and we get αv -→ α v, so we may assume u 1 = ε. It follows u 2 ∈ (RF(u)\{u})∩X that implies u 2 ∈ LF(v). So we get v = u 2 v 1 for some word v 1 and finally: αv

= xu 1 v 1 u 2 = xu 1 u 2 v 1 - → xv 1 u 2 v 1 = xv 1 v = α v.
2 =⇒ 3: This is an easy induction, using Corollary 1 that states that if αu -→ w * -→ α u then w ∈ A * u.

3 =⇒ 2: Let us suppose αu -→ α u then αu -→ α u -→ α v. From 3, it follows αv * -→ α v and we get αu -→ αv * -→ α v. Since, given two words w and w , all the derivations from w to w have the same length, it follows αv -→ α v.

2 =⇒ 1: Let u 1 , u 2 , u 3 , v ∈ A * with u = u 1 u 2 = u 2 u 3 , v = v u 2 and u 1 , v = ε; we have to prove u 2 ∈ LF(v). Since u 1 u = uu 3 - → vu 3 = v u, it follows from 2 u 1 v - → v v.
One can distinguish two cases:

(i) u ∈ LF(v). It follows u 2 ∈ LF(u) ⊆ LF(v). (ii) u ∈ LF(v).
It follows u ∈ dbA * and v ∈ daA * for some distinct letters a, b and some word d. That implies u 1 v ∈ dbA * and v v ∈ daA * : indeed,

u 1 u = uu 3 ∈ dbA * so u 1 d ∈ dbA * since u 1 = ε and v u = vu 3 so v d ∈ daA * since v = ε. Since u 1 v - → v v, we get u 1 v ∈ uA * that implies u 2 ∈ LF(v).
The following proposition establishes connections between P R , P L , u ∧ l v and u ∧ r v: Observe that, as we said before, property P R does not characterize prefixal onerule systems: S = {ba → aa} satisfies P R since RF(u) ∩ X = ∅ ⊆ Z and S is not prefixal. Nevertheless, we have the following result that will be used later:

Lemma 10. Let S satisfying P R . If αuβ * -→ α u for some α, α ∈ A * and some β ∈ D * then the following properties are satisfied: This lemma allows us to give the following definition that will be used in the definition of the context-free grammar: Definition 1. Let S satisfying P R , we define inductively ϕ : R S → A * u for all word w ∈ R S by ϕ(w

1. if β = ε then αvβ * -→ α u, 2. αvβ * -→ α v,
) = w if w ∈ A * u otherwise ϕ(w) = ϕ(αvβ) if w = αuβ with β ∈ D + .
This definition is sound since there is no ambiguity for the factorization of arguments of ϕ from Proposition 4. Moreover, the fact that all the derivations from a word to another have the same length, together with Lemma 10, ensure the termination of this recursive definition. Clearly, we get that if w * -→ zu for some words w and z, it holds that w * -→ ϕ(w) * -→ zu. More, thanks to Lemma 7, we can state: When u = ε, each one-rule rewrite system S = {u → v} is FIN/CF regardless of the right-hand side v, so, in the rest of this section, we assume that u = ε and that S is prefixal i.e. v = uf for some word f = ε and u = u 0 c with c ∈ A. Recall that such a system satisfies P R . We are now able to prove: Proposition 11. Each prefixal one-rule rewrite system is FIN/CF.

Clearly, every prefixal one-rule rewrite system S = {ε → f } for some word f is FIN/CF so we assume u = u 0 c for some word u 0 and some letter c. In order to prove the proposition, we shall use the following grammar for all prefixal one-rule rewrite system S = {u → uf } and all word w: We define the grammar G w = A, V, S w , R where

Let K 0 = sup({|ϕ(ue)| | e ∈ E}) and K = sup({|w|, K 0 , |uf |}). Let A ≤K = {α ∈ A * | |α| ≤ K} and B = A ≤K ∪ {αuβ | |αu| ≤ K ∧ |uβ| ≤ K}.
• V is the set of variables, V = {S α | α ∈ B} ∪ {S α | α ∈ B},
• S w is the axiom,

• and R ⊆ V × (V ∪ A) * is the set of production rules, R = {S α → α, S u0α → α, S αβ → S α S β , S αβ → S α S β | α, u o α, αβ ∈ B} ∪ {S αuβ → S αu0 S uβ , S αuβ → S αu0 S uβ | αuβ ∈ B} ∪ {S u → S uf , S u → S uf } ∪ {S ueβ → S e uβ | ueβ ∈ B, e ∈ E, β ∈ E * , ϕ(ue) = e u}
Intuitively, a variable S α may produce S * (α) and a variable S α may produce u -1 0 S * (α). The proof of Proposition 11 consists in the proof of the equality between S * (w) and L(G w ). Given a prefixal one-rule rewrite system S = {u → uf } and a word w, we prove the following lemma for the inclusion S * (w) ⊆ L(G w ):

Lemma 12. For all α ∈ B, if α * -→ S α then S α * --→ Gw α and if α = u 0 α then S α * --→ Gw α .
Proof. The proof is an induction on the length of the derivation in S: α * -→ α . If α = α , we can use the rules S α → α and S u0α → α, otherwise we may assume that α is right-complete with respect to α: indeed if α = α 1 α 2 and α = α 1 α 2 for some words α 1 , α 1 and α 2 with α 1 right-complete with respect to α 1 , there exist the rules S α1α2 → S α1 S α2 and S α2 → α 2 , moreover, if α 1 α 2 = u 0 α for some word α , we have α 1 = u 0 α 1 for some word α 1 since |α 1 | ≥ |u| and we can use the rules S α1α2 → S α1 S α2 and S α2 → α 2 .

Since α is right-complete with respect to α, there exists a derivation α = α 1 uα 2 * -→ zu -→ zuf * -→ α with α 2 ∈ E * by Proposition 8. Moreover, from Proposition 10, there exist two words α 1 and α 2 such that α = α 1 α 2 and α 1 u 0 * -→ α 1 and uα 2 * -→ u 0 α 2 . Note that we cannot have uα 2 = u 0 α 2 : indeed that would lead to a derivation α 1 uα 2 = α 1 u 0 cα 2 * -→ α 1 cα 2 = α that is not right complete, a contradiction. It follows uα 2 + -→ u 0 α 2 and we get from the inductive hypothesis on the length of the derivation α 1 u 0 * -→ α 1 that S α1u0 * -→ α 1 and, if α 1 = u 0 α 1 then S α1u0 * -→ α 1 . It remains to prove S uα2 * -→ α 2 for which we consider two cases: So we have:

(i) α 2 = ε. In this case, u - → uf * -→ u 0 α 2 . Since K ≥ |uf |,
• S α1u0 * -→ α 1 , • if α 1 = u 0 α 1 then S α1u0 * -→ α 1 , • S uα2 * -→ α 2 ,
and finally we get

S α = S α1uα2 - → S α1u0 S uα2 * -→ α 1 α 2 = α . Moreover, since |α 1 | ≥ |u 0 |, if α = u 0 α
for some word α , it follows that α 1 = u 0 α 1 for some word α 1 and we have

S α = S α1uα2 - → S α1u0 S uα2 * -→ α 1 α 2 = α
Conversely, an easy induction over the length of the derivations permits to state the following lemma, which gives, together with Lemma 12, a proof for Proposition 11:

Lemma 13. For all α ∈ B, if S α * --→ Gw α then α * -→ S α and if S α * --→ Gw α then α * -→ S u 0 α .

Non FIN/CF One-Rule String Rewrite Systems

The aim of this section is to prove that Proposition 11 cannot be generalized to every one-rule string rewrite system and we produce here an example of non FIN/CF one-rule string rewrite system. A example of non FIN/CF system has been provided by Matthias Jantzen in [START_REF] Jantzen | A note on a special one-rule semi-thue system[END_REF][START_REF] Jantzen | Confluent String Rewriting[END_REF] in the case of Thue systems i.e. string rewrite systems with symmetric rules. Jantzen proved that for S = {ε → abba, abba → ε} and each word w ∈ (a + b) * , S * (w) is not a context-free language. Here, we want to find a one-rule string-rewrite system S = {u → v}, as simple as possible, and a word w for which S * (w) is not a context-free language. The following proposition, that is a consequence of a result of [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF], shows that, for such an example, the left-hand side of the rule u must contain at least two distinct letters:

Proposition 12. Let S = {u → v} be a one-rule string rewrite system. If u ∈ a * for some letter a then S is FIN/CF.

Proof. Let S = {a i → v} be a one-rule rewrite system over an alphabet A. If i = 0 or v ∈ a * the property is clearly true. Otherwise there exists some letter b, distinct from a, that occurs in v. Such a system, that is called rewrite system with an inhibitor by McNaughton [START_REF] Mcnaughton | Semi-thue systems with an inhibitor[END_REF] have been proved FIN/CF by Geser et al. [START_REF] Geser | Termination proofs for string rewriting systems via inverse match-bounds[END_REF].

The example that we produce is the system S 1 = {ba → abab}. From above, we cannot find a simplest left-hand side of rule. We shall proceed in two steps: first, find a word w for which S * 1 (w) is not a context-free language and second, prove that we cannot find a simpler example. The proof of the first step uses the fact that the symmetric closure of S 1 is simplifiable. This notion of simplifiable system has been already used in [START_REF] Latteux | One-rule length-preserving rewrite systems and rational transductions[END_REF], a previous work on some one-rule string rewrite systems that are equivalent to a rational transduction. For any rewrite system S, we denote by S ↔ its symmetric closure:

S ↔ = S ∪ S -1 = S ∪ {v → u | u → v ∈ S}.
We say that a rewrite system is left simplifiable if for every words w, w and w , it holds that ww ∈ S * (ww ) implies w ∈ S * (w ). We define symmetrically the notion of right simplifiable rewrite system and we say that a rewrite system is simplifiable if it is both left simplifiable and right simplifiable.

Clearly, if a and b are distinct letters then any system S = {au → bv} , where u and v are arbitrary words, is left simplifiable. It is also true for S ↔ , the symmetric closure of S as stated in the following lemma. In the following, in order to simplify the notation for the derivations in a symmetric closure of a system S ↔ , we shall write ← → instead of --→ S ↔ for a single step of rewriting and * ← → instead of * --→ S ↔ for a derivation. Lemma 14. Let S = {u → v} with u, v ∈ A + . The three following statements are equivalent:

1. S is left simplifiable, 2. S ↔ is left simplifiable, 3. u ∈ aA * and v ∈ bA * for some distinct letters a and b.

Proof. Clearly 1 is equivalent to 3 and 2 implies 3; it remains to prove 3 implies 2. Assume u ∈ aA * and v ∈ bA * for some distinct letters a and b, we have to prove that for any words w, w and w it holds that ww * ← → ww implies w * ← → w . The proof is by induction on the length of the derivation ww * ← → ww . If this length is null, the property is trivially satisfied, otherwise we may clearly assume that w = x for some letter x. If x = a and x = b, the property is clearly true, otherwise we assume x = a, the proof in the case Remark 3. Clearly the previous lemma can be symmetrically stated in the case of a system S = {ua → vb} where a and b are two distinct letters. As a consequence, we get that the system S 1 = {ba → abab} is simplifiable.

We can now state: Proposition 13. Let S 1 = {ba → abab}. The language S * 1 (baba) is not a context-free language.

Proof. We shall prove that S * 1 (baba) ∩ a * (ba

) * b * = {a n (ba) f(n) b n | n ≥ 0} where f(n) is defined inductively by f(0) = 2 and f(i + 1) = 2 × f(i) -1. As (ba) n * -→ (ab) 2n = a(ba) 2n-1 b, an easy induction over n proves that {a n (ba) f(n) b n | n ≥ 0} ⊆ S * 1 (baba)
. Conversely, we observe first that S * 1 (baba) ∩ a * (ba) * b * is clearly included in {a n (ba) p b n | n, p ≥ 0}. We also observe that for non negative integers i and j, it holds that if (ba) i * ← → (ba) j then i = j. Indeed assume j > i, since S 1 is simplifiable it follows ε * ← → (ba) j-i a contradiction. This implies, using once again that S 1 is simplifiable, that for every non negative integers n, p and q, if a n (ba) p b n * ← → a n (ba) q b n then p = q. So for every non negative integer n, f(n) is the unique integer p such that baba * ← → a n (ba) p b n and that implies that

S * 1 (baba) = {a n (ba) f(n) b n | n ≥ 0} that is not a context-free language.
We have seen with Proposition 12 that for any example of non FIN/CF one-rule rewrite system S = {u → v}, the left-hand side u must contains two distinct letters so ba is among the two shortest possibilities. In order to show that S 1 is a smallest example of non FIN/CF one-rule rewrite system, we consider now different cases for the right-hand side v.

Let S = {ba → v} be a non FIN/CF rewrite system. We first observe that both a and b must occur in v otherwise, for every word w, S * (w) is finite. At last, if |v| a = |u| a or if |v| b = |u| b , such a one-rule string rewrite system S, called grid system in [START_REF] Geser | Decidability of termination of grid string rewriting rules[END_REF] in the context of the uniform termination, has been proved FIN/CF in [START_REF] Latteux | On one-rule grid semi-thue systems[END_REF]. All these observations imply that |v| a > 1 and |v| b > 1 so it is not possible to find a smaller example than S 1 .

Remark 4.

• For S 1 = {u → v} with u = ba and v=abab, clearly, S * 1 (u) = {a n (ba)b n | n ≥ 0} and so is a context-free language. It is not always the case: for instance, if we consider the system S 1 = {ba → ababab}, a proof very similar to the proof of Proposition 13 permits to show that S * 1 (w) is not context-free as soon as ba ∈ F(w).

• In [START_REF] Latteux | On one-rule grid semi-thue systems[END_REF], another example of a simple non FIN/CF rewrite system was given: S 2 = {u → v} with u = ba and v=aabb for which S * 2 (bbaa) is not a context-free language. The system S 1 enjoys two properties that are not satisfied by S 2 : for S 1 , u ∈ F(v) and S -1

• The systems S 1 and S 2 are the only non FIN/CF systems in the form S = {ba → v} with |v| a = |v| b = 2: indeed if v ∈ {abba, baab, baba} then the corresponding system is prefixal or suffixal and for S 3 = {u → v} with u = ba and v=bbaa there exists neither right nor left overlap between u and v nor u itself. That implies that for every word w, the set S * 3 (w) is context-free since it can be obtained by replacing each occurrence of ba in w by the language {b n a n | n > 0}. More precisely S * 3 corresponds to the composition of an inverse morphism and a context-free substitution.

Decidability of the Rationality

The aim of this section is to give a decidable characterization of prefixal onerule string rewrite systems that are rational transductions. Observe that this property is stronger than preserving regular languages: for instance every system S = {u → v} with |v| ≤ 1, called inverse context-free rewrite system in [START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF], preserves regular languages ([BO93]) but need not be rational transductions: S = {aa → ε} corresponds to the restricted Dyck reduction for which (S -1 ) * (ε) is not a regular language so (S -1 ) * is not a rational transduction that implies that S * is not a rational transduction either.

We shall first prove that for any prefixal system S = {u → uf }, it holds that S * (u) ∈ RAT if and only if S * (u) = uf * . Despite the fact that this result holds in both cases u ∈ RF(uf ) and u ∈ RF(uf ), the proofs are different in these two cases. First we state: Lemma 15. Let S = {u → uf } be a prefixal one-rule rewrite system such that u ∈ RF(uf ) and r be the root of f . The three following statements are equivalent:

1. S * (u) ∈ RAT, 2. S * (u) = uf * , 3. ur is the shortest member of A + u ∩ LF(uf ).

Proof. 1 =⇒ 3: Let xu = uy be the shortest word in A + u ∩ LF(uf ). Hence x and y are primitive words. Let us assume y = r; it follows f ∈ y * and f = y t z for some t > 0 with z = ε and y ∈ LF(z). We claim that z ∈ LF(y): indeed, since x t u = uy t , we get u ∈ RF(uy t ), and, together with u ∈ RF(uy t z), that implies u ∈ RF(uz). If we assume |z| < |y|, it follows uz ∈ LF(uf ) and z ∈ LF(y). Hence, {y, z} is a prefix code. We shall prove the following property, by induction on the length of the derivation:

∀k ≥ 0, ∀w ∈ A * , x k uw ∈ S * (u) =⇒ k ≤ t|w| (1)
Let us consider the derivation u * -→ dug -→ duf g = x k uw, for some words d and g, with xu ∈ LF(uw) and let us distinguish two cases:

(i) d = x p for some p. Recall that x t u = uy t and f = y t z so duf g = dx t uzg.

Since xu = uy and {y, z} is a prefix code, we get xu ∈ LF(uzg). It follows k = p + t and w = zg. From the inductive hypothesis, we have p ≤ t|g| so k = p + t ≤ t|zg|.

To prove 3, observe first that f ∈ r * : indeed, if f ∈ r * then uf i ∈ ur * that implies xu ∈ ur * and u ∈ RF(r * ), a contradiction. Now, since r is a primitive word, rf ∈ RF(r * ) and rf = z r j for some j with {z , r} a suffix code. Moreover xu = uf i-1 f = xzr p ∈ A * rf = A * z r j , that implies p = j, so rf = z r p with {z , r} a suffix code. We also have:

r ∈ RF(uf ) ⇐⇒ r ∈ RF(u) (4) Indeed from w 0 = xur t = uf i-2 f 2 = uf i-2 f r t f r t , it follows xu ∈ A * rf so xuf ∈ A * rf f . Now if r ∈ RF(uf ), we get r ∈ RF(rf f ) so r ∈ RF(rf ) that implies xu ∈ A * r.
Moreover, u ∈ RF(r) and it follows r ∈ RF(u); the converse implication is clear.

We are now able to prove 2 by considering two cases:

(i) p > 0. From the equality v = zr p f r t , we get, from 3, v = zr p-1 z r p+t and we can set v = z r p+t with z = zr p-1 z . (ii) p = 0. From 4 it follows r ∈ RF(uf ). Moreover, since uy ∈ A + uA * , we get uf ∈ RF(r) and we can set v = z r p+t with z = uf = zf .

We now use 2 to prove the key equation:

∀w, k, wr k ∈ S * (u) =⇒ k ≤ (p + t)|w| (5)
The proof is an induction over the length of the derivation from u to wr k . If u = wr k then w = zr As a consequence of the two previous lemmas, we get:

Proposition 14. If S = {u → uf } is rational then S * (u) = uf * .
The rest of this section is devoted to the converse of Proposition 14: if S = {u → uf } with S * (u) = uf * , then S is rational. First, we prove:

Lemma 17. Let S = {u → uf } be a prefixal one-rule rewrite system. If S * (u) = uf * then for all w ∈ A * , S * (uw) is a rational language.

Proof. If u = ε, then S * (uw) = f * t(w) where t is the rational substitution defined by: ∀x ∈ A, t(x) = xf * . Else, u = u 0 c for some word u 0 and some letter c. We make an induction on |w|, the length of the word w. If w = ε, S * (uw) = uf * else, we observe that if uf * w ∩ A + uA * = ∅, it follows S * (uw) = uf * w so we assume uf * w ∩ A + uA * = ∅ and we denote i, the smallest integer such that uf i w ∈ A + uA * . Let us consider the rightmost occurrence of u in uf i w: we set uf i w = xuy with x = ε and y ∈ A * uA * . From Proposition 10, we get S * (xuy) = S * (xu 0 )[(u 0 ) -1 S * (uy)]. Let us distinguish two cases:

(i) xu = uf i w with w = w y and w = w c. From the inductive hypothesis, S * (uw ) and S * (uy) are rational languages. It follows from the definition of the integer i that S * (uf i w ) is a rational language; indeed we get S * (uw ) = uw + uf w + • • • + uf i-1 w + S * (uf i w ) so S * (uw ) \ S * (uf i w ) is finite. As a consequence, we get that S * (uf i w) = S * (uf i w )[u -1 0 S * (uy)] is rational since . That finally implies that S * (uw) is a rational language since S * (uw

) = uw+uf w+• • •+uf i-1 w+S * (uf i w). (ii) xu ∈ LF(uf i ). In this case, since S * (u) ∩ A + uA * = ∅, Lemma 16 implies u ∈ RF(uf ) that also implies uw ∈ A + uA * . It follows uf * ⊆ A * u so S * (uw) = uf * w is rational.
In the following, we consider a prefixal one-rule rewrite system S = {u → uf } over an alphabet A and we assume S * (u) = uf * . The system S is rational if and only if the language M = {(w, w ) | w ∈ S * (w)} is a rational subset of A * × A * (See [START_REF] Berstel | Transductions and context-free languages[END_REF] for a reference study on rational transductions and their use for the classification of context-free languages.). If we denote L = {(w, w ) | uw ∈ S * (uw)}, we observe that if L is rational, so is M : indeed M can be obtained as M = Id ∪ Id(u, u)L where Id = {(w, w) | w ∈ A * }. So, it remains to prove that L is a rational language.

Let R = {w | uw ∈ A + u ∧ uw ∈ A + uA + } and K = {w | uw ∈ A + uA * }.
Intuitively, R permits to point out all the left factors of uw that are in

A + u. Clearly ε ∈ K and A * = R * K. One can also observe that if u = ε then R = A and K = {ε}. Let L R = L ∩ (R × A * ) and L K = L ∩ (K × A * ).
We first prove:

Lemma 18. L = (L R ) * L K . Proof. It is easily seen that L R L = {(w 1 w 2 , w 1 w 2 ) | (w 1 , w 1 ) ∈ L R , (w 2 , w 2 ) ∈ L} is included in L. It follows L = (L R ) * L that implies (L R ) * L K ⊆ L.
For the converse inclusion, let (w, w ) ∈ L; we consider two cases:

(i) uw ∈ A + uA + . In this case, w ∈ K ∪ R that implies (w, w ) ∈ L R ∪ L K ⊆ (L R ) * L K . (ii) uw ∈ A + uA + .
In this case, w = w 1 w 2 with w 1 ∈ R. So uw 1 = αu for some word α and by Corollary 2 it follows uw = w 1 w 2 for some words w 1 , w 2 with uw 1 = αu * -→ w 1 and uw 2 * -→ uw 2 . Observe that w 1 = uw 1 for some word w 1 since u -→ uf , that implies w = w 1 w 2 . Now, from the inductive hypothesis over the length of w, we get (w 2 , w 2 )

∈ (L R ) * L K . Moreover (w 1 , w 1 ) ∈ L R so (w, w ) = (w 1 , w 1 )(w 2 , w 2 ) ∈ (L R ) * L K .
For all word e ∈ E, we denote R e = u -1 S * (ϕ(ue))) where ϕ is the function defined in Definition 1 and we define U = e∈E ({e} × R e ) and V = ({ε} × f * )U * Id. From Lemma 17, R e ∈ RAT and, since E is finite, U and V are rational subsets of A * × A * . We get:

Lemma 19. L K = V ∩ (K × A * ).
Proof. Since V is clearly included in L, we have the inclusion V ∩(K×A * ) ⊆ L K . Conversely, let (w, w ) ∈ L K . The proof is an induction over |w|, the length of the word w. If w = ε then w ∈ f * , so (w, w ) ∈ {ε} × f * ⊆ V ∩ (K × A * ); if |w| > 0, since w ∈ K, it follows uw ∈ A + uA * , so u = ε and we consider two cases:

(i) uw is not right-complete with respect to uw. In this case, uw = uw 1 y and uw = uw 1 y for some y = ε and uw 1 * -→ uw 1 . From the inductives hypothesis, we get (w 1 , w 1 ) ∈ V that implies (w, w ) = (w 1 , w 1 )(y, y) ∈ V . Proof. Let us first consider the case u = ε. In this case, R = A, K = {ε}, L R = a∈A ({a} × f * af * ), U = ∅ and V = ({ε} × f * )Id. It follows that L R ⊆ V ({ε} × f * ) so we have L R = V ({ε} × f * ) ∩ (R × A * ). We now assume u = ε, so u = u 0 c for some word u 0 and some letter c. The inclusion V ({ε} × f * ) ∩ (R × A * ) ⊆ L R is clear. To prove the converse inclusion, let (w, w ) ∈ L R . Since w ∈ R, w = w 0 c for some word w 0 and, since uw 0 c * -→ uw , w can be factorized as w = w 1 cw 2 with uw 0 * -→ uw 1 and u * -→ uw 2 from Proposition 10. That implies w 2 = f i for some integer i so w = w 1 cf i . Now, since w = w 0 c ∈ R, it follows uw 0 c ∈ A + uA + that implies uw 0 ∈ A + uA * so w 0 ∈ K. As a consequence, we get (w 0 , w 1 ) ∈ L K = V ∩ (K × A * ) so (w 0 c, w ) = (w 0 , w 1 )(c, c)(ε, f i ) that is in V ({ε} × f * ).

As a consequence of Lemma 18, Lemma 19 and Lemma 20, we get that L is a rational subset of A * × A * that implies that S is rational, so using also Proposition 14, we can state:

Conclusion and Perspectives

We have proved in Proposition 11 that the image of a finite language by a prefixal one-rule rewrite system is always context-free, a property that is not satisfied by an arbitrary one-rule rewrite system as shown in Proposition 13. This question can be extended to rational languages rather than finite ones: are prefixal one-rule rewrite systems RAT/CF? And, in the case of a negative answer, is it possible to decide, given a prefixal one-rule rewrite system S = {u → uf } whether it is RAT/CF? More generally, we do not know whether prefixal onerule rewrite systems preserve context-free languages like inverse match-bound rewrite systems.

Of course, some of these questions deserve to be studied in the more general case of one-rule rewrite systems: is it possible to decide, given a one-rule rewrite system S = {u → v} Q 1 ) whether, S * preserves rational languages ?

Q 2 ) whether for all word w, S * (w) is a rational language ?

Q 3 ) whether, given a word w, S * (w) is a rational language ? Q 4 ) whether, S * preserves context-free languages ? Q 5 ) whether for all word w, S * (w) is a context-free language ? Q 6 ) whether, given a word w, S * (w) is a context-free language ?

Note that the following one-rule rewrite system S = {ba → a 2 b} gives an interesting example of a system where for all word w, S * (w) is a context-free language, but where S * (b * a) ∩ a * b * = {a 2 p b p | p ≥ 0} is not a context-free language.

We also remark that, in the case of prefixal one-rule rewrite systems, only Q 4 is an open question. Indeed, we have positively answered to Q 1 and Q 2 and, using the technics of Section 6, it is possible to positively answer to Q 3 by proving that S * (w) is a rational language if and only if S * (u) is rational or w ∈ A * uA * . Trivial positive answer to Q 5 and Q 6 is a direct consequence of Proposition 11.

Proposition 16 gives a decidable characterization of rational prefixal one-rule rewrite systems. We observe that we are unable to give such a decidable characterization for one-rule length-preserving rational rewrite systems S = {u → v}, that is in the case when |u| = |v| and u = v: indeed, it is conjectured that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u = xyz and v = zyx ([TS00, LR14, LR15]). This conjecture is still open. More generally, one can wonder whether this property is decidable for an arbitrary one-rule rewrite system.

  is the binary relation over words defined by : ∀w, w ∈ A * , w -→ w iff there exists u → v ∈ S and α, β ∈ A * such that w = αuβ and w = αvβ. The relation * -→, called derivation relation, is the reflexive and transitive closure of the relation -→ and we denote + -→the transitive closure of the relation -→ . For a derivation w = w 0 → w 1 • • • → w n = w , n is called the length of the derivation. A rewrite system S induces a transformation over languages: for every word w ∈ A * , we shall denote S * (w) the set S * (w) = {w ∈ A * | w * -→ w } and S + (w) the set S + (w) = {w ∈ A * | w + -→ w }; then, for every language L ⊆ A * , S * (L) = w∈L S * (w) and S + (L) = w∈L S + (w).

  Proof. D = ∅ if and only if there exist words u , α, α , α , β and two distinct letters x and y such that uu = αyβu , vu = α xβu and u = α xβu . It is equivalent to the existence of a word (xβ) in RF(v) ∩ F(u) which is not in RF(u) (since yβ ∈ RF(u)). Let d = u ∧ r v. Clearly, dD ⊆ A * d that implies dD * ⊆ A * d. Since u = v and |v| ≥ |u|, there exists some letter a ∈ A such that v ∈ A * ad and we can characterize D as D = {u ∈ A * | adu ∈ RF(u)}.

Proposition 4 .

 4 uD * ∩ A + uA * = ∅. The two following lemmas assume that u ∈ A * bd and v ∈ A * ad for some word d and two distinct letters a and b. Lemma 3. Let w ∈ D * and a word z that satisfy zw ∈ D * with bd ∈ RF(bdz) then z ∈ D * .

  Proof. First observe that the property is clearly true if D = ∅ by choosing w = z. So we assume D = ∅, u ∈ A * bd and v ∈ A * ad for some word d and some distinct letters a and b. We prove the property by induction on the length of derivation wuxy * -→ zu. Since y = ε, it follows from Proposition 4 that the length of the derivation wuxy * -→ zu is at least one. Assume wuxy -→ zu. It follows from Corollary 1 that zu = wvxy and, from Lemma 6, x = ε and y ∈ D. In this case, we can take w = w that gives the base case of our induction. Consider now a derivation wuxy -→ w * -→ zu for some word w . From Corollary 1, either w = wvxy, either w ∈ A * uxy. If w ∈ A * uxy, then w = w uxy for some word w with wu * -→ w u. From the inductive hypothesis, there exists some w such that w ux * -→ w u and w vxy * -→ zu. Hence we have wux * -→ w ux * -→ w u and w vy * -→ zu.

  That implies ug ∈ RF(A * v) so d ∈ RF(dg). On the other hand, we have already seen that dD + ⊆ A * bd. Now, from d ∈ RF(dg) and x ∈ D + , we get dgx ∈ A * bd which implies bd ∈ RF(bdgx). Since gxy = β ∈ D * and y ∈ D * , we get gx ∈ D * from Lemma 3. So we can apply the inductives hypothesis on the derivation wvxy = αugxy * -→ uz: there exists a word w with αugx * -→ w u and w vy * -→ zu that finishes the proof since we get wux -→ wvx = αugx * -→ w u and w vy * -→ zu.

  there exist words w , w 0 and w 0 such that w = w 0 uw 0 -→ w * -→ βu with w 0 ∈ D * \ U * . From the hypothesis on the length of the derivation it follows w ∈ A * uU * so w ∈ A * uw 0 , and, from Corollary 1, we get w = w 0 vw 0 . On the other hand, it follows w 0 = xyz with x, z ∈ D * and y ∈ D \ U from Item 5 of Lemma 5. Now, by Lemma 7, we get w 0 uxyz * -→ α 1 uyz * -→ α 2 uz * -→ βu for some words α 1 and α 2 . From the hypothesis on the length of the derivation, it follows x = z = ε and we get w = w 0 vy ∈ A * v(D \ U ). Since w ∈ A * uU * , this finishes the proof of the lemma.We can also characterize when the equality R S = A * uD * = A * uU * holds:Proposition 6. R S = A * uD * = A * uU * if and only if D ⊆ U . Proof. We have seen before that if D ⊆ U , the equality R S = A * uD * = A * uU *is a direct consequence of Proposition 3. Conversely, assume R S = A * uD * = A * uU * and let us consider a word w ∈ D. Since A * uD * = A * uU * , it follows uw ∈ A * uU * . Moreover, from Proposition 4, uw ∈ A + uA * so w ∈ U * . Since w ∈ D ∩ U * , it follows from Item 4 of Lemma 5 that w ∈ D ∩ U .Clearly, R S = A * uD * if and only if for each word w ∈ D, it holds that uw ∈ R S and we shall see at the end of this section that this property is decidable. We now state that the inclusions A * uU * ⊆ R S and R S ⊆ A * uD * , given in Proposition 3, can independently be strict or not by considering the four following examples:(i) As said before, a case where A * uU * R S A * uD * is given in Example 1 where R S is not rational. (ii) A case where A * uU * = R S = A * uD * is given by any system S where u ∈ RF(v). Indeed, in this case, D = ∅ ⊆ U and R S = A * u. (iii) A case where A * uU * = R S A * uD * is given by S = {u → v} with u = aab and v = bba: indeed we get for this example D = ab + b and U = ab. Clearly, ub ∈ R S so R S A * uD * . On the other hand, A * vb∩A * u(ab) * = ∅ and it follows R S = A * uU * from Proposition 5. (iv) A case where A * uU * R S = A * uD * is given by S = {u → v} with u = aab and v = aaba: in this case, U = ab and we have already seen in Remark 1 that R S = A * uD * . Moreover ub ∈ R S and ub ∈ A * uU * .

Proof.

  The proof is by induction over the length of a shortest derivation from wuw to a word of A * u, say zu. If wuw = zu then u ∈ RF(uw ) so uw ∈ R S . Else wuw = αuβ with β ∈ D + . From Proposition 4, we have |uβ| ≤ |uw | so uw = γuβ for some word γ. Since β ∈ D + , it follows αuβ -→ w * -→ zu for some word w . From Corollary 1 we have to distinguish two cases: (i) w ∈ A * uβ: in this case, w = α uβ * -→ zu for some word α and it follows from the inductive hypothesis that uβ * -→ z u for some word z . That implies uw = γuβ * -→ γz u so uw ∈ R S . (ii) w = αvβ: since u ∈ F(v), we have v = α uβ for some words α and β . We can apply the inductive hypothesis on the derivation αα uβ β * -→ zu and we get uβ β * -→ z u for some word z . It follows uw = γuβ -→ γvβ = γα uβ β * -→ γα z u so uw ∈ R S .

  Clearly, since D ⊆ D, there exists some integer n such that D n = D n+1 = D so D is an effectively computable set. We shall now prove D = E.D ⊆ E: let x ∈ D we make an induction on the smallest i such thatx ∈ D i . If i = 1, it follows vx ∈ A * u so ux ∈ R S and x ∈ E. If i > 1, it follows vx ∈ A * uD * i-1. That implies vx = wuw for some word w ∈ A * and some word w ∈ D * i-1 . From the inductive hypothesis, we get w ∈ E * so vx ∈ R S which implies ux ∈ R S and x ∈ E. E ⊆ D : Let x ∈ D such that ux ∈ R S . We shall prove x ∈ D by induction on the length n of a derivation ux n -→ zu with z ∈ A + . From Proposition 4 we have ux -→ vx n-1

Proof.

  Assume β ∈ D + . From lemma 7, it follows αu * -→ α u and α vβ * -→ α u for some word α . From Lemma 9, we get αv * -→ α v so αvβ * -→ α vβ * -→ α u -→ α v. Assume now β = ε, we get αv * -→ α v from Lemma 9.

Lemma 11 .

 11 If αuβγ * -→ α u for some words α, α ∈ A * and β, γ ∈ D * , then αuβγ * -→ ϕ(αuβ)γ * -→ ϕ(αuβγ) * -→ α u.

Proposition 10 .

 10 If wuw * -→ w for some words w, w , w ∈ A * then w = w 1 w 2 with wu 0 * -→ w 1 and uw * -→ u 0 w 2 .Proof. The proof is an induction on the length of the derivation wuw * -→ w . The case wuw = w is immediate. Else, from Property 1, there exist words w 1 , w 2 , w 1 , z such that wuw = w 1 w 2 , w 1 w 2 = w and w 1 * -→ zu -→ zuf * -→ w 1 . Let us consider two cases:(i) |w 2 | > |w |. In this case, w 2 = γcw for some word γ ∈ A * . Let w 1 = w 1 γ and w 2 = cw . We get w = w 1 w 2 , wu 0 = w 1 γ * -→ w 1 γ = w 1 since w 1 * -→ w 1 and uw = u 0 w 2 . (ii) |w 2 | ≤ |w |.In this case, w 1 = wu 0 cγ and w = γw 2 for some word γ with wuγ * -→ zu -→ zuf * -→ w 1 . It follows wuγ = wγ uγ for some γ ∈ A * and some γ ∈ D * . Moreover, γ u ∈ uA * . From Lemma 10, we get wγ uf γ * -→ zuf so there exists a word w 0 = γ uf γ with uγ -→ w 0 and ww 0 * -→ zuf . Moreover, by γ u ∈ uA * follows w 0 = uw 0 for some word w 0 . Since all the derivations from a word to another have the same length, the length of the derivation wuw 0 * -→ w 1 is strictly smaller than the length of the derivation wuγ * -→ zu -→ zuf * -→ w 1 so we can apply the inductive hypothesis on the derivation wuw 0 * -→ w 1 and we get w 1 = w 1 w 2 for some words w 1 and w 2 with wu 0 * -→ w 1 and uγ -→ uw 0 * -→ u 0 w 2 . Moreover, denoting w 2 = w 2 w 2 , we have uw = uγw 2 * -→ u 0 w 2 w 2 = u 0 w 2 .Proposition 10 needs u = ε but one can directly derive the following less precise property that holds in the case u = ε: Corollary 2. If wuw * -→ w for some words w, w , w ∈ A * then there exists a factorization w = w 1 w 2 with wu * -→ w 1 and uw * -→ uw 2 .

  Observe that, clearly, B is closed by factor, that is B = F(B), and if ueβ ∈ B with e ∈ E and β ∈ E * , then ϕ(ue)β ∈ B: indeed let e u = ϕ(ue) then |e u| ≤ K 0 ≤ K and, from Proposition 4, there is only one occurrence of u in ueβ so |ueβ| ≤ K and it follows |uβ| ≤ K.

  we get from the inductive hypothesis for the derivation uf * -→ u 0 α 2 that S u -→ S uf * -→ α 2 . (ii) α 2 = ε. There exist some word β ∈ E * and some word e ∈ E such that α 2 = eβ. From Proposition 8 and Lemma 11, we get ueβ + -→ e uβ * -→ u 0 α 2 with e u = ϕ(ue). Since ueβ ∈ B with e ∈ E, β ∈ E * and e u = ϕ(ue), it follows e uβ ∈ B and we get from the inductive hypothesis for the derivation e uβ * -→ u 0 α 2 that S e uβ * -→ α 2 . Moreover S ueβ → S e uβ is a rule in G so S ueβ -→ S e uβ * -→ α 2 .

  x = b being completely symmetric. If no step α ← → β involved in this derivation satisfies α = uγ and β = vγ then clearly w * ← → w so we assume that the derivation aw * ← → aw can be factorized in aw * ← → uα ← → vα * ← → vβ ← → uβ * ← → aw . We can apply the induction hypothesis on the derivation vα * ← → vβ to get α * ← → β. This gives a shorter derivation aw * ← → uα * ← → uβ * ← → aw from aw to aw and, by the inductive hypothesis, we get that w * ← → w .

  (ii) uw is right-complete with respect to uw. In this case, uw * -→ zu * -→ uw for some word z. Since w ∈ K and R S = A * uE * from Proposition 8, it follows w ∈ E + . That implies w = ey with e ∈ E, y ∈ E * , so y ∈ K and we have from Lemma 11: uey * -→ e uy * -→ zu * -→ uw with e u = ϕ(ue).From Proposition 10, it follows that w = w 1 w 2 with ue * -→ e u * -→ uw 1 and uy * -→ uw 2 . So, (y, w 2 ) ∈ L K that implies (y, w 2 ) ∈ V from the inductive hypothesis and (e, w 1 ) ∈ U . Finally, we get (w, w ) ∈ U V ⊆ V .Lemma 20. L R = V ({ε} × f * ) ∩ (R × A * ).

  is clearly sufficient to prove uU * ⊆ R S which is immediate since for all word u ∈ U there exists some word v such that vu = v u. The last inclusion A * uD * ⊆ A * d directly comes from the inclusion dD * ⊆ A * d that we have seen before. It remains to prove R S ⊆ A * uD * . Since this inclusion is clearly true if D = ∅, we may assume D = {u ∈ A . The proof is by induction over the length of the derivation. If w = zu, we are done. Else w

* | adu ∈ RF(u)} with u ∈ A * bd and v ∈ A * ad.

Let w in R S and consider a derivation of minimal length w * -→ zu with z ∈ A *

  Proposition 9. Let S = {u → v} be a one-rule rewrite system with |u| ≤ |v|. Then 1. if |u ∧ l v| ≥ |u ∧ r v| then S satisfies P R , 2. if |u ∧ l v| ≤ |u ∧ r v| then S satisfies P L , 3. S satisfies P R or S satisfies P L , 4. if S is prefixal then S satisfies P R , 5. if S is suffixal then S satisfies P L , 6. if S is confluent then S satisfies both P R and P L .Proof. Let α = u ∧ l v and β = u ∧ r v and assume |α| ≥ |β|. Let us consider x ∈ RF(u) ∩ X, it follows |x| ≤ |β| that implies x ∈ LF(α) ⊆ LF(v) so x ∈ Z (a system where X ∩ Z = ∅ is called bordered in[START_REF] Geser | Non-looping string rewriting[END_REF]) and S satisfies P

R from Lemma 9. That proves 1 and symmetrically 2. Items 3, 4 and 5 are direct consequences of 1 and 2. For 6, it has been proved in

[START_REF] Kurth | Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel[END_REF][START_REF] Wrathall | Confluence of one-rule thue systems[END_REF]

that a one-rule rewrite system S = {u → v} with |u| ≤ |v| is confluent if and only if (LF(u) ∩ RF(u)) \ {u} ⊆ LF(v) ∩ RF(v) that implies that S satisfies both P R and P L .

  (ii) if β = ε, since r is a primitive word, it follows r 2 ∈ A

p-k so k ≤ p + t and |w| ≥ |z| > 0 that implies k ≤ (p + t)|w|. Else, u * -→ αuβ -→ αvβ = wr k . Let β = β r j with r ∈ RF(β ) and let us consider two cases: (i) if β = ε, we get p + j ≤ (p + t)|αz| from the inductive hypothesis. Thus k ≤ p + t + j ≤ p|αz| + t(|αz| + 1). Since |z | > |z|, it follows k ≤ (p + t)|αz | ≤ (p + t)|w|. * rβ . Thus k ≤ j + 1 and |wr| ≥ |αvβ | > |αuβ | + |r|. From the inductive hypothesis, we get j ≤ (p + t)|αuβ | that implies j < (p + t)|w| and k ≤ j + 1 ≤ (p + t)|w|. Finally, since xuy ∈ S * (u), we get {x n uy n | n > 0} = {x n ur tn | n > 0} ⊆ S * (u) and it follows from 5 that S * (u) ∈ RAT.

is not confluent.

Acknowledgments

The authors thank the anonymous reviewer for his very careful reading and his many insightful comments and suggestions.

(ii) d = x p x for some p with x = ε and x ∈ LF(x ). We claim that x u ∈ LF(x + u): else we have x u ∈ A + u ∩ LF(uy) ⊆ A + u ∩ LF(uf We observe that in the case when u = ε, Lemma 15 states that S * (ε) is rational if and only if the root of f is its first letter, so we get the well known result: for all rewrite system S = {ε → f }, S * (ε) ∈ RAT if and only if f ∈ a * for some letter a. In the case when S = {u → v} is a one-rule string rewrite system that satisfies u ∈ RF(v), we can state:

Lemma 16. Let S = {u → v} be a one-rule string rewrite system with u ∈ F(v) \ RF(v). The three following statements are equivalent:

Proof. Assume S * (u) ∩ A + uA * = ∅. It follows v = uf for some f and S * (u) = uf * that implies S * (u) ∈ RAT. It remains to prove that if S * (u) ∈ RAT then S * (u)∩A + uA * = ∅. We shall prove the contrapositive: assume S * (u)∩A + uA * = ∅ and let w 0 be the smallest word of S * (u)∩A + uA * . One can set w 0 = xuy with x = ε and uy ∈ A + uA * . Since u ∈ RF(v), Lemma 1 implies that S * (u) ∩ A + u = ∅. Thus y = ε and we can write y = r t for some primitive word r, and some t > 0. If u ∈ RF(r * ), it follows uy ∈ RF(r * ) and u ∈ RF(uy), a contradiction. Thus u ∈ RF(r * ) and u admits a factorization u = zr p with p ≥ 0 and {z, r} a suffix code. We shall first prove: v = z r p+t for some word z with {z , r} a suffix code and |z | > |z| (2)

If w 0 = v then we can set z = xz else v = uf and w 0 = uf i for some i > 1. By definition, y ∈ RF(f i ). By minimality of w 0 , we have |y| < |f |, and so f = f y for some f ∈ A + . We claim that: rf = z r p for some word z with {z , r} a suffix code (3)

Proposition 15. Let S = {u → uf } be a prefixal one-rule rewrite system. The three following statements are equivalent:

As a corollary, we get:

Corollary 3. Let S = {u → uf } be a prefixal one-rule string rewrite system. If f ∈ a + for some letter a then S is rational.

Proof. Assume f = a i for some i > 0. Let us consider two cases:

An important point is that Proposition 15 gives a characterization of rational prefixal one-rule rewrite systems that is decidable: indeed, given a prefixal system S = {u → uf } one can decide whether S * (u) is a rational language (or equivalently whether S * (u) = uf * ), thanks to the more general following result:

Proposition 16. Let S = {u → v} be a one-rule string rewrite system with u ∈ F(v). Then S is rational if and only if S * (u) is rational, moreover this property is decidable.

Proof. Let S = {u → v} with u ∈ F(v). There exist four cases:

From Lemma 16 it follows that S * (u) is not a rational language so S is not rational. (ii) v = uf = gu for some words f and g: from Lemma 15, we have to check the third statement of this lemma, that is clearly decidable. (iii) v = uf and u ∈ RF(uf ): the equivalence comes from Proposition 15.

Moreover the rationality of S * (u) is equivalent to the emptiness of S * (u) ∩ A + uA * from Lemma 16. To check whether S * (u) ∩ A + uA * is empty or not is equivalent to check whether uf * ∩ A + uA * is empty or not which is decidable. (iv) v = gu and u ∈ LF(gu): this case is symmetric to the previous one.


T Glanowski

Y Marco

V Le Saux

B Huneau

C Champy

P Charrier

Fatigue crack initiation around inclusions for a carbon black filled natural rubber: an analysis based on micro-tomography

The fatigue properties of filled elastomers are strongly related to the inclusions' population induced by their complex recipes and the successive stages of the manufacturing process (mixing, injection and curing). The improvement of these properties involves at first an ability to describe the statistical features of these inclusions' population in terms of size, geometry, nature and spatial distribution. Then a detailed understanding of the damage mechanisms is required in order to define the mechanical criticality of inclusions according to their characteristics under cyclic loading. The aim of the study is to take advantage of tomography observations that enable a three dimensional vision to access the statistical description of the inclusions population and of the related damage mechanisms. First of all, a tool to detect and characterize accurately inclusions and cracks is presented. Then, this tool is applied to an interrupted specimen in fatigue, for a compound filled with carbon black. A statistical analysis is performed on the nature of inclusions leading to cracks, on the kind of damage mechanisms (polar crack, cavitation between 2 inclusions or failure of an inclusion) and on the density and the geometric properties of activated inclusions. An additional focus is given on the inclusions leading to the biggest cracks in order to assess more precisely the features (nature, size...…)of the most critical inclusions for fatigue.

INTRODUCTION

The industrial development of elastomers resistant to fatigue is very complex because the parameters driving the microstructure are incredibly numerous, including the original ingredients and the processing parameters, from mixing to injection and curing.

In elastomeric parts, the fatigue cracks are initiated either at the parting line, which can be considered as a geometrical defect acting as a strain concentrator, or around inclusions. In carbon black filled natural rubber, the initiation around inclusions seems to prevail (Masquelier 2014). In the literature, different inclusionary initiation mechanisms are distinguished (Gent et al. 1984, Le Saux et al. 2011, Le Gorgu Jago 2012, Le Cam et al. 2013): inclusions failure, cavitation at one pole or between close inclusions and debonding at one or both poles. The mechanism is strongly related to the microstructure features such as the inclusions modulus, their shape, size and spatial distribution and the cohesion and adhesion properties. Huneau et al. (2016) described the inclusions which induced micro-cracks during fatigue loading thanks to observations of interrupted fatigued samples and fatigue fracture surfaces using a scanning electron microscope. The study highlights that fatigue damage generally initiates on carbon black agglomerates or on metallic oxides such as ZnO. It was shown that the ones on carbon black agglomerates are almost always followed by a crack propagation leading to the failure of the sample. Scanning Electron Microscopy (SEM) observations enable the analysis of debonding and failure mechanisms but not cavitation mechanism. Moreover, the generation of statistical results requires a huge number of observations. Thus, this experimental protocol is time consuming and difficult to apply on a lot of compounds. Another way to assess the fatigue damage evolution can be X-ray micro-tomography (Le Gorgu Jago 2008, Le Gorgu Jago 2012, Le Saux et al. 2011). In this case, a lot of inclusions and cracks can be observed within the analysis of one sample and for a rather large volume compared to SEM. The treatment used is almost always a thresholding method of the gray levels in order to have the size and the number of cracks or of the inclusions, usually denser than the matrix. Then, the initiation mechanisms and the damage evolution are identified from the geometry of the detected cracks and inclusions.

The aim of this study is to provide a well resolved and statistical description of inclusions and the related micro-cracks. First of all, the experimental set-up to characterize the initiation mechanisms is presented. Then, a tool is developed to provide an accurate description of the microstructure features of both inclusions and cracks. Finally, the results obtained for a natural rubber filled with carbon black are presented and the conclusions on the inclusions criticality are highlighted.

EXPERIMENTAL SETTINGS

Materials and experimental protocol

The material studied is a fully formulated natural rubber reinforced with carbon black. Classic hourglass samples are used to characterize the fatigue properties. These samples are injected and representative of the manufacturing process used for automotive anti-vibration parts.

The damage evolution is followed thanks to the observations of interrupted fatigued samples, as presented in Huneau et al. (2016). First of all, the Wöhler curve for relaxing testing conditions is determined for the compound. The number of cycles at initiation (Ni) is defined according to the loss of specimen stiffness (Ostoja-Koczynski 2003). Then, for the interrupted tests, the nominal maximal principal strain is set to 200% and the imposed amount of cycles is chosen as 60% of the number of cycles leading to initiation (Ni). (Fig. 1).

Experimental devices

Micro-tomography is a remarkable tool to provide a non-destructive internal observation. This method has been widely used for the study of materials microstructure (Salvo 2003) including rubber. Compared with usual 2D analysis methods such as the SEM, the 3D reconstruction of the microstructure by micro-tomography grants to:

• Quantify statistically the number, size, shape and orientation of objects; • Study the spatial distribution of objects;

• Avoid artefacts due to cutting and surface preparation for 2D observations.

However, the micro-tomography has some drawbacks:

• Resolution is about a few micrometers (much poorer than the resolution of SEM); • Acquisition can demand long durations;

• Result files can be of huge size;

• Lack of access to the chemical composition (unlike SEM with EDS).

Furthermore, the X-ray micro-tomography is an excellent tool to follow in a 3D way the damage evolution (Le Gorgu Jago 2012, Le Saux et al. 2011). The sample of the study was analyzed with an X-Radia MicroXCT-400 micro-tomograph, located at Ecole Centrale de Nantes (GeM). In order to have a high enough resolution, the volume of the analyzed hourglass sample was reduced.

Samples

The sample observed by micro-tomography is a small cylinder (diameter≈3mm) extracted at the middle height of the interrupted fatigue sample. A resolution of 1.7µm is reached with this small sample. In order to open the cracks, the sample's faces were glued to plexiglas® plates and the sample was stretched thanks to small plexiglas® pins (Fig. 2).

ANALYSIS PROTOCOL

Images processing

Many softwares are available to process and visualize 3D micro-tomography images, such as Avizo3D, myVGL, Paraview and ImageJ. However, our choice was to select the Python programming language which is widely used in the scientific world and can provide access to more specific developments. Indeed, the use of a programming language for tomography processing allows finer control and more complex analysis possibilities. Gouillart et al. (2016) show the ability of Python and the scikit-image library to analyse micro-tomography data.

The goal of the images processing is the segmentation of the different types of objects (inclusions and voids) in the material. The segmentation consists in partitioning the tomography into several regions, in which the voxels satisfy a given homogeneity criterion, based for example on the gray level. The segmentation algorithm must minimize the loss of information on the microstructure caused by the simplification of the images, due to the different applied transformations. Thus, segmentation remains a difficult step since the choice of the segmentation algorithm can lead to significant differences in the morphological characterization of the microstructure. The used algorithms to segment regions of interest depend on the properties of the images. They can be classified in different families such as the thresholding algorithms (Otsu 1979), the region growing algorithms (Grady 2016) and the active contour algorithms (Kass 1988). Thresholding methods are the most common. They use the histogram data of the images. The threshold gray level is chosen manually or automatically to select the objects of interest. These techniques consider voxels independently and do not use their spatial information. These techniques are effective when the objects and the background have two distinct peaks on the grayscale histogram. This segmentation approach was used by Le Gorgu Jago (2012) and Le Saux et al. (2011) to detect inclusions denser than the matrix and cavities inside the specimens, in order to assess the damage evolution. In this paper another segmentation method is used. First of all, a pre-treatment is applied to the reconstructed data, then, the inclusions and cracks are detected thanks to a region growing algorithm.

Pre-treatment

An exposure adjustment is performed in order to increase the contrast and delete extreme values due to the experimental noise. For practical reasons, the gray levels are set between 0 and 1 (0: white voxels and 1: black voxels). Then, a 3D median filter is applied to make the segmentation easier afterwards. It reduces noise while preserving edges. The mask of the filter is chosen small (3x3x3 voxels) in order to avoid deleting small inclusions.

Inclusions segmentation

The classical thresholding method is not used here for the inclusions segmentation because the choice of the threshold value (i.e. the gray value) is sensitive. Indeed, the chosen threshold has a strong influence on the shape and size of the biggest detected inclusions (Fig. 3).

Moreover, the bright inclusions do not create a specific peak on the grayscale histogram (Fig. 4). Thus, in order to have an accurate inclusions segmentation, a 3D region growth algorithm ("random walk") that combines information on the value of the gray level and the position of the voxels is used (Grady 2016). First of all, the user defines markers labeling regions of the image belonging clearly either to the inclusion or to the matrix. Some regions remain indeterminate like highlighted in the Figure 4. Then, an anisotropic diffusion equation is solved with tracers initiated at the marker's positions. The local diffusivity coefficient is defined as higher if neighboring voxels have similar values, so that diffusion is difficult across high gradients. The label of each unknown voxel is set to the label of the known marker that has the highest probability to be reached first during the diffusion process.

The matrix value is set as the one for which the curve of the grayscale histogram of the whole tomography deviates from the line drawn (i.e. 0.77) (see the top right scheme in Fig. 4). It corresponds to the end of the matrix peak. The value of inclusions is chosen arbitrary as equal to 0.9.

Thanks to this segmentation method, the size of the biggest inclusions is almost insensitive to the markers defined by the user. Indeed, the Figure 5 shows that the threshold value of inclusions has little influence on the shape and size of the biggest inclusions, unlike conventional thresholding algorithms. Moreover, the choice of the matrix markers has almost no effects on the results (Fig. 5).

Finally, only inclusions with more than 27 voxels (i.e. size of the filter 3x3x3 voxels) are kept. Consequently, the smallest inclusions have an equivalent diameter of 6.3µm.

It should also be underlined that the contrast observed thanks to micro-tomography is highly dependent on the chemical nature of the inclusions. In this study, the metallic oxide inclusions are identified clearly but it was not possible to do so with the carbon black inclusions (except for the biggest ones).

Sample and cracks segmentation

In that particular case, a conventional thresholding operation is applied in order to separate it from the background because the voids and the matrix have two distinct peaks on the grayscale histogram (see top right figure in Fig. 4). The threshold value is set at middle distance between those two peaks (i.e. 0.36). The cracks are detected with the same regions growth algorithm than inclusions. The voids markers are set to the middle distance between the matrix and voids peaks (i.e. 0.36). The matrix markers for the crack detection are set like for inclusions but this time at the beginning of the matrix peak (i.e. 0.64) (Fig. 4). The outer cracks are not considered in this study because the micro-tomography images have a thin bright line around the border of the specimen. Thus, in order to delete this contour, the specimen is eroded of a few voxels. Only inclusions and cracks inside this eroded volume are kept.

Combination of inclusions and cracks

Once the inclusions and cracks are detected, the next step is to associate them. A specific algorithm has also been developed (Fig. 6) to detect the cracks in the vicinity of one inclusion's pole. Special attention to artifacts induced by metallic oxides, such as ZnO (Le Gorgu Jago 2012) has to be paid, in order to not identify them as voids. This "metal artifact" appears only in (x, y) plane of the tomography and close to metallic oxides. Thus, the identified voxels as voids but located in the immediate vicinity of the inclusions are not considered (Fig. 6).

At the end of this process, it is possible to identify if a crack is located at one of an inclusion's poles or if the cracks are detected without inclusions nearby, and, reversely, if some inclusions present no cracks.

Combination with the mechanical states in the sample

The complex geometry of the AE2 sample leads to different local strains and stresses. Relating the damage description to the mechanical state therefore requires a specific analysis. Figure 7 shows the identified strain field in the sample thanks to a FE numerical simulation. It can be observed that, in the volume of the cylinder cut for the micro-tomography observations, the strain is almost constant along the sample axis (Z axis on Figure 7). It was therefore decided to analyze the sample according to radial slices (see Figure 7). To do so, the outline of the specimen is detected for each slice of the tomography (in the planes XY), and then polygonised. Once the exterior edge of the sample detected, 6 volumes are defined and the corresponding strains states coming from the FE simulations associated.

Computation

As evoked in the introduction, the manipulation and the analysis of tomographic data raise several challenges related to the calculation time and the management of the memory for the images processing. In our case, the python script is run on a powerful cluster and the growing regions algorithm is computed using multiprocessing. To do so, the volume is split into 54 subvolumes with a covering rate of 50%.

The volume of investigated material is around 9.7mm 3 . Then, each detected inclusion can be morphologically (size, shape, spatial distribution and orientation) analyzed (Glanowski et al. 2018). To give an idea of the statistical relevancy of the analysis, the images processing gave access to the features of 118 640 metallic oxides.

RESULTS

Nature of inclusions leading to cracks

The first question arising concerns the chemical natures of the inclusions leading to cracks. As explained previously, only metallic inclusions were detected directly here. As cracks are initiated on inclusions, the assumption is made here that cracks detected without any associated inclusions are due to carbon black agglomerates. The associated cracks without inclusions or with a metallic oxide are counted for each defined strain zone. As regions have not the same volume, the volume density of cracks, defined as the number of cracks divided by the analyzed volume, is followed rather than the number of cracks. Figure 8 highlights that both the cracks volume densities without inclusions (possibly due to carbon black agglomerates) and associated to metallic oxides, increase with strain level. A sudden increase is visible for a nominal principal strain of 200%.

Mechanisms

The understanding of the initiation mechanisms is important for the industrial development of the materials, in order to find a way to delay them. The analysis tool developed here gives access to polar cracks (that could be induced by interface debonding or cavitation near the poles) and cracks due to several inclusions (induced either by the cavitation between close inclusions or by the failure of inclusions (Le Saux et al. 2011)). Figure 9 presents the evolutions of these two populations of inclusions. First, it can be concluded that more than 75% of the cracks are polar ones. Another interesting observation is that the cracks involving two inclusions are detected only for the highest nominal strains.

Volume density of activated metallic oxides

The analysis over a large number of inclusions also offers access to the percentage of metallic oxides that are activated (i.e. inducing one or two cracks). Figure 10 shows that the percentage of metallic oxides activated increases with strain.

Average size of metallic oxides with and without cracks

Finally, one of the most import information for the industrial development of these materials is the size of metallic oxides that would not induce any cracks during considered fatigue loads. Figure 11 shows the equivalent diameter of metallic oxides for 3 cases: presenting no cracks, with polar cracks and with cracks related to two inclusions. For each case, the median value is given and the interval is set between the 5 th and the 95 th percentiles. The metallic oxides presenting no cracks have a median value lower than the ones with cracks in any configuration. Moreover, these metallic oxides exhibit a median value independent on the strain level. It means that metallic oxides with an equivalent diameter below 9µm do not create micro-cracks in the present case. Another observation is that the inclusions related to a same crack exhibit a higher median value than those with polar cracks, except for the highest strain levels.

CONCLUSIONS

This paper aimed at providing quantitative data on the relation between inclusions and the early stages of micro-cracks initiation. X-ray micro-tomography data have been used and specific images processing tools have been developed. The region growth algorithm of Grady (2016) is used in this study in order to detect accurately inclusions and voids. This kind of algorithm has the main advantage to be less dependent on parameters value, compared to thresholding approach. The analysis provided statistical 3D data at a scale that seems relevant (below 10 µm for cracks and inclusions). The geometric features (size, orientation and shape) of the inclusions in the material leading or not to one or several cracks are indeed described. It was found that metallic oxides with an equivalent diameter below 9µm do not create micro-cracks. Thus, this size could be set as an objective for the mixing stage in order to improve the compounds duration life. Another observation is that more than 75% of the cracks initiated on metallic oxides are polar cracks associated with only one inclusion. It was also observed that the cracks generated by metallic oxides (over the minimum detected size) represent around 25% of the total number of detected cracks, except for the highest strains, for which is a 50-50% share. The generated data are clearly appealing and calls for further analysis.

Figure 1 .

 1 Figure 1. Evolution of the stiffness versus the number of cycles (X-log scale).

Figure 2 .

 2 Figure 2. Specimen extracted from the hourglass sample and stretched.

Figure 3 .

 3 Figure 3. Effect of the threshold value for thresholding algorithm on the inclusion shape and size (d eq : equivalent diameter of the sphere corresponding to the same volume).

Figure 4 .

 4 Figure 4. Inclusions segmentation steps and result of the algorithm superposed to the denoised data.

Figure 5 .

 5 Figure 5. Effect of the inclusions and matrix threshold values for regions growth algorithm on the inclusions shape and size.

Figure 6 .

 6 Figure 6. Strategy of association of cracks with inclusions and removal of "metal artifact".

Figure 7 .

 7 Figure 7. Mechanical fields in the sample analyzed.

Figure 8 .

 8 Figure 8. Volume density of cracks for the different zones.

Figure 9 .

 9 Figure 9. Volume density of metallic oxides with cracks with respect to the maximal principal strain for the various fatigue crack initiation mechanisms.

Figure 10 .

 10 Figure10. Mechanical fields in the specimen.

ACKNOWLEDGEMENTS

The authors would like to thank the ANRT for its financial support and François Bertrand (GeM) for performing the micro-tomography measurements.