Nawfal Blal
email: nawfal.blal@univ-montp2.fr

Loïc Daridon
email: loic.daridon@univ-montp2.fr

Yann Monerie
email: yann.monerie@irsn.fr

Stéphane Pagano
email: stephane.pagano@univ-montp2.fr

Blal Nawfal

-Daridon Loïc

Monerie Yann

-Pagano Stéphane

Micromechanical-based criteria for the calibration of cohesive zone parameters

Keywords: Micromechanics, Damage, Cohesive Zone Model, Homogenization

published or not. The documents may come

Introduction

The cohesive approaches had emerged as one of the most efficient method in computational fracture mechanics. However these approaches exhibit strong mesh sensitivity [START_REF] Song | A bilinear cohesive zone model tailored for fracture of asphalt concrete considering viscoelastic bulk material[END_REF][START_REF] Turon | An engineering solution for mesh size effects in the simulation of delamination using cohesive zone models[END_REF] and an accurate calibration of the cohesive parameters to extract physically-based macroscopic properties is up to now a cumbersome task [START_REF] Matouš | Multiscale cohesive failure modeling of heterogeneous adhesives[END_REF].

Various (semi-) empirical criteria have been proposed in the ten past years in order to avoid these difficulties (among others, see [START_REF] Espinosa | A grain level model for the study of failure initiation and evolution in polycrystalline brittle materials. Part I: Theory and numerical implementation[END_REF][START_REF] Tomar | Bounds for element size in a variable stiffness cohesive finite element model[END_REF]). To fix the idea, a cohesive zone model can be seen as a traction-separation law involving two main parameters: a peak stress R coh max and a cohesive energy G coh . Whatever the shape of the traction-separation law a characteristic length is thus invoked, e.g. G coh /R coh max . The computational challenge is to obtain rigorous criteria linking these characteristic length to the surrounding bulk properties and to the size and the type of the underlying spatial discretization. Previous criteria developed in the literature are mainly limited to unidimensional loadings and no theoretical result is available at any triaxiality loading ratio in three dimensions.

Following a micromechanical-based approach initially proposed by [START_REF] Acary | Nonsmooth fracture dynamics using a cohesive zone approach[END_REF], [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] have recently obtained such rigorous criteria for a linear elastic cohesive zone model (no surface damage). We extend here these criteria to any damageable intrinsic cohesive zone model. The main idea is to consider each face of a three dimensional mesh with embedded cohesive zone models as a penny shaped damageable inclusion (Figure 1). A cohesive-volumetric finite element (CVFE) scheme is thus replaced by a matrix-inclusion composite, and the spatial distribution of inclusions corresponds to the mesh morphology. Using a variational approach [START_REF] Castañeda | The effective mechanical properties of nonlinear isotropic composites[END_REF][START_REF] Suquet | Overall properties of nonlinear composites : Secant moduli theory and its link with Ponte Castaneda's variational procedure[END_REF] and a linear lower bound [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF], a rigorous theoretical estimate of the overall strain potential of this composite is obtained.

Theoretical criteria on cohesive parameters are thus derived from this estimate. The elastic criterion of [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] is recalled (Eq. ( 21)) and new damageable criteria are proposed. In particular, considering a bilinear cohesive law, closed-form relationships (Eqs. (25)-(30)) between the microscopic cohesive parameters and the macroscopic fracture properties are exhibited through an inverse analysis .

Embedding cohesive zone models in bulk media

The proposed micromechanical model is based on a cohesive-volumetric finite element (CVFE) scheme. The overall behavior results in the coupling of the volumetric behavior of bulk elements and the smeared out cohesive surfaces incorporating all softening processes. We focus our attention to elastic bulk behaviors and intrinsic cohesive zone models, i.e. cohesive law with initial stiffness.

Bulk behavior

We consider the case of linear isotropic elastic media whose behavior is characterized by the constitutive relationships:

σ = C M : ε with C M = 3k M J + 2µ M K, (1)
where σ (resp. ε) is the stress (resp. strain) field , C M is a fourth order stiffness tensor, k M and µ M are the bulk and the shear modulus respectively. The symmetric tensors J and K define the generic basis of the fourth order isotropic and symmetric tensors:

3J = i ⊗ i and K = I -J with 2I ijkl = (i ik i jl + i il i jk ) ( 2
)
where i is the second order identity tensor.

Cohesive Zone Model

Without loss of generality, any intrinsic cohesive law can be given as a three-dimensional traction-separation law linking the cohesive stress vector R coh to the opening displacement vector [[u]] = u +u -, where u + (resp. u -) is the displacement of the upper (resp. lower) part of the cohesive zone. In a local normal-tangent frame oriented by the normal vector n, the opening displacement vector can be decomposed into a normal, u N , and a tangential, u T , component: [[u]] = u N n+u T . A generic cohesive constitutive relation reads:

R coh = K • [[u]] with K = β × (C N n ⊗ n + C T (i -n ⊗ n)) , (3)
where C N (resp. C T ) is the normal (resp. tangential) initial 'stiffness' of the cohesive law and β is a surface damage parameter ( β = 1 the cohesive zone is undamaged, 0 < β < 1 cohesive zone is partially damaged and β = 0 the cohesive zone is fully damaged). Following [START_REF] Turon | An engineering solution for mesh size effects in the simulation of delamination using cohesive zone models[END_REF], we assume that the damage parameter β introduced in (3) depends on the euclidian norm of the opening displacement vector [[u]], i.e. β = β( [[u]] ) with β a damage function.

Micromechanical model

3.1. The cohesive-volumetric finite element scheme as a matrix-inclusion composite In order to accurately estimate the overall behavior resulting from a CVFE discretization, the procedure proposed in [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] is considered. The idea consists in introducing a continuous equivalent matrix-inclusion composite as a convenient representation of the underlying cohesive-volumetric discretization (Figure 1). The continuous matrix has the same behavior as the bulk finite element behavior (Eq. ( 1)) whereas the inclusions behavior should represent the cohesive zone model (Eq. ( 3)). Associating to the inclusions a fictitious thickness e that should tend to zero, and with the help of the strain definition across the cohesive zones:

ε coh = 1 2 [[u]] ⊗ n + n ⊗ [[u]] e , (4)
a damageable fourth order stiffness tensor C coh is defined for the cohesive inclusions following [START_REF] Acary | Nonsmooth fracture dynamics using a cohesive zone approach[END_REF][START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF]:

σ coh = C coh [[u]] : ε coh with C coh [[u]] = eβ [[u]] C N E l +C T K l .
(5) where σ coh is the cohesive stress field and the tensors E l and K l are two components of the fourth order symmetric and transversely isotropic tensors generic frame:

E l = n ⊗ n ⊗ n ⊗ n, K l = 2(j s ⊗ j s + j t ⊗ j t )
where j s = n⊗ s s and j t = n⊗ s t with s and t being two orthogonal vectors defining the transversal plane; (n, t, s) define the local orthogonal basis of the cohesive inclusion. We underline that combining (5) and ( 4), the cohesive stress vector R coh = σ coh • n satisfies the constitutive relationship [START_REF] Turon | An engineering solution for mesh size effects in the simulation of delamination using cohesive zone models[END_REF].

The cohesive inclusions are distributed according to the spatial distribution of the underlying cohesive-volumetric mesh morphology. Their density, denoted by Z, corresponds to the specific cohesive surface: Z = A/S where A is the total edge length (resp. area) in 2-D (resp. in 3-D) and S is the total area (resp. volume) of the 2-D (resp. 3-D) meshed body. For a discretization characterized by a mesh size L mesh , A is proportional to L q-1 mesh and S is proportional to L q mesh where q is the considered dimension. The density Z is thus inversely proportional to the mesh size and can be expressed as:

Z = γ L mesh ,
where the parameter γ depends on the spatial distribution of the considered mesh [START_REF] Blal | Artificial compliance inherent to the intrinsic cohesive zone models: criteria and application to planar meshes[END_REF]. In particular, in the case of a statistical isotropic mesh, e.g. a Delaunay-type mesh, the inclusions are randomly distributed in space and in orientation. Moreover we assume that the cohesive inclusions have a penny-shaped form (Figure 1). This geometric assumption has no consequence for planar meshes where the edges are replaced by zero thickness whiskers. For 3-D meshes, we suppose that the polygonal edges are replaced by flat disks. We admit that these situations are close to each other but are different in full rigour.

Overall elastic stiffness

As a first step, the results obtained in [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] for the elastic behaviors are briefly recalled. In this section, the cohesive inclusions behavior is assumed to be linear, i.e. β = 1. The overall behavior of the matrix-inclusion composite is estimated using the Hashin-Shtrikman scheme [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF][START_REF] Willis | Bounds and self-consistent estimates for the overall properties of anisotropic composites[END_REF] and a lower bound of the overall elastic moduli is derived under the assumption of macroscopic isotropy, i.e. isotropic bulk behavior and isotropic distribution of inclusions (e.g. Delaunay-type meshes). This bound is obtained by considering the inclusions as the reference medium, and the corresponding overall stiffness tensor reads after the passage to limit e → 0 [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF]:

C hom = 3k hom J + 2µ hom K, (6)
where the overall bulk and shear moduli are respectively given by:

       k hom k M = ξ k ξ k + 1 with ξ k = C N Zk M , µ hom µ M = ξ µ ξ µ + 1 with ξ µ = 15 4(1 + 3C N /C T ) × C N Zµ M . (7)
The overall Young's modulus and Poisson ratio associated to this bound read:

E hom E M = ξ E 1 + ξ E where ξ E = 5 1 + (4/3)(C N /C T ) × C N E M Z , (8)
ν hom ν M = 15C N ν M + (2C N /C T -1)E M Z 15C N ν M + (4C N /C T + 3)E M Zν M . (9)
It is worth noting that Eqs. ( 7) and [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] show respectively that a cohesivevolumetric formulation with vanishing tangential cohesive stiffness (C T → 0) leads to a macroscopic no shear (µ hom → 0) and no tension (E hom → 0) material.

Overall quasi-brittle damage

