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

2.6 qui sont des expansions de tmaj

v1 .

Génération des arbres à partir d'un automate

Tout comme il est possible de générer des mots du langage accepté par un automate classique (automate sur les chaînes de caractères) à partir de ce dernier, il est possible de générer des arbres à partir d'un automate d'arbres. En effet, il suffit de partir de l'état initial vers les états finals en se laissant guider par les transitions de l'automate. Il existe tout de même le risque de tourner en rond (indéfiniment) lorsque les transitions de l'automate décrivent un cycle ; on passe alors plusieurs fois par un même état. Pour régler ce problème, il suffit de fixer le nombre maximum d'utilisation d'un état dans la génération. Sur ce principe, un générateur (dont le code Haskell est donné dans l'an-nexe B) a été proposé dans [BTT08, BTT07] ; ce dernier énumère les arbres les plus simples acceptés par un automate d'arbre, c'est à dire, les arbres tels que dans aucune branche, un état de l'automate n'est utilisé plus d'une fois pour la génération des noeuds de la branche. L'application de cette fonction de génération à l'automate fournit l'AST P1[P5[P1[P5[P2[],P7[]],P3[P7[],P2[]]],P7[]],P3[P7[],P2[]]] correspondant au second arbre de la figure 2.6.

2.4. Fusion des répliques partielles mises à jour

La dernière étape du procédé d'édition coopérative présenté à la section 2.1.3 est la fusion des mises à jour portées par les co-auteurs sur les différentes répliques partielles. Pour cela, on synchronise les expansions des différentes répliques mises à jour. Ces expansions étant représentées par des automates d'arbre qui leur ont été associés, leur synchronisation implique une synchronisation à base d'une opération (produit synchrone) de ces automates. Dans cette section, nous définissons le produit synchrone de plusieurs automates d'arbre puis nous montrons comment ce produit peut être utilisé pour réaliser la fusion des mises à jour portées sur les répliques partielles.

2.4.1. Produit synchrone des automates d'arbre

Définition 14 Produit synchrone de k automates

Soient (1) = (E,Q(¹),R(¹),qo¹⁾),. ., (k) = (Ó,Q(^k),R(^k),qa^k)) k automates d'arbre. Le produit synchrone de cesⁱ k automates (1) ®··· ® (k) noté ®i (ⁱ), est l'automate (sc) = (Ó,Q,R,q0) défini comme suit :

Ses états sont les vecteurs d'états : Q = Q(¹) x ··· x Q(^k) ;

Son état initial est formé par le vecteur des états initiaux des différents automates : q0 = (q⁽¹⁾

0 ,···,q(k)

0 );

2.5. Synthèse 32

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

-- Ses transitions sont données par :

~ ~

(q(1),...,q(k)) a ? (q⁽¹⁾

1 ,...,q(k) ₁ ),...,(q(1)

n ,...,q^(k)

n ) ?

a

q(i) ? (q⁽₁ⁱ⁾,...,qS_iⁱ⁾) ?i, 1 = i = k)

L'automate d'arbre produit permet de représenter l'intersection des langages d'arbre acceptés par les automates intervenants dans le calcul de ce produit ; il (l'automate produit) accepte donc les arbres (documents) qui sont reconnus par tous les automates qui permettent de le calculer. Plus formellement,

(?k )
i=191(i) ` t r (q1,··· ,qk)) ? (?i, 91(<sup>i</sup>) ` t r qi) donc 2' (?k i=191(i), (q1,··· ,qk)) = T2' (91(ⁱ), qi

2.4.2. Fusion des répliques partielles

Le but de la fusion des mises à jour portées sur les répliques partielles est celui de trouver un document tf conforme à la grammaire globale qui intègre toutes les contributions des différents co-auteurs. Pour chaque réplique partielle, on sait déjà représenter, à l'aide d'un automate, son expansion. Un arbre appartenant à l'expansion d'une réplique partielle est conforme à la grammaire globale et admet cette réplique comme trace visible (c'est à dire qu'il intègre tous les noeuds de cette réplique). Pour atteindre l'objectif de la fusion, il faut trouver des arbres qui appartiennent à toutes les expansions des différentes répliques partielles à fusionner : il faut donc calculer l'intersection de ces expansions. Comme ces expansions sont représentées par des automates d'arbre, leur intersection peut être représentée par un automate d'arbre qui est le produit synchrone de ces automates. On peut donc en déduire que, pour fusionner les mises à jour apportées à k répliques partielles tV1,··· ,tV_k d'un document structuré t il faut :

1. Associer un automate d'arbre (91(ⁱ)) à chaque réplique partielle mise à jour (tma j

Vi , ? 1 =

i =k);

2. Calculer l'automate produit ⁹1(SC) = ?i91(ⁱ) de ces automates;

3. Les documents reconnus par _91(SC) sont des documents globaux qui intègrent toutes les mises à jour des différents co-auteurs.