Mathieu Giraud
email: mathieu@algomus.fr

Florent Jacquemard
email: florent.jacquemard@inria.fr

Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations

Keywords: Edit Distance, Edit Operation, Weighted Automata, Consolidation, Fragmentation, Bounded Semiring

We study edit distances between strings, based on operations such as character substitutions, insertions, deletions and additionally consolidations and fragmentations. The two latter operations transform a sequence of characters into one character and viceversa. They correspond to the compression and expansion in Dynamic Time-Warping algorithms for speech recognition and are also used for the formal analysis of written music.

We show that such edit distances are not computable in general, and propose weighted automata constructions to compute an edit distance taking into account both consolidations and deletions, or both fragmentations and insertions. Assuming that the operation ruleset has a constant size, these constructions are polynomial into the lengths of the involved strings. We finally show that the optimal weight of sequences made of consolidations chained with fragmentations, in that order, is computable for arbitrary rulesets, and not computable for some rulesets when we reverse the order of fragmentations and consolidations.

Introduction

In general, edit distances measure similarity between two sequences of symbols, usually with substitution, insertion and deletion operations: Each of these operations is given a weight (or cost), and the edit distance is defined as the minimal weight of a transformation of one sequence into the other using the operations. For the Levenshtein distance [START_REF] Wagner | The string-to-string correction problem[END_REF], all operations have a weight of 1, but more elaborated weights schemes are also used: In bioinformatics, to compare proteins seen as sequences over the 20-letter alphabet of amino acids, the BLOSUM62 substitution matrix [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF] reflects the probability of substitution of any two amino acids.

In a digital humanities context, edit distances are fundamental in Music Information Retrieval (MIR) studies, for measuring melodic similarity in written music. In 1990, Mongeau and Sankoff [START_REF] Mongeau | Comparison of musical sequences[END_REF] proposed to extend edit distance with consolidation and fragmentation operations to account for common transformations between melodic patterns Figure 1: Theme, Variations 1 and 7 from Mozart's "Ah vous dirai-je maman" Variations K265. Transformations between the theme and the variations can be seen as a sequence of fragmentation operations, breaking a note into several ones and possibly substituting resulting notes, with also a deletion for the Variation 7.

var. 7 theme var. 1 d -see Figure 1. These two operations consist basically in compressing a substring down to a single letter and expanding a single letter into multiple letters, respectively. They correspond namely to the compression and expansion operations defined in the context of dynamic time-warping algorithms for speech recognition, where they allow to compare two speech recordings with different variations in speed [START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF]. The Mongeau-Sankoff distance and algorithm have been very influential in the MIR community: The article [START_REF] Mongeau | Comparison of musical sequences[END_REF] is one of the most cited papers in this field.

Edit distances between strings are usually computed with dynamic programming [START_REF] Wagner | The string-to-string correction problem[END_REF]. More generic algorithms have been proposed to compute the edit distance between two regular languages [START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF] with construction and composition of weighted transducers. These approaches are applied to standard Levenshtein edit-distance and are applicable to more general edit-distances defined by arbitrary sets of edit operations, provided that these operations are expressed as weighted string transducers [START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF]. In an unweighted context, it has been shown that some classes of string rewriting rules including consolidations (as well as other kind of rules) effectively preserves regular languages [START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF].

In this paper, after defining edit distances with consolidation and fragmentation operations (Section 2), we show that they are not computable in general. We then propose a construction of weighted automata to compute the optimal weight of edit operations sequences including either consolidations together with deletions, or either with fragmentations together with insertions, but not both in the same time (Section 3, and in particular Theorem 13). We finally show how to account for edit operations sequences that include consolidations chained with fragmentations (Section 4).

Definitions

In this section, we define extended edit distances between finite sequences of symbols, that can involve generic consolidation or fragmentation operations (Sections 2.1 and 2.4) and where the weights are values in a semiring with some properties (Section 2.2). We also introduce the notions that we shall use to compute such distances in Section 3: the resolution of polynomial systems over a bounded semirings (Section 2.3), and the weighted automata (Section 2.5). Let us consider a fixed finite alphabet Σ. We use letters a, b... to denote symbols of Σ. The monoid of words (strings) over Σ is denoted Σ * , ε is the empty sequence, uv denotes the concatenation of u ∈ Σ * and v ∈ Σ * , and |u| the length of u. For a string s = a 1 . . . a n ∈ Σ * with a j ∈ Σ for each i ≤ j ≤ n, and 0 ≤ i ≤ n, s i..n denotes the suffix of s of length n -i + 1: s i..n = a i . . . a n when 0 < i ≤ n, and s n+1..n = ε.

Edit Operations and Rulesets

The Levenshtein edit distance [START_REF] Wagner | The string-to-string correction problem[END_REF] between two strings s and t is defined as the minimum number of elementary editions transforming s into t, using operations of substitution (replacement of one character by another), single-character insertion and deletion. Here, we consider more general edition operations ranged in two families, which possibly include substitution, insertion and deletion.

An edit operation is a pair u → v with u, v ∈ Σ * . Note that both u and v can be ε, whereas this is generally not the case for u in classical string rewriting theory [START_REF] Book | String-rewriting systems[END_REF]. The operations of the first family, called fragmentations, have the form

a → b 1 . . . b n (fragmentation)
where a, b 1 , ..., b n ∈ Σ, and n ≥ 0. When n = 0, the fragmentation operation is called (deletion), and when n = 1, it is a (substitution). The operations of the second family, called consolidations, have the form

a 1 . . . a n → b (consolidation)
where a 1 , ..., a n , b ∈ Σ, and n ≥ 0. When n = 0, the consolidation operation is called (insertion). The case n = 1 still corresponds to (substitution) -the latter is hence both a special case of (fragmentation) and (consolidation).

A ruleset E is a finite set of edit operations. Its size ∥E∥ is the sum of the length of the strings in its rules. Its inverse is E -1 = {v → u u → v ∈ E}. We denote by C(E) the set of all suffixes of left-hand-side (lhs) of a consolidation rule.

Example 1. The ruleset

E 0 = { a → b, ε → b, a → ε a, b ∈ Σ, a ̸ = b
} contains all the substitution, insertion, and deletion operations over Σ. We have ∥E∥ = O(|Σ| 2 ) and

E -1 = E.

Example 2. Figure 2 describes, on a 3-letter alphabet, the rulesets

E 0 = E 3,s ∪ E 3,i ∪ E 3,d (
substitutions, insertions, deletions), E 3,c (same-letter consolidations up to 3 letters) and E 3,f (same-letter fragmentations up to 3 letters). We have

C(E 3,c ) = {ϵ, i, ii, iii, t, tt, ttt, u, uu, uuu}
In music analysis, consolidation/fragmentation rules are used to transform a note into several ones, most of the time preserving the total duration (see Figure 1). In speech processing, compression and expansion are used in time-wrapping techniques for comparing time series subject to variations in speed [START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF]. In both of these cases, it is more accurate to define these operations rather than using several insertions/deletions.

E 3,s i --→ αs t i --→ αs u t --→ αs i t --→ αs u u --→ αs i u --→ αs t E 3,i ε --→ α i i ε --→ α i t ε --→ α i u E 3,d i --→ α d ε t --→ α d ε u --→ α d ε E 3,c ii --→ αc i iii --→ αc i tt --→ αc t ttt --→ αc t uu --→ αc u uuu --→ αc u E 3,f i --→ α f ii i --→ α f iii t --→ α f tt t --→ α f ttt u --→ α f uu u --→ α f uuu Figure 2:
Rulesets over the alphabet Σ3 = {i, t, u} for substitutions (E3,s, weight αs), insertions (E3, i , α i ), deletions (E3, d , α d ), same-letter consolidations and fragmentations up to 3 letters (E3,c and E3, f , of respective weights αc and α f ).

Weight Domains

An edit distance is defined by assigning every edit operation in a ruleset E with a weight value. In the case of usual edit distances based on E 0 (Example 1), these weight values are strictly positive real numbers (1 for the Levenshtein distance) and the weight of a sequence of edit operations is the sum of the individual weights of the rules involved. The edit distance between two strings s and t is then the minimal weight of a sequence transforming s into t, and there is always at least one such sequence, deleting all characters of s then inserting all characters of t.

In the case of an arbitrary E, there does not always exists a sequence transforming s into t. To capture this general situation, we consider abstract domains for weights, with two distinguished values: 1 which is a minimal distance, and 0 which corresponds to the impossibility of transforming s into t (e.g. infinite distance in the case of positive weight values).

More precisely, weight values are in a semiring with an operator ⊗, for the composition of weights in a sequence of edit operations (with neutral element 1), and an operator ⊕ for the selection of the optimal sequence in the definition of the edit distance (with neutral element 0). This generalisation enables the identification of the algebraic properties of the weight domain which are necessary for ensuring the correctness of our construction for the computation of edit distances.

Definition 3.

A semiring S = ⟨S, ⊕, ⊗, 0, 1⟩ is a structure with a domain S = dom(S) equipped with two binary operators ⊕ and ⊗ such that: ⟨S, ⊕, 0⟩ is a commutative monoid: ⊕ is associative and commutative and 0 ∈ S is a neutral element for ⊕; ⟨S, ⊗, 1⟩ is a monoid: ⊗ is associative and