In this section, the case of non linear damageable cohesive zone models is considered (0 ≤ β < 1). The macroscopic stress Σ associated to the softening part is obtained via the constitutive law: Σ = C hom : E, where the homogeneous stiffness tensor C hom is estimated using the modified secant method [START_REF] Suquet | Overall properties of nonlinear composites : Secant moduli theory and its link with Ponte Castaneda's variational procedure[END_REF], which is equivalent to the Ponte Castañeda variational approach [START_REF] Castañeda | Nonlinear composites[END_REF]. The non linear stiffness of the inclusions is approached by a secant modulus:

C coh sct = C coh [[u]] 2 I , (10)
where . I denotes the mean value over the cohesive inclusions. This secant stiffness C coh sct replaces the cohesive tensor C coh in Hashin-Shtrikman estimate.

With the help of definition (4), the opening displacement norm [[u]] can be linked to the fourth order tensor ¯= (1/2)ε ⊗ ε as:

[[u]] 2 = 2e 2 (-J + 2K) :: ¯. (11)
Moreover, the generalized Hill lemma allows to derive the second moment of the strain in the inclusion phase ¯ I from the overall elastic energy [START_REF] Kreher | Residual stresses and stored elastic energy of composites and polycrystals[END_REF]:

¯ I = 1 2eZ ∂(E : C hom : E) ∂C coh sct . (12)
Hence, substituting ( 12) into [START_REF] Hashin | A variational approach to the theory of the elastic behaviour of multiphase materials[END_REF], the mean square root of the opening displacement norm reads:

[[u]] 2 I = e Z (-J + 2K) :: ∂(E : C hom : E) ∂C coh sct , (13)
Involving the hydrostatic part of the strain loading E m = (1/3) tr(E) and the equivalent part E eq = (2/3)E dev : E dev (with E dev being the deviatoric strain tensor:

E dev = E -E m i), this last relation is rewritten as: [[u]] 2 I = AE 2 m + BE 2 eq ( 14
)
where A and B requires to calculate the derivatives ∂(E : C hom : E)/∂C coh sct . Due to the specific form of the chosen homogenization scheme, these derivatives can be here determined analytically. In more complicated cases, a numerical derivation can be used as proposed in [START_REF] Monerie | Overall elastoplastic behavior of anisotropic metal-matrix composites reinforced by aligned inclusions. application to hydrided and irradiated zircaloy-4 cladding tubes[END_REF].

Moreover, incorporating an intermediate result of [START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF] linking the normalto-tangential cohesive stiffness ratio C N /C T to the Poisson ratio:

C N C T = 1 2 1 + 3ν M 1 -2ν M , (15)
the coefficients A and B are reduced to:

A = 2 2 + ν M 1 -2ν M 3E M E M Z + 3 βC N (1 -2ν M ) 2 (16) B = 23 + (63 + 82ν M )ν M 10(1 + ν M ) 2 3E M E M Z + 3 βC N (1 -2ν M ) 2 (17)
Finally, the expression of the secant modulus is given by:

C coh sct = e × β × (C N E l + C T K l ), with β = β AE 2 m + BE 2 eq . (18)
The cohesive secant stiffness tensor C coh sct is thus obtained solving the non linear problem (18)-right in which A and B depend on the damage parameter β (see Eqs ( 16) and ( 17)). For any damage function β -i.e. for any shape of the cohesive law -the solution β of this non linear problem requires generally a numerical method as fixed point schemes. The overall secant behavior is thus derived using the Hashin-Shtrikman bound ( 6) and [START_REF] Acary | Nonsmooth fracture dynamics using a cohesive zone approach[END_REF] and the equation ( 15):

Σ = C hom sct : E with C hom sct = 3k hom sct (E)J + 2µ hom sct (E)K, (19)
where

       k hom sct k M = ξ k sct ξ k sct + 1 with ξ k sct = βC N Zk M , µ hom sct µ M = ξ µ sct ξ µ sct + 1 with ξ µ sct = 3(1 -2ν M ) 2(1 + ν M ) × βC N Zµ M . ( 20
)
This overall behavior defines a micromechanical damage model whatever the triaxiality loading ratio and the cohesive law type. In section 4.2, the case of a bilinear cohesive law is discussed: the non linear problem (18)-right can be solved in a closed-form.

4.

Inverse identification and practical criteria on cohesive parameters

Cohesive stiffness

Using cohesive zone models induces an inherent additional compliance that should be controlled. This problem arrises naturally for cohesive laws with initial stiffness (intrinsic models) but also for cohesive law with an initial infinite slope (extrinsic models) when dealing with unloading-reloading behaviors. Moreover, the elastic cohesive stiffness is known to be meshdependent as illustrated in [START_REF] Song | A bilinear cohesive zone model tailored for fracture of asphalt concrete considering viscoelastic bulk material[END_REF][START_REF] Turon | An engineering solution for mesh size effects in the simulation of delamination using cohesive zone models[END_REF].

To overcome these difficulties, some semi-empirical criteria have been proposed in the literature and can be summarized as follows: if L mesh denotes the mesh size of a cohesive-volumetric discretization, the effective elastic stiffness of an elastic medium with embedded cohesive zone model is not significantly disturbed if the condition

C N L mesh E M ≥ α
is satisfied, where the real α has to be much more larger than 1, e.g. [START_REF] Espinosa | A grain level model for the study of failure initiation and evolution in polycrystalline brittle materials. Part I: Theory and numerical implementation[END_REF][START_REF] Tomar | Bounds for element size in a variable stiffness cohesive finite element model[END_REF][START_REF] Turon | An engineering solution for mesh size effects in the simulation of delamination using cohesive zone models[END_REF].

Recently, the rigorous micromechanical-based criterion proposed by [START_REF] Blal | Artificial compliance inherent to the intrinsic cohesive zone models: criteria and application to planar meshes[END_REF][START_REF] Blal | Criteria on the artificial compliance inherent to the intrinsic cohesive zone[END_REF]:

C N L mesh E M ≥ γ R 1 -R 1 3 -6ν M and C T C N = 2 1 -2ν M 1 + 3ν M (21)
has shown the dependency of α on the bulk Poisson ratio ν M , on the spatial distribution of the underlying mesh (through γ) and on the apparent stiffness reduction tolerated by the user: R = E hom /E M .

Cohesive peak stress and critical opening displacement

Focusing on the case of quasi-brittle elastic materials, we attempt in what follows to derive micromechanical based criteria for the calibration of softening cohesive parameters. For the sake of simplicity, and without any loss of generality, the case of a bilinear cohesive law (Figure 2) and of overall pure deviatoric loadings (J : E = 0 and J : Σ = 0) are first considered. A procedure is proposed to calibrate the cohesive parameters as a function of: (1) the overall material properties (e.g. experimental data), (2) the shape of the cohesive law, (3) the spatial cohesive-volumetric discretization (mesh morphology and mesh size). These detailed results are then given for the case of overall pure hydrostatic loadings on a crude form.

Overall pure deviatoric loadings

For the case of a bilinear cohesive law, the damage function β reads:

β ( [[u]] ) = D [0,δa] ( [[u]] ) + D [δa,δc] ( [[u]] ) δ a δ a -δ c 1 - δ c [[u]] (22)
where D ∆a ∆c For this bilinear cohesive law, the non linear problem (18) can be solved analytically for the case of pure deviatoric loadings (E m = 0). In particular, an overall damage initiation strain E 0 eq can be defined when the cohesive peak stress is reached:

R N max R N u N C N Β C N ∆a ∆c R T max R T u T C T Β C T
E 0 eq = √ 2(1 + ν M )(1 -2ν M )(1 + 3ν M ) (1 -2ν M + 5(ν M ) 2 ) (23 + 63ν M + 82(ν M ) 2 ) R coh max E M R , (23)
where

R coh max = (R max N ) 2 + R max T 2
is the maximal cohesive strength. This macroscopic failure initiation depends on the matrix properties E M and ν M , on the maximal cohesive strength R coh max and on the apparent stiffness reduction R, but does not depend on the morphology γ or the density Z of the mesh. In the same way, the overall critical failure strain E c eq is reached when the cohesive resistance vanishes (Z = γ/L mesh ):

E c eq = √ 10(1 + ν M ) 3 23 + 63ν M + 82(ν M ) 2 γδ c L mesh . ( 24
)
This critical failure strain does not depend on the Young's modulus of the matrix E M or on the apparent stiffness reduction R, but increases linearly with respect to the critical opening displacement δ c and decreases wit respect to the mesh size L mesh .

Based on these definitions, three main results can be derived. First, in order to avoid that a complete failure can occur before the local surface damage begins, i.e. to satisfy the condition E c eq ≥ E 0 eq , the critical opening displacement has to respect the condition

δ c ≥ 3 √ 5 (1 -2ν M ) 1 + 3ν M 1 -2ν M + 5(ν M ) 2 L mesh γR R coh max E M . ( 25
)
Hence, we assume in the sequel that the critical opening displacement is linearly proportional to the right part of the inequality (25) through a multiplier coefficient larger than one. Second, the overall deviatoric strain, E eq , leading to the overall deviatoric peak stress Σ eq , satisfies the equation:

∂Σ eq ∂E eq | Eeq = 0 with Σ eq = (3/2)Σ : K : Σ E eq = (2/3)E : K : E , (26)
which, once solved, leads to the cohesive-to-overall peak stress relationship:

R coh max Σ eq = √ 2 (1 -2ν M + 5(ν M ) 2 ) (23 + 63ν M + 82(ν M ) 2 ) 3 (1 -2ν M ) (1 + 3ν M ) . ( 27
)
This last ratio can be understanded as a stress concentration factor that tends to infinity when the Poisson ratio ν M of the matrix tends to 1/2. For practical purpose, this stress concentration factor increases from about 2.7 to 5.4 for ν M ranging between 0.2 and 0.35. These values have to be compared to 3, corresponding to a circular void in an isotropic and infinite elastic plate subjected to remote loadings. The proposed micromechanical model has thus to be viewed as an effective brittle damage model rather than a model dealing with a single crack propagation. Third, the overall failure energy W c under pure deviatoric loading (the area under the overall stress-strain curve Σ eq -E eq ) is given after integrating [START_REF] Perales | A NonSmooth Contact Dynamics-based multi-domain solver -Code coupling (Xper) and application to fracture[END_REF] from sound material ( β = 1) to fully damaged material ( β = 0):

