Patrick L Combettes

Sever A Hirstoaga

Visco-penalization of the sum of two monotone operators

Keywords: Approximating curve, monotone operator, penalization, variational inequality, viscosity, Yosida approximation

A new type of approximating curve for finding a particular zero of the sum of two maximal monotone operators in a Hilbert space is investigated. This curve consists of the zeros of perturbed problems in which one operator is replaced with its Yosida approximation and a viscosity term is added. As the perturbation vanishes, the curve is shown to converge to the zero of the sum that solves a particular strictly monotone variational inequality. As an offspring of this result, we obtain an approximating curve for finding a particular zero of the sum of several maximal monotone operators. Applications to convex optimization are discussed.

1 Problem statement A central problem which arises in various areas of nonlinear analysis and its applications is the inclusion problem find

x ∈ zer(A + B) = z ∈ H | 0 ∈ Az + Bz , (1.1)
where A and B are maximal monotone operators from a real Hilbert space H to its power set 2 H , e.g., [START_REF] Attouch | A general duality principle for the sum of two operators[END_REF][START_REF] Combettes | Solving monotone inclusions via compositions of nonexpansive averaged operators[END_REF][START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF][START_REF] Mercier | Inéquations Variationnelles la Mécanique[END_REF][START_REF] Tseng | Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[END_REF][START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]. In many instances, (1.1) admits multiple solutions and one can select a particular point x 0 ∈ zer(A + B) by solving the variational inequality

x 0 ∈ zer(A + B) and (∃ v 0 ∈ V x 0 )(∀z ∈ zer(A + B)) x 0 -z | v 0 ≤ 0, (1.2)
1 where V : H → 2 H is a strictly monotone operator referred to as a viscosity operator. Bringing into play the normal cone operator (see (1.8)), we can conveniently rewrite (1.2) as 0 ∈ N zer(A+B) x 0 + V x 0 .

(1.3)

We shall investigate the problem of solving (1.3) under the following standing assumptions (see Section 1.1 for notation).

Assumption 1.1

(i) A and B are maximal monotone operators from H to 2 H such that A+B is maximal monotone and zer(A + B) = ∅.

(ii) V : H → 2 H is a maximal monotone operator which satisfies the following properties.

