Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

AnnexeA

Un autre exemple complet de fusion

consensuelle

Dans cette annexe, nous illustrons notre algorithme de réconciliation (chap. 3 sect. 3.2) sur le workflow d'édition coopérative présenté comme exemple dans le chapitre 2 (figure 2.5 page 27). Pour rappel le document t conforme à la grammaire Gexpl est projeté suivant les vues V1 = {A,B} et V2 = {A,C} pour engendrer les forêts (répliques partielles) tv1 et _tv2. Ces répliques partielles sont éditées respectivement sur les sites 1 et 2 ; le coauteur 1 (resp. le co-auteur 2) ne peut éditer que les bourgeons de type A (resp. C) (c'est à dire que V (1)

edit = {A} et Vedit(2) = {C}) ; les documents mis à jour sont respectivement _tma j

v1 et

_tma j

v2 . Nous allons donc fusionner _tma j

v1 et _tma j

v2 grâce à notre algorithme. Le but recherché ici est celui de montrer que notre algorithme prend en compte les documents non clos (tma j

v2 )

et aussi qu'il peut s'appliquer lorsque la fusion n'engendre pas de conflits.

Les schémas des règles de transition

Rappelons que les schémas des transitions (complétés pour prendre en compte les documents non clos) de l'automate permettant de représenter les expansions des répliques partielles suivant la vue V1 = {A,B} lorsqu'on associe les symboles de Dyck '(' et ')' (resp. '[' et ']') au symbole visible A (resp. B) et qu'on associe les symboles '(_W' et ')_W' (resp. '[_W' et ']_W') au bourgeon A_W (resp. B_W) de type A (resp. B), sont les suivants :

hA,w1i -? (P1,[hC,ui,hB,vi]) si w1 = u[v]

hA,w2i -? (P1,[hC,ui,hB,w11i]) si w2 = uw11 avec w11 = [W]W

hA,w3i -? (P2,[]) si w3 = E

hA,w4i -? (A_W,[]) si w4 = (_W )_W

hB,w5i -? (P3,[hC,ui,hA,vi]) si w5 = u(v)

hB,w6i -? (P3,[hC,ui,hA,w4i]) si w6 = uw4

hB,w7i -? (P4,[hB,ui,hB,vi]) si w7 = [u][v]

hB,w8i -? (P4,[hB,w11i,hB,vi]) si w8 = w11[v]

hB,w9i -? (P4,[hB,ui,hB,w11i]) si w9 = [u]w11

hB,w10i -? (P4,[hB,w11i,hB,w11i]) si w10 = w11w11

hB,w11i -? (B_W,[]) si w11 = [W]W

hC,w12i -? (P5,[hA,ui,hC,vi]) si w12 = (u)v

hC,w13i -? (P5,[hA,w4i,hC,vi]) si w13 = w4v

hC,w14i -? (P6,[hC,ui,hC,vi]) si w14 = uv =6 E

hC,w15i -? (C_W,[]) si w15 = E

Les automates 91(¹) et 91(²) 66

De même, en associant au symbole grammatical C (resp. A) les symboles de Dyck '[' et ']' (resp. '(' et ')'), en associant aussi au bourgeon C_W (resp. A_W) les symboles de Dyck '[_W' et ']_W' (resp. '(_W' et ')_W'), les schémas des transitions (complets) des automates associés aux répliques partielles suivant la vue V2 = {A,C} sont les suivants :

(A,w1) -+ (P1,[(C,u),(B,v)]) si w1 = [u]v

(A,w2) -+ (P1,[(C,w20),(B,v)]) si w2 = w20v avec w20 = [_W ]_W

(A,w3) -+ (P2,[]) si w3 = E

(A,w4) -+ (A_W,[]) si w4 = (_W )_W

(B,w5) -+ (P3,[(C,u),(A,v)]) si w5 = [u](v)

(B,w6) -+ (P3,[(C,w20),(A,v)]) si w6 = w20(v)

(B,w7) -+ (P3,[(C,u),(A,w4)]) si w7 = [u]w4

(B,w8) -+ (P3,[(C,w20),(A,w4)]) si w8 = w20w4

(B,w9) -+ (P4,[(B,u),(B,v)]) si w9 = uv =6E

(B,w10) -+ (B_W,[]) si w10 = E

(C,w11) -+ (P5,[(A,u),(C,v)]) si w11 = (u)[v]

(C,w12) -+ (P5,[(A,w4),(C,v)]) si w12 = w4[v]

(C,w13) -+ (P5,[(A,u),(C,w20)]) si w13 = (u)w20

(C,w14) -+ (P5,[(A,w4),(C,w20)]) si w14 = w4w20

(C,w15) -+ (P6,[(C,u),(C,v)]) si w15 = [u][v]

(C,w16) -+ (P6,[(C,w20),(C,v)]) si w16 = w20[v]

(C,w17) -+ (P6,[(C,u),(C,w20)]) si w17 = [u]w20

(C,w18) -+ (P6,[(C,w20),(C,w20)]) si w18 = w20w20

(C,w19) -+ (P7,[]) si w19 = E

