Le demi-groupe libre engendré par `2` générateurs `a` et `b` est l'ensemble des mots non vides d'alphabet `{a,b}`. L'opération interne du demi-groupe noté `"∗"`, ou noté par absence de symbole, correspond à la concaténation de mots. Si on ajoute le mot vide, noté 1, on obtient le monoïde bigène libre.
Le monoïde bigène libre se définie comme un magma trigène engendré par `{1,a,b}` et quotienté par les deux propriétés, l'opérateur interne `"∗"` est associatif, et l'élément `1` est l'élément neutre de `"∗"` :
`("<∗(.,.)",1,a,b">")/("{"AAxAAyAAz, (xy)z"="x(yz), 1x"="x, x1"="x"}")`
Le monoïde bigène libre se définie aussi comme un ensemble d'opérateurs unaires engendré par `{1"(.)", a"(.)", b"(.)}` et quotienté par la propriété suivante : L'opérateur `1"(.)"` est l'élément neutre de l'opérateur de composition `"∘"`. C'est à dire que l'opérateur `1"(.)"` constitue l'identité.
`("<"1"(.)", a"(.)", b"(.)>")/("{"1"="(x"↦"x) "}")`
L'opérateur de composition `"∘"` est nécessairement associatif par construction, c'est pourquoi cette propriété n'est pas mentionnée.
Le monoïde bigène libre est un arbre sans fin, avec l'élément `1` comme racine. Chaque élément `x` est un noeud de l'arbre qui possède `2` fils qui sont `xa` et `xb`.
On se propose de construire des sous-monoïdes obtenus à partir de règles d'égalités entre mots, ce qui revient à complèter la théorie du monoïde en y ajoutant ces règles d'égalité, par exemple en ajoutant les 3 équations suivantes :
`{ab"="ba, aa"="1, b b b"="1}`
Ce monoïde se définie comme un ensemble d'éléments :
`("<∗(.,.)",1,a,b">")/("{"AAxAAyAAz, (xy)z"="x(yz), 1x"="x, x1"="x, ab"="ba, aa"="1, b b b"="1"}")`
ou bien comme ensemble d'opérateurs unaires :
`("<"1"(.)", a"(.)", b"(.)>")/("{"AAx, 1(x)"="x, a(b(x))"="b(a(x)), a(a(x))"="x, b(b(b(x)))"="x"}")`
La présentation du monoïde ne mentionne que les générateurs et les équations :
`"<"a,b "|" aa"="1,b b b"="1,ab"="ba">"`
Le monoïde bigène libre est un arbre sans fin où chaque élément est un noeud possèdant deux fils, un par générateur. Chaque équation est une égalité entre deux chemins et va fusionner des noeuds de cet arbre et le transformer en un graphe orienté. Il est alors possible d'exploiter la puissance mésentropique d'un tel graphe pour accroître les connaissances d'égalités entre éléments du monoïde, et obtenir trés rapidement la connaissance complète si le monoïde s'avère fini.
Cette tâche est faite par un programme informatique. On choisi le langage Golang (Go), un langage proche de la machine, autant que le langage C, mais avec en plus les facilités de développement apportées par l'informatique comtemporaine.
On commence par définir la structure de donnée la plus appropriée. Puis on développe un framework, un ensemble de fonctions fondamentales. On utilise un système d'exploitation Linux, l'éditeur de texte gedit, le compilateur go, et pour le confort bien que cela ne soit pas indispensable, la plate forme de développement eclipse avec goclipse. Pour l'installation de go, sdl, eclipse, goclipse, voir Le langage Go
La gestion des pointeurs et de la mémoire dans Go est simplifiée par la présence d'un ramasse-miette. C'est un système de gestion de la mémoire intégré qui libére les mémoires occupés lorsqu'elle sont rendues inaccessibles. Cela nous permet de programmer des algorithmes sur les graphes sans avoir à nous préoccuper de libérer les mémoires perdues.
Le monoïde bigène est un arbre binaire dans lequel les noeuds sont les éléments du monoïde, et se fusionnent entre-eux selon les règles prescrites dans sa présentation. L'arbre devient donc un graphe orienté où chaque noeuds `x` possède exactement `2` arcs sortant labélisés `a` et `b` et allant sur les noeuds fils de `x` qui sont les éléments `xa` et `xb` du monoïde.
Nous allons programmer un ensemble de fonctions qui permettra de construire et de modifier cet arbre, qui est en faite un graphe.
On déclare le type Cell comme suit :
type Cell struct {
d, u uint16
L, A, B *Cell
}
Chaque élément du monoïde correspondra à un noeud, appelé aussi cellule, et qui est de type `"Cell"`. Mais pas tous d'un coup, car dans le processus de construction, les premiers noeuds à être construits sont la racine, puis ses fils, puis les fils de ses fils, etc., degrés par degrés.
Le graphe représente la partie explorée du monoïde. On crée la racine comme suit :
var R *Cell = &Cell{0, 0, nil, nil, nil}
Cela crée une case mémoire de type `"Cell"`, initialisée à `d"="0`, `x"="0`, `L"="nil`, `A"="nil`, `B"="nil`. Et `R` pointe sur cette case mémoire qui constitue la racine. On dit que `R` est la racine, bien que en fait c'est un pointeur vers la case mémoire de la racine. De même, on dit que `x` est un noeud, bien que en fait c'est un pointeur vers la case mémoire du noeud.
La fonction `A`, appliquée à `x` va retourner son premier fils `xa`, en le créant s'il n'existe pas. Et la fonction `B`, appliquée à `x` va retourner son second fils `xb`, en le créant s'il n'existe pas :
func A(x *Cell) *Cell {
if x.A == nil {
x.A = &Cell(x.d + 1, 0, nil, nil, nil)
return x.A
}
func B(x *Cell) *Cell {
if x.B == nil {
x.B = &Cell{x.d + 1, 0, nil, nil, nil}
return x.B
}
}
Ainsi par exemple, l'instruction `x"="A(A(B(A(R))))` va retourner le noeud `abaa` en créant les noeud `a`, `ab`, `aba`, `abaa` s'ils n'existaient pas.
L'affichage du graphe sous forme d'un emboitement de parenthèses, se fait en partant de la racine, en balayant le graphe en profondeur d'abord, et en marquant chaque noeud parcouru d'un flag de passage afin de ne pas repasser deux fois par le même noeud. Un deuxième balayage sera nécessaire pour remettre à zéro ce flag de passage. C'est pourquoi la fonction d'affichage `"aff(.)"` se décompose en deux fonctions `"affw(.)"` qui va faire le travail (d'où le suffixe "w" pour work) et `"affc(.)"` pour effacer les flags (d'où le suffixe "c" pour clear).
|
|
Les opérations de bits à bits permettent de tester et modifier les bits isolément de `x"."u`, qui sont utilisés comme flags de passage. Ainsi nous utilisons le jeu d'instructions suivant :
x.u & 1 == 1 Teste si le premier bit de `x"."u` est à `1`. x.u & 1 == 0 Teste si le premier bit de `x"."u` est à `0`. x.u = x.u | 1 met le premier bit de `x"."u` à `1`. x.u = x.u &^ 1 met le premier bit de `x"."u` à `0`.
L'instruction aff(R) affiche le graphe sous forme d'un emboitement de parenthèses : ○(○(_,○(○(○,_),_)),_). Chaque o correspond à un noeud et est suivi par le couple de ses fils s'il en a. Chaque _ correspond à un noeud fils inconnu. Chaque • correspond à un noeud déjà parcouru.
On procéde à la construction du monoïde par degrés. Au degrés `0`, il n'y a que la racine. Au degrès `1` on ajoute les fils `{a, b}`. Au degrès `2` on ajoute les fils des fils `{aa,ab,ba,b b}`, etc.. En procédant ainsi, le graphe représente tous les éléments du monoïde atteignable en `N` étapes à l'aide des `2` générateurs. Le nombre `N` est alors une variable globale que l'on déclare comme suit :
var N uint16 = 0
Il s'en suit qu'il ne faut créer aucun fils individuellement pour rester au même degrès d'exploration du monoïde.
Le balayage du graphe doit pouvoir être utiliser pour appliquer une fonction à tous les sommets. C'est pourquoi on établit un modèle de fonction `"balay"` prenant en argument une racine `r` d'un graphe (on doit prévoir pour un développement futur la possiblité de manipuler plusieurs graphes) et manipulant une variable globale qu'est la fonction `f` que l'on veut appliquer à tous les noeuds du graphe.
Notez que le flag de passage utilisé est le premier bit de l'attribut `u`. S'il y a deux balayages emboités, il sera alors nécessaire d'utiliser un deuxième flag de passage, de la même façon que l'on utilise des indices différents dans des boucles "for" emboitées.
|
|
Si nous voulons utiliser le second flag de passage alors nous utiliserons ces instructions :
x.u & 2 == 2 Teste si le second bit de `x"."u` est à `1`. x.u & 2 == 0 Teste si le second bit de `x"."u` est à `0`. x.u = x.u | 2 met le second bit de `x"."u` à `1`. x.u = x.u &^ 2 met le second bit de `x"."u` à `0`.
Et si nous voulons utiliser le flag de passage n° `3, 4, 5, 6, 7, 8` alors nous utiliserons ces mêmes instructions mais en remplaçant l'entier `2` respectivement par l'entier `4, 8, 16, 32, 64, 128`.
Le quotientage du monoïde par une équation se fait en deux étapes :
Nous voulons pouvoir fusionner deux noeuds `x` et `y`, c'est à dire les considérer comme équivalent. On les lie par une relation d'équivalence `"≈"`. Et on notera symboliquement `x"≈"y`.
Mais le traitement informatique n'est pas symétrique. Dans le cas où aucun lien n'existe, on établit un lien de `x` vers `y` que l'on mémorisera dans la mémoire de `x`, dans son attribut `L`. Autrement dit `x"."L` sera égale à `y` (c'est à dire précisement `x"."L` pointera sur le noeud que pointe `y` ce qui se note `x"."L"="y`). Et pour décrire précisement cette implémentation on notera `x"↦"y`.
Puis dans le cas où il existe déjà des liens, plusieurs noeuds peuvent être liés dans un arbre inversé de liens, dont la tête (qui en constitue la racine) se trouve au bout des liens. Par exemple considérons cet ensemble de 7 liens `x"↦"y"↦"z"↦"t` et `a"↦"b"↦"y"` et `u"↦"v"↦"b`. Dans ces liens, le parcourt de tous les liens en partant de n'importe qu'elle noeud abouti toujours à la tête de l'arbre inversé (racine de l'arbre) qui est `t`. Lors d'une nouvelle liaison entre `2` noeuds `x,y`, le cas général qui se produit est la fusion de deux arbres inversés. L'instruction fusion(x,y) va calculer les têtes des arbres et lier l'une sur l'autre.
func fusion(x, y *Cell) {
for x.L != nil {
x.L = x.L.L
}
for y.L != nil {
y.L = y.L.L
}
if x != y {
x.L = y
}
}
Chaque noeud `x` peut être considéré comme la racine d'un graphe (cela correspond au sous-demi-groupe `x"<"a,b">"`).
Chaque noeud `x` ne possède que deux fils `xa` et `xb`. Aussi, le lien d'équivalence `x"≈"y` va entrainer une série d'autres liens sur les descendants. Les fils de `x` devrons être liés aux fils respectifs de `y`. Autrement dit :
`x"≈"y => ((xa"≈"ya),(xb"≈"yb))`
Et on applique la contrainte qu'aux noeuds connus. Il faut donc parcourir de façon parallèle les deux graphes de racine `x` et `y`. C'est la fonction `"fusionD"` qui le fera (avec le suffixe "D" pour descendance). Mais avant de la programmer, on programme un modèle de fonction.
On établit un modèle de fonction `"balay2"` prenant en argument deux noeuds `x, y` (et qui ne sont pas nécessairement dans le même graphe. On doit prévoir pour un développement futur la possiblité de manipuler plusieurs graphes), et manipulant une variable globale qu'est la fonction `f` que l'on souhaite appliquer à tous les couples de noeuds parcouru en parallèle.
Notez que le flag de passage utilisé est le second bit de l'attribut `u`. Et s'il y a deux balayages emboités, il sera alors nécessaire d'utiliser un autre flag de passage, de la même façon que l'on utilise des indices différents dans des boucles "for" emboitées.
|
|
On applique se modèle de fonction pour définir la fonction `"fusionD"` qui appliquera sur tous les couples de noeuds constituant la descendance parcourus en parallèle, la fonction `"fusion"` :
|
|
Chaque élément est désigné par des mots d'alphabets `{a,b}` qui représentent des chemins partant de la racine pour aller sur l'élément en question. Par exemple `x"="aaba`, qui signifie aussi `x"="1aaba`, signifit que en partant de `1`, en empruntant l'arc `a`, puis l'arc `a`, puis l'arc `b`, puis l'arc `a`, on aboutit à `x`.
Le monoïde impose des symétries. Si deux éléments sont égaux, cela signifie que les deux chemins partant de la racine pour aller sur ces éléments, sont égaux indépendamment du point de départ. Ainsi par exemple si `aa"="bbb` nous auront pour tout point `x` l'égalité `xaa"="xbbb` ce qui est une évidence quelque soit la structure (c'est le transport de l'égalité à travers les applications).
Ainsi la fusion de deux noeuds est équivalent à l'égalité de deux chemin, que nous appellons une équation. L'équation est composé d'un premier mot d'alphabet `{a,b}` ou par le mot `1` suivie du symbole `"="` suivi d'un second mot d'alphabet `{a,b}` ou par le mot `1`. En voici trois exemples :
`aaaa"="1, b b b b"="1, ab"="ba`
L'équation s'applique à tous les noeuds en les considérant comme point de départ. On mémorise l'équation dans une chaine de caractères qui sera utilisée comme argument de la fonction `"relation"`. Cette fonction construira la relation d'équivalence découlant de cette équation, mais uniquement sur la partie explorée du monoïde.
L'équation `e` va engendrer de nombreuse fusions de noeud. L'équation comprend deux chemins. Si on fait partir ces deux chemins d'un point `x` quelconque du graphe, il établira une fusion entre deux noeuds. C'est la fonction `"raccord"` qui executera cette tâche avec l'instruction raccord(x,e).
La fonction `"relation"` parcours tous les points du graphe pour tester les deux chemins à l'aide de la fonction `"raccord"`. On utilise le modèle de balayage à simple entrée vue plus haut.
Mais comme nous voulons contrôler le nombre de degrés connus du monoïde, on ne laissera pas les chemins créer des noeuds. Si le chemin mène à un noeud non encore créé, on considèrera qu'il échoue.
|
|
La fonction `"raccords"`, appliquée à un noeud `x` et à une équation `e`, va décomposer l'équation en deux mots qui représentent deux chemins, puis va emprunter ces deux chemins en partant de `x` pour accéder à deux noeuds, puis va fusionner ces deux noeuds. Mais si un des chemins abouti à `nil` alors la fonction s'arrête sans rien fusionner.
func raccord(x *Cell, e string) {
var x1, x2 *Cell
z := x
for _, v := range eq {
switch v {
case 'a':
if z.A==nil {return}
z = z.A
case 'b':
if z.B==nil {return}
z = z.B
case '1':
case '=':
x1 = z
z = x
}
x2 = z
}
fusion(x1,x2)
}
Une fois la relation d'équivalence construite, l'étape suivante consiste à associer à chaque classe d'équivalence un nouvel élément. Le choix le plus simple à programmer consiste à parcourir le graphe et à chaque noeud, prendre la tête de l'arbre inversé. Puis si celle-ci n'est pas marqué par un flag special, créer un nouveau noeud en le marquant du flag spécial, et lier la tête à ce noeud. La fonction `"represente"` appliqué à un noeud `x` fera ce travail et retournera un représentant de la classe en le créant si nécessaire.
| func represente(x *Cell) *Cell { for x.L != nil { x.L = x.L.L } if x.u & 32 == 0 { y := &Cell(0, 32, nil, nil) x.L = y } return x.L } |
Puis c'est la fonction `"concretise"` qui applique cette fonction `"represente"` sur tous les noeuds du graphe et complétera les liens de filiations, puis on rompt le cordon ombilicale en effaçant les liens entre les deux graphes.
|
|
La racine du graphe quotienté est represente(R)
Reste à recalculer le degrès de profondeur de chaque noeuds. Cela se fait par la fonction `"degres"` :
func degres(r *Cell)
degresw(r)
degresc(r)
}
func degresw(x *Cell) {
if x != nil && (x.u & 1) == 0 {
x.u = x.u | 1
if x.A != nil && (x.A.d==0 || x.A.d > x.d+1) {
x.A.d=x.d+1
}
if x.B != nil && (x.B.d==0 || x.B.d > x.d+1) {
x.B.d=x.d+1
}
degresw(x.A)
degresw(x.B)
}
}
func degresw c(x *Cell) {
if x != nil && (x.u & 1) == 1 {
x.u = x.u &^ 1
if x.A != nil || x.B != nil {
degresc(x.A)
degresc(x.B)
}
}
}
---- 18 avril 2020 ----