(a) V is uniformly monotone in the sense that there exists an increasing function c : [0, +∞[ → [0, +∞[ that vanishes only at 0 such that lim t→+∞ c(t)/t = +∞ and (∀(x, u) ∈ gr V )(∀(y, v) ∈ gr V ) x -y | u -v ≥ c( x -y ).

(1.4) (b) V maps every bounded subset of H into a bounded set.

It follows from [START_REF] Combettes | Approximating curves for nonexpansive and monotone operators[END_REF]Theorem 3.10] that, under Assumption 1.1, the solution x 0 to (1.3) is uniquely defined and so is the approximating curve (x ε ) ε∈]0,1[ defined by

(∀ε ∈ ]0, 1[) 0 ∈ Ax ε + Bx ε + εV x ε . (1.5)
Moreover, x ε → x 0 when ε ↓ 0 (historically, the earliest result in this direction was obtained in [START_REF] Bruck | A strongly convergent iterative solution of 0 ∈ U (x) for a maximal monotone operator U in Hilbert space[END_REF] with A = 0 and V = Id, in which case x 0 is the zero of B of minimum norm). The asymptotic behavior of approximating curves plays a central role in proving the convergence of parent discrete or continuous dynamical systems for solving (1.3), e.g., [START_REF] Ya | A new approach to investigation of evolution differential equations in Banach spaces[END_REF][START_REF] Attouch | A dynamical approach to convex minimization coupling approximation with the steepest descent method[END_REF][START_REF] Bruck | A strongly convergent iterative solution of 0 ∈ U (x) for a maximal monotone operator U in Hilbert space[END_REF][START_REF] Chidume | Approximation of solutions of nonlinear equations of Hammerstein type in Hilbert space[END_REF][START_REF] Reich | Constructing zeros of accretive operators II[END_REF]. However, inclusions involving, as in (1.5), several set-valued operators are not easily dealt with and neither are the associated dynamical systems. A common relaxation of Problem (1.1) is obtained by replacing A with its Yosida approximation (see (1.7)), which is a better-behaved, single-valued, Lipschitz continuous operator. In the context of discrete dynamical systems, such relaxations lead to splitting algorithms that have been studied in several places, e.g., [START_REF] Bauschke | The asymptotic behavior of the composition of two resolvents[END_REF][START_REF] Combettes | Solving monotone inclusions via compositions of nonexpansive averaged operators[END_REF][START_REF] Mahey | Partial regularization of the sum of two maximal monotone operators[END_REF][START_REF] Mercier | Inéquations Variationnelles la Mécanique[END_REF]. The objective of the present paper is to investigate the asymptotic behavior of an approximating curve obtained by replacing A with Yosida approximations in (1.5). More precisely, our main result (Theorem 3.1) establishes the strong convergence to the solution x 0 to (1.3) of the inexact approximating curve

(x ε,φ(ε) ) ε∈]0,1[ defined by (∀ε ∈ ]0, 1[) 0 ∈ φ(ε) Ax ε,φ(ε) + Bx ε,φ(ε) + εV x ε,φ(ε) + e ε , (1.6)
under suitable conditions on the function φ : ]0, 1[ → ]0, 1[ and the error process (e ε ) ε∈]0,1[ . The outline of the remainder of the paper is as follows. In Section 2, we provide the preliminary results that will be required to obtain our main result on the asymptotic behavior of (1.6) in Section 3. Finally, in Section 4, we address the case of more than two operators. Applications to convex optimization are discussed.

Notation

Throughout, H is a real Hilbert space with scalar product • | • , norm • , and identity operator Id. The symbols → and ⇀ denote, respectively, strong and weak convergence.

Let M : H → 2 H be a set-valued operator. Then dom M = x ∈ H | M x = ∅ is the domain of M , ran M = u ∈ H | (∃ x ∈ H) u ∈ M x its range, zer M = x ∈ H | 0 ∈ M x its set of zeros, and gr M = (x, u) ∈ H × H | u ∈ M x its graph. The inverse of M is the operator M -1 : H → 2 H with graph (u, x) ∈ H × H | u ∈ M x , the resolvent of M is J M = (Id +M ) -1 , and the Yosida approximation of M of index φ ∈ ]0, +∞[ is φ M = 1 φ (Id -J φM ). (1.7)
Moreover, M is γ-strongly monotone for some γ ∈ ]0, +∞[ if M -γ Id is monotone. For background on monotone operators, see [START_REF] Aubin | Set-Valued Analysis[END_REF] and [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF].

The projection operator onto a nonempty closed convex subset C of H is denoted by P C , its distance function by d C , and its normal cone operator by N C , i.e.,

N C : H → 2 H : x → u ∈ H | (∀y ∈ C) y -x | u ≤ 0 , if x ∈ C; ∅, otherwise. (1.8) A function f : H → ]-∞, +∞] is proper if dom f = x ∈ H | f (x) < +∞ = ∅; in this case, its subdifferential is ∂f : H → 2 H : x → u ∈ H | (∀y ∈ H) y -x | u + f (x) ≤ f (y) . (1.9) Moreover, f is γ-strongly convex for some γ ∈ ]0, +∞[ if f -γ • 2 /2 is convex. The class of proper lower semicontinuous convex functions from H to ]-∞, +∞] is denoted by Γ 0 (H). Now let f ∈ Γ 0 (H). The conjugate of f is the function f * ∈ Γ 0 (H) defined by f * : u → sup x∈H x | u -f (x)
and the Moreau envelope of index φ ∈ ]0, +∞[ of f is the finite and continuous convex function

φ f : x → inf y∈H f (y) + x -y 2 /(2φ).
For every x ∈ H, the function y → f (y) + x -y 2 /2 admits a unique minimizer, which is denoted by prox f x. We have prox f = J ∂f and [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF]

(∀φ ∈ ]0, +∞[) ∇ φ f = φ (∂f ) = 1 φ (Id -prox φf ) = prox f * /φ (•/φ). (1.10)
For background on convex analysis, see [START_REF] Zȃlinescu | Convex Analysis in General Vector Spaces[END_REF].

Preliminary results

Lemma 2.1 Let u and v be points in H, and let φ and ρ be real numbers in [0, +∞[. Then

φu -ρv | v -u ≤ 1 4 φ v 2 + ρ u 2 .
(2.1)

Proof. We have 0 ≤ 2u -v 2 = 4 u 2 -4 u | v + v 2 . Hence, φu | v ≤ φ( u 2 + v 2 /4). Likewise, ρv | u ≤ ρ( v 2 + u 2 /4
). Adding these two inequalities yields (2.1).

Lemma 2.2 Let M : H → 2 H be a maximal monotone operator and suppose that Assumption 1.1(ii) is satisfied. Then the inclusion 0 ∈ M x + V x possesses exactly one solution.

Proof. Assumption 1.1(ii)(b) implies that V is locally bounded. Consequently, it results from [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]Theorem 32.G] that V -1 is surjective. Thus,

dom M ⊂ dom V = ran V -1 = H (2.
(ε n ) n∈N in ]0, 1[ such that ε n ↓ 0, x εn ⇀ x and 1 M εn x εn → 0 ⇒ (∀ε ∈ ]0, 1[) x ∈ zer M ε . (2.3)
The following result is an extension of [14, Theorem 3.10] which allows for inexact inclusions.

Theorem 2.4 Let (M ε ) ε∈]0,1[ be a family of maximal monotone operators from H to 2 H such that C = ε∈]0,1[ zer M ε = ∅, and suppose that Assumption 1.1(ii) is satisfied. Then there exists a unique point x 0 ∈ C such that 0 ∈ N C x 0 + V x 0 . Moreover, the inclusions

(∀ε ∈ ]0, 1[) 0 ∈ M ε x ε + εV x ε + e ε , where e ε ∈ H, (2.4)
define a unique family (x ε ) ε∈]0,1[ . Now suppose that e ε /ε → 0 as ε ↓ 0 and that (x ε ) ε∈]0,1[ is A-focused with respect to (M ε ) ε∈]0,1[ . Then x ε → x 0 as ε ↓ 0.

Proof. By maximal monotonicity of the operators (M -1 ε ) ε∈]0,1[ , the sets (zer M ε ) ε∈]0,1[ are closed and convex [START_REF] Aubin | Set-Valued Analysis[END_REF]Proposition 3.5.6.1]. Thus C is nonempty, closed, and convex, and N C is therefore maximal monotone [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]Example 32.15]. Consequently, it follows from Lemma 2.2 that x 0 is uniquely defined. Since the operators ε -1 (M ε + e ε ) ε∈]0,1[ are maximal monotone, it also follows from Lemma 2.2 that the family (x ε ) ε∈]0,1[ is uniquely defined. The same argument also shows that the auxiliary family of inclusions

(∀ε ∈ ]0, 1[) 0 ∈ M ε y ε + εV y ε (2.5)
defines a unique approximating curve (y ε ) ε∈]0,1[ . Moreover, [14, Theorem 3.10] asserts that

(y ε ) ε∈]0,1[ is A-focused with respect to (M ε ) ε∈]0,1[ ⇒ y ε → x 0 as ε ↓ 0. (2.6)
It follows from (2.4) and (2.5) that, for every ε ∈ ]0, 1[, there exist points

v ε ∈ V x ε and w ε ∈ V y ε such that -εv ε -e ε ∈ M ε x ε and -εw ε ∈ M ε y ε . (2.7)
Using the monotonicity of the operators (M ε ) ε∈]0,1[ and the uniform monotonicity of V , we obtain

(∀ε ∈ ]0, 1[) 0 ≤ x ε -y ε | w ε -ε -1 e ε -v ε (2.8) and (∀ε ∈ ]0, 1[) c( x ε -y ε ) ≤ x ε -y ε | v ε -w ε , (2.9)
respectively. Adding (2.8) to (2.9), and then using Cauchy-Schwarz, we obtain

(∀ε ∈ ]0, 1[) c( x ε -y ε ) ≤ - 1 ε x ε -y ε | e ε ≤ x ε -y ε e ε ε .
(2.10)

Now suppose that e ε /ε → 0 as ε ↓ 0. Then it follows from (2.10) that there exists β ∈ ]0, +∞[ such that

(∀ε ∈ ]0, 1[) x ε = y ε ⇒ c( x ε -y ε ) x ε -y ε ≤ β. (2.11)
Hence, since lim t→+∞ c(t)/t = +∞, we infer from (2.11) that ( x ε -y ε ) ε∈]0,1[ is bounded and, in turn, from (2.10) that x ε -y ε → 0 as ε ↓ 0.

(2.12)

In addition, since the operators

( 1 M ε ) ε∈]0,1[ are Lipschitz continuous [7, Theorem 3.5.9(ii)], we obtain 1 M ε x ε -1 M ε y ε → 0 as ε ↓ 0. Altogether, if (x ε ) ε∈]0,1[ is A-focused with respect to (M ε ) ε∈]0,1[ , (y ε ) ε∈]0,1[ is likewise.
In view of (2.6) and (2.12), we conclude that x ε → x 0 as ε ↓ 0.

The following theorem, which is of interest in its own right, will also be required. It is a natural extension of the well-known Brézis-Crandall-Pazy condition [START_REF] Brézis | Perturbations of nonlinear maximal monotone sets in Banach space[END_REF]. Theorem 2.5 Let M 1 and M 2 be maximal monotone operators from H to 2 H . Suppose that Assumption 1.1(ii) is satisfied and consider the inclusions

(∀ρ ∈ ]0, 1[) 0 ∈ ρ M 1 z ρ + M 2 z ρ + V z ρ .
(2.13)

Then the following hold.

(i) The family (z ρ ) ρ∈]0,1[ is uniquely defined.

(ii) The following conditions are equivalent:

(a) There exists a unique point

z 0 ∈ H such that 0 ∈ M 1 z 0 + M 2 z 0 + V z 0 . (b) The family ( ρ M 1 z ρ ) ρ∈]0,1[ is bounded. (iii) If one of the conditions in (ii) is satisfied, then z ρ → z 0 as ρ ↓ 0.
Proof. (i): It follows from [7, Theorem 3.5.9] that the operators ( ρ M 1 ) ρ∈]0,1[ are maximal monotone with domain H. In turn, [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]Theorem 32.I] asserts that the operators ( ρ M 1 +M 2 ) ρ∈]0,1[ are maximal monotone. Thus, we obtain the desired conclusion through Lemma 2.2.

(ii): We first suppose that there exists a point z 0 ∈ H such that

0 ∈ M 1 z 0 + M 2 z 0 + V z 0 . (2.14)
Note that, since M 1 + M 2 + V is strictly monotone, this point is necessarily unique. Now fix ρ ∈ ]0, 1[. We deduce from (2.14), (2.13), and (i) that there exist u 0 ∈ M 1 z 0 , v 0 ∈ V z 0 , and

v ρ ∈ V z ρ such that -u 0 -v 0 ∈ M 2 z 0 and -ρ M 1 z ρ -v ρ ∈ M 2 z ρ . (2.15)
Hence, the monotonicity of M 2 yields

z ρ -z 0 | u 0 -ρ M 1 z ρ ≥ z ρ -z 0 | v ρ -v 0 , (2.16)
and, in view of the monotonicity of V , we obtain

z ρ -z 0 | u 0 -ρ M 1 z ρ ≥ 0. (2.17)
On the other hand, the inclusions u 0 ∈ M 1 z 0 and ρ M 1 z ρ ∈ M 1 (J ρM 1 z ρ ), together with the monotonicity of M 1 , lead to the inequality

z 0 -J ρM 1 z ρ | u 0 -ρ M 1 z ρ ≥ 0. (2.18) Adding (2.17) to (2.18) results in 0 ≤ z ρ -J ρM 1 z ρ | u 0 -ρ M 1 z ρ = ρ ρ M 1 z ρ | u 0 -ρ M 1 z ρ 2 . (2.19)
Consequently, Cauchy-Schwarz yields

ρ M 1 z ρ ≤ u 0 . (2.20)
Conversely, suppose that (ii)(b) is satisfied, i.e., there exists β ∈ ]0, +∞[ such that

sup ρ∈]0,1[ ρ M 1 z ρ ≤ β. (2.21)
It suffices to show the existence of a point z 0 ∈ H such that 0 ∈ M 1 z 0 +M 2 z 0 +V z 0 as its uniqueness will follow from the strict monotonicity of M 1 + M 2 + V . Let us first prove that z ε -z ρ → 0 as ε ↓ 0 and ρ ↓ 0. To this end, take ε and ρ in ]0, 1[. By (2.13) and (i), there exist

v ε ∈ V z ε and v ρ ∈ V z ρ such that -ε M 1 z ε -v ε ∈ M 2 z ε and -ρ M 1 z ρ -v ρ ∈ M 2 z ρ . (2.22)
On the one hand, the monotonicity of M 2 and the uniform monotonicity of V yield

c( z ε -z ρ ) ≤ z ε -z ρ | ρ M 1 z ρ -ε M 1 z ε . (2.23)
On the other hand, it follows from the monotonicity of M 1 and the inclusions

ε M 1 z ε ∈ M 1 (J εM 1 z ε ) and ρ M 1 z ρ ∈ M 1 (J ρM 1 z ρ ) that 0 ≤ J ρM 1 z ρ -J εM 1 z ε | ρ M 1 z ρ -ε M 1 z ε . (2.24) c( z ε -z ρ ) ≤ ε( ε M 1 z ε ) -ρ( ρ M 1 z ρ ) | ρ M 1 z ρ -ε M 1 z ε ≤ 1 4 (ε + ρ)β 2 . (2.25)
Thus, z ε -z ρ → 0 as ε ↓ 0 and ρ ↓ 0.

(2.26)

Now let (ρ n ) n∈N be an arbitrary sequence in ]0, 1[ such that ρ n ↓ 0 as n → +∞. We deduce from (2.26) that (z ρn ) n∈N is a Cauchy sequence. Hence, there exists a point z 0 ∈ H such that

z ρn → z 0 as n → +∞. Let us show that 0 ∈ M 1 z 0 + M 2 z 0 + V z 0 . First,
v ∈ V z 0 . (2.28) Likewise, since -v ρ kn -ρ kn M 1 z ρ kn ⇀ -v -u,
0 ∈ M 1 z 0 + M 2 z 0 + V z 0 .
(iii): Suppose that there exists z 0 ∈ H such that 0 ∈ M 1 z 0 + M 2 z 0 + V z 0 and let ρ ∈ ]0, 1[. Then there exist u 0 ∈ M 1 z 0 , v 0 ∈ V z 0 , and v ρ ∈ V z ρ such that (2.15) holds. In turn, (2.16) is satisfied and the uniform monotonicity of V leads to

c( z ρ -z 0 ) ≤ z ρ -z 0 | u 0 -ρ M 1 z ρ .
(2.30)

Adding this inequality to (2.18), and then using Cauchy-Schwarz and (2.20), we obtain

c( z ρ -z 0 ) ≤ z ρ -J ρM 1 z ρ | u 0 -ρ M 1 z ρ ≤ ρ ρ M 1 z ρ u 0 -ρ M 1 z ρ 2 ≤ ρ u 0 2 . (2.31)
We conclude that z ρ → z 0 as ρ ↓ 0. 3 The visco-penalization approximating curve Theorem 3.1 Suppose that Assumption 1.1 is satisfied. Then there exists a unique point x 0 ∈ zer(A + B) such that 0 ∈ N zer(A+B) x 0 + V x 0 .

(3.1)

Moreover, given φ : ]0, 1[ → ]0, 1[, the inclusions

(∀ε ∈ ]0, 1[) 0 ∈ φ(ε) Ax ε,φ(ε) + Bx ε,φ(ε) + εV x ε,φ(ε) + e ε , where e ε ∈ H, (3.2)
define a unique family (x ε,φ(ε) ) ε∈]0,1[ . Now suppose that c is continuous, that (φ(ε) + e ε )/ε → 0 as ε ↓ 0, and that one of the following holds:

(i) x 0 ∈ int dom A. (ii) x 0 ∈ int dom B.
(iii) A and B satisfy the "angle property"

(∃ σ 1 ∈ R)(∃ σ 2 ∈ [0, +∞[)(∃ σ 3 ∈ [0, +∞[)(∀ρ ∈ ]0, 1[)(∀(x, u) ∈ gr B) ρ Ax | u ≥ -σ 1 ( ρ Ax) + σ 2 u -σ 3 , (3.3)
and one of the following holds:

(a) dom B is bounded.

(b) V is Lipschitz continuous and strongly monotone.

Then x ε,φ(ε) → x 0 as ε ↓ 0.

Proof. The set zer(A + B) is nonempty and, since (A + B) -1 is maximal monotone, it is also closed and convex [7, Proposition 3.5.6.1]. Hence, N zer(A+B) is maximal monotone [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]Example 32.15]. The existence and uniqueness of x 0 in (3.1) therefore follow from Lemma 2.2. On the other hand, arguing as in the proof of Theorem 2.5(i), we obtain the maximal monotonicity of the operators ε -1 ( φ(ε) A+B+e ε ) ε∈]0,1[ and, in turn, the existence and uniqueness of (x ε,φ(ε)

) ε∈]0,1[ via Lemma 2.2.
Using once again Lemma 2.2, we observe that the inclusions

(∀ε ∈ ]0, 1[) 0 ∈ (A + B)y ε + εV y ε + e ε (3.4)
also define a unique approximating curve (y ε ) ε∈]0,1[ . Now suppose that e ε /ε → 0 as ε ↓ 0. Then, upon setting M ε ≡ A + B in Theorem 2.4, we get

y ε → x 0 as ε ↓ 0, ( 3.5)
since the A-focusing property of (y ε ) ε∈]0,1[ follows at once from the sequential closedness of gr(A+B) in H weak × H strong , which is guaranteed by the maximal monotonicity of A + B [7, Proposition 3.5.6.2]. Next, we shall show that there exist η ∈ ]0, 1] and τ ∈ ]0, +∞[ such that

(∀ε ∈ ]0, η[) c( x ε,φ(ε) -y ε ) ≤ τ φ(ε) ε . (3.6)
For this purpose, take ε and ρ in ]0, 1[. As seen above, there exists a unique point

x ε,ρ ∈ dom B such that 0 ∈ ρ Ax ε,ρ + Bx ε,ρ + εV x ε,ρ + e ε . (3.7)
It follows from (3.7) and (3.2) that there exist points v ε,ρ ∈ V x ε,ρ and w ε ∈ V x ε,φ(ε) such that

-ρ Ax ε,ρ + εv ε,ρ + e ε ∈ Bx ε,ρ (3.8)
and

-φ(ε) Ax ε,φ(ε) + εw ε + e ε ∈ Bx ε,φ(ε) . (3.9)
Consequently, the monotonicity of B yields

0 ≤ x ε,φ(ε) -x ε,ρ | ρ Ax ε,ρ -φ(ε) Ax ε,φ(ε) -ε x ε,φ(ε) -x ε,ρ | w ε -v ε,ρ , (3.10)
and we deduce from (1.4) that

εc( x ε,φ(ε) -x ε,ρ ) ≤ x ε,φ(ε) -x ε,ρ | ρ Ax ε,ρ -φ(ε) Ax ε,φ(ε) . (3.11)
On the other hand, the inclusions ρ Ax ε,ρ ∈ A(J ρA x ε,ρ ) and φ(ε) Ax ε,φ(ε) ∈ A(J φ(ε)A x ε,φ(ε) ), (3.12) and the monotonicity of A lead to the inequality

0 ≤ J ρA x ε,ρ -J φ(ε)A x ε,φ(ε) | ρ Ax ε,ρ -φ(ε) Ax ε,φ(ε) . (3.13)
Adding (3.11) to (3.13), and then using Lemma 2.1, we obtain

εc( x ε,φ(ε) -x ε,ρ ) ≤ φ(ε)( φ(ε) Ax ε,φ(ε) ) -ρ( ρ Ax ε,ρ ) | ρ Ax ε,ρ -φ(ε) Ax ε,φ(ε) ≤ 1 4 φ(ε) ρ Ax ε,ρ 2 + ρ φ(ε) Ax ε,φ(ε) 2 . (3.14)
Note that, since V satisfies Assumption 1.1(ii), so does V ε = εV + e ε . Hence, applying Theorem 2.5 with M 1 = A, M 2 = B, and V ε instead of V , we deduce from the existence of y ε in (3.4) that the family ρ Ax ε,ρ ρ∈]0,1[ is bounded and that

x ε,ρ → y ε as ρ ↓ 0. (3.15)
More precisely, it follows from (3.4) that there exists a point u ε ∈ Ay ε such that

-u ε ∈ By ε + εV y ε + e ε (3.16)
and, proceeding as in (2.15)-(2.20), we obtain

(∀ρ ∈ ]0, 1[) ρ Ax ε,ρ ≤ u ε . (3.17)
We shall now show that if one of conditions (i)-(iii) holds, then

(∃ η ∈ ]0, 1])(∃ τ ∈ ]0, +∞[) sup ε∈]0,η[ sup ρ∈]0,1[ ρ Ax ε,ρ 2 ≤ 4τ. ( 3.18)
(i) Suppose that x 0 ∈ int dom A. Then, by [START_REF] Zeidler | Nonlinear Functional Analysis and Its Applications II/B -Nonlinear Monotone Operators[END_REF]Proposition 32.33], A is locally bounded at x 0 and, therefore, there exists a bounded neighborhood X 1 of x 0 such that A(X 1 ) is bounded. On the other hand, it follows from (3.5) that there exists

