K-expressions rationnelles

Multiplicités

K-expressions rationnelles

Afin de généraliser nos résultats, il nous faut d’abord donner une définition des expressions rationnelles à multiplicités. En particulier il nous faut énoncer les identités triviales qui seront utilisées. Certains choix sont justifiés lors de la définition des termes dérivés. 5.1.1 Définitions et notations Lorsque l’on traite des séries rationnelles, plus particulièrement de l’étoile de celles-ci, il faut définir une distance, au moins implicitement, sur le semianneau des coefficients. Dans tout ce chapitre, K est donc un semi-anneau topologique, c’est-à-dire que K est muni d’une topologie pour laquelle l’addition et la multiplication sont continues, et A est un alphabet. L’addition sur K est notée ⊕ et la multiplication est notée par une simple concaténation. Par extension, ⊕ note également l’addition dans les séries à coefficients dans K. Le semi-anneau K n’est, a priori, pas commutatif. Sur le semi-anneau topologique K pour tout élément k, la famille {k n}n∈N peut être, ou ne pas être, sommable. Lorsqu’elle est sommable, nous appellerons étoile de k sa somme, notée k ∗ : k ∗ = X n∈N k n . Lorsqu’elle n’est pas sommable, nous dirons que l’étoile de k n’est pas définie. Si K est un semi-anneau topologique fort, c’est-à-dire que le produit de deux familles sommables est sommable, alors il est possible de munir le semi-anneau des séries formelles KhhA∗ ii de la topologie produit dérivée de la topologie de K – ce qui est plus intéressant que d’utiliser la topologie produit dérivée de la topologie discrète sur K – (cf. [43, III.1.3]). 88 Les opérations rationnelles peuvent alors être définies pour les séries rationnelles. Soient s et t deux séries : = ⊕ , = σuv=w , s ∗ = σn∈Ns n . L’étoile de la série s n’est définie que si la série est propre, c’est-à-dire si le coefficient de 1K dans la série s est nul. Expressions rationnelles à multiplicités Définition 18. Une expression rationnelle sur A∗ à multiplicités dans un semi-anneau K, ou K-expression rationnelle, est une formule bien parenthésée obtenue inductivement par la grammaire : E → {a | a ∈ A} | 0 | 1 | (E + E) | (E · E) | (E ∗ ) | (kE), k ∈ K | (Ek), k ∈ K . On note K RatE A∗ l’ensemble des K-expressions rationnelles sur A∗ . L’unité du semi-anneau K est notée 1K pour éviter toute confusion avec le mot vide 1A∗ et l’expression 1. Pour éviter également des confusions entre des scalaires et l’expression 1 (par exemple dans l’expression (21), nous nous autorisons à noter l’expression 1 par 1A∗ (qui donne (21A∗ )) même si nous sommes conscient que le mot vide et l’expression 1 ne sont pas les mêmes objets. Exemple 35. Les formules suivantes sont des expressions rationnelles : ((3a) + (2b)) ((a · ((a ∗ 2) + 1A∗ ))3) . Remarque 9. Les expressions rationnelles à multiplicités sont souvent (cf. [41] ou [14] par exemple) définies par : E → {a | a ∈ A} | 0 | 1 | k ∈ K | (E + E) | (E · E) | (E ∗ ) . C’est-à-dire que les multiplicités sont considérées directement comme des atomes et les multiplications scalaires à gauche et à droite sont alors confondues avec la concaténation. Nous ne prenons pas ce formalisme car dans nos constructions les scalaires et les lettres ne jouent pas le même rôle et les multiplications à droite et à gauche ne sont pas traités comme la concaténation. 89 Le parenthésage des expressions rationnelles pourra être implicite lorsqu’il n’y a pas de confusion (par exemple les multiplicités à gauche et à droite sont appliquées à la plus petite expression à laquelle elles sont accolées –. De plus, les concaténations à droite consécutives pourront être écrites sans parenthèses. Nous appelons K-expression unitaire (à gauche et à droite) une expression rationnelle qui n’est ni (kE), ni (Ek) – donc soit une somme, soit une concaténation, soit une étoile, soit un atome –. Exemple 36. L’expression rationnelle 3(a·b) n’est pas unitaire. En revanche, l’expression (3a · b) l’est (avec le parenthésage explicite, la multiplicité 3 s’applique à a et non à a · b). Comme dans le cas booléen, nous définissons des identités dites triviales modulo lesquelles les K-expressions rationnelles sont calculées. Ces identités sont les identités (T) du cas booléen auxquelles on ajoute des identités pour les multiplications à gauche et à droite par un scalaire : (0KE) ≡ (E0K) ≡ 0 , (1KE) ≡ (E1K) ≡ E (1k) ≡ (k1) , ((k1) · E) ≡ (kE) , (E · (k1)) ≡ (Ek) , (k(k ′E)) ≡ (kk′E) , ((kE)k ′ ) ≡ (k(Ek ′ )) , ((Ek)k ′ ) ≡ (Ekk′ ) . La considération de ces identités permet à nouveau d’éviter d’avoir 0 comme sous-expression d’une expression non nulle. En outre, les trois dernières identités permettent de représenter toute K-expression rationnelle par un triplet (k, E, k′ ) où k et k ′ sont des éléments de K et E est une expression unitaire. 

 Représentation canonique

Dans le cas booléen, les termes dérivés étaient représentés par des mots sur les nœuds car ils étaient des concaténations à droite de sous-expressions. Pour les expressions à multiplicités, nous allons montrer par la suite que les termes dérivés, et les termes dérivés cassés, sont des concaténations de sous-expressions unitaires pondérées. Il apparaît donc que les termes dérivés pourront être représentés par des mots sur les u-nœuds pondérés. Nous allons donc développer dans cette sous-section une méthode similaire à celle du cas booléen, avec des marques sur les nœuds et u-nœuds, qui permet de les identifier et d’avoir une représentation canonique d’une concaténation de sous-expressions unitaires pondérées par un mot sur les u-nœuds pondérés. Plusieurs particularités des multiplicités rendent la tâche plus complexe que dans le cas booléen. 95 Dans le cas booléen, il était possible de ne s’intéresser qu’aux mots propres car il suffisait ’d’effacer’ les lettres 1 du mot sans que cela ne change l’expression associée. Ceci n’est pas aussi direct dans le cas à multiplicités car seules les lettres (1K, 1, 1K) peuvent être effacées. Les autres poids non égaux à l’unité doivent être traités différemment. En particulier il est nécessaire, avant de faire tout autre calcul, de transformer le mot afin de se ’conformer’ aux identités triviales introduites par les multiplicités. La première opération est alors de regrouper les poids successifs. Les marques L’arbre syntaxique de l’expression E est ’marqué’ de telle manière que chaque u-nœud u a une marque u telle que u = v si [|u|] = [|v|], c’est-à-dire que u et v sont racines d’arbres isomorphes. La définition de marque s’étend aux u-nœuds pondérés par : (k, u, k′) = (k, u, k′ ) . Dans un souci de simplicité, nous continuons d’appeler poids les marques des poids (les u-nœuds pondérés dont l’expression unitaire est l’unité). Les mots sur les marques sont les mots dont les lettres sont des marques de u-nœuds pondérés. Exemple 42 (Ex. 38 cont.). Notons αi la marque du u-nœud ui . On a alors les égalités suivantes : α4 = α7 α5 = α8 de plus comme les poids sont identiques, on a x4 = x7 et x5 = x8 et donc on a également : α2 = α6 . Il est important de remarquer que l’on n’a néanmoins pas x2 = x6 car les poids diffèrent. Les identités triviales Dans un premier temps, pour transformer un mot sur les marques en un mot canonique pour l’expression associée, nous allons le transformer de la même manière que les identités triviales permettent de transformer des expressions. Il faut noter que, contrairement aux réductions vues dans le cas booléen – et dont l’adaptation aux multiplicités suit –, les réductions que nous effectuons ici sont totalement indépendantes de l’expression E. 96 Nous allons ainsi tout d’abord transformer un mot sur les marques afin qu’il soit cohérent avec les identités : ((Ek)k ′ ) = (Ekk′ ) et (k(k ′E)) = (kk′E) . Pour cela il suffit de remplacer tous poids consécutifs en leur produit : α1 :: . . . :: k :: k ′ :: · · · →ρ1 α1 :: . . . :: kk′ :: . . . . Exemple 43 (Ex. 38 cont.). Par exemple 3 :: x5 :: 2 :: 3 se réduit par ρ1 en 3 :: x5 :: 6. Dans un deuxième temps, nous rendons cohérent le mot pour l’identité : ((k1) · (k ′E)) = (kk′E) . Pour cela il faut rentrer le coefficient dans le premier terme de la concaténation à droite : k :: (k1, u1, k′ 1 ) :: · · · →ρ2 (kk1, u1, k′ 1 ) :: . . . . Exemple 44 (Ex. 38 cont.). Par exemple 3 :: x5 :: 6 se réduit par ρ2 en (3, α5, 1K) :: 6. Finalement, nous transformons l’expression pour la rendre cohérente avec : ((Ek) · (k ′ 1) = (Ekk′ ) Comme les mots sur les marques représentent des concaténations à droite, le coefficient en fin de mot ne doit être rentré dans la marque précédente que dans le cas où celle-ci est également la première marque du mot : (k1, u1, k′ 1 ) :: k →ρ3 (k1, u1, k′ 1k) . Exemple 45 (Ex. 38 cont.). Par exemple (3, α5, 1K) :: 6 se réduit par ρ3 en (3, α5, 6). En revanche, (3, α5, 1K) :: 6 :: (2, α1, 3) ne se réduit pas par ρ3. Après avoir réalisé successivement les transformations ρ1, ρ2 et ρ3, un mot de marque X quelconque est donc remplacé par un mot de marque Y i = ρ3(ρ2(ρ1(X))) tel que : (i) il n’y a pas deux poids consécutifs dans Y ; (ii) Y ne commence pas par un poids ; (iii) si Y est de longueur 2 alors ses lettres ne sont pas des poids ; (iv) X et Y représentent la même expression.