1 ∈ S is a neutral element for ⊗; ⊗ distributes over ⊕: ∀x, y, z ∈ S, x ⊗ (y ⊕ z) = (x ⊗ y) ⊕ (x ⊗ z) and (x ⊕ y) ⊗ z = (x ⊗ z) ⊕ (y ⊗ z); and 0 is absorbing wrt ⊗: ∀x ∈ S, 0 ⊗ x = x ⊗ 0 = 0.
We may simply write x ∈ S to mean x ∈ S. A semiring S is commutative if ⊗ is commutative. It is idempotent if for each x ∈ dom(S), x ⊕ x = x. Following the terminology of [START_REF] Mohri | Semiring frameworks and algorithms for shortest-distance problems[END_REF], when ∀x ∈ dom(S), 1 ⊕ x = 1, the semiring S is is called bounded. Note that every bounded semiring is idempotent: by boundedness, 1 ⊕ 1 = 1, and idempotency follows by multiplying both sides by x and distributing. semiring In the following applications, we need to consider infinite sums with ⊕. A semiring S is complete if for every family {x i | i ∈ I} of elements of dom(S) over an index set I ⊂ N, an infinite sum ⊕ i∈I x i is well-defined and in dom(S), and the following properties hold:

domain ⊕ ⊗ 0 1 ordering (1 ≤ S 0) Boolean {⊥, ⊤} ∨ ∧ ⊥ ⊤ ⊤ ≤ S ⊥ Viterbi [0, 1] ⊂ R + max . 0 1 x ≤ S y ⇐⇒ x ≥ y Tropical R + ∪ {+∞} min + +∞ 0 x ≤ S y ⇐⇒ x ≤ y
i. infinite sums extend finite sums:

⊕ i∈∅ x i = 0, ∀j ∈ N, ⊕ i∈{j} x i = x j , ∀j, k ∈ N, j ̸ = k, ⊕ i∈{j,k} x i = x j ⊕ x k ,
ii. associativity and commutativity: for all I ⊆ N and all partition (I j ) j∈J of I,

⊕ j∈J ⊕ i∈I j x i = ⊕ i∈I x i ,
iii. distributivity of product over infinite sum:

for all I ⊆ N, ⊕ i∈I (x ⊗ y i ) = x ⊗ ⊕ i∈I y i , and
⊕ i∈I (x i ⊗ y) = ( ⊕ i∈I x i ) ⊗ y.
Every idempotent semiring S induces an ordering relation ≤ S defined, for each x and y, as x ≤ S y iff x ⊕ y = x. Note that this ordering is sometimes defined in the opposite direction [START_REF] Droste | Semirings and formal power series[END_REF]. The ordering used here follows [START_REF] Mohri | Semiring frameworks and algorithms for shortest-distance problems[END_REF], and allows to be the same than the usual ordering on the Tropical semiring (min-plus) in Figure 3. The semiring S is monotonic wrt ≤ S iff: for all x, y, z, x ≤ S y implies x ⊕ z ≤ S y ⊕ z, x ⊗ z ≤ S y ⊗ z, and z ⊗ x ≤ S z ⊗ y.

From now on, we assume that S is a commutative, complete, and bounded semiring (which is, hence, idempotent). This is the case for the three common semirings shown on Figure 3.

Resolution of Polynomial Systems

We will use in our proofs the notion of polynomial over a variable set X, with coefficients in S, which is a sum of the form:

P = a ⊕ ⊕ n i=1 b i ⊗ M i
where a ∈ S and for every i such that 1 ≤ i ≤ n, b i ∈ S and M i is a product, with ⊗, of variables of X (possibly with repetitions). Every element of the above sum (either a or b i ⊗ M i ) is called a monomial. The size of P is the number of monomials, and the degree of P , deg(P ), is the maximal number of variables inside a monomial. The set of polynomials over S and a set of variables X is denoted S[X]. When X is a singleton X = {x}, we may write P (x) for P ∈ S[X], and P (a) for the replacement of x by a ∈ S in P . Definition 4. For an integer n ≥ 1, we call n-system over a semiring S and variables {x 1 , . . . , x n } a set of n equations of the form

{ x i = P i 1 ≤ i ≤ n, P i ∈ S[x 1 , . . . , x n ] } .
The goal of this section is to prove that when S is commutative and bounded, one can build a solution for every n-system over S (Lemma 7). Solving n-systems works by elimination of the variables x 1 , . . . , x n , one by one and in that order. Variable elimination uses Lemma 5, which is based on the following notion: For x ∈ X and P ∈ S[X], the x-loop-free form of P is the polynomial P \x is obtained from P by deleting every monomial that contains x.

Lemma 5. if S is a commutative and bounded semiring and P (x) ∈ S[x], P \x = P (P \x).

In other terms, P \x ∈ S is a solution of the equation x = P (x).

Proof. P (x) has the following form, for some d ≥ 0:

P (x) = a 0 ⊕ ⊕ d i=1 a i ⊗ x i
, where a 0 , a 1 , . . . , a d ∈ S and the exponentiations x i are built with ⊗. Then P \x = a 0 and Now we prove the main Lemma of this subsection.

P (a 0 ) = a 0 ⊗ ( 1 ⊕ ⊕ d i=1 a i ⊗ a i-1 0 ) = a 0 ,

Lemma 7.

Let S be a commutative and bounded semiring. Every n-system has a solution effectively constructible.

Proof. Let X = {x 1 , . . . , x n } and let U be an n-system over S and X. Let U 0 = U , and let us write U 0 = {x i = P 0,i | 1 ≤ i ≤ n}. For 0 < j ≤ n, assume that we have constructed a n-system U j-1 = {x i = P j-1,i | 1 ≤ i ≤ n} over S and X, and let us define the transformation of U j-1 into another n-system U j = {x i = P j,i | 1 ≤ i ≤ n} over S and X, as follows (elimination of x j ):

1. P j,j = P j-1,j \x j , 2. for all i ̸ = j with 1 ≤ i ≤ n, P j,i is obtained from P j-1,i by replacing every occurrence of x j by P j,j and normalizing the expression obtained into a polynomial form.

This definition implies, by a straightforward induction on j, that:

For all 0 ≤ j ≤ n and 1 ≤ i ≤ n, P j,i ∈ S[x j+1 , . . . , x n ]. ( †)
Let us now show the following claim:

For all j such that 1 ≤ j ≤ n, every solution of U j is a solution of U j-1 . ( ‡)

Let σ : {x 1 , . . . , x n } → S be a solution of U j . Following ( †), by replacing in P j-1,j , respectively P j,j , every variable in {x j+1 , . . . , x n } by its image under σ, we obtain a polynomial R j (x j ) ∈ S[x j ], respectively R ′ j ∈ S. By construction of P j,j , R ′ j = R j \x j , hence by Lemma 5, applied to R j (x j ), we have

R ′ j = R j (R ′ j ). Moreover, since σ is a solution of U j , it holds that σ(x j ) = R ′ j .
Therefore, σ is a solution of x j = P j-1,j . Every P j,i for i ̸ = j is obtained from P j-1,i by replacements of x j by P j,j . It follows that σ is a solution of the remaining equations of U j-1 , and thus ( ‡) is proved.

Note that U n is solved, because, by ( †), P n,i ∈ S for all 1 ≤ i ≤ n. By applying ( ‡) inductively, the solution of U n is also a solution of U 0 = U and Lemma 7 follows.

□ Each of the above n steps transform n equations. The maximum size of the polynomial is in O(n d ), where d is the maximum degree of this polynomial. Note that in the worst case, d = n max(deg(P i )), where the P i are the polynomials of the n-system to be solved. Altogether, a n-system can be solved in time O(n d+2 ).

Weighted Edit Operations and Optimal Weight

A weighted ruleset E is a ruleset equipped with a weight function, which is a mapping weight : E → S \ {0, 1}. By abuse of notation, we write u -→

x v ∈ E when x = weight(u → v). A weighted ruleset E is symmetric when E = E -1 and for every operation u → v ∈ E, weight(v → u) = weight(u → v).
From now on, we assume that all rulesets are weighted.

A positioned operation π of E is a pair ⟨u → v, i⟩ made of an edit operation of E and a number i ∈ N, meaning that u → v is applied at position i in a string. We write s -→ π t when for some w, w ′ ∈ Σ * , s = wuw ′ , t = wvw ′ , and i = |w|. For each s, t ∈ Σ * , we write s --→ E t when s ------→ ⟨u→v, i⟩ t for some u → v ∈ E, and s --→ * E t for the transitive closure of this relation, called edition.

Let σ = π 1 π 2 . . . π n be a finite sequence of positioned operations of E (called edition sequence), with π j = ⟨u j → v j , i j ⟩ for each j = 1..n. We write s -→

σ t if s = s 0 --→ π 1 s 1 . . . --→
πn s n = t for some strings s 0 , . . . , s n ∈ Σ * . The weight of the sequence σ is defined by

weight(σ) =      1 if σ is empty (n = 0), n ⊗ i=1 weight(u i → v i ) otherwise.
Then we define the optimal weight between s and t wrt E by

D E (s, t) =    1 if s = t, ⊕ s-→ σ t weight(σ) otherwise.
Note that the hypothesis that S is complete is important in our context, for D E being well-defined, since the above sum may be infinite. Moreover, following this hypothesis, when s ̸ = t and the above sum is empty