W c = Σ : dE.
This gives a relationship between the critical opening δ c and the overall failure energy W c :

δ c L mesh = 3 γ 2 5 23 + 63ν M + 82(ν M ) 2 1 + ν M W c Σ eq (28)
Based on these three main results and if we are in position to determine, experimentally for example, the macroscopic maximal stress Σ eq and the overall energy failure W c , then the cohesive parameters R coh max and δ c can be conveniently calibrated as:

R coh max = √ 2 (1 -2ν M + 5(ν M ) 2 ) (23 + 63ν M + 82(ν M ) 2 ) 3 (1 -2ν M ) (1 + 3ν M ) Σ eq , (29)
and

δ c = 3 2 5 23 + 63ν M + 82(ν M ) 2 1 + ν M W c Σ eq L mesh γ . (30)
It is clearly shown that the cohesive peak stress depends only on the material Poisson ratio whereas the critical opening is given in terms both of material properties and the mesh quantities L mesh and γ. The criteria resulting from equations (21), ( 29) and (30) define practical rules to suitably calibrate the cohesive law parameters, namely: 1/ the cohesive stiffnesses C N and C T , 2/ the maximal cohesive stress R coh max and 3/ the critical separation δ c (equivalently the cohesive energy) as functions of the overall material properties (E M , ν M ) for a given mesh size L mesh and a user-defined elastic reduction R = E hom /E M (Figure 3).

Although these results exhibit a mesh dependence of the local cohesive parameters (except R coh max as shown in Figure 3-left), the proposed approach leads to a mesh-independent overall behavior since the macroscopic behavior remains invariant regardless of the mesh size (Figure 3-right). Indeed, taking into account the previous relationships, the evolution of the macroscopic secant moduli k hom sct and µ hom sct is given as function only of the material properties and the applied macroscopic strain E (cf Eqs. ( 6), ( 8), ( 21) and here E m = 0):

k hom sct (E) k M = µ hom sct (E) µ M = R Σ eq Σ eq 2 -6RW c µ M Σ eq -2 W c E eq . (31)
Another key point when dealing with cohesive zone models, is the socalled internal cohesive length l coh . Following [START_REF] Jaubert | Justification of Paris-type fatigue laws from cohesive forces model via a variational approach[END_REF], this characteristic length l coh can be defined as the ratio between the toughness of the material G coh (the area under the cohesive stress-opening curve) and the cohesive peak stress, R coh max

l coh = G coh R coh max . (32)
It should be noticed that this characteristic length has not to be confused with the cohesive length scale over which the cohesive bonds act at the crack tip (process zone), but corresponds to an internal length for the cohesive zone model. For sake of simplicity, defining G coh for mixed modes as:

G coh = G coh N + G coh T with G coh N = 1 2 C N δ a δ c and G coh T = 1 2 C T δ a δ c , (33)
our approach leads to (see equations ( 21), ( 29), ( 30) and ( 33)):

l coh L mesh = 3 5 √ 2γ 3 -ν M 1 + ν M 23 + 63ν M + 82(ν M ) 2 1 -2ν M + 5(ν M ) 2 W c Σ eq . (34)
It is worth noting that the characteristic cohesive length does not only depend on physical properties, but also on the mesh morphology, on the mesh size and on the loading rate.

Overall pure hydrostatic loadings

For the case of pure hydrostatic loadings (E eq = 0), the same procedure gives after some algebra a set of relationships for the calibration of cohesive parameters:

R coh max = √ 10 1 + 3ν M (2 + ν M ) (1 -2ν M + 5(ν M ) 2 ) 1 -2ν M Σ m (35)
and

δ c = 6 √ 2 2 + ν M 1 -2ν M W c Σ m L mesh γ . ( 36
)
The combination of ( 6), ( 35) and (36) leads to the following equations for the evolution of the macroscopic secant moduli k hom sct and µ hom sct with no meshdependency:

k hom sct (E) k M = µ hom sct (E) µ M = R Σ m Σ m 2 -6RW c k M Σ m -2 W c E m . ( 37
)
This last relationship is similar to the previous one obtained for pure deviatoric loadings (see equation ( 31)). Moreover, using equations (33), ( 21), ( 35) and (36), the cohesive length reads:

l coh L mesh = 3 √ 2 √ 5γ (3 -ν M ) 2 + ν M (1 -2ν M ) (1 -2ν M + 5(ν M ) 2 ) W c Σ m . (38)
Again, a same form is obtained as in the deviatoric case (see equation ( 34)) but with a different pre factor depending on the material Poisson ratio. For practical purpose, the cohesive length is about two times larger for pure hydrostatic loadings than for pure deviatoric one. 19)) obtained using the bilinear cohesive law (Eq. ( 22)). Left: The proposed criteria (Eqs. ( 21)-( 30)) for the selection of the cohesive parameters (Table 1): the case of a shear loading for a mesh set of parameters and a user tolerated elastic loss of 5%, i.e. R = 0.95 (the material properties are given in Table 1)

E M (MPa) ν M Σ eq (MPa) W c (MPa) 100 1/7 200 100 Mesh C N = C T (GPa) R coh max (MPa) δ c (mm) (a) 2

Numerical Validation

The accuracy of the proposed criteria is illustrated on a numerical analysis. In particular, these criteria concern the cohesive parameters but are a priori related to the bilinear shape of the cohesive law. The proposed numerical simulations aim to extend the validity of these criteria to an other shape for the cohesive law. Following [START_REF] Michel | An analytical and numerical study of the overall behaviour of metal-matrix composites[END_REF], a specific form of the cohesive law proposed by [START_REF] Perales | Two field multibody method for periodic homogenization in fracture mechanics of nonlinear heterogeneous materials[END_REF] is used in this section:

β ( [[u]] ) = D [0,δa] ( [[u]] ) + D [δa,δc] ( [[u]] ) δ c -[[u]] δ c /3 + [[u]] (39)
with

δ c = 3 w 9 -4ln4 1 C N + 1 C T
where w being a reference surface fracture energy and ln the natural logarithm (Figure 4-(b)).

The simulations concern the case of a unit square cell under a pure shearing loading and considering 2-D plane-strain conditions. The cell is meshed using triangular elements arranged in a "crossed-triangle" quadrilateral pattern (Figure 4-(a)). The bulk behavior is supposed to be elastic brittle (E M = 1 MPa, ν M = 1/7, Σ eq = 6 × 10 3 Pa). The software Xper [START_REF] Perales | A NonSmooth Contact Dynamics-based multi-domain solver -Code coupling (Xper) and application to fracture[END_REF] is used for the cohesive-volumetric finite element simulations.

As shown in Figure 4, the numerical results confirm that, even if, the local cohesive parameters are mesh-dependent, the overall fracture properties are mesh-independent: the difference between the critical separation of the cohesive law for the two meshes is about 15%; Figure 4-(b)), while the difference between the critical overall strain and failure energy for the two meshes is about 0%; Figure 4-(c-d). This mesh-independency is obtained since:

1. the finite element calculus convergence is reached, 2. the cohesive parameters are suitably calibrated for the given mesh type and size.

These results are consistent with previous remarks obtained in the literature (Tijssens et al. [START_REF] Tijssens | Numerical simulation of quasi-brittle fracture using damaging cohesive surfaces[END_REF] for instance).

Conclusion

Practical criteria for the calibration of cohesive zone parameters are obtained through a new micromechanical model. This model is based on the 14 study of the overall constitutive behavior of an equivalent 'matrix-inclusions' composite introduced as a representation of a cohesive-volumetric finite element scheme. The approach can be applied whatever the macroscopic triaxiality loading rate and the shape of the cohesive law, extending thus previous partial results from the literature. The case of a bilinear cohesive zone model leads to an overall damage model for quasi-brittle materials. This closed-form model allows to link, through an inverse analysis, all local cohesive parameters to the overall material properties at any given mesh size. The accuracy of the proposed approach and its wide ability to deal with various cohesive laws have been illustrated on a numerical analysis.

Figure 1 :

 1 Figure 1: Principle of the approach: from a cohesive-volumetric discretization to a 'matrixinclusions' composite; (left) 2-D illustration, (right) 3-D illustration.

  [a,b] (x) is the door function equal to 1 if x ∈ [a, b] and 0 otherwise, δ a is the opening displacement at the peak cohesive stress for pure normal or tangent loadings, i.e. R max N = C N δ a and R max T = C T δ a , and δ c is the critical opening displacement where the complete local failure occurs ( R coh = 0 when [[u]] = δ c ).

Figure 2 :

 2 Figure 2: A bilinear cohesive law: pure opening, u T = 0, (left) and pure shear separation, u N = 0, (right).

Figure 3 :

 3 Figure 3: Cohesive zone model with no mesh sensitivity. Right: the overall material behavior (Eq.(19)) obtained using the bilinear cohesive law (Eq. (22)). Left: The proposed criteria (Eqs. (21)-(30)) for the selection of the cohesive parameters (Table1): the case of a shear loading for a mesh set of parameters and a user tolerated elastic loss of 5%, i.e. R = 0.95 (the material properties are given in Table1)

Figure 4 :

 4 Figure4: Illustration of the mesh-independency of the overall behavior: (a) the unit cell with ''crossed-triangle quadrilateral" meshes, (b) the cohesive law (39) calibrated with respect to the obtained micromechanical criteria for two given mesh sizes, (c) the overall deviatoric behavior Σxy vs Exy and (d) the overall mesh-independent failure energy corresponding to the mesh-dependent local cohesive law.

Table 1 :

 1 Mechanical parameters used in Figure3. Top: material properties. Bottom: cohesive parameters calibrated using criteria (21), (29) and (30).

		.6	342.54	1.62
	(b)	5.2	342.54	0.81

Preprint submitted to Journal of Computational and AppliedMathematicsNovember 12, 2012