(C,w20) -+ (C_W,[]) si w20 = [W]W

Les automates 91⁽¹⁾ et 91⁽²⁾

Construction de l'automate 91⁽¹⁾ associé à _tma j

v1

La trace visible des documents de l'expansion de _tma j

v1 est ((()[()])[()]); A étant l'axiome de la grammaire et aussi un symbole visible (appartenant à la vue), l'état initial de l'auto-mate 91(¹) est q¹₀ = (A,(()[()])[()]). En ne considérant que les états accessibles à partir de q¹₀ et en appliquant les schémas de règles présentés précédemment, nous obtenons l'automate d'arbre suivant pour la réplique _tma j

q^10 q^11 q^11 q^12 q^13 q^14 q^15 q^16 q^16

-+ -+ -+ -+ -+ -+ -+ -+ -+

(P1,[q^11,q^12]) (P5,[q^13,q^14]) (P6,[q^14,q^11]) (P3,[q^14,q^15]) (P1,[q^16,q^12]) (CW,[]) (P2,[]) (P5,[q^15,q^14]) (P6,[q^14,q^16])

| (P6,[q^11,q^14]) | (P6,[q^1 6,q^14])

avec avec avec avec

v1 :

q¹₁ = (C,(()[()])) et q¹₂ = (B,())

q¹₃ = (A,()[()]) et q¹₄ = (C,E)

q1 5 = (A,E) q¹₆ = (C,())

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

L'état q¹₄ est le seul état de sortie de cet automate.

L'automate consensuel Asc 67

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Construction de l'automate A⁽²⁾ associé à tmaj

v2

Ayant associé au symbole grammatical C (resp. A) les symboles de Dyck '[' et ']' (resp. '(' et ')'), la linéarisation de la réplique partielle _tma j

v2 (fig. 2.5) donne le mot de

Dyck ([(_ù )_ù[]][[][]]()). L'automate A(²) associé à cette réplique a donc pour état initial q²₀ = hA,[(_ù)_ù[]][[][]]()i et pour transitions :

q^20 q^21 q^22 q^22 q^23 q^24 q^25 q^26 q^27 q^28 q^29

-? -? -? -? -? -? -? -? -? -? -?

(P1,[q^2 1,q^22]) (P5,[q^23,q^24]) (P3,[q^25,q^26]) (P4,[q^27,q^22]) (P4,[q^22,q^27]) (Aù,[]) (P7,[]) (P6,[q^24,q^24]) (P2,[]) (Bù,[]) (P4,[q^27,q^28]) | (P4,[q^27,q^29]) |

| (P4,[q^28,q^29]) (P4,[q^28,q^27]) (P4,[q^29,q^27])

|

avec avec avec avec

q^21 = hC,(ù)ù[]i et q^22 = hB,[[][]]()i q^23 = hA,(ù)ùi et q^24 = hC,åi q^25 = hC,[][]i et q^26 = hA,åi q^27 = hB,åi, q^28 = hB,[[][]]i et q^29 = hB,()i

Les états q²₃ et q²₇ sont les seuls états de sortie de cet automate.

L'automate consensuel Asc

En appliquant notre algorithme de calcul du produit synchrone de plusieurs automates d'arbre aux automates A(¹) et A(²), on obtient l'automate du consensus A(sc) = _A(1)_?Ù _A(2) ayant pour état initial q0 = (q¹₀,q²₀) et dont les transitions sont les suivantes :

q0 q1 q2 q3 q4 q5 q6 q7 q7 q8 q9 q10 q11

-? -? -? -? -? -? -? -? -? -? -? -? -?

(P1,[q1,q2]) (P5,[q3,q4]) (P3,[q5,q6]) (P1,[q7,q8]) (P7,[]) (P6,[q9,q9]) (P2,[]) (P5,[q10,q11]) (P6,[q11,q7]) | (P3,[q11,q10]) (P7,[]) (P2,[]) (Cù,[])

(P6,[q7,q11])

avec avec avec avec avec avec

q0 = (q^1 0,q^2 0) q1 = (q^1 1,q^21) et q2 = (q^1 2,q^22) q3 = (q^13,q^23) et q4 = (q^14,q^24) q5 = (q^14,q^25) et q6 = (q^1 5,q^26) q7 = (q^16,qs1), qs1 = hOpen C,[]i et q8 = (q^1 2,qs2), qs2 = hOpen B,[]i q9 = (qs1,q^24) q10 = (q^15,qs3), qs3 = hOpen A,[]i et q11 = (q^14,qs1)

l'état _q11 de A(sc) = _A(1) ?ÙA(2) est un état de sortie ; en effet, les états qui le composent (q¹₄ et _qs1) sont tous des états de sortie. L'absence d'états de sortie dont les états composites

L'automate consensuel Asc 68

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

soient en conflit est une preuve de l'absence des conflits dans le workflow étudié ici. Notre générateur fournit un seul arbre (figure A.1) à partir de l'automate A(sc).

FIGURE A.1 - AST et arbre de dérivation généré à partir de l'automate consensuel A(sc).

69