(i.e. s ̸ --→ * E t ), then D E (s, t) = 0. tutti tuti ttti utti uti tti tui ti α d α d α c ⊕ α d α c α c ⊕ α d α c ⊕ α d α d α d α d α d α d α c ⊕ α d α d Figure 4: Subgraph of GE 0 ∪E 3,c (tutti)
showing some rewriting operations from tutti using deletion and consolidation rules from E0 ∪ E3,c.

In general, we use the term optimal weight for D E as this measure may not be a distance -that is a symmetric relation satisfying separation (∀s,

t D E (s, t) = 1 iff s = t) and triangle inequality (∀s, t, u D E (s, u) ≤ S D E (s, t) ⊗ D E (t, u)).
When E is symmetric and when the ordering ≤ S is total (i.e. for all x, y, x

⊕ y = x or x ⊕ y = y), D E is a distance called edit distance.
Example 8. On the tropical semiring (0 = +∞ and 1 = 0) and assuming that all edit operations have a weight of

α s = α i = α d = α c = α f = 1, E 0 is symmetric, D E 0 is the Levenshtein distance,
and D E 0 (tutti, ti) = 3 (three deletions), whereas D E 0 ∪E 3,c (tutti, ti) = 2 (one deletion of u followed by one consolidation ttt -→ t). See Figure 4.

Weighted Automata

In Section 3, we will present algorithms to compute D E in some cases, using Weighted Automata [START_REF]Handbook of Weighted Automata[END_REF]. Definition 9. A weighted automaton A over the alphabet Σ and the semiring S is a tuple (Q, in, weight, out) where Q is a finite set of states, in : Q → S, respectively out : Q → S, is a function defining the weight for entering, respectively leaving, a state, and weight :

Q × Σ × Q → S is a transition weight function.
The functions defining A might be subscripted by A when needed. The set of transitions of A is {⟨q, a, q ′ ⟩ q, q ′ ∈ Q, a ∈ Σ}. The size of A is ∥A∥ = |Q| + |{⟨q, a, q ′ ⟩ weight(q, a, q ′ ) ̸ = 0}|. We might write below q ---→ A a,w q ′ to express that w = weight(q, a, q ′ ). Every weighted automaton A defines a mapping from the strings of Σ * into weights of S, based on the following intermediate function weight A defined recursively for every q, q ′ ∈ Q and for every string of Σ * :

weight A (q, ε, q) = 1 weight A (q, ε, q ′ ) = 0 if q ̸ = q ′ weight A (q, au, q ′ ) = ⊕ q 1 ∈Q weight(q, a, q 1 ) ⊗ weight A (q 1 , u, q ′ ) for a ∈ Σ, u ∈ Σ * .
The weight associated by A to a string u ∈ Σ * is then defined as follows:

A(u) = ⊕ q,q ′ ∈Q in(q) ⊗ weight A (q, u, q ′ ) ⊗ out(q ′ ).
The standard Finite State Automata are a particular case of Weighted Automata over the Boolean Semiring of Figure 3, where A(u) = ⊤ (resp. A(u) = ⊥) means acceptation (resp. non-acceptation) of u by A.

Lemma 10. For each u, v ∈ Σ * , and q, q ′ ∈ Q, it holds that

weight A (q, uv, q ′ ) = ⊕ q 1 ∈Q weight A (q, u, q 1 ) ⊗ weight A (q 1 , v, q ′ ) .
Proof. We prove by induction on |u|. The case u = ε is immediate by definition of weight A (q, ε, q ′ ), using the facts that 0 is neutral for ⊕ and that 0 is absorbing and 1 is neutral for ⊗. If u = au ′ , then

weight A (q, uv, q ′ ) = ⊕ q 1 ∈Q weight(q, a, q 1 ) ⊗ weight A (q 1 , u ′ v, q ′ ) = ⊕ q 1 ∈Q
weight(q, a, q 1 ) ⊗ ( ⊕

q 2 ∈Q weight A (q 1 , u ′ , q 2 ) ⊗ weight A (q 2 , v, q ′ ) ) = ⊕ q 1 ,q 2 ∈Q weight(q, a, q 1 ) ⊗ weight A (q 1 , u ′ , q 2 ) ⊗ weight A (q 2 , v, q ′ ) = ⊕ q 2 ∈Q ( ⊕ q 1 ∈Q weight(q, a, q 1 ) ⊗ weight A (q 1 , u ′ , q 2 ) ) ⊗ weight A (q 2 , v, q ′ ) ) = ⊕ q 2 ∈Q weight A (q, u, q 2 ) ⊗ weight A (q 2 , v, q ′ ).
The first and last equalities hold by definition of weight A , the second by induction hypothesis, the two next by distributivity. □

Computation of D E

Intuitively, D E (s, t) is the smallest weight (wrt ≤ S ) of a path in the edit graph associated to E. More precisely, we can associate to E and s ∈ Σ * a graph G E,s whose vertices are {w s --→ * E w}, the descendants of s wrt E, and where each edge corresponds to one positioned operation of E and labeled by its associated weight (Figure 4). D E (s, t) is then the smallest weight of a path between s and t in G E,s (the weight of a path π is the product with ⊗ of the edges forming π). However, in order to compute this optimal weight, we cannot construct G E and apply a shortest-path algorithm, like the ones in [START_REF] Backhouse | Regular algebra applied to path-finding problems[END_REF] (computation of the closure of the matric of the graph) or in [START_REF] Mohri | Semiring frameworks and algorithms for shortest-distance problems[END_REF], because G E is not finite in general (consider e.g. the case where E contains insertions). Actually, D E (s, t) is even not computable for some E containing fragmentations and consolidations (Section 3.2). We show nevertheless that under some restrictions, we can build a weighted automaton A E s as a finite representation of G E in order to compute the optimal weight (Sections 3.3 and 3.4).

The case of E 0

We consider here E = E 0 of Example 1, and suppose that the triangle inequality holds for E 0 , that is, for every a, b, c

∈ Σ ∪ {ε}, weight(a → c) ≤ S weight(a → b) ⊗ weight(b → c).
Then D E 0 can be computed in polynomial time using dynamic programming equations [START_REF] Needleman | A general method applicable to the search for similarities in the amino acid sequence of two proteins[END_REF][START_REF] Wagner | The string-to-string correction problem[END_REF][START_REF] Ukkonen | Algorithms for approximate string matching[END_REF]. This works by tabulating ∆(i, j) = D E (s 1..i , t 1..j ), for 1 ≤ i ≤ |s| and 1 ≤ j ≤ |t|, with ∆(0, 0) = 1 and

∆(i, j) = ∆(i -1, j -1) if s i = t j (match) ⊕ ∆(i -1, j -1) ⊗ weight(s i → t j ) if s i ̸ = t j (substitution) ⊕ ∆(i -1, j) ⊗ weight(s i → ε) (deletion) ⊕ ∆(i, j -1) ⊗ weight(ε → t j ) (insertion)
It holds indeed that D E (s, t) = ∆(|s|, |t|).

Adding lines for fragmentations and consolidations to the above equation, as what was done by [START_REF] Mongeau | Comparison of musical sequences[END_REF], does not always compute the optimal weight of edit operations sequences.

Example 11. With the ruleset E 0 ∪ E 3c as in Example 8 and Figure 4, we have seen that D E 0 ∪E 3,c (tutti, ti) = 2. However, even after adding to the above equation a line with consolidations, we have ∆(5, 2) = 3. Indeed the best operation sequence includes a consolidation over a string that already underwent through a deletion, with

D E 0 ∪E 3,c (tutt, t) = D E 0 ∪E 3,c (ttt, t) + 1.
However ttt is not a factor of s and is not handled by ∆.

More generally, as soon as E contains insertion and deletion rules for every character, we have always D E (s, t) ̸ = 0, and D E (s, t) is computable. However, D E is not computable in general when E ̸ = E 0 and contains fragmentations and consolidations, as shown in the next section.

Uncomputability of D E

Proposition 12. There are a ruleset E containing fragmentation and consolidation rules and strings s and t such that D E (s, t) is not computable.

Proof. By definition, the problem whether D E (s, t) ̸ = 0 for two strings s and t is equivalent to the problem of reachability s --→ * E t, which is undecidable for some E containing fragmentation and consolidation rules. This can be shown by reduction of e.g. the Post Correspondence Problem (PCP).

Let us consider an instance of PCP

P = { ⟨u i , v i ⟩ 1 ≤ i ≤ n, u i , v i ∈ Σ * } . The problem is to find a sequence 1 ≤ i 1 , . . . , i k ≤ n (possibly with repetitions) such that u i 1 . . . u i k = v i 1 . . . v i k .
Let us add two marker symbols ♯ and ♮ to Σ. Intuitively in the reduction of PCP, the fragmentation operations are used for generating a candidate solution (to the problem) from a constant symbol ♯, and the consolidation operations are used for checking that a candidate is indeed a solution, by reduction to another constant symbol ♮. More precisely, let the ruleset E f contain one fragmentation ♯ → u i ♯ v i for each pair ⟨u i , v i ⟩ ∈ P ( v i is the mirror image of v i ). And let the ruleset E c contain two consolidations a ♯ a → ♮ and a ♮ a → ♮ for each a ∈ Σ. We assign to all these edit operations a non-null weight in S, say 1, and call