published or not. The documents may come   L'archive ouverte pluridisciplinaire

  cc-pVQZ PES for HOCO • 3261 RCCSD(T) /cc-pVQZ points were calculated • analytical 6D representation with 193 parameters in the bond-distance-bond-angle coordinates r1, r2, r3, 5, 6, 7 V(r1,r2,r3,5,6,7)=8 Cijklmn s1i s2j s3k (5-5ref)l (6-6ref)m cos(n7) using Morse coordinates for the stretches reference geometry = saddle-point geometry • standard deviation of the fit was 2for the quartic force fields developed recently for trans-HOCO, cis-HOCO, and the cis-HOCO anion 4,5 . Our results help to clear up a large discrepancy between previously reported vibrational perturbation theory (VPT) and vibrational configuration interaction (VCI) predictions for the torsional frequency.


Nicolas Nisse

Ronan Soares

On The Monotonicity of Process Number

Keywords: Graph Searching, Process Number, Monotonicity La Monotonie du Process Number Recherche dans les Graphes, Monotonie, Process Number

Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree-and pathdecomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.

Introduction

During the last few years, an important research effort has been done in order to design digraph decompositions that are as powerful as path-decomposition or tree-decomposition in the case of undirected graphs (e.g., see [START_REF] Ganian | Are there any good digraph width measures? In 5th In[END_REF]). Because graph searching games are equivalent to path-and tree-decompositions in undirected graphs, several attempts have been done to define such games in directed graphs [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF][START_REF] Berwanger | The dag-width of directed graphs[END_REF][START_REF] Hunter | Digraph measures: Kelly decompositions, games, and orderings[END_REF].

Graph Searching and monotonicity

In graph searching games, a team of searchers aims to capture a fugitive that stands at the vertices of a graph G (see [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF] for a survey). The fugitive can move arbitrary fast along the paths of G as long as it does not meet any searcher. A node v ∈ V (G) is clear if all paths from v to the node occupied by the fugitive contain a node occupied by a searcher. In particular, a node occupied by a searcher is clear. A vertex that is not clear is said contaminated. Given a graph G with all nodes initially contaminated, a strategy for the searchers is a sequence of the following two possible actions: (R 1 ) place a searcher at a node of G, or (R 2 ) remove a searcher from a node. A strategy is winning if it allows to capture the fugitive whatever it does or, equivalently, if all nodes are eventually clear. That is, in a winning strategy, a searcher eventually occupies the same vertex as the fugitive and the fugitive cannot move anymore (i.e., all the neighbors of its current position are occupied by searchers). The number of searchers used by a strategy is the maximum number of occupied vertices throughout all steps of the strategy and the search number of a graph G is the smallest integer k ≥ 1 such that there is a winning strategy using k searchers in G.

There are many variants of this problem arising due to different properties, or behaviors, given to the fugitive or to the searchers. For instance, if the fugitive is visible, the corresponding search number of a graph equals its tree-width plus one [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF]. On the other hand, if the fugitive is invisible, the search number is equal to the path-width plus one [START_REF] Kirousis | Searching and pebbling[END_REF]. The relationship between graph decompositions and search strategies mainly relies on the monotonicity property of these variants of graph searching. A strategy is said monotone if the area reachable by the fugitive is never increasing, i.e., once a node is clear it never becomes contaminated anymore. Equivalently, in the case of an invisible fugitive, a searcher cannot be removed from a node if it has a neighbor that is neither occupied nor has been occupied before, i.e., once a node has been occupied, the fugitive must not be able to reach it anymore. A variant of graph searching is said monotone if "recontamination does not help", i.e., for any graph with search number k, there is a winning monotone strategy using k searchers. That is, the number of searchers necessary to capture a fugitive considering only monotone strategies is not bigger than without this consideration.

The visible and invisible variants of graph searching were proven to be monotone in [START_REF] Lapaugh | Recontamination does not help to search a graph[END_REF] (invisible) and [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF] (visible). A more simpler proof in the invisible case has been proposed by Bienstock and Seymour [START_REF] Bienstock | Monotonicity in graph searching[END_REF], and a unified proof for both visible and the invisible case can be found in [START_REF] Mazoit | Monotonicity of non-deterministic graph searching[END_REF]. Note that there are graph searching variants that are not monotone in undirected graphs, i.e., imposing the monotonicity of strategies may increase the number of searchers required to capture the fugitive. In connected graph searching, the area that cannot be reached by the fugitive is restricted to be connected along all stages of the strategy. The connected graph searching variant has been proved to be not monotone when the fugitive is invisible [START_REF] Yang | Sweeping graphs with large clique number[END_REF] neither when the fugitive is visible [START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF].

Graph searching in directed graphs

In [START_REF] Johnson | Directed tree-width[END_REF], Johnson et al. defined the first variant of graph searching in directed graphs, related to directed tree-width. This variant, where the visible fugitive can move along directed cycles that are free of searchers, is however not monotone [START_REF] Adler | Directed tree-width examples[END_REF]. [START_REF] Berwanger | The dag-width of directed graphs[END_REF] proposed a variant where the visible fugitive can move along directed paths without searchers and [START_REF] Kreutzer | Digraph decompositions and monotonicity in digraph searching[END_REF] defined a variant where the invisible fugitive can move along directed paths without searchers only when a searcher is about to land at the node that the fugitive is currently occupying. Both these variants, respectively related to DAG-width and Kelly-width, are not monotone [START_REF] Kreutzer | Digraph decompositions and monotonicity in digraph searching[END_REF].

In some other cases, considering an invisible fugitive, more optimistic results have been provided. Barát defined the directed path-width related to a graph searching variant where the invisible fugitive is constrained to follow the direction of the arcs, i.e., it can move along directed paths free of searchers [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF]. Barát adapted the framework of Bienstock and Seymour [START_REF] Bienstock | Monotonicity in graph searching[END_REF] to show that, in this variant, the monotonicity cannot increases the number of searchers by more than one [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF]. Hunter then completed this proof to show the monotonicity of this variant [START_REF] Hunter | Losing the +1: Directed path-width games are monotone[END_REF]. Other variants that generalize the edge-graph searching (e.g., see [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF]) to directed graphs have been defined. Yang and Cao proved the monotonicity of strong and weak graph searching variants where the searchers can moreover slide along arcs either in both directions (strong) or in the direction of arcs (weak) [START_REF] Yang | Digraph strong searching: Monotonicity and complexity[END_REF][START_REF] Yang | On the monotonicity of weak searching[END_REF].

Process Number

Surprisingly, a variant of graph searching in directed graphs has been defined in the context of routing reconfiguration in WDM networks [START_REF] Coudert | Rerouting requests in wdm networks[END_REF]. An instance of the routing reconfiguration problem is defined by a network, a set of connections, an initial routing and a final routing. The networks is represented by an directed graph N . The set of connections is given by C ⊆ V (N ) × V (N ). An initial routing of these connections, I, is given by a set of directed paths in N joining each pair (a, b) ∈ C, with the restriction that two different paths do not share an arc of N , that is, these paths are disjoint arc-wise. The final routing, F , is represented in the same manner as the initial routing, i.e. a set of arc-wise disjoint paths joining each pair (a, b) ∈ C.

Let P i a be the path joining two vertices of a connection a in its initial routing and P f a be the path joining two vertices of a connection a in its final routing. The objective of the routing reconfiguration problem is change the routing of the connections from the initial routing, I, to the final routing, F , while minimizing some criteria. In order to do this the following operations are allowed on the current routing of the connections on the network, at the beginning, this is the initial routing. One first operation is interrupting a connection, a, that is we remove the path P i a ∈ I joining the two nodes of a from the current routing on the network. The second operation is to re-establish an interrupted connection a in its final routing, that is we add the path P f a ∈ F to the current routing on the network. The last operation allowed is to switch the routing of a connection, a, from its initial path P i a ∈ I to its final path P f a ∈ F on the current routing of the network. These operations are allowed as long as there is no conflict in the routing, that is all paths in the current routing are disjoint arc-wise. We remark that it is always possible to change from the initial routing to the final routing by interrupting every connection then re-establishing these connections in their final routing.

There are several criteria that can be used to measure how "good" are different the sequences of operations used to change the initial routing of the network to the final routing. For example, the total number of interruptions is studied in [START_REF] Cohen | Tradeoffs in process strategy games with application in the wdm reconfiguration problem[END_REF] and the maximum number of simultaneous interruptions during the re-routing is studied in [START_REF] Coudert | Rerouting requests in wdm networks[END_REF].

In the processing game, a team of searchers aims at processing all nodes of a digraph. A node is said safe if all its out-neighbors are either occupied or already processed. Given a digraph Inria D = (V, A) where initially all nodes are unoccupied and not processed, a monotone process strategy is a sequence (s 1 , . . . , s n ) of steps that results in processing all nodes of D, where each step s i is one of the following three moves.

M 1 : place a searcher at node v ∈ V ; M 2 : process a safe unoccupied node v ∈ V ; M 3 : process a safe occupied vertex v ∈ V and remove the searcher from it.

The minimum number of searchers used by a monotone process strategy of D is the monotone process number, denoted by monpr(D).

The relationship between the processing game and the routing reconfiguration problem is given by the dependency digraph. The dependency digraph D = (V, A) of an instance of the routing reconfiguration problem has one vertex for each connection in the routing reconfiguration instance and there is an arc e = (u, v) ∈ A if the connection given by u in its final routing shares an arc in the network with the connection given by v in its initial routing. Hence, a strategy for the process game gives a strategy for the routing reconfiguration problem. An important result is that for any directed graph D there is an instance of the reconfiguration problem such that D is its dependency digraph [START_REF] Cohen | Tradeoffs in process strategy games with application in the wdm reconfiguration problem[END_REF].

