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

3.2.3. Illustration de l'algorithme de la fusion consensuelle

Nous illustrons l'algorithme de fusion consensuelle avec la grammaire Gexpl de l'exemple 8. Nous associons des automates d'arbre .91(¹) et .91(²) respectivement aux répliques par-

tielles mises à jour _tma j

v1 et _tma j

v2 (figure 3.2.c et 3.2.e), puis nous construisons l'automate du

3.2. Calcul du consensus 40

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

consensus 91(sc) = 91⁽¹⁾ 0 91⁽²⁾ par application de la démarche décrite dans la section 3.2.2 et enfin nous présentons les documents les plus simples du consensus (figure 3.3 page 43).

FIGURE 3.2 - Exemple de workflow d'une édition avec conflit et consensus correspondant.

Les schémas de transition pour la vue {A,B}

Une liste d'arbres (forêt) est représentée par la concaténation de leurs linéarisations. Nous utilisons la parenthèse ouvrante '(' et fermante ')' pour représenter les symboles de Dyck associés au symbole visible A et le crochet ouvrant '[' et fermant ']' pour représenter ceux associés au symbole visible B. Puisque les arbres manipulés peuvent contenir des bourgeons, ils est nécessaire de pouvoir linéariser ces derniers. Nous associons donc les symboles '(_w' et ')_w' (resp. '[_w' et ']_w') au bourgeon A_w (resp. B_w) de type A (resp. B). Chaque transition des automates associés aux répliques partielles suivant la vue {A,B} est conforme à l'un des schémas de règles suivants :

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

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

(A,w3) -+ (A_w,[]) si w3 = (_w )_w

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

(B,w5) -+ (P4,[(B,u),(B,v)]) si w5 = [u][v]

(B,w6) -+ (B_w,[]) si w6 = [w]w

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

(C,w8) -+ (P6,[(C,u),(C,v)]) si w8 = uv =6 E

(C,w9) -+ (C_w,[]) si w9 = E

Ces schémas de règles [BTT08] sont obtenus à partir des productions de la grammaire. Les états (A,w3) avec w3 = (_w )_w, (B,w6) avec w6 = [w]w et (C,w9) avec w9 = E sont des états de sortie [BTT08]. La règle (C,w9) -+ (C_w,[]) liée à la production P7 stipule que l'AST

3.2. Calcul du consensus 41

généré à partir de l'état (C,w9) est réduit à un bourgeon de type C (C est le symbole situé en partie gauche de P7).

Remarque 15 Nous ne représentons pas tout l'ensemble des schémas de règles dans cet exemple; seul le sous-ensemble utile pour la réconciliation des documents clos est représenté car les documents à réconcilier ici sont tous clos. L'ensemble des schémas de règles est totalement représenté dans l'annexe A.

Construction de l'automate A⁽¹⁾ associé à tv1

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

.

v1 (fig. 3.2.c) donne (([[()()][()]])[()])

Comme A est l'axiome de la grammaire et qu'il est visible, l'état initial de l'automate A(1) 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

v1 (fig. 3.2.c) :

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

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

(P1,[q^11,q^12]) (P5,[q^13,q^14]) (P6,[q^1 4,q^11]) | (P3,[q^14,q^15]) (P1,[q^14,q^16]) (Cw,[]) (P2,[]) (P4,[q^17,q^12]) (P3,[q^18,q^15]) (P5,[q^15,q^14]) (P6,[q^18,q^14]) |

(P6,[q^11,q^14]) (P6,[q^14,q^18])

avec avec avec avec avec avec

q^11 = (C,([[()()][()]])) et q^12 = (B,()) q^13 = (A,[[()()][()]]) et q^14 = (C,e) q^15 = (A,e) q^16 = (B,[()()][()]) q^17 = (B,()()) q^1 8= (C,())

L'état q¹₄ = (C,e) est le seul état de sortie de l'automate A(¹). Il est aisé de vérifier que le document de la figure 3.2.f issu de la projection inverse de tv1^maj appartient au langage accepté par l'automate A(¹).

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

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 des automates associés aux répliques partielles suivant la vue {A,Cl sont les suivants :

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

(A,w2) -+ (P2,[])

si w2 = e

(A,w3) -+ (A_w,[]) si w3 = (w)w

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

(B,w5) -+ (P4,[(B,u),(B,v)]) si w5 = uv =6 e

(B,w6) -+ (B_w,[]) si w6 = e

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

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

(C,w9) -+ (P7,[]) si w9 = e

(C,w10) -+(C_w,[]) si w10 = [w]w

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

3.2. Calcul du consensus 42

Le mot de Dyck ([([][]()[]())[]][[][]]()) est la linéarisation de la réplique partielle _tma j

v2

(fig. 3.2.e). L'état q²₀ = hA,[([][]()[]())[]][[][]]()i est donc l'état initial de l'automate 91(²) associé à cette réplique. Ses transitions sont :

avec q²₁ = hC,([][]()[]())[]i et q²₂ = hB,[[][]]()i

avec q²₃ = hA,[][]()[]()i et q²₄ = hC,åi avec q²₅ = hC,[][]i et q²₆ = hA,åi avec q²₇ = hB,[]()[]()i

avec q²₈ = hB,åi, q²₉ = hB,[]i, q²₁₀ = hB,()[]()i, q²₁₁ = hB,[]()i, q²₁₂ =

hB,[]()[]i et q2 13 = hB,()i

q²₀

q^21 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]) (P1,[q^24,q^27]) (P7,[]) (P6,[q^24,q^24]) (P2,[]) (P4,[q^28,q^27]) | (P4,[q^29,q^210]) | (P4,[q2 11,q211]) | (P4,[q^212,q^213]) | (P4,[q^27,q^28]) (Bù,[]) (P4,[q^2 8,q^29]) | (P4,[q^29,q^28])

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