E = E f ∪ E c . Then it holds that ♯ --→ * E u i 1 . . . u i k ♯ v i k . . . v i 1 --→ * E ♮ iff P has a solution i 1 . . . i k . Thus D E (♯, ♮) ̸ = 0 iff ♯ --→ * E ♮ iff P has a solution.
□

The following sections propose weighted automata constructions to correctly compute the optimal weight D E (s, t) for some rulesets E different from E 0 , and including in particular fragmentations and consolidations.

The case of Consolidation and Deletion Rulesets

In this section we show that D E is computable when the ruleset E contains only consolidation and deletion edit operations, as a consequence of the following theorem.

Theorem 13. Assume that S is a commutative, complete, and bounded semiring. Let E be a ruleset over S containing only consolidation and deletion edit operations, and let s ∈ Σ * . One can build a weighted automaton A E s over Σ and S such that for each

t ∈ Σ * , A E s (t) = D E (s, t).
Assuming that E is of constant size, this construction is in polynomial time in |s|.

To prove this Theorem 13, we build in a weighted automaton A E s , that will be noted A to simplify notations, by a polynomial system of equations (Sections 3.3.1 and 3.3.2). We show in Section 3.3.3 that for every t he satisfies A(t) = D E (s, t). We then show how to effectively compute D E in Section 3.3.4.

Equations for Automata Construction

Let S, E, and s ∈ Σ * be like in Theorem 13.

The construction of A starts with an automaton A 0 s , such that A 0 (s) = 1 It will be noted A 0 in order to simplify notations. Then we update the transition weight function of A 0 in order to make it compute the optimal weight. q 0 q 1 q 2 q 3 q 4 q 5 0 0 t, 0 i, 0 t, 0 u, 0 t, 0

q i q i 1 q i n-1 q j a 1 , w 1 a n , w n b, ... ⊕ [w ⊗ w 1 ⊗ . . . ⊗ w n ] q i q ℓ q j y ℓ ... ⊕ [w ⊗ y ℓ ⊗ w a ] b, w b a, w a b, ... ⊕ [w ⊗ w b ⊗ w a ]
= ( Q = {q 0 , q 1 , . . . , q m }, in 0 , weight 0 , out 0 )
where:

in 0 (q 0 ) = 1 and in 0 (q i ) = 0 for each 0 < i ≤ m, out 0 (q i ) = 0 for each 0 ≤ i < m and out 0 (q m ) = 1, weight 0 (q i , s i+1 , q i+1 ) = 1 for each 0 ≤ i < m, and weight 0 (q i , s j , q k ) = 0 for all other transitions. Example 14. Figure 5 shows an example of A 0 for s = tutti in the tropical semiring (where 0 = +∞ and 1 = 0).

The following lemma is an immediate consequence of the definition of A 0 .

Lemma 15. It holds that A 0 (s) = 1 and A 0 (t) = 0 for each t ̸ = s.

Updated Automaton. The weighted automaton A of Theorem 13 will have the form (Q, in, weight, out 0 ). It is constructed from A 0 , leaving the state set Q as well as the outgoing weight functions unchanged, while updating the entering and transition weight functions. The updated weight functions in and weight are defined by fixpoint equations over S and its binary operators and over the following variables.

For every i and j such that 0 ≤ i ≤ j ≤ m (remember that m = |Q| -1 is the length of s) and for every a ∈ Σ, we consider a variable x i,a,j representing weight(q i , a, q j ), and a variable y i representing in(q i ). Moreover, we consider one variable x a for each a ∈ Σ, which will be used below to define the values of all looping transitions (from one state q i to itself) x i,a,i . We also consider one variable z i,u,j for every i and j with 0 ≤ i < j ≤ m and for every u ∈ C(E) (suffix of a left-hand-side of a consolidation rule in E).

Update of looping transitions. Initially, every looping transition of A 0 is such that weight 0 (q i , a, q i ) = 0. The following equations ( 1) and ( 2) define the updated weights of looping transitions, for each b ∈ Σ and all 0 ≤ i ≤ m.

x b =    ⊕ a 1 ...an-→ w E b,n≥0 w ⊗ n ⊗ k=1 x a k    ⊕   ⊕ a-→ w E ε w ⊗ x a   (1)
x i,b,i = x b (2)
Update of non-looping transitions. The weights of looping transitions are defined in the same way for all states, (2). The first sum in [START_REF] Wagner | The string-to-string correction problem[END_REF], with n = 0, treats the case ε --→ w E b of the insertion of a symbol b. In this case, while reading b, the automaton stays in state q i , and updates the weight with the weight w of the insertion rule. The first sum with n ≥ 1 and the second sum in (1) treat respectively the case of consolidation and deletion, following principles that will be described for the next equations (3). The updated weights of the other (non-looping) transitions are defined by the following equations (3) for every b ∈ Σ, and for every i and j such that

0 ≤ i < j ≤ m, x i,b,j = weight 0 (q i , b, q j ) ⊕ ⊕ a 1 ...an-→ w E b,n≥1 w ⊗ z i,a 1 ...an,j (3)
⊕ ⊕ a-→ w E ε ⊕ i≤ℓ≤j w ⊗ x i,b,ℓ ⊗ x ℓ,a,j
And for the variables z: for every i and j such that 0 ≤ i ≤ j ≤ m, and for every au ∈ C(E) with a ∈ Σ, u ∈ Σ * ,

z i,au,j = ⊕ i≤ℓ≤j x i,a,ℓ ⊗ z ℓ,u,j (4)
z i,ε,i = 1 (5) z i,ε,j = 0 if i ̸ = j (6)
Figure 6 illustrates the intuitions behind the weight updates defined by (3). The first sum in (3) corresponds to the case of a consolidation a 1 . . . a n --→ w E b. Intuitively, the variable z i,a 1 ...an,j is the weight for going from q i to q j while reading successively a 1 , . . . , a n , as defined in (4-6). To take into account the edition a 1 . . . a n --→ w E b, we add the product of this variable and the weight w of the consolidation (into b) as a possible weight for going from q i to q j while reading b. Note that, unlike (1), the equations (3) do not consider insertions (condition n ≥ 1). Indeed, since A 0 contains no ε-transitions, it is needed to consider updates by insertions only for looping transition.

q 0 q 1 q 2 q 3 q 4 q 5 0 0 t, 0 i, 0 i, 1 t, 0 u, 1 i, 1 t, 1 u, 0 i, 1 t, 0 u, 1 * , 1 * , 1 * , 1 * , 1 i, α d + α s = 2 t, α d = 1 u, α d = 1 i, α d + α s = 2 t, α d = 1 u, α d = 1 i, α s + α d + α d = 3 t, α d + α c = 2 u, α s + α d = 2
Figure 7: Automaton A E tutti on the tropical semiring after solving wi,a,j for every a ∈ Σ3 and every i and j with 0 ≤ i ≤ j ≤ 3, considering the ruleset E0 ∪ E3,c. All edition rules have here a weight of 1. Solving w0,t,3 is done through the x0,t,3 variable. By equation ( 3), we have: x0,t,3 = min(+∞, 1 + z0,tt,3, 1 + z0,t,3, mina∈Σ 3 min 0≤ℓ≤3 (1 + x 0,t,ℓ + x ℓ,a,3 )) By equations (4-6), z0,tt,3 = x0,t,2 + x2,t,3 = 1 once all x i,b,j variables with (i, j) ≺ (0, 3) have been solved. This finally gives x0,t,3 = 2.

Update of entering weights. Finally, the equations ( 7) define the updated entering weights, for every j with 0 ≤ j ≤ m.

y j = in 0 (q j ) ⊕ ⊕ a-→ w E ε ⊕ ℓ≤j w ⊗ y ℓ ⊗ x ℓ,a,j (7)
The second sum of (3) together with the equation ( 7) treat the case of a deletion. They are seen as the addition of an ε-transition q ℓ -→ ε q j in place of the transition labeled by a, followed by the on-the-fly suppression of this ε-transition, using a technique similar to e.g. [START_REF] Mohri | Generic ε-removal algorithm for weighted automata[END_REF][START_REF] Lombardy | The removal of weighted ε-transitions[END_REF].

Example 16. On the tropical semiring, the equation ( 3) on x 0,t,3 in the Figure 7 has the form x 0,t,3 = min(w, γ + x 0,t,3 ), where w = min(+∞, 1 + z 0,tt,3 + ...) contains the weight of the best sequence of edition operations and γ gathers all terms involving again x 0,t,3 . They correspond to cycles that will not improve the weight and are removed in the loop-free form of the equation.

Equations solving

The above equations (1-7) form a n-system over S. By Lemma 7, this system can be solved in exponential time in n. For a better efficiency, we rather decompose the resolution into several steps, following the dependencies between the variables.

Equations [START_REF] Wagner | The string-to-string correction problem[END_REF][START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF]. First, we solve the |Σ|-system of equations of the form (1), using Lemma 7. This defines a solution for the variables x i,b,i , with 1 ≤ i ≤ m and b ∈ Σ, according to [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF]. The maximum size of the polynomials in the rhs of these equations is in O(||E||). In the worst case, solving this system is done in exponential time in ||E||.

Equations [START_REF] Mongeau | Comparison of musical sequences[END_REF][START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF][START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF][START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF]. Next, we solve these equations in several steps, according to a partial ordering ≺ on {1, ..., m} × {1, ..., m} defined by: (i ′ , j ′ ) ≺ (i, j) for every i, i ′ , j ′ , and j such that 0 ≤ i ≤ i ′ ≤ j ′ ≤ j ≤ m and (i ′ , j ′ ) ̸ = (i, j).