In [START_REF] Coudert | Rerouting requests in wdm networks[END_REF], it is shown that, for any digraph D, vs(D) ≤ monpr(D) ≤ vs(D) + 1 where vs(D) is the vertex separation of D. Moreover, to compute the monotone process number is NP-complete in general but it is polynomial in the class of graphs D with monpr(D) ≤ 2 [START_REF] Coudert | Characterization of graphs and digraphs with small process number[END_REF] and in the class of trees [START_REF] Coudert | A distributed algorithm for computing the node search number in trees[END_REF]. The relationship between the monotone process number of a digraph and its minimum feedback vertex set has been studied in [START_REF] Cohen | Tradeoffs in process strategy games with application in the wdm reconfiguration problem[END_REF]. The process number of digraphs has been mainly studied for its applications in the rerouting problem in WDM networks [START_REF] Coudert | Routing reconfiguration/process number: Coping wih two classes of services[END_REF][START_REF] Solano | A mixed-integer programing formulation for the lightpath reconfiguration problem[END_REF][START_REF] Solano | Analyzing two conflicting objectives of the wdm lightpath reconfiguration problem[END_REF]. Note also that, in undirected graphs (seen as symmetric digraphs1 ), the monotone processing game is equivalent to the monotone graph searching game where the invisible fugitive is captured if all the neighbors of its position are occupied, i.e., it is not anymore required that a searcher occupies the same node as the fugitive.

It is important to notice that the processing game when played on a symmetric digraph is not equivalent to the invisible graph searching games. Given a symmetric directed graph G the following inequation is true: s( Ḡ) -1 ≤ monpr(G) ≤ s( Ḡ), where Ḡ denotes the underlying graph of G and s( Ḡ) denotes the minimum number of searchers necessary to capture an invisible fugitive in Ḡ. Moreover, this inequality is tight. Let K n be the complete directed graph with n vertices, then s( Kn ) = monpr(K n ) + 1 and, for every directed graph G let G be the directed graph obtained from G by adding a loop to every vertex of G, then s( Ḡ ) = monpr(G ).

Let G be any directed graph, cn(G) denotes the number of searchers necessary to capture an invisible fugitive that can only move in the direction of the arcs as defined in [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF]. Then, for any directed graph G, cn(G) -1 ≤ monpr(G) ≤ cn(G), again the same examples above are sufficient to show that this inequality is tight in both sides.

In this work, we consider the more general variant of non necessarily monotone processing game. That is, we allow a processed node to become unprocessed. More precisely, a process strategy for a digraph D is a sequence (s 1 , . . . , s n ) of steps that results in processing all nodes of D, where each step s i consists of a move M 1 or M 2 or M 3 : process an occupied vertex v ∈ V and remove the searcher from it. If v was not safe then recontamination occurs: successively, all processed vertices (including v) that have an unoccupied and unprocessed out-neighbor become unprocessed.

The minimum number of searchers used by a process strategy of D is the process number, denoted by pr(D). In [START_REF] Coudert | A distributed algorithm for computing the node search number in trees[END_REF], it is proved that pr(D) = monpr(D) for any symmetric digraph D. In this work, we prove that the result holds for any digraph. Moreover, our monotonicity result allows us to prove that pr(D) = pr( ← -D) for any digraph D = (V, A), where

← - D = (V, ← - A ) and ← - A = {(a, b) : (b, a) ∈ A}.

recontamination does not help to process a digraph

In this section, we present the result that the process number is monotone, i.e. monpr(D) = pr(D) for any directed graph D. For this purpose, we use the techniques introduced in [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF] and adapted for directed graphs in [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF][START_REF] Yang | Digraph strong searching: Monotonicity and complexity[END_REF][START_REF] Yang | On the monotonicity of weak searching[END_REF]. More precisely, we first define the notion of mixed processing game and show its monotonicity thanks to an intermediate result dealing with crusades. Then, from any mixed process strategy we construct a process strategy with the same number of agents in a way that monotonicity is preserved.

Preliminaries

Throughout this section, we use the following notations. Let D = (V, A) be a digraph. For any v ∈ V , let N -(v) denote the set of in-neighbors of v. The border of a set X ⊆ A, denoted by δ(X), is the set of vertices that are the head of an arc in X and the tail of an arc in A \ X. For any X ⊆ A, X c denotes A \ X. First, we show that the border function δ is submodular.

Lemma 1. For any digraph D and any X, Y ⊆

A(D), |δ(X ∩ Y )| + |δ(X ∪ Y )| ≤ |δ(X)| + |δ(Y )|.
Proof. We show that every vertex counted in the left side of the equation is counted at least the same amount of times in the right side of the equation.

Let v ∈ δ(X ∪ Y ) ∪ δ(X ∩ Y ). If v ∈ δ(X ∩ Y ), let e 1 = (u, v) ∈ X ∩ Y and e 2 = (v, w) ∈ X c ∪ Y c . Therefore, either (v, w) ∈ X c and v ∈ δ(X), or (v, w) ∈ Y c and v ∈ δ(Y ). If v ∈ δ(X ∪ Y ), let e 1 = (u, v) ∈ X ∪ Y and e 2 = (v, w) ∈ X c ∩Y c . Therefore, either (u, v) ∈ X and v ∈ δ(X), or (u, v) ∈ Y and v ∈ δ(Y ). Finally, let us assume that v ∈ δ(X ∪ Y ) ∩ δ(X ∩ Y ). Because v ∈ δ(X ∩ Y ), there exists an edge e 1 = (u, v) ∈ X ∩ Y and because v ∈ δ(X ∪ Y ), there exists an edge e 2 = (v, w) ∈ X c ∩ Y c . Hence, v ∈ δ(X) ∩ δ(Y ).
Let D = (V, A) be a digraph whose no arcs are initially processed. A mixed process strategy of D is a sequence (s 1 , . . . , s n ) with the following actions that results in processing all arcs in A. R 1 (Place): place a searcher at an unoccupied node v ∈ V ; R 2 (Remove): remove a searcher from node v ∈ V ; if there were unprocessed arcs with tail v and v is now unoccupied, then recontamination occurs. That is, successively, any processed arc (u, w) ∈ A such that w is unoccupied and there is an unprocessed arc (w, z) becomes unprocessed.

R 3 (Head): process an arc (u, v) ∈ A if v ∈ V is occupied;
R 4 (Slide): slide the searcher at u along (u, v) ∈ A if u is occupied, v is not occupied and all arcs e = (u, v) with tail u are already processed, this process the arc (u, v); R 5 (Extend): process an arc (u, v) ∈ A if all arcs with tail v are already processed.

Inria

The number of searchers used by a mixed process strategy is the maximum number of occupied vertices over all steps of the strategy. The mixed process number, denoted by mpr(D), is the fewest number of searchers used by such a strategy. Moreover, in the mixed process number game, we say that a vertex, v, is processed if all edges with tail v are processed. A mixed process strategy is monotone if no recontamination occurs, i.e., once an arc has been processed, it must remain processed until the end of the strategy.

Next, we recall the definition of crusades used in [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF] and give these crusades an appropriate border function to work with the mixed process number game.

A

crusade in D = (V, A) is a sequence (X 0 , X 1 , . . . , X n ) of subsets of A such that X 0 = ∅, X n = E, and |X i \ X i-1 | ≤ 1, for 1 ≤ i ≤ n. The crusade has border k if |δ(X i )| ≤ k for 0 ≤ i ≤ n. A crusade is progressive if X 0 ⊂ X 1 ⊂ . . . ⊂ X n . Hence, in a progressive crusade (X 0 , X 1 , . . . , X n ), |X i \ X i-1 | = 1 for all i ≤ n.
Note that the notion of mixed strategy and crusade are different from the ones defined in [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF].

Monotonicity

Lemma 2. Let D be a digraph. If mpr(D) ≤ k, then D admits a crusade with border k.

Proof. Let S = (s 1 , . . . , s n ) be a mixed process strategy of D = (V, A) that uses at most k searchers. For any 0 < i ≤ n, let A i be the set of processed arcs and Z i be the set of occupied vertices after the step s i . Moreover, let

A 0 = Z 0 = ∅.
By definition of a mixed process strategy, at most one arc is processed in each step s i (one arc is processed if

s i corresponds to R 3 , R 4 or R 5 ), hence |A i \ A i-1 | ≤ 1 for any 1 ≤ i ≤ n.
After the last step s n of S, all the arcs of the graph must be processed, hence A n = A. This proves that C = (A 0 , . . . , A n ) is a crusade.

It remains to show that δ(A i ) ≤ k for every 0 ≤ i ≤ n. To do so, we prove by induction that δ(A i ) ⊆ Z i for any 1 ≤ i ≤ n. It is clearly true for i = 0. Assume that δ(A i-1 ) ⊆ Z i-1 for some i, 0 ≤ i < n. We prove that δ(A i ) ⊆ Z i :

• If s i is R 1 (Place), then A i = A i-1 and thus δ(A i ) = δ(A i-1 ) ⊆ Z i-1 ⊆ Z i .
• If s i is R 2 (Remove) at a vertex v, let u be a vertex of δ(A i ), hence there is an arc e 1 = (w 1 , u) ∈ A i and an arc e 2 = (u, w 2 ) ∈ A \ A i , therefore u ∈ Z i , otherwise e 1 would also become unprocessed

in step i making u / ∈ δ(X i ), hence δ(A i ) ⊆ Z i . • If s i is R 3 (Head), then A i = A i-1 ∪ {(u, v)} and δ(A i ) \ δ(A i-1 ) ⊆ {v}. Since v must be occupied, we have v ∈ Z i = Z i-1 , by induction δ(A i-1 ) ⊆ Z i-1 , and therefore δ(A i ) ⊆ Z i . • If s i is R 4 (Slide) at an edge e = (u, v), then A i = A i-1 ∪ {(u, v)} and Z i = (Z i-1 \ {u}) ∪ {v}.
Since all arcs with tail u are processed after this step, u / ∈ δ(A i ). Moreover,

δ(A i ) \ δ(A i-1 ) ⊆ {v}. Hence δ(A i ) ⊆ Z i . • If s i is R 5 (Extend), then A i = A i-1 ∪ {(u, v)} and Z i = Z i-1 . Since all arcs with tail v must be already processed, δ(A i ) = δ(A i-1 ) ⊆ Z i-1 = Z i . Lemma 3.
If there is a crusade of D = (V, A) with border k, then there is a progressive crusade with border k.