q210

q211 q212 q213 q214

-? -? -? -? -?

(P4,[q^28,q^210]) (P4,[q^214,q^213]) (P3,[q^2 4,q^26]) (P4,[q^28,q^212]) (P4,[q2 11,q29]) (P4,[q^28,q^213]) (P4,[q2 8,q214]) (P4,[q^214,q^28])

| (P4,[q^213,q^211]) | (P4,[q^210,q^28]) | (P4,[q29,q2 14]) | (P4,[q^212,q^28]) | (P4,[q2 13,q28]) | (P4,[q2 13,q29])

| | |

avec

q^214 = hB,()[]i

L'état q²₈ est le seul état de sortie de l'automate 91(²). Construction de l'automate du consensus 91(sc)

Par application du produit synchrone de plusieurs automates d'arbres décrit dans la section 3.2.2 aux automates 91(¹) et 91(²), l'automate du consensus ⁹¹(sc) = 91(1) ?^Ù 91(²) a pour état initial q0 = (q¹₀,q²₀). 91(¹) possède une transition de q¹₀ vers [q¹₁,q¹₂] étiquetée P1. De même, 91(²) possède une transition de q²₀ vers [q²₁,q²₂] étiquetée P1. On a donc dans _91(sc) une transition étiquetée P1 permettant d'accéder aux états [q1 = (q¹₁,q²₁),q2 = (q¹₂,q²₂)] à partir de l'état initial q0 = (q¹₀,q²₀). Suivant ce principe, on construit l'automate consensuel suivant :

q0 q1 q2 q3 q4 q5 q6

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

(P1,[q1,q2]) (P5,[q3,q4]) (P3,[q5,q6]) (P1,[q4,q7]) (P7,[]) (P6,[q8,q8]) (P2,[])

q0 = (q^10,q^20) avec q1 = (q^1 1,q^21) et q2 = (q^1 2,q^22) avec q3 = (q^13,q^23) et q4 = (q^14,q^24) avec q5 = (q^14,q^25) et q6 = (q^15,q^26) avec q7 = (q^16,q^27) avec q8 = (qs1,q^24) et qs1 hOpen C,[]i

=

3.3. Synthèse 43

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

q7 -+ (P4,[q9,q10]) | (P4,[q11,q12]) | (P4,[q13,q14]) | (P4,[q15,q16]) | (P4,[q17,q18])

avec q9 = (q^17,q^28), q10 = (q^12,q^27), q11 = (q^17,q^29), q12 = (q^12,q^210), q13 = (q^17,q^211), q14 = (q^12,q^211), q15 = (q^17,q^212), q16 = (q^12,q^213), q17 = (q^17,q^27) et q18 = (q^12,q^28)

q8 -+ (P7,[])

q9 -+ (P3,[q19,q20]) avec q19 = (q¹8,qs1) et q20 = (q¹₅,q_s2),

qs2 = (Open A,[])

q13 -+ (P3,[q21,q6]) avec q21 = (q¹ ₈,q² ₄)

q14 -+ (P3,[q4,q6])

q18 -+ (P3,[q22,q20]) avec q22 = (q¹4,qs1)

q19 -+

(P5,[q20,q22]) | (P6,[q19,q22]) | (P6,[q22,q19])

q20 -+ (P2,[])

q10 -+

(B_a),[]), _q11 -+ (B_a),[]), _q12 -+ (B_a),[]), _q15 -+ (B_a),[]), _q16 -+ (B_a),[]),

q17 -+ (B_a),[]), _q21 -+ (C_a),[]), _q22 -+ (C_a),[])

Les états {q10,q11,q12,q15,q16,q17,q21,q22} sont les états de sortie de l'automate .(sc). Ce sont des états dont les états composites sont soit en conflit (par exemple q10 = (q¹₂,q₇) et q¹₂ y q²₇), soit sont tous des états de sortie (par exemple q22 = (q¹₄,q_s1)).

L'utilisation de la fonction de génération des AST (avec bourgeons) les plus simples d'un langage d'arbre à partir de son automate [BTT08, BTT07, TT09] sur l'automate .(sc), produit quatre AST dont les arbres de dérivations (les consensus) sont schématisés sur la figure 3.3.

FIGURE 3.3 - Arbres consensuels générés à partir de l'automate .(sc).