For every i and j such that 0 ≤ i ≤ j ≤ m, let us denote by X i,j the set of variables of the form x i,b,j or z i,u,j , for some b ∈ Σ, and u ∈ C(E). For convenience, we denote by x i,b,j = P i,b,j and z i,u,j = Q i,u,j the equations in [START_REF] Mongeau | Comparison of musical sequences[END_REF][START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF][START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF][START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF] with a left-hand side in X i,j . Fact 17. For every i and j such that

0 ≤ i ≤ j ≤ m, b ∈ Σ, and u ∈ C(E), P i,b,j , Q i,u,j ∈ S [∪ (i ′ ,j ′ )⪯(i,j) X i ′ ,j ′ ] .
Using the previous observation, we can solve [START_REF] Mongeau | Comparison of musical sequences[END_REF][START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF][START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF][START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF] following the ordering ≺. The minimal variables wrt ≺ are in ∪ m i=0 X i,i , and they have already been above solved with (2). Then, let 0 ≤ i < j ≤ m be such that all the variables in ∪ (i ′ ,j ′ )≺(i,j) X i ′ ,j ′ have already been solved. Then, according to Fact 17, after replacement of the former variables by their solution in S in equations in [START_REF] Mongeau | Comparison of musical sequences[END_REF][START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF][START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF][START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF] with a left-hand-side in X i,j , we obtain a |X i,j |-system which can be solved using Lemma 7.

Example 18. Figure 7 shows an example of the construction of A E

tutti by updating the transition weights of A 0 tutti (in the tropical semiring).

The above approach solves the equations [START_REF] Mongeau | Comparison of musical sequences[END_REF][START_REF] Kruskal | The symmetric time-warping problem: from continuous to discrete[END_REF][START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF][START_REF] Hofbauer | Deleting string rewriting systems preserve regularity[END_REF] Equation [START_REF] Book | String-rewriting systems[END_REF]. Finally, after a replacement of all variables in X i,j by their solution in S, we can solve in O(m) applications of Lemma 5 the equations ( 7) on y j , starting from j = 0 until j = m. Assuming that ||E|| is constant, these applications take a time O(m 2 ).

Let σ be a solution of the equations (1-7), computed as above. We define the entering and transition weight functions of the automaton A by: for every i and j such that 1 ≤ i ≤ j ≤ m and for every a ∈ Σ, weight(q i , a, q j ) = σ(x i,a,j ),

for every i and j such that 1 ≤ j < i ≤ m and for every a ∈ Σ, weight(q i , a, q j ) = weight 0 (q i , a, q j ) = 0,

for every i such that 1 ≤ i ≤ m, in(q i ) = σ(y i ).
To summarize, the weighted automaton A has m + 1 states q 0 , . . . , q m where m is the length |s| of s. Assuming that Σ and E are constant, the size of A is in O(|s| 2 ) and its construction time is in O(|s| 3 ).

q 0 q 1 q 2 q 3 q 4 q 5 0 0 t, 0 i, 0 t, 0 u, 0 t, 0 * * * * * * * * * * * t, α d + α c = 2 1 2 3 3 4
Figure 8: Generalised Levenshtein automaton Atutti, considering ruleset E0 ∪ E3,c. Each state is initial. There are transitions labeled with every letter between each pair of states, with various weights. We detail the noteworthy transition q0 -→ t q4. It uses the consolidation ttt -→ t, giving

DE 0 ∪E 3,c (tutti, ti) = α d + αc = 2. and also in(q4) = 2 + α d = 3, giving DE 0 ∪E 3,c (tutti, i) = 3.

Completeness and Correctness of the Automaton Construction

We now conclude the proof of Theorem 13 by showing that the weighted automaton A over S and Σ constructed in the above Section 3.3.2 by solving the equations of Section 3.3.1 is such that for each t ∈ Σ * , A(t) = D E (s, t). The proof is decomposed into two directions:

A(t) ≤ S D E (s, t)
in Lemma 24 (completeness) based on Lemma 23, and

A(t) ≥ S D E (s, t) in Lemma 25 (correctness).
Completeness. Let σ be the solution of (1-7) used in Section 3.3.1 for the construction of A. The proof of Lemma 23 is by induction on σ, with a case analysis of the last operation in σ. It uses the three technical Facts 20, 21, 22, corresponding to the three type operation that can be involved (respectively consolidation, insertion and deletion). The following Fact 19 is an immediate consequence of (4-6) and the definition of weight A . Fact 19. For every i, j such that 0 ≤ i ≤ j ≤ m, for every b ∈ Σ and u ∈ C(E), weight A (q i , b, q j ) = σ(z i,b,j ), and weight A (q i , u, q j ) = σ(z i,u,j ).

Fact 20. For each consolidation a 1 . . . a n -→ w b ∈ E with a 1 , . . . , a n , b ∈ Σ and n ≥ 1, for all states q i , q j ∈ Q, with 0 ≤ i ≤ j ≤ m, it holds that weight A (q i , b, q j ) ≤ S w ⊗ weight A (q i , a 1 . . . a n , q j ).
Proof. If i < j, then w ⊗ z i,a 1 ...an,j is a monomial of the rhs of (3), whose lhs is x i,b,j . By idempotency of S, it follows that σ(x i,b,j ) ⊕ w ⊗ σ(z i,a 1 ...an,j ) = σ(x i,b,j ), by adding w ⊗ σ(z i,a 1 ...an,j ) to both sides. Hence σ(x i,b,j ) ≤ S w ⊗ σ(z i,a 1 ...an,j ). [START_REF] Wagner | The string-to-string correction problem[END_REF]. In both cases, the inequality of Fact 20 follows, by Fact 19. □ Fact 21. For each insertion ε -→ w a ∈ E with a ∈ Σ, for each q i ∈ Q, with 0 ≤ i ≤ m, it holds that weight A (q i , a, q i ) ≤ S w.

Similarly if i = j, then w ⊗ ⊗ n k=1 x a k is a monomial of (1) and σ(x i,b,i ) = σ(x b ) ≤ S w ⊗ ⊗ n k=1 σ(x i,a k ,i ), where σ(x i,b,i ) = σ(x b ) and σ(x i,a k ,i ) = σ(x a k ) follow from
Proof. The weight w is a monomial of (1) (first sum), and hence σ(x i,a,i ) = σ(x a ) ≤ S w. As in the proof of Fact 20, we conclude using Fact 19. □ Fact 22. For each deletion a -→ w ε ∈ E with a ∈ Σ, for all states q ℓ , q j ∈ Q with 0 ≤ ℓ ≤ j ≤ m, it holds that in A (q j ) ≤ S w ⊗ in A (q ℓ ) ⊗ weight A (q ℓ , a, q j ).

and for any state

q i ∈ Q with 0 ≤ i ≤ ℓ, it holds that weight A (q i , b, q j ) ≤ S w ⊗ weight A (q i , b, q ℓ ) ⊗ weight A (q ℓ , a, q j ).
Proof. The principle is the same as in the proof of Fact 20, considering the form of the equations ( 3) and [START_REF] Book | String-rewriting systems[END_REF]. □ Lemma 23. For each t ∈ Σ * , and each edition sequence σ such that s --→ σ E t, it holds that A(t) ≤ S weight(σ).

Proof. We prove by induction on the length of the edition sequence σ.

If σ is empty, then t = s and weight(σ

) = 1. By construction of A 0 s , A 0 s (t) = A 0 s (s) = weight A 0 s (q 0 , s, q m ) = ⊗ m i=1 weight A 0 s (q i-1 , s i , q i ) = 1.
That still holds for A, by construction and boundedness of S.

Assume that σ = σ ′ π where π = ⟨e, p⟩ is a positioned operation of E, and let w = weight(e).

Consolidations. We consider the case of a consolidation: e = a 1 . . . a n -→ w b (n ≥ 1). In this case, the edition s --→ σ E t can be decomposed into:

s --→ E σ ′ t ′ = u a 1 . . . a n u ′ --→ π E u b u ′ = t.
For q i , q j ∈ Q, with 0 ≤ i ≤ j ≤ m, by Lemma 10, and using the fact that A has no backward transition, it holds that

weight A (q i , t, q j ) = ⊕ i≤k≤j weight A (q i , u, q k ) ⊗ weight A (q k , bu ′ , q j ) = ⊕ i≤k≤j weight A (q i , u, q k ) ⊗ ( ⊕ k≤ℓ≤j weight A (q k , b, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ) ) = ⊕ i≤k≤ℓ≤j weight A (q i , u, q k ) ⊗ weight A (q k , b, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ).
Moreover, using Lemma 10 twice, weight A (q i , t ′ , q j ) = ⊕ i≤k≤ℓ≤j weight A (q i , u, q k ) ⊗ weight A (q k , a 1 . . . a n , q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ).

Therefore, by Fact 20, and using monotonicity of S and distributivity of ⊗, weight A (q i , t, q j ) ≤ S w ⊗ weight A (q i , t ′ , q j ).