Proof. Let C = (X 0 , . . . , X n ) be a crusade of D with border k such that:

n i=0 |δ(X i )| is mini- mum, and subject to this, n i=0 |X i | is minimum. We show that C is progressive. Let 0 < i ≤ n, we show that X i-1 ⊂ X i : • Assume first that |X i \ X i-1 | = 0, then X i ⊆ X i-1 . Hence, (X 0 , . . . , X i-1 , X i+1 , . . . , X n ) is a crusade with border k, contradicting the minimality of n i=0 |X i |. Thus, |X i \ X i-1 | = 1.
• Then assume that |δ(X i-

1 ∪X i )| < |δ(X i )|, hence (X 0 , . . . , X i-1 , X i-1 ∪X i , X i+1 , . . . , X n ) is
a crusade with at most k searchers, contradicting the minimality of

n i=0 |δ(X i )|. Therefore |δ(X i-1 ∪ X i )| ≥ |δ(X i )|. • By Lemma 1, |δ(X i-1 ∩ X i )| + |δ(X i-1 ∪ X i )| ≤ |δ(X i-1 )| + |δ(X i )|. Hence, by previous item, |δ(X i-1 ∩ X i )| ≤ |δ(X i-1 )|. Therefore, (X 0 , . . . , X i-2 , X i-1 ∩ X i , X i , . . . , X n ) is a crusade with at most k searchers. From the minimality of n i=0 |X i | we have that |X i-1 ∩ X i | ≥ |X i-1 |, hence X i-1 ⊆ X i . Lemma 4.
If there is a progressive crusade of D = (V, A) with border k, then there is a monotone mixed process strategy using at most k searchers.

Proof. Let C = (X 0 , . . . , X n ) be a progressive crusade of D using at most k searchers. We build a a monotone mixed process strategy S = (s 1 , . . . , s n ) of D with the following properties. For any 0 < i ≤ n , let A i be the set of processed arcs and let Z i be the set of occupied vertices after step s i . Let A 0 = Z 0 = ∅. There are 0 = j 0 < j 1 < j 2 < • • • < j n = n such that:

1. for any 0 ≤ i ≤ n, A ji = X i ; 2. for any 0 < i ≤ n and for any j i-1 < < j i , Z ⊆ δ(X i ) or Z ⊆ δ(X i-1 ), and Z ji = δ(X i ).

Starting with S = ∅, the two above properties hold for i = 0. Let 0 < i ≤ n and let us assume that (s 1 , . . . , s ji-1 ) is a sequence of actions that satisfies the two above properties for any 0 ≤ j < i. We will build the next steps of the strategy until s ji . Let X i \ X i-1 = {e i }, where e i = (u, v). Note that δ(X i ) \ δ(X i-1 ) ⊆ {v} and δ(X i-1 ) \ δ(X i ) ⊆ {u, v}. We have several cases to consider:

• let us first assume that v ∈ δ(X i-1 ). Hence, v ∈ Z ji-1 and there is a searcher at v after step s ji-1 . We define the step s ji-1+1 to be R 3 (Head) at e i , i.e., the arc e i is processed.

-If moreover v / ∈ δ(X i ) then we define the step s ji-1+2 to be R 2 at v, i.e., we remove the searcher at v. Because v / ∈ δ(X i ) and (u, v) is processed, there are no unprocessed arcs with tail v and therefore, no recontamination occurs.

Let k = j i-1 + 3 if v / ∈ δ(X i ) and k = j i-1 + 2 otherwise.
-Finally, if u ∈ δ(X i-1 ) \ δ(X i ), then we define the step s k to be R 2 at u, i.e., we remove the searcher at u. Because u ∈ δ(X i-1 ), there is an arc with head u that was processed after step s ji-1 . Because u / ∈ δ(X i ) and (u, v) is processed, there are now no unprocessed arcs with tail u and therefore, no recontamination occurs.

Hence, j

i-1 + 1 ≤ j i ≤ j i-1 + 3. Clearly, for any j i-1 + 1 ≤ ≤ j i-1 + 3, Z ⊆ δ(X i-1 )
and δ(X i ) = Z ji in all cases. Moreover, in all cases, no recontamination occurs and then A ji = X i .

• Now, let us assume that v / ∈ δ(X i-1 ). By induction, there was no searcher at v after step s ji-1 .

-First, let us consider the case when u ∈ δ(X i-1 ):

Inria * if v ∈ δ(X i ) and u ∈ δ(X i ):
Let us define the step s ji-1+1 to be R 1 at v, i.e., a searcher is placed at v, and the step s ji = s ji-1+2 is defined as R 3 (Head) at e i , i.e., the edge e i is processed. Clearly,

A ji = A ji-1 ∪ {e i } and Z ji-1+1 = Z ji = Z ji-1 ∪ {v} = δ(X i ). * if v ∈ δ(X i ) and u /
∈ δ(X i ): in that case, the only arc in A \ X i-1 which has u as tail is e i , otherwise u ∈ δ(X i ). Therefore we define the step s ji-1+1 = s ji to be R 4 through e i , i.e., the searcher at u slides to v processing e i . Note that no recontamination occurs and

A ji = A ji-1 ∪{e i } = X i-1 ∪{e i } = X i . The induction hypothesis holds since Z ji = (Z ji-1 \ {u}) ∪ {v} = (δ(X i-1 ) \ {u}) ∪ {v} = δ(X i ). * if v /
∈ δ(X i ) then there are no arcs with tail v that are in A \ X i-1 . Hence, we can define the step s ji-1+1 to be R 5 (extend) at e i , i.e., e i is processed. If moreover u / ∈ δ(X i ), let s ji = s ji-1+2 be defined as R 2 at u, i.e., the searcher at u is removed. Because u ∈ δ(X i-1 ) \ δ(X i ) and (u, v) is now processed, there are no unprocessed arcs with tail u and therefore, no recontamination occurs. Hence, j i-1 + 1 ≤ j i ≤ j i-1 + 2 and the induction hypothesis holds in both cases.

-Finally, consider the case when u / ∈ δ(X i-1 ). Note that, in that case, since u / ∈ δ(X i-1 ) and u is a tail of e i ∈ X i , then u / ∈ δ(X i ). * if v ∈ δ(X i ) then we define the step s ji-1+1 to be R 1 at v, i.e., a searcher is placed at v, and s ji = s ji-1+2 to be R 3 (Head) at e i , i.e., e i is processed. The induction hypothesis holds. * if v / ∈ δ(X i ), since e i ∈ X i , then there are no arcs with tail v that are in A \ X i-1 . Hence we can defined the step s ji = s ji-1+1 as R 5 (Extend) at e i , i.e., e i is processed. The induction hypothesis holds.

Therefore, S = (s 1 , . . . , s jn ) satisfies the two properties, and S is a monotone mixed process strategy using at most k searchers in D, since, for all 1 ≤ i ≤ j n , we have that

|Z i | ≤ k, for all 1 ≤ i < j n , A i ⊆ A i+1 , and A jn = X n = A.
In what follows, let mpr( D) be the digraph obtained from any digraph D = (V, A) by adding a copy of every arc of D.

Theorem 5. For any digraph D = (V, A), monpr(D) ≤ mpr( D) ≤ pr(D).

Proof. We first show that mpr( D) ≤ pr(D).

Let S p = (s 1 , . . . , s n ) be a process strategy for D using k searchers. We define a mixed process strategy S m = (m 1 , . . . , m j ) using at most k searchers for D. Let P i be the set of processed vertices at step i ≤ n in S p and let M j be the set of vertices u such that, at step m j in S m , all arcs with u as tail are processed. Also, let O p i , resp., O m i , be the set of vertices occupied by a searcher at step s i in S p , resp., at step m i in S m .

For any 0 < i ≤ n, we build a phase of S m according to s i . That is, depending on the type of rule applied in s i , we add a sequence of moves m ji-1+1 , m ji-1+1 , . . . , m ji in S m such that P i ⊆ M ji . Hence, since P n = V , at the last step all arcs are processed. To do this, assume that m 1 , . . . , m ji-1 are already defined based on (s 1 , . . . , s i-1 ) and that

P i-1 ⊆ M ji-1 . Moreover, assume that O p i-1 = O m ji-1 .
We define m ji-1+1 , m ji-1+1 , . . . , m ji depending on which rule is applied in s i :

• If s i is a place operation at vertex v (move M 1 ), then let us define the step m ji-1+1 to be R 1 at vertex v, i.e., a searcher is placed at v. Then, let {e 1 , • • • , e r } be the set of arcs with head v. For any ∈ [2, r + 1], let us define the step m ji-1+ to be R 3 (Head) at e . That is, all arcs with head v are sequentially processed.

Hence, j i = j i-1 + r + 1. The claim holds since P i = P i-1 ⊆ M ji-1 ⊆ M ji , and moreover, for any

j i-1 < ≤ j i , O m = O p i = O p i-1 ∪ {v}. • If s i consists in processing an unoccupied vertex v (move M 2 ), then after step s i-1 in
S p , all vertices that are in the out-neighborhood of v are already processed. Hence, by the construction of S m , after step s ji-1 in S m , all arcs with tail v are already processed.

Moreover, because v / ∈ O p i-1 = O m ji-1 then v is also unoccupied at step j i-1 of S m . Hence, let {e 1 , • • • , e r }
be the set of arcs with head v. For any 1 ≤ ≤ r, let us define m ji-1+ as R 5 (Extend) at e i . That is, all arcs with head v are sequentially processed.

In that case, j i = j i-1 + r. The claim holds, since, in particular, v ∈ M ji-1 .

• Now consider the case when s i consists in processing an occupied vertex v and removing the searcher at v (move M 3 ). Let us define the step m ji-1+1 = m ji to be R 2 at v, i.e., the searcher at v is removed. In the case of recontamination in S m , all vertices, v, in v ∈ M ji-1 \ M ji are tail of some arc e such that there is a path from v avoiding agents and passing through e that reaches an unprocessed arc in D. Therefore, v also becomes unprocessed in S p , i.e. v ∈ P i-1 \ P i . Hence, the claim holds.