η ∈ ]0, 1] such that (∀ε ∈ ]0, η[ ) y ε ∈ X 1 . Hence, (∀ε ∈ ]0, η[) u ε ∈ Ay ε ⊂ A(X 1
). We thus obtain the boundedness of (u ε ) ε∈]0,η[ and therefore (3.18) via (3.17).

(ii) Suppose that x 0 ∈ int dom B. As in (i), there exists a bounded neighborhood X 2 of x 0 such that B(X 2 ) is bounded. However, by (3.5), there exists η ∈ ]0, 1] such that (∀ε ∈ ]0, η[ ) y ε ∈ X 2 . On the other hand, (e ε ) ε∈]0,η[ lies in some bounded set U and, by Assumption 1.1(ii)(b), V (X 2 ) is bounded. Altogether, we derive from (3.16) that -(u ε ) ε∈]0,η[ lies in the bounded set B(X 2 ) + ε∈]0,η[ εV (X 2 ) + U . In view of (3.17), we obtain (3.18).

(iii) Suppose that (3.3) holds. We deduce from (3.3) and (3.8) that

ρ Ax ε,ρ | ρ Ax ε,ρ + εv ε,ρ + e ε ≤ (σ 1 -σ 2 )( ρ Ax ε,ρ ) -σ 2 (εv ε,ρ + e ε ) + σ 3 . (3.19)
Therefore, using Cauchy-Schwarz and setting ω = sup ε∈]0,1[ e ε , we obtain

ρ Ax ε,ρ 2 ≤ ρ Ax ε,ρ εv ε,ρ + e ε + |σ 1 -σ 2 | + σ 2 εv ε,ρ + e ε + σ 3 ≤ ρ Ax ε,ρ ε v ε,ρ + κ 1 + σ 2 ε v ε,ρ + κ 2 , (3.20)
where κ 1 = ω + |σ 1 -σ 2 | and κ 2 = σ 2 ω + σ 3 . We now consider two cases. (b) Suppose that V is β-Lipschitz continuous (hence single-valued) and γ-strongly monotone, for some β and γ in ]0, +∞[. Fix z ∈ dom A ∩ dom B, v ∈ Bz, and set w = V 0 and

r ρ = ρ Az. Then v ε,ρ ≤ v ε,ρ -w + w ≤ β x ε,ρ + w . (3.21) Moreover, r ρ + v ∈ ( ρ A + B)z and we derive from (3.7) that -(εv ε,ρ + e ε ) ∈ ( ρ A + B)x ε,ρ .
Hence, by monotonicity of ρ A + B,

r ρ + v + εv ε,ρ + e ε | x ε,ρ -z ≤ 0. (3.22)
Now let r 0 be the element of minimal norm in Az. Then r ρ ≤ r 0 [7, Theorem 3.5.9]. Hence, upon setting κ 5 = r 0 + v + ω and κ 6 = κ 5 z , we deduce from (3.22) and the Cauchy-Schwarz inequality that

ε x ε,ρ | v ε,ρ ≤ κ 5 x ε,ρ + ε z v ε,ρ + κ 6 . (3.23)
On the other hand, the γ-strong monotonicity of V yields

γ x ε,ρ 2 ≤ x ε,ρ | v ε,ρ -w ≤ x ε,ρ | v ε,ρ + w x ε,ρ . (3.24)
By first combining (3.23) and (3.24), and then using (3.21), we obtain

γ(ε x ε,ρ ) 2 ≤ ε 2 x ε,ρ | v ε,ρ + w (ε x ε,ρ ) ≤ κ 5 (ε x ε,ρ ) + z (ε v ε,ρ ) + w (ε x ε,ρ ) + κ 6 ≤ κ 5 (ε x ε,ρ ) + β z (ε x ε,ρ ) + z w + w (ε x ε,ρ ) + κ 6 . (3.25)
In other words, there exist constants κ 7 and κ 8 in [0, +∞[, which are independent from ε and ρ, such that

(ε x ε,ρ ) 2 ≤ κ 7 (ε x ε,ρ ) + κ 8 . (3.26)
Accordingly, sup ε∈]0,1[ sup ρ∈]0,1[ ε x ε,ρ < +∞ and, in view of (3.21), we have

sup ε∈]0,1[ sup ρ∈]0,1[ ε v ε,ρ < +∞. (3.27)
Therefore, it follows from (3.20) that there exist constants κ 9 and κ 10 in [0, +∞[, which are independent from ε and ρ, such that ρ Ax ε,ρ 2 ≤ κ 9 ρ Ax ε,ρ + κ 10 . This shows that (3.18) holds with η = 1.

To complete the proof, let us observe that (3.14) and (3.18) yield

(∀ε ∈ ]0, η[)(∀ρ ∈ ]0, 1[) c( x ε,φ(ε) -x ε,ρ ) ≤ τ ε (φ(ε) + ρ). (3.28)
In view of (3.15), if c is continuous, passing to the limit when ρ ↓ 0 in (3.28) yields (3.6). Thus, if φ(ε)/ε → 0 as ε ↓ 0, we obtain x ε,φ(ε) -y ε → 0 as ε ↓ 0 and, in view of (3.5), we conclude that x ε,φ(ε) → x 0 as ε ↓ 0.

Remark 3.2 (infeasible case) Suppose that Assumption 1.1 is satisfied, except that we now assume that zer(A + B) = ∅. In addition, suppose that φ(ε) + e ε → 0 as ε ↓ 0 in (3.2). Then

x ε,φ(ε) → +∞ as ε ↓ 0. (3.29)
Proof. Suppose that (3.29) is not true. Then there exists a decreasing sequence (ε n ) n∈N in ]0, 1[ that converges to 0 and such that (x εn,φ(εn) ) n∈N is bounded. In view of (3.2), there exists a sequence (v εn ) n∈N in H such that (∀n ∈ N) v εn ∈ V x εn,φ(εn) and -(ε n v εn + e εn ) ∈ ( φ(εn) A + B)x εn,φ(εn) .

(3.30)

Since Assumption 1.1(ii)(b) implies that (v εn ) n∈N is bounded, we have

ε n v εn + e εn → 0. (3.31)
On the other hand, we can extract a subsequence (x ε kn ,φ(ε kn ) ) n∈N such that By setting V = Id and e ε ≡ 0 in Theorem 3.1, we obtain our first corollary.

x ε kn ,φ(ε kn ) ⇀ x, (3.32
Corollary 3.4 Suppose that Assumption 1.1(i) is satisfied, let φ : ]0, 1[ → ]0, 1[ be such that φ(ε)/ε → 0 as ε ↓ 0, and set x 0 = P zer(A+B) (0). Then the inclusions

(∀ε ∈ ]0, 1[) 0 ∈ φ(ε) Ax ε,φ(ε) + Bx ε,φ(ε) + εx ε,φ(ε) (3.33)
define a unique family (x ε,φ(ε) ) ε∈]0,1[ , and x ε,φ(ε) → x 0 as ε ↓ 0 if one of the following holds:

(i) x 0 ∈ (int dom A) ∪ (int dom B).
(ii) A and B satisfy (3.3).

Remark 3.5

(i) In [START_REF] Moudafi | On the regularization of the sum of two maximal monotone operators[END_REF]Theorem 3], the convergence of (x ε,φ(ε) ) ε∈]0,1[ in Corollary 3.4 is announced without any additional hypothesis such as (i) or (ii). However, it is not clear to us how (3.18) can be satisfied without such an hypothesis.

(ii) Suppose that A = 0 in Corollary 3.4. Then we obtain the strong convergence of the approximating curve (x ε ) ε∈]0,1[ defined by

(∀ε ∈ ]0, 1[) 0 ∈ Bx ε + εx ε (3.34)
to the zero x 0 of B of minimum norm as ε ↓ 0. This classical result is due to Bruck [START_REF] Bruck | A strongly convergent iterative solution of 0 ∈ U (x) for a maximal monotone operator U in Hilbert space[END_REF]. When B = ∂f with f ∈ Γ 0 (H), we recover the standard Tikhonov regularization setting [START_REF] Tikhonov | Solution of Ill-Posed Problems[END_REF].

Our second corollary deals with a visco-penalization method for finding a specific minimizer of the sum of two convex functions. We require the following notion of an inexact minimizer. Definition 3.6 Let f : H → ]-∞, +∞] be a proper function and let e ∈ H. Then Argmin ≈e f =

x ∈ H | -e ∈ ∂f (x) .

Corollary 3.7 Let f and g be functions in Γ 0 (H) such that the set Z of minimizers of f + g is nonempty and such that the cone generated by dom f -dom g is a closed vector subspace. Let h ∈ Γ 0 (H) be a finite function that maps every bounded subset of H into a bounded set, and which is uniformly convex in the sense that there exists an increasing function c : [0, +∞[ → [0, +∞[ that vanishes only at 0 such that lim t→+∞ c(t)/t = +∞ and

(∀x ∈ H)(∀y ∈ H)(∀α ∈ ]0, 1[) h αx + (1 -α)y + α(1 -α)c( x -y ) ≤ αh(x) + (1 -α)h(y). (3.35)
Then h admits a unique minimizer x 0 over Z. Moreover, given φ : ]0, 1[ → ]0, 1[, the inexact minimization problems

(∀ε ∈ ]0, 1[) x ε,φ(ε) ∈ Argmin ≈eε φ(ε) f + g + εh , where e ε ∈ H, (3.36)
define a unique family (x ε,φ(ε) ) ε∈]0,1[ . Now suppose that c is continuous, that (φ(ε) + e ε )/ε → 0 as ε ↓ 0, and that one of the following holds:

(i) x 0 ∈ int dom f .
(ii) x 0 ∈ int dom g.

(iii) f and g satisfy

(∃ σ 1 ∈ R)(∃ σ 2 ∈ [0, +∞[)(∃ σ 3 ∈ [0, +∞[)(∀ρ ∈ ]0, 1[)(∀(x, u) ∈ gr ∂g) g(prox ρf x) ≤ g(x) + ρ σ 1 prox f * /ρ (x/ρ) + σ 2 u + ρσ 3 , (3.37)
and one of the following holds:

(a) dom g is bounded.

(b) h is strongly convex and differentiable with a Lipschitz continuous gradient.

Then x ε,φ(ε) → x 0 as ε ↓ 0.

Proof. Set A = ∂f , B = ∂g, and V = ∂h. Our hypotheses on f and g, [START_REF] Zȃlinescu | Convex Analysis in General Vector Spaces[END_REF]Theorem 3.1.11], and the sum rule for subdifferentials [START_REF] Attouch | Duality for the sum of convex functions in general Banach spaces[END_REF] (see also [25, Then it follows from (1.10), (1.9), and (3.37) that

(∀ρ ∈ ]0, 1[) ρ (∂f )x | u = x -prox ρf x | u /ρ ≥ g(x) -g(prox ρf x) /ρ ≥ -σ 1 prox f * /ρ (x/ρ) + σ 2 u -σ 3 = -σ 1 ( ρ (∂f )x) + σ 2 u -σ 3 , (3.38)
and we obtain (3.3). Finally, if dom g is bounded, so is dom ∂g ⊂ dom g, while the conditions in (iii)(b) imply that V = ∇h is Lipschitz continuous and strongly monotone. (ii) V : H → 2 H is a maximal monotone operator which is γ-strongly monotone for some γ ∈ ]0, +∞[, and which maps every bounded subset of H into a bounded set.

Theorem 4.2 Suppose that Assumption 4.1 is satisfied. Then there exists a unique point

x 0 ∈ zer( m i=1 A i ) such that 0 ∈ N zer( P m i=1 A i ) x 0 + V x 0 . (4.2)
Moreover, given φ : ]0, 1[ → ]0, 1[, the inclusions

(∀ε ∈ ]0, 1[) 0 ∈ m i=1 φ(ε) A i x ε,φ(ε) + εV x ε,φ(ε) + e ε , where e ε ∈ H, (4.3)
define a unique family (x ε,φ(ε) ) ε∈]0,1[ . Now suppose that (φ(ε) + e ε )/ε → 0 as ε ↓ 0 and that x 0 ∈ int m i=1 dom A i . Then x ε,φ(ε) → x 0 as ε ↓ 0.

Proof. We reformulate our m-operator problem as a 2-operator problem in a product space (similar setups are considered in [START_REF] Pierra | Decomposition through formalization in a product space[END_REF] and [START_REF] Spingarn | Partial inverse of a monotone operator[END_REF]). Let H be the Hilbert space obtained by endowing the Cartesian product H m with the scalar product

A : H → 2 H : x → m × i=1 A i x i , (4.4)
D = (x, . . . , x) ∈ H | x ∈ H , and
V : H → 2 H : x → 1 m m × i=1 V x i . (4.5)
It is easily checked that A is maximal monotone with Yosida approximations

(∀φ ∈ ]0, +∞[) φ A : x → φ A i x i ) 1≤i≤m . (4.6)
Moreover, since D is a closed vector subspace of H, (1.8) yields

(∀x ∈ H) N D x = D ⊥ = u ∈ H | m i=1 u i = 0 , if x ∈ D; ∅, otherwise. ( 4
(∀ε ∈ ]0, 1[) 0 ∈ φ(ε) Ax ε,φ(ε) + N D x ε,φ(ε) + εV x ε,φ(ε) + e ε ;
(4.9) (c) the strong convergence of (x ε,φ(ε) ) ε∈]0,1[ to x 0 as ε ↓ 0 if φ(ε)/ε → 0 as ε ↓ 0 and x 0 ∈ int dom A.

∈ N Z x + V x ⇔ (∃ v ∈ V x) -v ∈ N Z x ⇔ (∃ v ∈ V x) - m i=1 v i ∈ N Z x and m i=1 v i ∈ V x ⇔ 0 ∈ N Z x + V x. (4.11)
In view of (a), we therefore have x 0 = (x 0 , . . . , x 0 ), where x 0 is the unique solution to (4.2). Next, we observe that (4.9) and (4.7) imply that (x ε,φ(ε) ) ε∈]0,1[ lies in D. Hence, (∀ε ∈ ]0, 1[)(∃ x ε,φ(ε) ∈ H) x ε,φ(ε) = (x ε,φ(ε) , . . . , x ε,φ(ε) ). (4.12)

Let us show that the inclusions (4.9) in H are equivalent to the inclusions (4.3) in H. We derive from (4.9), (4.6), and (4.7) that, for every ε ∈ ]0, 1[, there exists (v ε,i ) 1≤i≤m ∈ (V x ε,φ(ε) ) m such that φ(ε)

A i x ε,φ(ε) + εm -1 v ε,i + m -1 e ε 1≤i≤m ∈ D ⊥ , i.e., m i=1 φ(ε)

A i x ε,φ(ε) + εm -1 m i=1 v ε,i + e ε = 0 or, equivalently, -m i=1 φ(ε)

A i x ε,φ(ε) -e ε = εm -1 m i=1 v ε,i ∈ εV x ε,φ(ε) since V x ε,φ(ε) is convex. This shows that (x ε,φ(ε) ) ε∈]0,1[ satisfies (4.3). Conversely, arguing along the same lines, we deduce that, if (x ε,φ(ε) ) ε∈]0,1[ satisfies (4.3), then (x ε,φ(ε) ) ε∈]0,1[ = (x ε,φ(ε) , . . . , x ε,φ(ε) ) ε∈]0,1[ satisfies (4.9). Therefore, we derive from (b) the existence and uniqueness of the curve (x ε,φ(ε) ) ε∈]0,1[ in (4.3). Finally, if φ(ε)/ε → 0 as ε ↓ 0 and x 0 ∈ int m i=1 dom A i , then x 0 ∈ int dom A and (c) yields x ε,φ(ε) -x 0 2 = m -1 |||x ε,φ(ε)x 0 ||| 2 → 0 as ε ↓ 0.

Corollary 4.3 Let (f i ) 1≤i≤m be functions in Γ 0 (H) such that the sets (dom f i ) 1≤i≤m are open and satisfy m i=1 dom f i = ∅, and such that the set Z of minimizers of m i=1 f i is nonempty. Let h ∈ Γ 0 (H) be a finite function that maps every bounded subset of H into a bounded set, and which is γ-strongly convex for some γ ∈ ]0, +∞[. Then h admits a unique minimizer x 0 over Z. Moreover, given φ : ]0, 1[ → ]0, 1[, the inexact minimization problems Proof. Arguing as in the proof of Corollary 3.7, we learn that this is a special case of Theorem 4.2 with (∀i ∈ {1, . . . , m}) A i = ∂f i and V = ∂h. Note that the hypotheses on (f i ) 1≤i≤m imply that x 0 ∈ m i=1 dom f i = m i=1 int dom f i = int m i=1 dom A i .

Remark 2 . 6

 26 In particular, if V = Id -h, where h ∈ H, then Assumption 1.1(ii) is satisfied and Theorem 2.5 reduces to the Hilbert space version of results found in [9,Section 2].

≤ κ 3 ρ

 3 (a) Suppose that dom B is bounded. Then (3.7) implies that sup ε∈]0,1[ sup ρ∈]0,1[ x ε,ρ < +∞ and Assumption 1.1(ii)(b) yields sup ε∈]0,1[ sup ρ∈]0,1[ v ε,ρ < +∞. Consequently, it follows from (3.20) that there exist constants κ 3 and κ 4 in [0, +∞[, which are independent from ε and ρ, such that ρ Ax ε,ρ 2Ax ε,ρ + κ 4 . Thus, (3.18) holds with η = 1.

Remark 3 . 3

 33 ) for some x ∈ H. Moreover, it follows from Assumption 1.1(i) and [3, Proposition 5.3] that the sequence ( φ(ε kn ) A + B) n∈N graph-converges to A + B. Consequently, (3.30), (3.31), (3.32), and [2, Proposition 3.59] force x ∈ zer(A + B), which contradicts our assumption. Condition (i) in Theorem 3.1 is satisfied in particular when dom A is open. For instance, if A = ∂f , where f ∈ Γ 0 (H), then int dom f ⊂ dom ∂f ⊂ dom f [25, Theorem 2.4.9] and therefore dom A is open if dom f is open. Regarding Condition (iii) in Theorem 3.1, the "angle property" (3.3) was first used in [10, Section 2.3] with σ 1 = σ 2 = 0.

Remark 3 . 8 1 (

 381 Consider the special case of Corollary 3.7 in which the following additional assumptions are made: f is the indicator function of a nonempty closed convex subset C of H, g is Lipschitz continuous on H, h = • 2 /2, e ε ≡ 0, and φ : ε → ε θ , where θ ∈ ]1, +∞[. Then(3.36) becomes(∀ε ∈ ]0, 1[) x ε = argmin y∈H 1 2ε θ d 2 C (y) + g(y) + ε 2 y 2 ,(3.39)and Corollary 3.7 asserts that the unique curve (x ε ) ε∈]0,1[ thus defined converges strongly to the minimizer of g over C of minimal norm as ε ↓ 0. This result was established in[START_REF] Attouch | A dynamical approach to convex minimization coupling approximation with the steepest descent method[END_REF] Example p. 531].4 The case of m operatorsIn this section we derive from the results of Section 3 a visco-penalization approximating curve for the problem find x ∈ zer i) (A i ) 1≤i≤m is a finite family of maximal monotone operators from H to 2 H such that zer m i=1 A i = ∅ and int m i=1 dom A i = ∅.

. 7 )

 7 Now let us set Z = zer A + N D and Z = zer( m i=1 A i ). Then it follows at once from (4.4) and (4.7) that Z = D ∩ Z m . (4.8) Consequently, Assumption 4.1(i) implies that Z = ∅ and that dom N D ∩ int dom A = D ∩ int dom A = ∅. In turn, it follows from [26, Theorem 32.I] that A + N D is maximal monotone. Thus, Assumption 1.1(i) is satisfied by A and N D . On the other hand, it follows from Assumption 4.1(ii) that V satisfies Assumption 1.1(ii) with c : t → γt 2 /m in (1.4). Now suppose that e ε /ε → 0 as ε ↓ 0 and set (∀ε ∈ ]0, 1[) e ε = m -1 (e ε , . . . , e ε ). Then |||e ε |||/ε = m -1/2 e ε /ε → 0 as ε ↓ 0 and we can apply Theorem 3.1 in H to the operators A, N D , and V to obtain: (a) the existence and uniqueness of a point x 0 ∈ Z such that 0 ∈ N Z x 0 + V x 0 ; (b) the existence and uniqueness of the curve (x ε,φ(ε) ) ε∈]0,1[ defined by

  Now let x = (x, . . . , x) be an arbitrary point in Z. Then (1.8) and (4.8) yieldN Z x = u ∈ H | (∀z ∈ D ∩ Z m ) zx | u ≤ 0 = u ∈ H (∀z ∈ Z) m i=1 z -x | u i ≤ 0 = u ∈ H m i=1 u i ∈ N Z x .(4.10)Note that, by maximal monotonicity of V , the set V x is convex [7, Proposition 3.5.6.1]. It therefore results from (4.10) and (4.5) that 0

(

  ∀ε ∈ ]0, 1[) x ε,φ(ε) ∈ Argmin ≈eε m i=1 φ(ε) f i + εh , where e ε ∈ H,(4.13)define a unique family (x ε,φ(ε) ) ε∈]0,1[ . Now suppose that (φ(ε) + e ε )/ε → 0 as ε ↓ 0. Then x ε,φ(ε) → x 0 as ε ↓ 0.

  Let (M ε ) ε∈]0,1[ be a family of maximal monotone operators from H to 2 H and let (x ε ) ε∈]0,1[ be a family in H. Then (x ε ) ε∈]0,1[ is A-focused with respect to (M ε ) ε∈]0,1[ if, for every x ∈ H and every sequence

	2)
	and, since [26, Theorem 32.I] implies that M + V is maximal monotone, the conclusion follows from
	[14, Lemma 3.8(ii)].
	Definition 2.3 [14, Definition 3.1]

  since the sequence ( ρn M 1 z ρn ) n∈N is bounded, there exist a point u ∈ H and a subsequence (ρ kn ) n∈N of (ρ n ) n∈N such that ρ kn M 1 z ρ kn ⇀ u. Since z ρ kn → z 0 , using the fact that ( ρ kn M 1 ) n∈N graph-converges to M 1 (see[2, p. 360]) and applying [2, Proposition 3.59], we obtain

u ∈ M 1 z 0 .

(2.27) Furthermore, since (z ρn ) n∈N is bounded, so is (v ρn ) n∈N in the light of Assumption 1.1(ii)(b). Therefore, passing to a further subsequence if necessary, we assume that v ρ kn ⇀ v for some v ∈ H. Since V is maximal monotone, gr V is sequentially closed in H strong × H weak [7, Proposition 3.5.6.2] and therefore, recalling that z ρ kn → z 0 , we get

  Theorem 2.8.7]) imply that Z = zer(A + B), and that A and B satisfy Assumption 1.1(i). Moreover, we infer from [25, Theorem 3.5.10] and[START_REF] Zȃlinescu | Convex Analysis in General Vector Spaces[END_REF] Theorem 2.4.13] that V satisfies Assumption 1.1(ii). Next, it follows from [25, Theorem 2.9.1] that a point x 0 ∈ H minimizes h over Z if and only if 0 ∈ N Z x 0 + ∂h(x 0 ), i.e., if and only if (3.1) holds. Since int dom f = int dom ∂f and int dom g = int dom ∂g [25, Theorem 2.4.9], this is clearly the case for (i) and (ii). Next, let us show that (3.37) ⇒ (3.3). To this end, fix (x, u) ∈ gr ∂g.

	Furthermore, it follows from Definition 3.6, [25, Theorem 2.8.7], and (1.10) that (3.36) reduces to
	(3.2). To apply Theorem 3.1, it remains to check that items (i)-(iii) imply their counterpart in
	Theorem 3.1.

  • | • : (x, y) → m i=1 x i | y i , where x = (x i ) 1≤i≤m and y = (y i ) 1≤i≤m denote generic elements in H. We shall denote by |||•||| the associated norm on H. Now set

Acknowledgments

The authors wish to express their gratitude to the anonymous referee for his valuable remarks.


Jean-Marc Champarnaud

Georges Hansel

Dominique Perrin

Unavoidable sets of constant length

A set of words X is called unavoidable on a given alphabet A if every infinite word on A has a factor in X. For k, q ≥ 1, let c(k, q) be the number of conjugacy classes of words of length k on q letters. An unavoidable set of words of length k on q symbols has at least c(k, q) elements. We show that for any k, q ≥ 1 there exists an unavoidable set of words of length k on q symbols having c(k, q) elements.

Introduction

A word t is said to avoid a word p if p is not a factor of t, i.e. if the pattern p does not appear in the text t. For example the word abracadabra avoids baba. The set of all words avoiding a given set X of words has been of interest in several contexts including the notion of a system of finite type in symbolic dynamics (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF] for example) or in enumerative combinatorics (see [START_REF] Stanley | Enumerative combinatorics[END_REF] for example).

A set X of words on the alphabet A is called unavoidable on A if any long enough word on the alphabet A has a factor in X. The notion of an unavoidable set has been the subject of several results since its introduction by M.P. Schützenberger in [START_REF] Schützenberger | On the synchronizing properties of certain prefix codes[END_REF]. In particular L. Rosaz has shown in [START_REF] Rosaz | Inventories of unavoidable languages and the wordextension conjecture[END_REF] that there is a finite number of types of unavoidable sets having a given number of elements.

It is easy to see that an unavoidable set of words of constant length k on some alphabet A has to contain at least one word of each conjugacy class of words of length k on this alphabet. Thus the minimal number m(k, q) of elements of an unavoidable set of words of length k on q letters is greater than or equal to the number c(k, q) of conjugacy classes of words of length k on q letters. It has been shown by Schützenberger that it is asymptotically true that m(k, q) ∼ c(k, q) ( actually both numbers are asymptotically equivalent to q k /k). Later on, answering a conjecture of S. W. Golomb, J. Mykkeltveit proved that actually, m(k, q) = c(k, q) [START_REF] Mykkeltveit | A proof of Golomb's conjecture for the de Bruijn graph[END_REF]. His proof uses trigonometric sums (see the last section).

Our main result here is a new proof of this equality, namely that for every k ≥ 1 and q ≥ 1, there exists an unavoidable set with c(k, q) elements (Theorem 1). We actually obtained this result without being aware of J. Mykkelveit's work (see below the script of the story).

It may be convenient for the reader to formulate the statement in terms of graphs. A feedback vertex set in a directed graph G is a set F of vertices containing at least one vertex from every cycle in G. Consider, for k ≥ 1, the De Bruijn graph B k of order k on the alphabet A whose vertices are the words of length k on A and the edges are the pairs (au, ub) for all a, b ∈ A and u ∈ A k-1 . It is easy to see that a set of words of length k is unavoidable if the corresponding set of vertices is a feedback vertex set of the graph B k . Thus, the problem of determining an unavoidable set of words of length k of minimal size is the same as determining the minimal size of a feedback vertex set in B k . The problem is, for general directed graphs, known to be NP-complete (see [START_REF] Garey | A guide to the theory of NP-completeness[END_REF] for example).

The genesis of our work has a rich background and it has benefited from the help of several colleagues that we would like to thank. First of all, it was Christopher Saker who pointed out to the third author a mistake in [START_REF] Lothaire | Combinatorics on words[END_REF] where it is asserted erroneously that m(2, 5) = 9 although c(2, 5) = 8 (Exercise 5.1.4 page 99). He was able to verify that m(k, n) = c(k, n) for k = 2 and n ≤ 7. It was conjectured then by P. Higgins and C. Saker (see [START_REF] Saker | Unavoidable sets of words of uniform length[END_REF]) that one has actually m(k, q) = c(k, q). In a joint work with Guoniu Han [START_REF] Han | Ensembles inévitables[END_REF], the third author was able to reach n = 9 and to discuss some generalizations on systems of finite type (see at the end of this paper). The first two authors found a first proof of the main result (see [START_REF] Champarnaud | Ensembles inévitables et classes de conjugaison[END_REF] and the last section) and the final form given here is the result of this extended cooperation. We learnt after completing a first version that the conjecture had already been proved by J. Mykkelveit [START_REF] Mykkeltveit | A proof of Golomb's conjecture for the de Bruijn graph[END_REF]. We would like to thank David Penman and Christopher Saker again for pointing out this reference. The authors wish also to express their thanks to Donald Knuth for reading the paper and suggesting several improvements.

We begin this paper by some preliminaries on words (see [START_REF] Lothaire | Combinatorics on words[END_REF] for a more general introduction). We state in particular elementary properties of Lyndon words used in the sequel. The following section contains the proof of the main result.

Preliminaries

Let A be a finite set with a linear order <. A word on the alphabet A is a finite sequence of elements of A, including the empty sequence called the empty word. We denote by A * the set of all words on the alphabet A. The length of a word w ∈ A * is denoted by |w|. A word p is said to be a prefix of a word w if there exists a word u such that w = pu. The prefix p is proper if p = w. The definition of a suffix is symmetrical. A word x is a factor of a word w if there exist words p, q such that w = pxq.

We shall also use infinite words. A two-sided infinite word on A is a sequence (a n ) n∈Z . A word x is a factor of a two-sided infinite word w = (a n ) n∈Z if there exists an index n ∈ Z such that x = a n a n+1 • • • a n+k-1 where k = |x|. A twosided infinite word (a n ) n∈Z is said to be periodic if there is an integer p ≥ 1 such that a n+p = a n for all n ∈ Z. Thus a two-sided infinite word is periodic if it is made of the repetition of a finite word u. We denote by u ζ the set of periodic words of this form.

The same notions hold for one-sided infinite words which are sequences (a n ) n∈N . For x, y ∈ A * with y non-empty, we denote by xy ω the infinite word xyyy • • • .

A border of a word w is a non-empty word which is both a prefix and a suffix of w. A word is called unbordered if its only border is itself.

The set A * of all words on the alphabet A is linearly ordered by the alphabetic order induced by the order < on A. By definition, one has x < y either if x is a proper prefix of y or if x = uav, y = ubw with u, v, w ∈ A * , a, b ∈ A and a < b. A basic property of the alphabetic order is that if x < y and if x is not a prefix of y, then for all words u, v, xu < yv.

Two words x, y are conjugate if there exist words u, v such that x = uv and y = vu. Conjugacy is an equivalence class in A * . A word is primitive if it is not a proper power, i.e. if it is not of the form r n for r ∈ A * and n > 1. The number p(k, q) of conjugacy classes of primitive words of length k on q symbols is given by the well-known Witt's formula.

p(k, q) = 1 k d|k µ(k/d)q d
where µ is the Möbius function. The number c(k, q) is given by

c(k, q) = 1 k d|k ϕ(k/d)q d
where ϕ is the Euler function. The values of p(k, 2) and c(k, 2) for k ≤ 13 are tabulated below. A word is said to be minimal if it the least one in its conjugacy class. We denote by M the set of minimal words and by P the set of prefixes of minimal words. A Lyndon word is a word which is both primitive and minimal. We denote by L the set of Lyndon words.

The following propositions give elementary and well-known properties of Lyndon words used in the sequel. We include a proof for the sake of completeness.

The first one gives equivalent definitions of Lyndon words. It shows in particular that Lyndon words are unbordered.

Proposition 1

The following conditions are equivalent for any non-empty word w.

(i) w is a Lyndon word.

(ii) for any non-empty words u, v such that w = uv, we have w < vu.

(iii) w is strictly less than any of its proper non-empty suffixes.

Proof. If u, v are non-empty and if uv is primitive, then uv = vu as it is well-known. Thus (i)⇒ (ii). (ii)⇒ (iii). Let w = vq with v, q both non-empty. It is not possible that q be a prefix of w. Indeed, otherwise, we have w = qu for some non-empty word u. Since vq = qu < uq, we obtain v < u and thus qv < qu = vq, a contradiction. Since q is not a prefix of w, it follows from w < qv that w < q. (iii)⇒ (i). It is clear that w is primitive. Next, if w = uv, with u, v non-empty, if follows from w < v that w < vu. Thus w is a Lyndon word.

The following proposition is clear since every non-empty word is in a unique way a power of a primitive word.

Proposition 2 A word is minimal if and only if it is a power of a Lyndon word. This Lyndon word is uniquely determined.

The following proposition is also straightforward to prove. Its converse is actually also true.

Proposition 3 Let w be a prefix of a minimal word. Then any suffix of w either is a prefix of w or is greater than w. Equivalently, any prefix of w is less than or equal to the suffix of the same length of w.

A word w ∈ A * is said to be a sesquipower of a word x if it is of the form w = x n p where n ≥ 1 and p is a proper prefix of x. We will be especially interested in sesquipowers of Lyndon words. For example, if a < b, the word w = aabbaabbaa is a sesquipower of the Lyndon word l = aabb.

The following property is linked to a method of generation of Lyndon words due independently to Fredericksen and Maiorana [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF] and to Duval [START_REF] Duval | Factorizing words over an ordered alphabet[END_REF]. It is indeed relatively easy to generate the elements of P in alphabetic order and this gives a method to generate also either the elements of M or those of L. This generation problem has been considered in several contexts (see [START_REF] Reutenauer | Free Lie algebras[END_REF], [START_REF] Moreno | A note on the theorem of Fredericksen and Maiorana[END_REF] or [START_REF] Knuth | The Art of Computer Programming[END_REF] in particular).

Proposition 4

The following conditions are equivalent for any word w ∈ A * .

(i) w is a non-empty prefix of a minimal word.

(ii) w is a sesquipower of a Lyndon word.

Proof. It is obvious that (ii) implies (i). Let us show the converse. By hypothesis there is a Lyndon word s such that w is a prefix of s n . If |w| ≥ |s|, then w is clearly a sesquipower of s. It is therefore enough to consider the case where w is a non-empty prefix of s.

We use an induction on the length of w. If |w| = 1, then w is a Lyndon word and the property is true. Let us then suppose that |w| > 1 and let w = va with a ∈ A. By the induction hypothesis, we have a factorization v = l n p where l is a Lyndon word, n ≥ 1 and p is a proper prefix of l.

Let l = pbx with b ∈ A and x ∈ A * . We are going to show that either a = b and thus w = va is a sequipower of l or w itself is a Lyndon word.

Indeed, since w ∈ P , we have by Proposition 3, pb ≤ pa and thus b ≤ a. We therefore have to prove that if b < a, then w is a Lyndon word. For this, let s = ta be a proper suffix of w = l n pa. The word u = tb is a proper suffix of z = l n pb. Since z ∈ P , the word u is larger than or equal to the prefix of the same length of z and thus also of w. But since s > u, the word s is larger than w and thus w is a Lyndon word.

It follows from the proof above that P is actually equal to the set of prefixes of Lyndon words.

A division of a word w ∈ P is a pair (l n , u) such that w = l n u where l ∈ L, n ≥ 1 and u ∈ A * with |u| < |l|.

By Proposition 4 each word in P admits at least one division. We say that a Lyndon word l ∈ L meets the word w if there is a division of w of the form (l n , u). It is clear that for any l ∈ L there is at most one such division of w.

The main division of w ∈ P is the division (l n , u) where l is the shortest Lyndon word which meets w. The word l n is the principal part of w, denoted by p(w), and u is the rest, denoted by r(w).

For example, with a < b, the word aabaabbba admits two divisions which are (aabaabbb, a) and (aabaabb, ba). The first one corresponds to its decomposition as a sesquipower of a Lyndon word. The second one is its main division.

Unavoidable sets

Let A be a finite alphabet. An unavoidable set on A is a set I ⊂ A * of words on the alphabet A such that any two-sided infinite word (a n ) n∈Z on the alphabet A admits at least one factor in I. It is of course equivalent to ask that any one-sided infinite word has a factor in I or also, since the alphabet is finite, that the set of words that avoids I is finite (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] for an exposition of the properties of unavoidable sets). Example Let A = {a, b}. The set U = {a, b 10 } is unavoidable since any word of length 10 either has a letter equal to a or is the word b 10 . On the contrary, the set V = {aa, b 10 } is avoidable. Indeed, the infinite word (ab) ω = ababababab . . . has no factor in V .

In the sequel, we will be interested in unavoidable sets made of words having all the same length k. The following proposition is easy to prove. Proposition 5 Let A be a finite alphabet and let I be an unavoidable set of words of length k on A. The cardinality of I is at least equal to the number of conjugacy classes of words of length k on the alphabet A.

Proof. Let u ∈ A * be a word of length k. The factors of length k of the word u ω are the elements of the conjugacy class of u. Thus I must contain at least one element of this class.

Let k ≥ 1 be an integer and let M k be the set of minimal words of length k. For each m ∈ M k , let p(m) be its principal part and r(m) its rest. Let I k be the set

I k = {r(m)p(m)|m ∈ M k }
We remark that any minimal word which is not primitive appears in I k .

Example.

Main result

We are going to prove the following result which shows that the lower bound c(k, q) on the size of unavoidable sets of words of length k on q symbols is reached for all k, q ≥ 1. This has, as said in the Introduction, already been obtained by J. Mykkelveit [START_REF] Mykkeltveit | A proof of Golomb's conjecture for the de Bruijn graph[END_REF].

Theorem 1 For all k, q ≥ 1, there exists an unavoidable set formed of c(k, q) words of length k on q symbols. The theorem will be a consequence of the following one, giving a construction of the minimal unavoidable sets.

Theorem 2 Let A be a finite alphabet and let k ≥ 1. Let M k be the set of words on the alphabet A of length k and which are minimal in their conjugacy class. For every word m ∈ M k , let p(m) be the principal part of m and let r(m) be its rest. Then the set

I k = {r(m)p(m)|m ∈ M k } is an unavoidable set.
To prove Theorem 2, we need some preliminary results. The first one is a simple equivalent definition of finite unavoidable sets.

Proposition 6 Let I ⊂ A * be a finite set of words. The following conditions are equivalent.

(i) The set I is unavoidable.

(ii) Each two-sided infinite periodic word has at least one factor in I.

Proof. It is enough to show that (ii) ⇒ (i). Let (a n ) n∈Z be a two-sided infinite sequence of letters. Let u ∈ A * be a word longer than any word in I and having an infinite number of occurrences in the sequence (a n ) n∈Z . This sequence has at least one factor of the form uvu. By the hypothesis, the infinite periodic word . . . uvuvuvuv . . . has a factor w ∈ I. The word w is a factor of at least one of the words uv and vu. It is also a factor of the sequence (a n ) n∈Z and thus I is unavoidable.

Proposition 7 Let λ and l be two Lyndon words, with λ a prefix of l. Let s ∈ A * be a proper suffix of l, with |s| < |λ|. Then for all n > 0, the word w = λ n s is a Lyndon word.

Proof. Let t be a proper suffix of w. Three cases may arise. 1. One has |t| ≤ |s|. Then t is a proper suffix of the Lyndon word l and thus t > l ≥ λ and since |t| < |λ|, we have t > λ n s = w. 2. One has |t| > |s| and the word t factorizes as t = λ i s, with 0 ≤ i < n. Since s is a proper suffix of l, we have s > l ≥ λ. Consequently t = λ i s > λ i+1 and since |s| < |λ|, we have t > λ n s = w. 3. One has |t| > |s| and the word t factorizes as t = s ′ t ′ , where s ′ is a proper suffix of λ. Since λ ∈ L, one has s ′ > λ, and consequently t = s ′ t ′ > λ n s = w.

In all cases t > w and thus w is a Lyndon word.

Proposition 8 Let w be a prefix of a minimal word and let (λ n , u) be its main division. Let u ′ ∈ A * be a word of the same length as u and such that the word w ′ = λ n u ′ is also a prefix of a minimal word. Then the main division of w ′ is the pair (λ n , u ′ ).

Proof. Let (µ i , v) be the main division of w ′ . We have w ′ = µ i v with |v| < |µ|. Since (λ n , u ′ ) is a division of w ′ , the word µ is a prefix of λ. We are going to show by contradiction that µ cannot be a proper prefix of λ.

Suppose that µ is a proper prefix of λ. Since the factorization of a minimal word as a power of a Lyndon word is unique, we cannot have the equality

µ i = λ n . Suppose first that |µ i | < |λ n |. Since w ′ = µ i v = λ n u ′ ,
the word µ i is a proper prefix of the word λ n . Thus there exists a non-empty word x ∈ A * such that µ i x = λ n et xu ′ = v. We thus have

w = λ n u = µ i xu Since |xu| = |xu ′ | = |v| < |µ|, the pair (µ i , xu
) is a division of w, which is a contradiction since µ is a proper prefix of λ and that (λ n , u) is the main division of w.

Let us now suppose that

|µ i | > |λ n |. Since w ′ = µ i v = λ n u ′ ,
the word λ n is a proper prefix of the word µ i . Since µ is a proper prefix of λ, there exists an integer j > 0 and a prefix µ ′ of µ such that λ = µ j µ ′ . Since λ is a primitive word, µ ′ is non-empty. As a consequence, λ admits µ ′ both as a non-empty prefix and and suffix, which is contradictory since λ is a Lyndon word.

The final property needed to prove Theorem 2 is the following.

Proposition 9 Let l be a Lyndon word. Let n ∈ N be the smallest integer such that |l n | > k. Then the word l n+1 has a factor in I k .

Proof. Let w be the prefix of length k of l n . Let (λ i , u) be the main division of w. If u is the empty word, then, by construction, w ∈ I k and the proposition is true. Suppose that u is not empty. The word λ is a prefix of l since either |w| < |l| or w admits a division of the form (l j , l ′ ). Let s be the suffix of l having the same length as u. By Proposition 7, the word λ i s is a Lyndon word. Thus, by Proposition 8, the main division of λ i s is the pair (λ i , s). Consequently, the word sλ i belongs to I k . But this word is a factor of l n+1 . Thus l n+1 has a factor in I k .

We are now able to prove Theorem 2. By Proposition 6, it is enough to show that every periodic two-sided infinite word of the form . . . uuuuu . . . has at least one factor in I k . We may suppose without loss of generality that u is a Lyndon word. Let n be the least integer such that n|u| > k. Then, by Proposition 9, the word u n+1 has a factor in I k . Thus I k is unavoidable.

Conclusion

The proof of J. Mykkeltveit in [START_REF] Mykkeltveit | A proof of Golomb's conjecture for the de Bruijn graph[END_REF] is based on the following principle, presented in the case of a binary alphabet. Let us associate to a word w = a 0 a 1 • • • a n-1 on the alphabet {0, 1} the sum s(w) = a j ω j where ω = e 2iπ/n . We denote by Is(w) the imaginary part of s(w). It can be shown that for each conjugacy class of words, only two cases occur:

(i) either all words w are such that Is(w) = 0 (and then, for n > 2 one has actually s(w) = 0 for each of them) (ii) or there is, in clockwise order, one block of words w such that Is(w) > 0 followed by one block of words w such that Is(w) < 0 separated by at most two words w such that Is(w) = 0.

Consider the set S n of words of length n formed of (i) a representative of each conjugacy class of words w of length n such that Is(w) = 0 for all the conjugates.

(ii) the words w = a 0 a 1 • • • a n-1 of length n such that Is(w) > 0 for the first time clockwise.

It is shown in [START_REF] Mykkeltveit | A proof of Golomb's conjecture for the de Bruijn graph[END_REF] that this set is unavoidable for all n > 2. The comparison with our definition of a minimal unavoidable set shows that the definitions have nothing in common. Moreover, the sets obtained are indeed different. The sets defined by J. Mykkeltveit have a slight advantage on ours in the sense that the maximal length of words avoiding the set is less. For example, for n = 20, there are 256 words of length 2579 that avoid I n , but none of length 563 that avoid all of S n (and there is a unique way to avoid S n with length 562). This computation has been performed using D. Knuth's program UNAVOIDABLE2 (see http://www-cs-faculty.stanford.edu/~knuth/programs.html). Our proof has the advantage of using only elementary concepts and in particular no real or complex arithmetic. The first proof of Theorem 1 obtained by the first two authors (see the Introduction) is a construction working by stages. To explain these stages, let us consider to simplify the notation the case of a binary alphabet A = {a, b}. Given a set X of two-sided infinite words, we say that a set Y of words is unavoidable in X if every word of X has a factor in Y .

For n ≥ 1, let X n be the set of two-sided infinite words on A which avoid a n . Let c n (k, q) be the number of conjugacy classes of words x of length k on q symbols such that the words of the form

x ζ = • • • xxx • • • are in X n .
It is thus also equal to the number of orbits of period k in X n . The table below gives the values of c n (k, 2) for 1 ≤ n ≤ 10 and 1 ≤ k ≤ 10. The idea of the step by step construction of a minimal unavoidable set of words of length k is to construct a sequence Y 1 ⊂ Y 2 ⊂ . . . ⊂ Y k of sets of words of length k such that for 1 ≤ n ≤ k, the set Y n is unavoidable in X n with c n (k, q) elements. This can be stated as the following result.

Theorem 3 For each q ≥ 1, and k ≥ n ≥ 1, there exists a set of c n (k, q) words of length k on q symbols which is unavoidable in X n .

The proof consists in showing that the c n (k, q) last elements of I n form a set unavoidable in X n .

It is interesting to remark that not all minimal unavoidable sets are build in this way. Indeed, there are sets which are minimal unavoidable in X n+1 which do not contain a minimal unavoidable set in X n .

For example, let Y 1 = {bbb}, Y 2 = {bbb, bab}, Y 3 = {bbb, bab, aab}. Then each Y n for 1 ≤ n ≤ 3 is unavoidable in X n of size c n (3, 2) and I 3 = Y 3 ∪ {aaa}. In particular, the set I 3 contains an unavoidable set in X 2 with 2 elements, namely Y 2 . However, the set J 3 = {aaa, aba, bba, bbb} obtained from I 3 by exchanging a and b does not contain a two element set unavoidable in X 2 .

A set of the form X n is a particular case of what is called a system of finite type. This is, by definition the set of all two-sided infinite words avoiding a given finite set of words (see [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]). We do not know in general in which systems of finite type it is true that for each k there exists an unavoidable set having no more elements than the number of orbits of period k.

Table 1 .

 1 Table 1 gives the sets M 7 and I 7 . The object of what follows is to show that I k is an unavoidable set. By Proposition 5, the number of elements of I k is the minimal possible number of elements of an unavoidable set of words of length k. The sets M 7 and I 7

	aaaaaaa	aaaaaaa
	aaaaaab	aaaaaab
	aaaaabb	baaaaab
	aaaabab	abaaaab
	aaaabbb	bbaaaab
	aaabaab	aabaaab
	aaababb	abbaaab
	aaabbab	babaaab
	aaabbbb	bbbaaab
	aabaabb	baabaab
	aababab	abaabab
	aababbb	bbaabab
	aabbabb	abbaabb
	aabbbab	babaabb
	aabbbbb	bbbaabb
	abababb	bababab
	ababbbb	bbababb
	abbabbb	babbabb
	abbbbbb	bbbabbb
	bbbbbbb	bbbbbbb


Maxime Crochemore

Christophe Hancart
email: hancart@dir.univ-rouen.fr

Thierry Lecroq
email: lecroq@dir.univ-rouen.fr

A Unifying Look at the Apostolico-Giancarlo String-Matching Algorithm

Keywords:

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function ("matching shift") of the well-known Boyer-Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer-Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of ¢¡ ¤£ ¢¥ character comparisons (where ¥ is the length of the text).

Introduction

The string matching problem consists in finding one or more usually all the occurrences of a pattern ¦ of length § in a text ¨of length © . It can occur in information retrieval, bibliographic search and most recently it has some applications in molecular biology. It has been extensively studied and numerous techniques and algorithms have been de-signed to solve this problem (see [START_REF] Crochemore | Text algorithms[END_REF], [START_REF] Stephen | String searching algorithms[END_REF] and [START_REF] Charras | Exact string matching algorithms[END_REF]). We are interested here in the problem where the pattern is given first and can then be searched in various texts. Thus a preprocessing phase is allowed on the pattern.

Basically a string-matching algorithm uses a window to scan the text. The size of this window is equal to the length of the pattern. It first aligns the left ends of the window and the text. Then it checks if the pattern occurs in the window (this specific work is called an attempt) and shifts the window to the right. It repeats the same procedure again until the right end of the window goes beyond the right end of the text. One of the most famous string matching algorithm was given in 1977 by Boyer and Moore [START_REF] Boyer | A fast string searching algorithm[END_REF]. Its main feature is that at each attempt it scans the characters of the pattern from right to left which enables it to "jump" over some portions of the text and therefore to save some comparisons. Its main drawback is that after a shift, it forgets all the characters it has previously matched. This make the complexity analysis of the Boyer-Moore algorithm very difficult. Cole [START_REF] Cole | Tight bounds on the complexity of the Boyer-Moore string matching algorithm[END_REF] proved, a long time after the design of the algorithm, the tight bound of © ¢¡ © ¤£ § comparisons to locate a non-periodic pattern. When search- ing for all the occurrences of the pattern in the text, the Boyer-Moore algorithm has a quadratic worst-case time complexity. The exact complexity is ¥ §¦ © © § © where is the number of occurrences of the pattern in the text (see [START_REF] Knuth | Fast pattern matching in strings[END_REF]). A major difficulty when one wants to implement the Boyer-Moore algorithm is to understand the computation of the "matching shift" which is one of the two shift functions usually used by the algorithm. We give a new method to compute this function. This method uses values needed by the Apostolico-Giancarlo algorithm. To remedy the oblivious feature of the Boyer-Moore algorithm, Apostolico and Giancarlo [START_REF] Apostolico | The Boyer-Moore-Galil string searching strategies revisited[END_REF] gave in 1986 an algorithm which remembers at each position of the text previously aligned with the right end of the pattern, the length of the longest suffix of the pattern ending at this position. This technique leads to an upper bound of © ¡ § text character comparisons. Actually remembering only the last suffix of the pattern matched in the text also leads to an upper bound of © comparisons. The Turbo-BM algorithm [5] applies this strategy and reaches this bound. In analyzing more in detail the Apostolico-Giancarlo algorithm, we are able to give an upper bound of © text characters comparisons. We show that this bound is tight by exhibiting a family of patterns and texts reaching this bound. Moreover we reformulate the algorithm in order to save other kinds of comparisons and to improve the length of the shifts.

This paper is organized as follows: Section 2 recalls briefly the Boyer-Moore algorithm; in Section 3 we give an history of the Boyer-Moore algorithm and its variants; in Section 4 we give a method to compute the matching shift function of the Boyer-Moore algorithm and in Section 5 we describe a new version of the Apostolico-Giancarlo algorithm; a new tight bound of ! #" © text character comparisons is proved in the same section. Throughout this paper the pattern is denoted by a word ¦ of length § , ¦ %$ ¦ '& #( ) 0 ¤ § 1¡ 2 43 . The text is denoted by a word ¨of length © , 5$ 6& #( ) 0 ¤© ©¡ 73 . Both ¦ and ¨are built over a finite alphabet 8 of size 9 .

Boyer-Moore string-matching algorithm

The Boyer-Moore algorithm is considered as the most efficient string matching algorithm in usual applications. A simplified version of it or the entire algorithm is often implemented in a text editor for the "search" and "substitute" commands.

The algorithm scans the characters of the pattern from right to left beginning with the rightmost symbol. In case of a mismatch (or a complete match of the whole pattern) it uses two precomputed functions to shift the pattern to the right. These two shift functions are called the matching shift and the occurrence shift.

Assume that a suffix £ of ¦ has been matched and a mismatch occurs between the character ¦ & ¥¤ 3 $ of the pattern and the character 6& ¥¤ ¤ §¦ 3 $

¡

of the text during an attempt where ¦ is aligned with

)& ¦ ! ¦ ¨ § ¡ 43 . Then, ¦ & ¥¤ ¨ ! ¤ § 1¡ 43 '$ 6& ¥¤ ¨¦ ! ¦ ¨ § ¡ 73 $ £ and $ ¦ & ¥¤ 3 ¢ $ 6& ¥¤ ¨¦ 3 $ ¡
(see Fig. 1). The matching shift consists in aligning the substring

£ $ ¦ & ¤ ) § 1¡ 73 $ )& ¤ ¦ ¨ ¦ ¨ § ¡ 2 43
with one of its reoccurrences in ¦ . Informally, let us distinguish three matching shift cases on the grounds of the restrictions imposed on the character © preceding this reoccurrence: weak matching shift : there is no condition on the character © preceding £ , it is then possible that © $ (see Fig. 2). strong matching shift : the character © must be different from the character (see Fig. 3).

best matching shift : the character © must be equal to ¡ (see Fig. 4).

It is not too difficult to see that the following inequality holds:

weak matching shift strong matching shift best matching shift where the absolute value of a shift denotes the length of the shift. If there exists no other occurrence of £ , the matching shift consists in aligning the longest suffix of )& ¥¤ ¦ ¨ ! ¦ ¨ § ¡ 73 with a matching prefix of ¦ (see Fig. 5). The occurrence shift consists in aligning the text character 6& ¥¤ ¨¦ 3 with its rightmost occurrence in ¦ & #( 6 ¤ § 2¡ % 3 (see Fig. 6). If 6& ¥¤ ¦ 3 does not appear in the pattern ¦ , no occurrence of ¦ in ¨can include )& ¥¤ ¨¦ 3 , and the left end of the pattern is aligned with the character immediately after )& ¥¤ ¨¦ 3 , namely )& ¤ ¨¦ ¨ 43 (see Fig. 7).

The three shift functions will be denoted by the variables wMatch, sMatch, and bMatch. We will define these three variables with the aid of the condition functions Cs, Cos and Cob:

For

( ¤ § 1¡ , ¡ §
and £¢ 8 , let us define the following conditions.

¤ The condition of suffix Cs is defined for a position ¤ and a shift ¡ :

Cs¦ ¤ ¦¥ ¡ $ § ¨© ( ¡ ¤ and ¦ '& ¥¤ ¡ ¡ ¨ § ¡ ¡ ¡ 73 is a suffix of ¦ or ¡ ¤ and ¦ & #( § 1¡ ¡ ¡ 43 is a suffix of ¦ ¤
The strong condition of occurrence Cos is defined for a position ¤ and a shift ¡ :

Cos¦ ¤ ¦¥ ¡ $ ( ¡ ¤ and ¦ & ¥¤ ¡ ¡ 3 ¢ $ ¦ & ¥¤ 3 or ¡ ¤ ¤
The best condition of occurrence Cob is defined for a position ¤ , a character and a shift ¡ : ¤ the weak matching shift is defined by:

Cob¦ ¤ ¦¥ ¥ ¡ $ ( ¡ ¤ and ¦ & ¥¤ ¡ ¡ 3 $ or ¡ ¤ BOYER-MOORE ¦ ¦ ¥ § ¥ ¨¥ © ¤ 1 ¦ ¡ ( 2 while ¦ © §¡ § 3 do ¤ ¡ § ¡ 4 while ¤ £¢ ( and ¦ & ¤ 3 $ )& ¥¤ ¦ 3 5 do ¤ ¡ ¤ ¡ 6 if ¤ ( 7 then REPORT ¦ ¦ ! 8 ¦ ¡ ¦ ¨MATCH ¦ ( ¥ 4( ! 9 else ¦ ¡ ¦ ¥¤ §¦ ©¨¦ MATCH ¦ ¤ ¥ ¦ ! ¥ occ& ¤)& ¤ ¨¦ 3 3 ¡ § ¨¤ 6¨
wMatch& ¥¤ ¦¥ ¦ 3 $ ¤ ¡ ( Cs¦ ¤ ¦¥ ¡ holds
¤ the strong matching shift is defined by:

sMatch& ¥¤ ¦¥ ¦ 3 $ ¤ ¡ ( Cs¦ ¤ ¦¥ ¡ and Cos¦ ¤ ¥ ¡ hold
¤ the best matching shift is defined by:

bMatch& ¤ ¦¥ ¦ 3 $ ¤ ¡ ( Cs¦ ¤ ¥ ¡ and Cob¦ ¤ ¥ 6& ¥¤ ¨¦ 3 ¥ ¡ hold Remark: wMatch& #( 3 $ sMatch& ( 3 $ bMatch& #( ¥ ¦ 3 is equal to the period of ¦ for all ( ¦ ©
¡ . The occurrence shift is defined as follows. For ¢ 8 :

occ& 3 $ ¤ ! ¤ ¤ § 1¡ and ¦ & ¤ § 1¡ ¡ ¤ 3 '$ if appears in ¦ ¥ § otherwise.
The Boyer-Moore algorithm is shown in Fig. 8. The function MATCH ¦ ¤ ¦¥ ¦ ! can re- turn either wMatch& ¤ 3 , sMatch& ¤ 3 or bMatch& ¥¤ ¦¥ ¦ 3 . In the three cases the algorithm will locate all the occurrences of ¦ in ¨. When shifting the pattern, it applies the maximum between the occurrence shift and the matching shift.

A brief history

In April 1974, Robert S. Boyer (Stanford Research Institute) and J. Strother Moore (Xerox Palo Alto Research Center) designed a string-matching algorithm with the following features: right-to-left comparisons, occurrence shift, weak matching shift and a fast loop [START_REF] Boyer | A fast string searching algorithm[END_REF]. At the same period and independently R. W. Gosper (Stanford University) discovered the right-to-left comparisons system and the occurrence shift. In December 1975, Ben Kuipers (Artificial Intelligence Laboratory, MIT) communicated to Boyer and Moore the idea of the strong matching shift. And at the same period Boyer and Moore introduced the best matching shift in ¥ §¦ § ¡ 9 ¤ time and space complexities.

In January 1976, Donald E. Knuth (Stanford University) showed that the strong matching shift is enough for the linearity of the algorithm when the pattern is not present in the text giving a bound of ¢ © character comparisons. He also gave a general bound of ¥ §¦ © 5 § © character comparisons where is the number of occurrences of the pattern in the text. He finally introduced the Boyer-Moore automaton which conceptualizes an algorithm that remembers all the matched text characters among the § last scanned [START_REF] Knuth | Fast pattern matching in strings[END_REF]. In 1979, Zvi Galil (Tel Aviv University) published a linear algorithm for finding all occurrences of the pattern in the text [START_REF] Galil | On improving the worst case running time of the Boyer-Moore string searching algorithm[END_REF] using prefix memorization. In 1980, Wojciech Rytter (Warsaw University) gave the first published correct version of the preprocessing of the strong matching shift [START_REF] Rytter | A correct preprocessing algorithm for Boyer-Moore string searching[END_REF]. This same year Leo J. Guibas (Xerox Corporation, Palo Alto Research Center) and Andrew M. Odlyzko (Bell Telephone Laboratories) gave a proof of a £ © bound and conjectured that the right bound was © [9]. Still in 1980 R. Nigel Horspool (McGill University) designed a practical algorithm using only the occurrence shift based on the rightmost character of the window [START_REF] Horspool | Practical fast searching in strings[END_REF]. In 1986 Alberto Apostolico (Purdue University) and Raffaele Giancarlo (Salerno University) presented an algorithm that they proved performs © character comparisons in the worst case for finding all the occurrences of the pattern in the text using ¥ §¦ § © extra space [START_REF] Apostolico | The Boyer-Moore-Galil string searching strategies revisited[END_REF].

In 1987, Zhu Rui Feng and Tadao Takaoka (Ibaraki University) presented an algorithm using a two-dimensional occurrence shift [START_REF] Zhu | On improving the average case of the Boyer-Moore string matching algorithm[END_REF]. In 1988, R. Schaback (Göttingen University) published a study on the expected sublinearity of the Boyer-Moore algorithm [START_REF] Schaback | On the expected sublinearity of the Boyer-Moore algorithm[END_REF]. In 1990, Richard Cole (Courant Institute, New York University) gave a simple proof of a £ © bound and a tight bound of © character comparisons [START_REF] Cole | Tight bounds on the complexity of the Boyer-Moore string matching algorithm[END_REF]. The same year Daniel Sunday (Johns Hopkins University) designed the Quick Search algorithm (using the occurrence shift with the text character immediately to the right of the window) [START_REF] Sunday | A very fast substring search algorithm[END_REF]. In 1991, Andrew Hume (AT&T Bell Laboratories) and Daniel Sunday (Johns Hopkins University) published a study on practical string matching algorithms where they gave the Tuned Boyer-Moore algorithm which consists of a fast loop with three consecutive occurrence shifts [START_REF] Hume | Fast string searching[END_REF]. In 1992, Maxime Crochemore (LITP, University Paris 7), Artur Czumaj (Warsaw University), Leszek Ga ¸sieniec (Warsaw University), Stefan Jarominek (Warsaw University), Thierry Lecroq (LITP, University of Orleans), Wojciech Plandowski (Warsaw University) and Wojciech Rytter (Warsaw University) designed the Turbo-BM algorithm which has a bound of © character comparisons in the worst case when searching for all the occurrences of the pattern in the text with a constant extra-space [START_REF] Crochemore | Speeding up two string matching algorithms[END_REF] using last match memorization. In 1993, Christophe Hancart (LITP, University Paris 7) computed the best matching shift in ¥ §¦ § [11]. In 1996, Maxime Crochemore (IGM, University of Marne-la-Vallée) and Thierry Lecroq (LIR, University of Rouen) gave a new presentation of the Apostolico-Giancarlo algorithm and a tight bound of ! #" © character comparisons [6].

It is worth noting that the Boyer-Moore string-matching algorithm has been introduced to the wide public in the PC Magazine and Dr. Dobbs Journal by Costas Menico in 1989 [START_REF] Menico | Faster string searches[END_REF] and Jeff Prosise in 1996 [START_REF] Prosise | High-performance string searching: How a smart algorithm can make a big difference[END_REF] respectively.

SUFFIXES¦ ¦ ¥ § 1 suf & ¤ § 1¡ 73 ¡ § 2 ¡ § 1¡ 3 for ¤ ¡ § ¡ % downto ( 4 do if ¤ and suf & ¥¤ 6¨ § ¡ ¡ ¢¡ 3 ¤ ¡ £ 5 then suf & ¥¤ 3 ¡ suf & ¤ )¨ § 1¡ ¡ ¤¡ 3 6 else ¡ ¤ ¥ ¥ ¤ 7 ¡ ¡ ¤ 8 while ¢ ( and ¦ & 3 $ ¦ & ¨ § 1¡ ¡ ¤¡ 3 9 do ¡ ¡ 10 suf & ¤ 3 ¡ ¡ ¡ ¦ 11 return suf FIG. 9. Algorithm SUFFIXES.

Computing the strong matching shift

Since Knuth showed that the strong matching shift is sufficient to have a linear algorithm when looking for the first occurrence of the pattern ( [START_REF] Knuth | Fast pattern matching in strings[END_REF]), the strong matching shift is then the shift generally used when one implements the Boyer-Moore algorithm.

The first correct computation of the strong matching is due to Rytter [START_REF] Rytter | A correct preprocessing algorithm for Boyer-Moore string searching[END_REF] but it is quite difficult to understand. We will give here a simpler version based on the computation of the longest suffixes of ¦ ending at each position in ¦ . The lengths of these suffixes greatly help the computation of the matching shift.

Computing the longest suffixes ending at each position in the pattern

Let us first present the computation of the longest suffixes of ¦ ending at each position in ¦ . It can be viewed as an application from right to left of the fundamental preprocessing (or § algorithm) given by Gusfield [START_REF] Gusfield | Algorithms on strings, trees and sequences: computer science and computational biology[END_REF]. For ( The computation of the table suf is done by the algorithm SUFFIXES presented in Figure 9. Figure 10 depicts the variables and the invariants of the main loop of algorithm SUFFIXES. The values of suf are computed for each position ¤ in ¦ in decreasing order. The algorithm uses two variables ¡ and which satisfy:

¤ $ ¤ ¦ ¡ suf & ¦ 3 ¤ §¦ § ¡ ¤ ¡ is a position ¦ such that ¤ ¦ § ¡ and ¦ ¡ suf & ¦ 3 $ ¨
In order to prove the correctness of algorithm SUFFIXES we will first show an intermediate lemma. ( ¥ ¡ ¢ 8 ), ¦ $ ¨ § ¡ ¡ ¡ , and ¤ ¡ . The picture corresponds to the case where ¤ .

LEMMA 4.1

If ¤ , we have

suf & ¥¤ 3 $ suf & ¥¤ 6¨ § ¡ ¡ ¡ 3 if suf & ¤ )¨ § ¡ ¡ ¡ 3 ¤ ¤ ¡ £ ¨¡ otherwise where ¡ $ lcsuf ¦ ¦ '& #( !3 ¥ ¦ & #( § ¡ ¡ ¤ ¢ !3 . Proof: Let §$ ¦ & ¨ ¡ 3 . This word is a suffix of ¦ by definition of ¡ and . Let ¢ $ suf & ¥¤ ¨ § ¡ ¡ ¡ 3 . By definition of suf , the word ¦ '& ¥¤ ¨ § ¡ ¡ ¡ ¡ ¢ ¤ ¨ § ¡ ¡ ¡ )3 is a suffix of ¦ but ¦ & ¥¤ 6¨ § ¡ ¢¡ ¡ ¢ ¤ )¨ § 1¡ ¡ ¤¡ 3 is not a suffix of ¦ .
In the first case (¤ and suf & ¥¤ ¨ § ¡ ¡ ¡ 3 ¤ ¡ £ ), the word & ¤¦ ¨ § ¡ ¡ ©¡ ¢ ¤ 6¨ § ¡ ¡ ¢¡ 3 occurs in ending at position ¤ 6¨ § 1¡ ¡ ¤¡ . Thus it also occurs ending at position ¤ in ¦ which shows that ¦ '& ¥¤ ¨ § ¡ ¡ ¡ ©¡ ¢ ¤ ¨ § ¡ ¡ ¡ 3 is the longest suffix of ¦ ending at position ¤ . Thus suf & ¥¤ 3 ¤$ ¢ $ suf & ¤ )¨ § 1¡ ¡ ¤¡ 3 .

In the second case, the word ¦ & ¨ ¤ 3 , which is a prefix of , is a suffix of ¦ & ¥¤ § ¡ ¡ ¦¡ ¢¡ ¢ ¤ ¨ § ¡ ¡ ¡ 3 and thus of ¦ . It is easy to see that suf & ¥¤ 3 $ ¤ ¡ ¨¡ . £ THEOREM 4.2 Algorithm SUFFIXES computes correctly the table suf .

Proof:

The variables ¡ and satisfy the definition given before Lemma 4.1 before each execution of the main loop of the algorithm. Then for a given ¤ such that ¤ the algorithm applies the relation given by Lemma 4.1 which gives a correct value. It remains to check that the computation is correct when ¤

. In this situation the instructions from line 8 to line 9 compute

lcsuf ¦ ¦ '& #( ¤ 3 ¥ ¦ $ ¦ & ¡ 3
which is by definition the correct value for suf & ¥¤ 3 . Therefore algorithm computes correctly the table suf .

£

We will now give the time complexity of algorithm SUFFIXES. This shows that the total time of all the runs of the loop from line 8 to line 9 is ¥ §¦ § © .

STRONG-MATCHING

¦ ¦ ¥ § 1 ¦ ¡ ( 2 for ¤ ¡ § ¡ downto ¡ 3 do if ¤ '$ ¡ or suf & ¥¤ 3 $ ¤ ¨ 4 then while ¦ § ¡ ¡ ¤ 5 do sMatch& ¦ 3 ¡ § ¡ ¡ ¤ 6 ¦ ¡ ¦ ¨ 7 for ¤ ¡ ( to § ¡ % 8 do sMatch& ¤ § 1¡ ¡ suf & ¥¤ 3 3 ¡ § 1¡ ¡ ¤ 9
The other instructions of the loop from line 3 to line 10 are executed in contant time.

Thus the whole algorithm is in ¥ ¦ § . £

Computing the strong matching shift

We are now able to give, in Fig. . 11, the algorithm STRONG-MATCHING computes the table sMatch using the table suf . The invariants of the second loop of algorithm STRONG-MATCHING are presented in Fig. 12.

We will now show that algorithm STRONG-MATCHING computes correctly table sMatch. We first begin by proving two intermediate lemmas.

LEMMA 4.4 For ( ¤ § , if suf & ¥¤ 3 $ ¤ !¨ then, for ( ¦ § ¡ ¡ ¤ , sMatch& ¦ 3 § ¡ % ¡ ¤ . Proof: The assumption suf & ¥¤ 3 $ ¤ ¨ is equivalent to the assumption that ¦ & #( ¤ 3 is a suffix of ¦ . Thus § ¡ suf & ¥¤ 3 $ § ¡ '¡ ¤ is a period of ¦ . Let ¦ be a position such that ( ¦ § ¡ ¡ ¤ . Condition Cs¦ ¦ ¥ § ¡ ¡ ¨¤ is satisfied since § 1¡ ¡ ¤ ¦ and ¦ & ( § ¡ ¦ § ¡ ¡ ¤ ¡ % 43 ¤$ ¦ & #( ¤ 3 is a suffix of ¦ . Condition Cos¦ ¦ ¥ § ¡ % ¡ ¤ is also satisfied since § 1¡ ¡ ¤ ¦ .
$ lcsuf ¦ ¦ ¥ ¦ & #( ¤ 3 and ¢ $ ¡ ( ¥ ¡ ¢ 8 ) and suf & ¥¤ 3 ¤$ . Thus sMatch& ¦ 3 § 1¡ ¡ ¤ with ¦ $ § ¡ ¡ suf & ¤ 3 . LEMMA 4.5 For ( ¤ § ¡ we have sMatch& ¤ § 1¡ ¡ suf & ¥¤ 3 3 § 1¡ ¡ ¤ . Proof: If suf & ¥¤ 3 ¤ § , condition Cs¦ § ¡ ¡ suf & ¥¤ 3 ¥ § ¡ ¡ ¤ is satisfied since we have both § ¡ ¡ ¤ § ¡ § ¡ suf & ¥¤ 3 and ¦ & ¥¤ 4¡ suf & ¤ 3 ¨ ¤ 3 $ ¦ '& ¤ § ¡ § ¡ suf & ¤ 3 ¨ § ¡ § 43 . Moreover condition Cos¦ § %¡ )¡ suf & ¥¤ 3 ¥ § ¡ 6¡ ¤ is also satisfied since ¦ '& ¥¤ ¡ suf & ¥¤ 3 3 ¢ $ ¦ & § 1¡ ¡ suf & ¥¤ 3 3 by definition of suf . Thus sMatch& § 1¡ ¡ suf & ¥¤ 3 3 § 1¡ ¡ ¤ . If suf & ¥¤ 3 $ ¤ '1 , by lemma 4.4 we have for ¦ $ § ¡ 2 ¡ suf & ¥¤ 3 $ § ¡ ¤ ¡ , sMatch& ¦ 3 § ¡ ¡ ¤ . £ THEOREM 4.6
Algorithm STRONG-MATCHING computes correctly the table sMatch.

Proof:

We have to show that for each ¦ , ( ¦ § , the final value ¡ given to sMatch& ¦ 3 by algorithm STRONG-MATCHING is the minimum value which satisfies

Cs¦ ¦ ¥ ¡ and Cos¦ ¦ ¥ ¡ .
Let us assume first that ¡ results from an assignment in the loop from lines 2 to 6. Then the first part of condition Cs is not satisfied. By lemma 4.4 we verify that ¡ is the minimum value that satisfies the second part of condition Cs¦ ¦ ¥ ¡ . In this case, ¡ $ § ¡ ¡ ¤ for a value ¤ such that suf & ¥¤ 3 $ ¤ 2 and ¦ § ¡ ¡ ¤ . This last inequality shows that condition Cos¦ ¦ ¥ ¡ is also satisfied. Thus ¡ $ sMatch& ¦ 3 .

Let us assume now that ¡ results from an assignment in the loop from lines 7 to 8. Thus ¦ $ § ¡ ¡ suf & ¥¤ 3 and ¡ $ § ¡ 2 ¡ ¤ , and, by lemma 4.5, sMatch& ¦ 3 ¡ . We also have ( ¡ ¤ , which shows that the second parts of conditions Cs¦ ¦ ¥ ¡ and Cos¦ ¦ ¥ ¡ cannot be satisfied. Since the values of § ¡ ¡ ¤ are considered in decreasing order during the execution of the loop, ¡ is the smallest value of § ¡ ¡ ¤ for which Proof: The extra space needed for the computation (excluding the word ¦ and the table sMatch) is constituted by the table suf and some variables, thus ¥ ¦ § .

¦ $ § ¡ ¡ suf & ¥¤ 3 . Thus ¡ $ sMatch& ¦ 3 .
The loop from line 2 to line 6 executes in ¥ ¦ § as each instruction executes in con- stant time for variables ¤ and ¦ which take § ¨ values.

The loop from line 7 to line 8 executes also in ¥ §¦ § © which gives the result. The computation of the table suf has the same complexity by Theorem 4.3.

£ 5 The Apostolico-Giancarlo algorithm

The main drawback of the Boyer-Moore algorithm is that after a shift it forgets completely what it has previously matched. Apostolico-Giancarloalgorithm remedies this. It remembers at the end of each attempt the length of the suffix of the pattern matched during this attempt. Matches so memorized are possibly used to avoid comparisons and compute shifts.

We are now going to see how the algorithm scans the characters. Assume that during an attempt where the pattern is aligned with the text characters 6& ¦ £ ¦ ¡ ¨ § ¡ 43 , a suffix of length ¡ of the pattern has been found i.e.

¦ '& ¤ § ¡ ¡ 0 ¤ § ¡ § 43 $ )& ¦ ¤ !¨ § ¡ ¡ 0 ¦ ¥ ¨ § ¡ 73 and ¦ & ¤ § 1¡ ¡ ¡ 73 ¢ $ )& ¦ ¥ ¨ § 1¡ ¡ ¡ 43 .
If during a later attempt where the pattern is aligned with the text characters )& ¦ ¦ § ¡ 73 with ¦ ¥ §¦ , a match is found between characters ¦ & ¥¤ 6¨ ! ¤ § 1¡ 43 and 6& ¦ ¤ § ¡ ¡ 0 ¦ ¨ § ¡ 43 where ¤ '$ § ¡ ¦ ¦ ¡ ¦ ¡ (see Fig. 13).

Actually four different cases can arise: they are illustrated by Figures 14 to 17.

Case 1 :

skip& ¥¤ ¨¦ 3 suf & ¥¤ 3 and ¤ % $ suf & ¥¤ 3 : then an occurrence of ¦ is found at position ¦ (see Fig. 14). A shift of length sMatch& #( 3 is performed and skip& ¦ ¨ § 3 is set to 16). Thus a shift can be performed using sMatch& ¤ ¡ skip& ¥¤ ¤¨¦ 3 3 and occ& ¤6& ¦ ¨¤ ¡ skip& ¤ ¤¨¦ 3 03 3 and skip& ¦ ¨ § 3 is set to 1¡ ¤ ¡ skip& ¥¤ 6¦ 3 ¡ . Following these four cases we are now able to formulate the Apostolico-Giancarlo algorithm (see Fig. 18).

The complexity of the Apostolico-Giancarlo algorithm

We are first going to show that comparing the same ¢ characters twice causes a right shift of ¦ of length greater than ¢ . A text character can be compared again only if the previous comparisons it was involved in were mismatches.

¦ ¦ ¨¦ ¥ ¦ skip& ¥¤ 6¨¦ 3 suf & ¥¤ 3 ¢ $ ¢ $ © ¡ FIG. 17. Case 4, skip& ¥¤ 6¨¦ 3 ¤$ suf & ¥¤ 3 ¥ ¢ $ ¡ and ¡ ¢ $ © . APOSTOLICO-GIANCARLO ¦ ¦ ¥ § ¥ ¨¥ © ¤ 1 ¦ ¡ ( 2 while ¦ © ©¡ § 3 do ¤ ¡ § ¡ 4 while ¤ ¢ (
¤ ¡ ¤ ¤¡ suf & ¥¤ 3 19 skip& ¤ )¨¦ 3 ¡ § ¡ ¤ ¡ 20 if ¤ ( 21 then REPORT ¦ ¦ ! 22 ¦ ¡ ¦ ¨sMatch& #( 3 23 else ¦ ¡ ¦ ¨¤ ¦ 6¦ sMatch& ¥¤ 3 ¥ occ& ¤6& ¥¤ ¦ 3 3 ¡ § ¨¤ 6¨

Conclusion

We gave a new method to compute the strong matching shift of the Boyer-Moore algorithm. This method is simpler than the previous published methods. It computes and uses a table storing the length of the longest suffix of the pattern ending at each position in the pattern. This table is extensively used in the new version of the Apostolico-Giancarlo algorithm, which performs a maximum number of comparisons that is half the maximum of the Boyer-Moore algorithm in the worst case.

FIG. 1 :

 1 FIG. 1: Typical situation during the Boyer-Moore algorithm: a suffix

FIG. 2 .FIG. 3 .FIG. 7 .

 237 FIG.2. Weak matching shift: © can be equal to .

FIG. 8 .

 8 FIG. 8. The Boyer-Moore string matching algorithm.

¤ § ¡ 2

 2 we denote by suf & ¥¤ 3 the length of the longest suffix of ¦ ending at position ¤ in ¦ . Let us denote by lcsuf £ ¥ ! the longest common suffix of two words £ and .

FIG. 10 :

 10 FIG. 10: Variables ¤ ¥ ¡ ¥ of algorithm SUFFIXES. The main loop has invariants: $ lcsuf ¦ ¦ ¥ ¦ '& 2 ¡ 3 and ¢ $ ¡

return sMatchFIG. 11 .

 11 FIG. 11. Algorithm STRONG-MATCHING.

FIG. 13 :

 13 FIG.13:A typical situation during the Apostolico-Giancarlo algorithm: jump or shift ? Dark gray areas correspond to factors that have been compared during the current attempt while light gray areas correspond to factor that have been jumped.

suf & ¤ 3 FIG. 14 :. 2 :

 3142 FIG. 14: Case 1, skip& ¥¤ ¤¨¦ 3 suf & ¥¤ 3 and suf & ¥¤ 3 $ ¤ ¨ then an occurrence of ¦ is found.

Case 4 : 3 (

 43 skip& ¥¤ ¨¦ 3 $ suf & ¥¤ 3 : then this is the only case where a "jump" has to be performed in order to resume the comparisons between characters ¦ & ¤ ¡ suf & ¥¤ 3 3 and )& ¦ ¨¤ ¡ suf & ¥¤ 3 see Fig.

17

 17

  ).

LEMMA 6 . 1 (FIG. 15 : 3 ¤FIG. 16 :

 6115316 FIG. 15: Case 2, skip& ¤ ¨¦ 3 suf & ¤ 3 and suf & ¥¤ 3 ¤ then a mismatch occurs between

¤

FIG. 18 .FIG. 19 :££

 1819 FIG.18. The Apostolico-Giancarlo algorithm revisited.

£

  Then by definition of suf , sMatch& ¦ 3 § 1¡ ¡ ¤ . FIG. 12: Variable ¤ of algorithm STRONG-MATCHING. Situation where suf & ¥¤ 3 ¤ 4¨ . The loop of lines 7-8 has the following invariants:

	(	¤	¦	§	¡
	¡
	¦
	£