This inequality still holds for q i , q j ∈ Q with 0 ≤ j < i ≤ m. In this case, weight A (q i , t, q j ) = weight A (q i , t ′ , q j ) = 0 since we do not update the weight of backward transitions in the construction of A from A 0 s . Multiplying each side of (8) by in(q i ) and out(q j ) and summing up the inequalities, by monotonicity of S and distributivity of ⊗, it follows that A(t) ≤ S w ⊗ A(t ′ ). Hence, by induction hypothesis and monotony of S:

A(t) ≤ S w ⊗ A(t ′ ) ≤ S w ⊗ weight(σ ′ ) = weight(σ).
Deletions. Let us now consider the case of a deletion: e = a -→ w ε. In this case, s --→ σ E t can be decomposed into:

s --→ E σ ′ t ′ = u a u ′ --→ π E u u ′ = t. If u = ε, then A(t) = ⊕ q k ,q j ∈Q in(q k ) ⊗ weight A (q k , u ′ , q j ) ⊗ out(q j ) A(t ′ ) = ⊕ q i ,q j ∈Q
in(q i ) ⊗ weight A (q i , au ′ , q j ) ⊗ out(q j ) = ⊕ q i ,q k ,q j ∈Q in(q i ) ⊗ weight A (q i , a, q k ) ⊗ weight A (q k , u ′ , q j ) ⊗ out(q j ).

We can actually restrict the above sums to the cases i ≤ k ≤ j since backward transitions have weight 0 in A. From the first part of Fact 22, in(q k ) ≤ S w ⊗ in(q i ) ⊗ weight A (q i , a, q k ), and using monotonicity of S and distributivity of ⊗, it follows that A(t) ≤ S w ⊗ A(t ′ ), and we conclude using the induction hypothesis as in the previous case.

If u ̸ = ε, for q i , q j ∈ Q, again by Lemma 10, it holds that on the one hand, weight A (q i , t, q j ) = ⊕ q ℓ ∈Q weight A (q i , u, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ) and on the other hand,

weight A (q i , t ′ , q j ) = ⊕ q k ∈Q weight A (q i , u, q k ) ⊗ weight A (q k , au ′ , q j ) = ⊕ q k ∈Q weight A (q i , u, q k ) ⊗ ( ⊕ q ℓ ∈Q weight A (q k , a, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ) ) = ⊕ q k ,q ℓ ∈Q
weight A (q i , u, q k ) ⊗ weight A (q k , a, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ).

In order to compare these two expressions, we use the following inequality, which holds for all q i , q ℓ ∈ Q and can be shown induction on the length of u, using Fact 22.

weight A (q i , u, q ℓ ) ≤ S ⊕ q k ∈Q w ⊗ weight A (q i , u, q k ) ⊗ weight A (q k , a, q ℓ ) Using this last inequality and the above identities on t and t ′ , it follows that weight A (q i , t, q j ) ≤ S w ⊗ weight A (q i , t ′ , q j ) for all q i , q j ∈ Q, and we conclude as in the above case of consolidation.

Insertions. It remains to consider the case of an insertion: e = ε -→ w a. In this case, s --→ σ E t can be decomposed into:

s --→ E σ ′ t ′ = u u ′ --→ π E u a u ′ = t. We have: weight A (q i , t, q j ) = ⊕ q k ∈Q weight A (q i , u, q k ) ⊗ weight A (q k , au ′ , q j ) = ⊕ q k ,q ℓ ∈Q weight A (q i , u, q k ) ⊗ weight A (q k , a, q ℓ ) ⊗ weight A (q ℓ , u ′ , q j ) ≤ S ⊕ q k ∈Q
weight A (q i , u, q k ) ⊗ weight A (q k , a, q k ) ⊗ weight A (q k , u ′ , q j ) ≤ S ⊕ q k ∈Q weight A (q i , u, q k ) ⊗ w ⊗ weight A (q k , u ′ , q j ) = w ⊗ weight A (q i , t ′ , q j ).

The second inequality is by Fact 21, and the last line by Lemma 10. We can conclude as in the other cases, and this concludes the proof of Lemma 23. □

Making the summation of the inequalities from Lemma 23 for each σ, and using the hypotheses that S is complete and idempotent, we have the completeness of A:

Lemma 24. For each t ∈ Σ * , it holds that A(t) ≤ S D E (s, t).

The correctness of the construction of A follows from the next lemma.

Lemma 25. For each t ∈ Σ * , it holds that D E (s, t) ≤ S A(t).

Proof. Every value A(t) returned by A has the form of a sum, by ⊕, of products, by ⊗, of 0/1 values for in 0 , weight 0 , and out 0 , as well as of weights of edit operations in E. Once the 0/1 values have been removed, each of the non-1 products has the same form as weight(σ) for some edit sequence σ such that s -→ σ t. This can be shown by induction using the ordering ≺ defined in Section 3.

A(t) ⊕ D E (s, t) = ⊕ σ∈P (t) weight(σ) ⊕ ⊕ s-→ σ t weight(σ) = ⊕ s-→ σ t weight(σ) = D E (s, t) It follows that D E (s, t) ≤ S A(t). □
Lemma 24 and Lemma 25 complete thus the proof of the Theorem 13.

Effective Computation of D E

Now that we have constructed A as in Theorem 13, we can use it to compute D E (s, t) for a given t ∈ Σ * . As there is no backward transition in A, the computation of A(t) = D E (s, t), given A can be done in a greedy way (Figure 9). Corollary 26. Given a semiring S as in Theorem 13, a ruleset E over S containing only consolidation and deletion edit operations, and s, t ∈ Σ * , D E (s, t) is computable in polynomial time, assuming that E is of constant size.

Proof. Let A be constructed as in the proof of Theorem 13. For 0 ≤ i ≤ |s| and 0 ≤ j ≤ |t|, we define ∆(i, j) recursively by

∆(i, 0) = in(q i ) ∆(i, j) = ⊕ i ′ ≤i ∆(i ′ , j -1) ⊗ weight A (q i ′ , t j , q i ) 1 ≤ j ≤ |t|.
Once A has been constructed, the values of ∆ can be computed and stored in a table

in time O(|s| 2 .|t|). It holds that ∆(i, j) = ⊕ i ′ ≤i in(q i ′ ) ⊗ weight A (q i ′ , t 1..j , q i ).

The case of Fragmentation and Insertion Rulesets

The construction of Theorem 13 can also be reused for computing D E for a symmetric case of ruleset E.

Corollary 27. Given a semiring S as in Theorem 13, a ruleset E over S containing only fragmentation and insertion edit operations, and t ∈ Σ * , one can build a weighted automaton B E t over Σ and S such that for each s ∈ Σ * , B E t (s) = D E (s, t). Assuming that E is of constant size, this construction is in polynomial time in |t|.

Proof. When E contains only fragmentations and insertions, the symmetric ruleset E -1 contains only consolidations and deletions. The construction of the Theorem 13 can thus be applied to E -1 and t, giving the automaton