Therefore, S m is a mixed process strategy for D using at most k searchers. Now, let us show that monpr(D) ≤ mpr( D). By Lemmas 2, 3 and 4, there exists a monotone mixed process strategy using mpr( D) searchers in D. Let S m = (m 1 , . . . , m n ) be such a strategy. We first notice that if there is a step m i (1 ≤ i ≤ n) that applies a rule of type R 4 (Slide) through an arc e 1 = (u, v), then the second arc e 2 = (u, v) must be processed and there must be no searcher at v. Hence it is possible to replace the step m i by the following: first remove the agent from u, without recontaminating any arc (since otherwise e 2 would have been recontaminated before), place the agent at v and apply R 3 (Head) operation at e 1 . Therefore, we may assume that S m never applies moves of type R 4 .

Another remark is that, if the step m i consists in processing an arc (u, v) such that u is occupied and all arcs with u as tail are already processed, then we may assume that the step m i+1 applies the rule R 2 to u, i.e., the searcher at u is removed (and no recontamination occurs). Indeed, after step m i , the searcher at u is not used to preserve from recontamination because all its outgoing arcs are processed and because the strategy is monotone. Moreover, if this searcher was used to process one in-coming arc of u at a step further, we can instead use the extend rule R 5 . Finally, by previous remark, this searcher is never used to apply rule R 4 .

Let M i be the set of unoccupied vertices u such that all arcs with tail u are already processed after step m i .

We now define a monotone process strategy S p = (s 1 , . . . , s n ) for D that uses at most mpr( D) searchers. Let P i be the set of processed vertices at step i ≤ n in S p and let M i be the set of unoccupied vertices u such that all arcs with tail u are already processed after step m i in S m . Also, let O p i , resp., O m i , be the set of vertices occupied by a searcher at step s i in S p , resp., at step m i in S m . Assume that (s 1 , . . . , s ji-1 ) is already defined such that O m i-1 = O p i-1 , and M i-1 ⊆ P i-1 or (M i-1 ⊆ P i-1 ∪ {v} and m i consists in removing a searcher from some node v). We define s i depending on m i :

• Assume first that m i consists in placing a searcher at vertex v (R 1 ). Then, let s i consist in placing a searcher at v (M 1 ). The claim holds, since

M i ⊆ M i and O p i = O p i-1 ∪ {v} = O m i-1 ∪ {v} = O m i .

Inria

• If m i consists in removing a searcher from a vertex v (R 2 ) then, since S m is monotone, recontamination does not happen. That is, there are no unoccupied directed path from a process arc to an unprocessed one. Note that v is occupied since

O m i-1 = O p i-1 .
In that case, let s i consists in processing v and removing the searcher at v (M 3 ), this is possible since all out-neighbors of v are either occupied or processed in S m .

The claim holds since P ji = P ji-1 ∪ {v} and M i = M i-1 ∪ {v}, and moreover,

O p i = O p i-1 \ {v} = O m i-1 \ {v} = O m i .
• If m i consists in processing an arc e = (u, v) ∈ A(D) (R 3 or R 5 ). Then, if e is the only unprocessed arc with tail u before m i then -If u is occupied by the remark above, the next step m i+1 consists in removing the searcher at u. In that case, s i consists in doing nothing and we have M i ⊆ P i ∪ {u} and O m i = O p i . -Else, let s i consists in processing u (applying M 2 ). Again, the properties hold.

If m i consists in processing an arc (u, v) ∈ A(D) that is not the last unprocessed out-going arc of u (in particular, we may assume it is the case for all arcs in A( D) \ A(D)), then s i consists in doing nothing and the properties hold. Therefore, S p is a monotone process strategy for D using at most mpr( D) searchers.

Process Decomposition

In this section we define a digraph decomposition that is equivalent to (monotone) process strategies. This allows us to prove that the process number is invariant when reversing all arcs of a digraph. Let D = (V, A) be a digraph.

A process decomposition of D is a sequence of pairs P = ((W 1 , X 1 ), • • • , (W t , X t )) such that:

• for any 1 ≤ i ≤ t, W i ⊆ V and X i ⊆ V ; • (X 1 , • • • , X t ) is a partition of V \ t i=1 W i ; • ∀i ≤ j ≤ k, W i ∩ W k ⊆ W j ;
• X i induces a Directed Acyclic Graph (DAG), for any 1 ≤ i ≤ t;

• ∀(u, v) ∈ A, ∃j ≤ i such that v ∈ W j ∪ X j and u ∈ W i ∪ X i .
The width of a process decomposition is given by max 1≤i≤n |W i |, and the process-width, denoted by prw(D), of a digraph D is given by the minimum width over all process decompositions of D.

A first result, shows that reversing the arcs of a digraph does not change its process width. Let ← -D be the digraph obtained by reversing the sense of the arcs of a digraph D = (V, A). Lemma 6. For any digraph D, prw(D) = prw( ← -D).

Proof. Let P = ((W 1 , X 1 ), . . . , (W t , X t )) be a process decomposition for D with width w. Let ← -P = ((W t , X t ), . . . , (W 1 , X 1 )). Clearly, the first three properties of process decomposition hold, and the width of

← - P is w. It remains to show that ∀(u, v) ∈ A( ← - D), ∃i ≤ j such that u ∈ W i ∪ X i and v ∈ W j ∪ X j .
To do that, consider an edge (u, v) ∈ A( ← -D), since P is a process decomposition of D and vu ∈ A(D), we have that for some j ≤ i, v ∈ W j ∪ X j and u ∈ W i ∪ X i , therefore ← -P is a process decomposition of ← -D.

Theorem 7. For any digraph D, pr(D) = prw(D).

Proof. By Theorem 1, pr(D) = monpr(D). Hence, we show that monpr(D) = prw(D).

To show that prw(D) ≥ monpr(D) let P = ((W 1 , X 1 ), . . . , (W t , X t )) be a process decomposition of D with width w. We construct a monotone process strategy of D using at most w searchers. For any 1 ≤ i ≤ t, we define the sequence of moves (Phase i) from (W i , X i ), such that, after this sequence, the vertices of W i ∩ W i+1 are occupied by searchers and the vertices in i j=1 (W j ∪ X j ) \ W i+1 have been processed.

At phase i + 1, we first place searchers at the vertices of W i+1 \ W i . Then, in the inverse of a topological ordering of the DAG induced by X i+1 , vertices of X i+1 are processed. This is possible because, for any vertex v in X i+1 , any out-neighbor u of v is in i+1 j=1 X j ∪ W j and so u is either already processed or occupied. Finally, searchers are removed from the vertices in W i+1 \ W i+2 and these vertices are processed. Again, this is valid since all out-neighbor of a vertex in W i+1 \ W i+2 belongs to i+1 j=1 X j ∪ W j (by the last property of the decomposition). Clearly, such a strategy is monotone and uses at most w searchers, hence monpr(D) ≤ prw(D). Now, let us show that monpr(D) ≥ prw(D). Let S = (s 1 , • • • , s t ) be a monotone process strategy of D using k searchers. We remark that a searcher is removed from a vertex v, this vertex is also processed during the same step. We construct a process decomposition of D with width at most k. For any 1 ≤ i ≤ t, let (W i , X i ) be defined as follows. Let (W 0 , X 0 ) = (∅, ∅):

• M 1 : if s i consists in placing a searcher at vertex v, then W i = W i-1 ∪ {v} and X i = ∅;

• M 2 : if s i consists in processing an unoccupied vertex v, then W i = W i-1 and X i = {v};

• M 3 : if s i consists in processing an occupied vertex v removing the searcher at v, then W i = W i-1 \ {v} and X i = ∅.

It is easy to see that (X 1 , • • • , X t ) is a partition of V \ t i=1 W i since all vertices are either occupied or processed (only once) without being occupied. Moreover, any X i being reduced to at most a singleton induces a DAG. By the rules of the monotone process strategy, any vertex is occupied at most once (i.e., there are no two steps of S that consist in placing a searcher at the same vertex), and so ∀i ≤ j ≤ k, W i ∩ W k ⊆ W j .

Finally, let (u, v) ∈ A and let i be the greatest integer such that u ∈ W i ∪ X i and let j be the smallest integer such that v ∈ W j ∪ X j . For purpose of contradiction, assume that j > i. Then, u is processed at step s i while its out-neighbor v is neither processed nor occupied at step i, since j > i, a contradiction.

Clearly, max i≤t |W i | ≤ k.

Remark 1. Note that, by the proof of Theorem 7, for any digraph D, there is an optimal process decomposition ((W 1 , X 1 ), . . . , (W t , X t )) of D such that X i has size at most one for any i ≤ t. Inria

Conclusion

We have shown that the same number of agents are needed even if we allow recontamination in the process number game. We defined a decomposition that is equivalent to the process number game. It is still not known whether or not there is a dual structure for this decomposition, in the same manner as a bramble is a dual structure for the tree-decomposition.

Corollary 1 .

 1 Since, for any digraph D, pr(D) ≤ monpr(D), we obtain the next corollary: recontamination does not help to process a digraph, i.e., for any digraph D, pr(D) = monpr(D).

Corollary 2 .

 2 Given a digraph D = (V, A) and ← -D, the graph obtained from D by reversing all the arcs, then monpr(D) = monpr( ← -D) = pr(D) = pr( ← -D).

RR n°8132

A digraph D = (V, A) is symmetric if, for any (a, b) ∈ A, then (b, a) ∈ A. RR n°8132

Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399


Nicolas Holzschuch

Open Archives and the Invisible College: driving forces towards a new publication model

Publication methods have been and are constantly evolving in Computer Science. My position, expressed in this paper, is that in this current landscape, there is room for a new publication model, combining OpenArchives for immediate access with editorial peer-reviewing. A key interest of this proposal is that peer-reviewing happens after the results have been released. I start by reviewing recent changes in publication methods in Computer Science and some of their consequences, drawing practical examples from Computer Graphics. I then review existing forces that are contributing to changes in publication methods, and how these forces push towards a new publication model. I describe this model, and review practical requirements to make it work.

Publications in Computer Science: a changing landscape

Computer Science has long been an outlier among scientific disciplines. Research in our domain is published preferably in conferences and workshops, while in other disciplines the usual benchmark is papers published in journals. This specificity is partly related to a positive feedback loop: we submit papers in conferences because they have a strong reputation in the field, conferences select from a larger pool of papers, improving the overall quality of papers published, thus increasing the reputation of the conference. Papers published in selective conferences have a larger impact2 . The fast reviewing cycle in conferences is also attractive for the authors, especially at an early stage of their scientific career.

The classical landscape has been evolving in recent years, with cooperation and exchanges between conferences and journals. This cooperation can take multiple forms3 :

• The conference proceedings are published as a regular issue of a journal (for example the Siggraph proceedings as issue 3 of ACM Transactions on Graphics, since 2002). Most major conferences in the field are now following this model. • Selected papers from the conference are published in a journal, after a second review cycle and addition of extra material. This model is preferred for less selective conferences. • Papers from a journal can be presented at the conference, either in a separate session or merged with regular conference papers (such as ACM Transactions on Graphics papers at Siggraph since 2010). Most major journals are offering this service. These changes have brought Computer Science (or at least, Computer Graphics) more in line with the other disciplines; they also had a positive impact on the journals: the total review cycle-the amount of time between the day the paper is submitted for review and the day it is published-is now less than a year for all major journals in Computer Graphics, with a first decision in less than 4 months. An interesting side effect is that the impact factor of the journals has been significantly increased by these changes. This could be an experimental confirmation of the study by Chen and Konstan. Figure 1 shows the impact factor of three major journals in Computer Graphics as a function of time. The first year after Siggraph proceedings were added to ACM Transactions on Graphics, the impact factor of the journal decreased because the number of citable papers had been multiplied by 6. After a short transition, the impact factor was multiplied by 2.

A less positive side effect of this convergence between conferences and journals is that journals are more likely to reject papers, not because they do not have the sufficient scientific quality, but because guiding and nurturing them until they are worthy of publication would take too long. For at least one major journal, if three reviewers say "Accept with major revisions", the editor has to reject the paper.

Forces driving towards further changes

Several forces can be seen as driving current and future changes in the publication culture. Some are specific to Computer Science, while others are more generic.

Open Access mandates:

Any publications by researchers that are employees of the United States government is in the public domain 4 . This policy has had little practical impact because the federal government employs few researchers, but it has been the inspiration for other Open Access mandates in recent years. Research funded by the NIH5 must be placed in an open archive within 12 months of publication. Major research universities (including, but not limited to, the MIT6 and Harvard7 ) require that work authored by their employees must be placed in an Open Archive. The European Union is considering a similar requirement on research projects it finances8 .

Several reasons explain this strong push for Open Access. Some of them are ethical: these research have been funded by the public, and the public should be able to see the results. Others are practical: the subscription I argue that the convergence between journals and conferences is unlikely to slow down or be reversed, because it answers the needs of journals, conferences and researchers: it increases the number of high quality papers published in journals, it gives conferences a better visibility outside of Computer Science and it helps researchers in their job applications and tenure reviews. Yet it leaves an empty niche in the publication landscape for Computer Science. Because of their short review cycle, conferences in Computer Science tend to accept for publication only papers that are close to perfection, both in their scientific content and presentation. Shortening the review cycle for journals has brought them in line with conferences in that respect: a paper with great scientific content but poorly written is now likely to be rejected at major journals, because improving the writing would take too long. The same applies to ideas that are too original or too innovative. Author can of course revise and resubmit their papers, either at the same venue or at a different venue. But this increases the delay before the idea is finally available for the public. Many shareholders, including those from the industry, are pushing for faster dissemination of ideas.

To fill this niche, I suggest to revert the order of publication: first, the author makes his paper available by placing it in an Open Archive. Once it is there, it becomes open for both comments (by the community) and reviewing (by journals):

• Comments by the community allow a discussion around the paper and the ideas or algorithms it presents.

It provides several levels of information: opinion about the paper or its usefulness, replicability. It is also a good place to ask about details of the algorithm or implementation details. It reproduces the discussion in emails, social networks and conferences, but the questions and answers can be made visible to all. • Reviewing by journals gives a level of scientific certification to the paper. Journal editors assign reviewers to a paper, and based on their reviews decides to accept the paper in this journal. This acceptance is both a stamp of quality for the paper (it appears on the paper web page), and a way to access the paper from the journal portal. Based on readers comments or reviews, the author can revise his paper (either minor or major revisions). Reviewers for a journal can be anonymous or not (single blind reviewing). New ideas will be available faster, but we maintain the scientific validation through peer-reviewing. This system has been proposed already by several people, in different domains. It is both feasible and desirable at this point in time, but we must meet several conditions:

• We need an open-archive system: ○ that can manage the discussions around a paper, both public and private. ○ that can handle all kind of supplemental materials (pictures, sample code, videos, models) both in the paper and the comments. ○ robust enough to handle the load, and nimble enough to implement the required changes. ○ shared by researchers from different research domains.

• We need the researchers to trust the system: ○ from the scientific point of view, this means high-quality scientific reviewing and editing. ○ from a practical point of view, the system must have independence, durability and stability. ○ to avoid negative incentives, I suggest financial independence from the number of accepted papers (unlike in the Gold Open-Access model). These requirements point towards a central repository such as HAL12 . This repository would be managed by a consortium and have financial independence through backup from public shareholders, such as states and research institutes. INRIA is ready to support this new publication model.

Figure 1 :

 1 Figure 1: Evolution over time of the Impact Factor for several reviews in Computer Graphics. Merging a major conference (Siggraph) with a journal (ACM Transactions on Graphics) increased the impact factor of the journal. Left: 2-years IF measured with ISI Web of Knowledge. Right: number of citations per document over 2 years, measured with ScimagoJR (using Scopus). Adding Siggraph Asia in 2008 doubled the number of citable papers.

INRIA, France.

Jilin Chen and Joseph A. Konstan. 2010. Conference paper selectivity and impact. Commun.ACM, vol. 53, n° 6 (June 2010), 79-83. DOI=10.1145/1743546.1743569

I am taking examples from the field of Computer Graphics, mainly because I happen to know it better, but also because the convergence between journals and conferences started earlier.

US Code, Title 17, Chapter 1, § 105: Subject matter of copyright: United States Government works.

National Institutes of Health Public Access. 2008. http://publicaccess.nih.gov/

MIT Faculty Open Access Policy. 2009. http://libraries.mit.edu/sites/scholarly/mit-open-access/open-access-at-mit/mit-open-access-policy/

Harvard University. 2010. Open Access Policies, http://osc.hul.harvard.edu/policies

Neelie Kroes. 2012. New Commission measures to open up science in Europe. http://blogs.ec.europa.eu/neelie-kroes/open-science/

Per H. Christensen. 2008. Point-Based Approximate Color Bleeding. Pixar Technical Memo #08-01. Cited 24 times according to Google Scholar, implemented by Pixar, ILM and Dreamworks Animation as early as 2008.

In Computer Graphics, researchers and industry developers are using mainly Twitter and blogs.

Including support by the Siggraph Asia 2009 technical papers chair. For more on this, please see, e.g.: http://www.realtimerendering.com/blog/ke-sen-huangs-paper-pages-are-down-will-soon-go-back-up/.

Laurent Romary and Chris Armbruster. 2010. Beyond institutional repositories. International Journal of Digital Library Systems, vol. 1, n° 1, p. 44-61. DOI: 10.4018/jdls.2010102703.

costs for major publishers are high, reaching a point where even major research institutions can not afford them. Open Access mandates are seen as a way to drive these subscription costs down.

The role of the industry:

Another specificity of Computer Science is the strong connection between our research and the industry. Companies are working with researchers, re-using results from scientific papers, sometimes funding research groups. Major companies have their own research centers. This strong connection is visible in the industrial exhibits at major conferences. This relationship between research and industry is not a one-way street: the industry also does research and publish; 50% of technical papers at Siggraph 2011 had at least one author working for a private company (the same proportion holds for Sigcomm 2011 and other conferences). Some of these technical papers from the industry are seminal, long-term research papers.

This strong connection is a driving force behind many important research problems. It is also a force pushing for fast dissemination of results. Private companies want fast results and quick publications. In that respect, they might be more impatient than academic researchers: one of the most important recent contributions in Global Illumination came from the industry and was only published as a technical report 9 , yet it had a major impact on both research and industry. The author chose the technical report format for faster dissemination and discussion.

Individuals and Social Networks:

Most publishers in Computer Science have opted for a Green Open-Access model: authors can place the final version of the manuscript, post-reviewing, on a personal web site or institutional repository. Researchers have embraced this model because they can propagate their results faster: final versions of papers are published as soon as authors receive the "final accept", several months before the paper is available on the publisher digital library (usually on the first day of the conference). This quick publication the web has empowered individuals, and changed the way we do research: papers are downloaded, discussed on social networks and sometimes replicated months before the actual presentation at the conference. The discussion on social networks 10 is a little like the discussion you can have after presentations at a conference, but more lively: people are less shy, don't hesitate to engage the author, ask questions, or to point out that this paper is useful (or not) for their industrial problems. This discussion looks a little like an Invisible College, a group of people working together even though they are not physically in the same room.

This immediate publication on web pages has also filled a need in the community. There is always a delay between the time when notice of acceptance is sent to authors and the time when the conference program is made public, with the full list of accepted papers. Researchers often complain that they would like to see the full list of accepted papers earlier. Now, armed with a classical web search engine, anyone can assemble a list of papers accepted at a conference, within hours of the decision. It might be a partial list, but that is better than no list. More importantly, researchers can share the list of papers they have found, and this list will likely include links towards the authors version of the papers. http://kesen.realtimerendering.com/ provides this list of papers, for all major conferences in Computer Graphics since 2000; these pages have become an invaluable tool for all researchers. In 2009, ACM tried to take them down arguing about copyright issues, but quickly reversed its position after a very strong show of support from the community 11 .