B E t = A E -1 t . Then B E t (s) = A E -1 t (s) = D E -1 (t, s) = D E (s,

Chaining Consolidations with Fragmentations

According to Proposition 12, one cannot generalise the automata constructions of Section 3 to rulesets mixing arbitrarily consolidation and fragmentation edit operations. However, the constructions of Section 3 can be generalized in order to compute the optimal weight of sequences chaining operations from a ruleset E c , containing consolidations and deletions, with operations from a ruleset E f containing fragmentation and insertions, in that order. Given such rulesets, we define the optimal weight D Ec,E f as follows:

D Ec,E f (s, t) = ⊕ o∈Σ * D Ec (s, o) ⊗ D E f (o, t) = ⊕ s-→ σ o-→ σ ′ t weight(σ) ⊗ weight(σ ′ )
where σ is an edit sequence of E c and σ ′ is an edit sequence of E f .

Lemma We now construct, in quadratic time, the Hadamard product A c,f s,t of A c s and B f t which is a weighted automaton such that ∀o ∈ Σ * , A c,f s,t (o) = A c s (o) ⊗ B f t (o) (see [START_REF] Droste | Semirings and formal power series[END_REF]). Let o ′ ∈ Σ * such that A c,f s,t (o ′ ) has minimal weight wrt ≤ S . This o ′ can be computed by a Viterbi algorithm on A c,f s,t (see e.g. [START_REF] Huang | Advanced dynamic programming in semiring and hypergraph frameworks[END_REF]). It holds then that A c,f s,t (o ′ ) = D Ec•E f (s, t). □ Note that following Proposition 12, it is not possible to iterate this procedure an arbitrary number of times. Moreover, the optimal weight of fragmentations chained with consolidations, in this order, is not computable.

Proposition 31. In general, D E f ,Ec (s, t) is not computable for a ruleset E f containing fragmentation rules and for a ruleset E c containing consolidation rules.

Proof. We consider the rulesets E f and E c constructed in the proof of Proposition 12. They are like in the hypothesis of Proposition 31, and it holds that ♯ --→ * E f o --→ * Ec ♮ for some o iff D E f ,Ec (s, t) ̸ = 0 iff P has a solution. □

Hence the result of Theorem 30 is close to undecidability. This construction can be applied to rulesets such as E 3,c ∪ E 0 and E 3,f ∪ E 0 . As substitution, insertion, and deletion operations of E 0 appear in both rulesets, these operations can thus be used anywhere in D Ec,E f . Such a computation of D Ec,E f may be used in computational music analysis. Back to the Figure 1, a transformation of the Variation 1 into the Variation 7 can be expressed as a sequence of consolidation operations followed by another sequence of fragmentation operations. One could thus evaluate here the distance between two variations without knowing the underlying theme.

Conclusion and Perspectives

We have shown how to compute extended optimal weights and edit distances, for rulesets mixing consolidations and deletions on the one side, and fragmentations and insertions on the other side, using weighted automata constructions, in a generic semiring framework. We also shown both how to compute optimal weights of sequences of consolidations followed by fragmentations and that, in general, optimal weights of sequences of fragmentations followed by consolidations are not computable. To our knowledge, this is the first time an algorithm is proposed to compute this distance (for which dynamic programming techniques used for Levenshtein edit-distance cannot be trivially generalized). These results can be applied to music similarity questions that motivated the Mongeau-Sankoff algorithm as tropical semirings satisfy our assumptions of boundedness, even if the time complexity in E of the proposed constructions may cause scalability issues.

In [START_REF] Mohri | Edit-distance of weighted automata: General definitions and algorithms[END_REF], Mohri proposed weighted transducers to compute the Levenshtein distance between regular languages, and explained that this technique can compute more complex edit distances as long as the operations are defined by transducers. Applying it in the context of an edit distance with consolidations and fragmentations reduces to express the application of these operations with transducers -a problem that we did not try to address.

Generalising the results of this paper to the computation of the extended edit distances between regular languages (or a language and a string) instead of between two strings s and t, is an open question. The generalisation of the construction to closed semirings [START_REF] Dolan | Fun with semirings: A functional pearl on the abuse of linear algebra[END_REF], instead of bounded ones, is another open problem.

Figure 3 :

 3 Figure 3: These common semirings are commutative, idempotent and bounded.

Figure 5 :

 5 Figure 5: The weighted automaton A 0 tutti on the tropical semiring. All transitions that are not represented have a weight of +∞.

Figure 6 :

 6 Figure 6: An illustration of the update equations (3) (left, first ⊕ , and bottom right, second ⊕ ) and (7) (top right). Terms in brackets are added (⊕) to the previous values of x i,b,j and yj.

  Hence, by Theorem 13, ∆(|s|, |t|) = A(t) = D E (s, t). □ As in the Theorem 13, the algorithm computing D E (s, t) takes a time exponential in ||E||. Assuming that E is constant, the whole computation of D E (s, t) runs in O(|s| 3 + |s| 2 • |t|).

	Note that once A has been constructed for a given s, it can be reused to compute
	D

E (s, t) for several t, in time O(|s| 2 • |t|), using the tabulation algorithm in the above proof.

  t) by commutativity of S. □ Using Corollary 27 and the technique used in the proof of Corollary 26, we obtain the following corollary. Given a semiring S as in Theorem 13, a ruleset E over S containing only fragmentation and insertion edit operations, and s, t ∈ Σ * , D E (s, t) is computable in polynomial time, assuming that E is of constant size.

	Corollary 28.

  29. When E c and E f are symmetric and ≤ S is total, D Ec,E f is a distance. Proof. By commutativity of ⊗ and idempotency of the semiring. □ Theorem 13 (and Corollary 27) can be generalised to compute D Ec,E f . Given a commutative semiring S, complete and bounded, E c (respectively E f ) a ruleset over S containing only consolidation and deletion (respectively fragmentation and insertion) edit operations, and s, t ∈ Σ * , the optimal weight D Ec,E f (s, t) is computable in polynomial time, assuming E c and E f of constant size. Proof. The principle is to apply the construction of Theorem 13 on the one side to s and E c , giving A Ec s (denoted A c s below) and on the other side, Corollary 27 to t and E f , giving B E f t = A Altogether, for every o ∈ Σ * , we have A c s (o) = D Ec (s, o) and B f t (o) = D E -1

	Theorem 30. E -1 f t	(denoted B f t below).

f (t, o) = D E f (o, t).

Acknowledgements. We thank the anonymous reviewers for their useful comments on an earlier version of this manuscript.


Laura Ascone
email: laura.ascone@etu.u-cergy.fr

Analyse statistique des Données Textuelles Textual Analysis of Extremist Propaganda and Counter-Narrative: a quanti-quali investigation

Keywords: jihadist propaganda, counter-narrative, discourse analysis, threat, persuasion

This paper investigates the rhetorical strategies of jihadist propaganda and counter-narrative in English and French. Since jihadist propaganda aims at both persuading the Islamic State's sympathisers and threatening its enemies, attention was focused on the way threat and persuasion are verbalised. As far as jihadist propaganda is concerned, the study was conducted on the Islamic State's two official online magazines: Dabiq, published in English, and Dar al-Islam, published in French. As for the counter-narrative, the corpus was composed of the articles published on the main English and French governmental websites. Combining quantitative and qualitative approaches allowed to examine the general characteristics as well as the specificities of both jihadist propaganda and counter-narrative. The software Tropes was used to analyse the corpora from a semantic-pragmatic perspective. The results' statistical validity was then verified and synthesised with the softwares Iramuteq and R. This study revealed that the rhetorical strategies varied between both jihadist propaganda and counter-narrative, and French and English.

Introduction

The recent terrorist attacks by Daesh in Western countries have led researchers and experts to examine the islamisation of radicalism [START_REF] Roy | Le djihad et la mort[END_REF]. Different studies have been conducted on the psychosociological contexts that may lead someone to adhere to the jihadist ideology [START_REF] Benslama | Un furieux désir de sacrifice : le surmusulman[END_REF][START_REF] Khosrokhavar | Radicalisation[END_REF], as well as on the role played by the Internet in the radicalisation process [START_REF] Behr | Radicalisation in the digital era: the use of the Internet in 15 cases of terrorism and extremism[END_REF]). Yet, even though terrorism would not exist without communication [START_REF] Mcluhan | The brain and the media: The "Western" hemisphere[END_REF], the rhetorical strategies of the jihadist propaganda have been neglected and remained unexplored. In an "argumentative war" [START_REF] Angenot | Dialogue de sourds[END_REF][START_REF] Aly | The Internet as Ideological Battleground[END_REF], that is, a war based on language, language and emotions play a critical role (Lombardi, 2015). This research investigates the rhetorical strategies of both jihadist propaganda and counternarrative published on the Internet in English and French. More precisely, this analysis focuses on the way threat and persuasion are expressed in jihadist propaganda, as well as on the way French government and international institutions face and counter jihadist propaganda. Threat is considered as "a statement of an intention to inflict pain, injury, damage, or other hostile action on someone in retribution for something done or not done" (from Oxford Living Dictionaries). On the other hand, persuasion is considered as "the action or process of persuading someone or of being persuaded to do or believe something" (from Oxford Living Dictionaries). From a linguistic perspective, threat and persuasion are complex speech acts. Therefore, pragmatics and, more specifically, [START_REF] Searle | Speech acts : an essay in the philosophy of language[END_REF] speech act theory, constituted the basis of this study.

As far as jihadist propaganda is concerned, the analysis was conducted on the Islamic State's two official online magazines: Dabiq, published in English, and Dar al-Islam, published in French. The French magazine, which is not a translation of the English one, addresses French readers only, whereas the English version addresses all non-Arabic speakers. As far as the counter-narrative is concerned, the corpus was composed of the articles published on the main French and English institutional websites such as stopdjihadism.fr or counterjihadreport.com. The fact that jihadist propaganda and counter-narrative address different readerships, led us to hypothesise that differences in both content and form might be identified between the two magazines, as well as among the different governmental websites. Combining quantitative and qualitative approaches [START_REF] Garric | L'analyse de corpus face à l'hétérogénéité des données : d'une difficulté méthodologique à une nécessité épistémologique[END_REF][START_REF] Rastier | La mesure et le grain : sémantique de corpus[END_REF] (that is, lexicometry and textometry for the quantitative approach, and the interpretation of the text according to the ideology behind it for the qualitative one), allowed to examine the general characteristics as well as the specificities of both jihadist propaganda and counter-narrative. Following [START_REF] Marchand | Analyse avec IRaMuTeQ de dialogues en situation de négociation de crise : le cas Mohammed Mehra[END_REF] work, the software Tropes was used to analyse the corpora from a semantic-pragmatic perspective. The results' statistical validity was verified with the softwares Iramuteq and R.

By comparing the rhetorical strategies used in both jihadist propaganda [START_REF] Huyghe | Terrorismes : violence et propagande[END_REF] and counter-narrative, the aim of this research was to identify the linguistic differences between these two discourses and these two languages. After having presented the rhetorical pattern of jihadist propaganda, the linguistic characteristics of English and French counter-narratives will be examined. The jihadist and governmental rhetorical strategies will then be contrasted.

Corpus and methodology

Jihadist propaganda

The analysis of the rhetorical strategies in jihadist propaganda was conducted on Daesh's official online magazines Dabiq, published in English, and Dar al-Islam, published in French. Since these two magazines address a readership that has already adhered to the jihadist ideology, their goal is to both reinforce the reader's adhesion and to incite him/her to act in the name of the jihadist ideology. The reader is then incited to adopt the behaviour a good Muslim should have, and to take revenge on who is presented by Daesh as the responsible for the Muslims' humiliation, that is the West. As far as Dabiq is concerned, the corpus investigated was composed of all the articles published on the first fourteen numbers (i.e. 377,450 words). As for Dar al-Islam, the analysis was conducted on the first nine issues (229,762 words).

To analyse the rhetorical strategies used in jihadist propaganda, a quanti-qualitative approach was adopted (cf. [START_REF] Garric | L'analyse de corpus face à l'hétérogénéité des données : d'une difficulté méthodologique à une nécessité épistémologique[END_REF][START_REF] Rastier | La mesure et le grain : sémantique de corpus[END_REF]. More precisely, this iterative approach was composed of four stages. A first qualitative analysis of the jihadist ideology, the radicalisation process, and the linguistic characteristics of hate speech and propagandistic discourse was essential to the understanding of the jihadist discourse as well as to the advancement of our first hypotheses. The second stage corresponded to a quantitative analysis whose goal was to verify the validity of our hypotheses: the corpus was then examined with the software Tropes, which allows to investigate a text from a semantic perspective. More precisely, based on a pre-established lexicon, the software identifies the themes tackled in the text, and shows how these themes are linked to one another. The most frequent themes in both magazines are religion and conflict. However, in order to study the way threat and persuasion are expressed in the two corpora, a deeper qualitative analysis was conducted on the themes sentiment for the French corpus, and feeling for the English one (third stage). In other terms, the quantitative analysis constituted the basis for a qualitative study, which was then conducted only on the expressions conveying feelings. Because of their size-difference, the nine issues of the French magazine count 318 sentiment-expressions, whereas Dabiq counts 705 feeling-expressions. Therefore, in order to conduct the analysis on same-size corpora and contrast the results, the study was conducted on the 318 French expression, and on the first 318 English ones. Finally, a last quantitative analysis was conducted with the softwares Iramuteq and R to test the hypotheses and results issued by the qualitative study (fourth stage). The combination and alternation of both quantitative and qualitative approaches allowed to examine Daesh's discourse in relation to the context in which it is produced [START_REF] Valette | Prévenir le racism et la xénophobie: propositions de linguistes[END_REF].

Counter-narrative

The analysis on the rhetorical strategies in French and English counter-narratives was conducted on the main governmental institutional websites. The French corpus was composed of the articles published on www.stop-djihadisme.gouv.fr (the platform created after the first terrorist attacks in France in 2015), www.interieur.gouv.fr (the website of the Minister of Interior), and www.cpdsi.fr (the website of the Centre de Prévention contre les Dérives Sectaires liées à l'Islam). The corpus counts 115,950 words. As far as the English corpus is concerned, it was composed of the articles published on www.counterjihadreport.com (a news aggregating website), www.consilium.europa.eu (the website of the European Council and of the European Union Council), www.ec.europa.eu (the website of the European Commission), and on the Radicalisation Awareness Network (this is a specific section of the website of the European Commission). The corpus counts 116,000 words.

In order to conduct comparable analyses, the same quanti-qualitative approach was adopted. The qualitative analysis of the geopolitical context and of the different campaigns used to face and counter the radicalisation process was essential to the understanding of both French and English counter-narratives (first stage). Then, a quantitative analysis was conducted with the software Tropes, which allowed to identify the most frequent themes. The themes religion and droit ("law") were the most present in the French corpus, whereas the themes education and communication were the most frequent in the English one (second stage). The third stage corresponded to the qualitative analysis that was conducted on the category sentiment, for the French corpus, and feeling, for the English one. Since the two corpora had almost the same size, this time the qualitative analysis was conducted on all the propositions identified by Tropes as belonging to the categories sentiment (292 propositions) and feeling (370 propositions). A last quantitative analysis was then conducted with the softwares Iramuteq and R to test the results issued by the qualitative study (fourth stage). The results of the analysis on jihadist propaganda and counter-narrative were then contrasted to compare the rhetorical strategies used in jihadist propaganda and counter-narrative.

The rhetorical strategies used in French and English jihadist propaganda

The quantitative analysis conducted with the software Tropes, and the qualitative study conducted on the categories sentiment and feeling, revealed the components of the jihadist discourse. The propaganda of the Islamic State is based on five key concepts: threat, persuasion, reward, obligation, and prohibition. Each of them was examined from both quantitative (i.e., its identification and distribution in the two magazines, Dabiq and Dar al-Islam, using the softwars Tropes and Iramuteq, and the corpus analysis toolkit AntoConc) and qualitative (i.e., analysing each concept in relation to the context in which it was produced) JADT 2018 : 14 es Journées internationales d'Analyse statistique des Données Textuelles perspectives. Yet, these five concepts are not independent from one another. Rather, they are strongly linked to one another.

Figure 1 shows the rhetorical pattern of jihadist discourse. Since Dabiq and Dar al-Islam aim at manipulating the reader's behaviour, jihadist propaganda is based on obligations and prohibitions. Rewards as well as guilty feelings towards the Muslims living in the Middle-East, aim at leading the reader to respect these indications. Not respecting them would mean facing negative consequences. Threat may then be expressed against the members of the Islamic State themselves and, more in general, against any Muslim. Obligations are also exploited to impose the readership a hostile and violent attitude against Western countries, which is justified by the feeling of victimisation. Fighting against the Muslims' enemy is presented by jihadists as a heroic and valorising action, and therefore, a persuasive one. Furthermore, not only are attractive factors rewards for the reader's obedience. They are sometimes presented as independent from the reader's behaviour. In other terms, persuasion is presented as a positive and valorising act that, contrary to rewards, does not depend on whether the reader respects or not the prescriptions imposed

The sentence "Jihad is necessary to obtain Allah's forgiveness", for instance, presents an obligation ("it is necessary") and a reward that will be granted if the obligation is respected ("to obtain Allah's forgiveness"). However, this sentence expresses more than an obligation and a reward. Jihad, which is interpreted as persuasive by jihadists, tends to be associated with terrorist attacks and, consequently, it will be perceived as threatening by Western countries. Furthermore, this sentence implies that if the obligation is not respected, the individual will not obtain Allah's forgiveness. In other terms, this sentence indirectly expresses a threat against the readership too.

The rhetorical strategies used in French and English counter-narratives

The large number of Daesh's sympathisers and foreign fighters shows that the communicative and rhetorical strategies adopted in Daesh's propaganda have an important and persuasive impact on the readership. On the contrary, the counter-narrative produced by the different governments to face and counter jihadist propaganda, has been criticised not to be as efficient as jihadist propaganda. In the French corpus, 292 propositions conveying sentiment ("feeling") were identified, whereas 370 propositions conveying feelings were identified in the English one.

The frequency of the five categories (i.e. of the propositions conveying threat, reward, obligation, and prohibition) was calculated in the French and English corpora. The reward-category is the only one that was more present in the French corpus than in the English one. Contrary to the Islamic State's propaganda, the propositions conveying rewards and prohibitions are almost absent in both French and English counter-narratives. On the contrary, what these two discourses have in common is the high frequency of the propositions conveying threat (Example 1).

1. "Terrorist groups will continue to exploit the refugee crisis in their propaganda, seeking to portray Western mistreatment of Muslims, and inciting fear by alleging that their supporters are being smuggled in amongst genuine refugees." (RAN website)

As Example 1 shows, threat tends to be associated to the other (i.e., the Islamic State), which implies that Western countries are presented as victims of the Islamic State. In the English corpus, 355 occurrences of the word victim(s) were identified. The corpus analysis toolkit AntConc showed that the most frequent collocation of this term is the word terrorism (57 cooccurrences). On the contrary, the French corpus, where the word victime/s occurs 70 times only, presents only 2 co-occurrences of the term terrorisme. Rather, French counter-narrative tends to talk about rescuing and helping victims (secours/aide aux victimes). Furthermore, differences were identified between the different websites in a same language.

Figure 2 shows the distribution and, more precisely, the under-and overuse of the most representative terms in two French governmental websites: stopdjihadisme and CPDSI. The figure revealed that CPDSI website focuses more on the religious dimension. The words islam, jihad and jihadiste ("jihadist") are overused in this sub-corpus. This implies that jihad and jihadiste are presented and interpreted as religious terms. On the contrary, the website of the stopdjihadisme campaign is characterised by an overuse of the words terroriste ("terrorist"), terrorisme ("terrorism"), Syrie ("Syria"), radicalisation ("radicalisation"), Irak ("Iraq"), français ("French"), and France ("France"). The overuse of these specific terms shows that the campaign and, consequently, its website focus more on the dimension, where the radicalisation process is presented in relation to terrorism and not to Islam.

Conclusion

This comparative analysis revealed that jihadist discourse and counter-narrative present both similarities and differences. As far as the differences are concerned, the frequency of the propositions conveying threats, persuasion, prohibitions, obligations, and rewards varied between these two discourses: they were more frequent in counter-narrative than in jihadist propaganda. The Islamic State's propaganda aims at reinforcing the reader's adhesion to the jihadist ideology, and at inciting him/her to act against its enemies in the name of the jihadist ideology. On the contrary, counter-narrative does not aim at reinforcing an ideology. Rather, it aims at countering the jihadist radicalisation process. This difference was confirmed by the variation of the different category-frequencies in jihadist propaganda and counter-narrative. Despite this crucial difference, similarities between these two discourses were identified. More precisely, both discourses present the respective speakers' communities as victims of the other and, consequently, incite the readership to fight, whether violently or not, against the enemy.

Figure 1 :

 1 Figure 1: the rhetorical pattern of jihadist propaganda

Figure 2 :

 2 Figure 2: under-and overuse of some key-terms in French counter-narrative