Nouvelle version, voir Construction de monoïdes
Le monoïde bigène libre, engendré par 2 générateurs a et b, est l'ensemble des mots non vides d'alphabets {a,b}. L'opération interne du monoïde noté * ou simplement par absence de symbôle, correspond à la concaténation de mots. Si on ajoute le mot vide que l'on note par 1, on obtient le monoïde unitaire bigène libre.
Le monoïde unitaire bigène libre se note linguistiquement comme ensemble d'éléments par :
<*(.,.),1,a,b>/{* est associatif, 1 est l'élément neutre de *}
ou bien comme ensemble d'opérateurs unaires par :
<1(.), a(.), b(.)>/{1 est l'application identité}
On représente le monoïde sous forme d'un arbre avec l'élément 1 comme racine. Chaque élément e est un noeud de l'arbre qui possède 2 fils qui sont ea et eb.
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 par exemple les 3 équations suivantes :
{ab=ba, aa=1, bbb=1}
Ce monoïde se note linguistiquement comme ensemble d'éléments par :
<*(.,.),1,a,b>/{* est associatif, 1 est l'élément neutre de *, ab=ba, aa=1, bbb=1}
ou bien comme ensemble d'opérateurs unaires par :
<1(.), a(.), b(.)>/{∀x, 1(x)=x, a(b(x))=b(a(x)), a(a(x))=x, b(b(b(x)))=x}
Le monoïde unitaire bigène libre est construit comme 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 noeuds. Chaque équation va fusionner deux 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 introspectivement en 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 C, un langage proche de la machine. On commence par définir la structure de donnée la plus appropriée. Puis on développe un framework regroupant toutes les opérations fondamentales. On utilise un système d'exploitation Linux, L'éditeur de texte gedit, et le compilateur gcc.
L'étude des graphes orientés fait apparaitre un maillage sous-jacent servant de mémoire et qui constitue une sorte de grille sur laquelle repose le raisonnement. Selon les intuitionistes, le raisonnement s'identifie au fonctionnement d'une machine. Et ce constat empirique nous amène a considérer cette grille comme une partie non immédiatement visible mais nécessaire à la nature machiniste du raisonnement. De la même façon, les philosophes physiciens avait considéré l'atome comme une nécessité sans pourtant être en mesure de le percevoir directement.
La grille est une mémoire, et la mémoire se présente dans la plus simple configuration comme un flux de bits, c'est à dire une succession de bits. On regroupe ces bits dans une première quantification appelé mot pour pouvoir mémoriser une adresse ou un pointeur. Et cette quantification va limiter la taille de la mémoire adressable. La quantification la plus courante est le mot de 32 bits, c'est à dire de 4 octects, et permet de mémoriser 4 Giga adresses différentes. Si ces adresses sont utilisées pour adresser des blocks de 20 octets, cela permet d'utiliser 80 Giga octets de mémoires vive.
On effectue une deuxième quantification qu'est la cellule et qui regroupe deux mots consécutifs. La cellule peut ainsi mémoriser deux pointeurs, chaque pointeur pouvant désigner une autre cellule. La cellule peut représenter un noeud du graphe orienté et possèder deux fils. Le graphe orienté représente le monoïde engendré par les deux générateurs. Cette structure de données de bas niveau appelée grille, est la structure utilisée par l'interpréteur du langage LISP.
La cellule est identifiée par sa position dans la grille. Et elle mémorise deux pointeurs. Lorsqu'elle est utilisée, elle désigne un élément du monoïde. Son premier pointeur pointe sur la cellule représentant l'élément obtenue en le multipliant selon la loi * du monoïde par le premier générateur, et son second pointeur pointe sur la cellule représentant l'élément obtenue en le multipliant par le second générateur. Comme la construction passe nécessairement par une phase incomplète, on autorise une autre valeur pour ces pointeurs, qu'est la valeur Nil, et qui signifie que l'élément produit est non encore déterminé ou plus exactement non encore exploré.
On se place dans un cas un peu plus général où la cellule est composée non pas seulement de deux mots consécutifs mais d'un premier bloc de g mots consécutifs correspondant à g générateurs, d'un mot supplémentaire pour mémoriser une redirection vers un autre noeud, d'un mot supplémentaire pour mémoriser une relation vers un autre noeud, et d'un mot supplémentaire pour mémoriser différentes informations relatives au noeud en question.
Lorsque la cellule n'est pas utilisée, elle est dite libre. Les cellules libres sont rangées en une liste chainée, et la première cellule libre est désigner par le pointeur p qui est une variable globale. Chaque cellule libre posséde un pointeur pointant sur la cellule libre suivante ou sur Nil si c'est la dernière cellule libre. L'ordre des cellules libres dans la liste chainée est initialement identique à l'ordre d'adressage, mais par la suite, l'ordre diffèrera au grès des allocations et libérations de cellules.
La fonction InitMem( ) crée la grille M et initialise la valeur de p pointant sur la première cellule vide.
La fonction Malloc( ) alloue une cellule et retourne son adresse.
La fonction Free(x) libère la cellule d'adresse x.
Lorsqu'il n'y pas assez de cellules libres disponnibles, on effectue un nettoyage de la mémoire (en anglais, garbage collection), c'est à dire que l'on parcourt le graphe en marquant chaque noeud utilisé, puis on parcourt la liste des celulles libres en les marquant pareillement, puis on parcourt la grille dans l'ordre en libérant toutes les cellules non marquées, puis on parcourt le graphe pour démarquer chaque noeud, puis on parcourt la liste des cellules libres pour les démarqués.
La grille M est constituée d'une succession de cellules allouées initialement à l'aide de l'instruction M = malloc(sizeof(Cellule[Nmax])); où Nmax est la taille de la grille souhaitée en nombre de cellules. La cellule est structurée comme suit :
typedef struct {
unsigned int G[g]; // Les fils
unsigned int R; // Redirection
unsigned int S; // Relation
unsigned int T : 29; // Profondeur
unsigned int w : 1; // Flag de passage
} Cellule;Cellule * M;
Lorsque g=2, la cellule ainsi définie a une taille de 20 octets.
Pour un noeud x référencé dans la grille, nous avons :
On utilise des variables globales suivantes :
On utilise un jeu de variables globales pour spécifier une position et un déplacement pris par le curseur dans le graphe :
A partir d'un ensemble d'égalités de mots appelé théorie, on construit un graphe initial qui contient les éléments du monoïde découverts lors du parcours de ces égalités en partant de la racine.
Considérons par exemple les égalités ab=ba, aaa=1, bbb=1. Le graphe orienté initial s'affiche comme suit : 0(1(5(0,.),2),3(2,7(.,0))). Chaque noeud est représenté par un numéro identifiant, et s'il apparaît pour la première fois et qu'il possède au moins un fils, alors il est immédiatement suivie du couple de noeuds correspondant à ses fils respectifs. Le point "." désigne un noeud non exploré. Le 0 désigne le noeud racine.
Ce graphe orienté contient toute l'information apportée par la théorie et est appliqué au noeud racine. Réciproquement un graphe orienté quelconque possédant une racine c'est à dire un sommet permettant d'atteindre tous les noeuds, représente un ensemble d'égalités de mots et une théorie.
Par analogie à la physique, de même que la loi physique s'applique pareillement en tout point de l'espace, la théorie d'égalité du monoïde s'applique à chaque élément du monoïde. Et en l'appliquant à chaque élément, on complète le graphe et on complète introspectivement la théorie par de nouvelles égalités déduites.
On peut donc reprendre les égalités et les reparcourir en partant d'un noeud quelconque afin d'appliquer la théorie pour ce noeud.
Par quels noeuds commencer ? Par les noeuds connus selon cette démarche constructive, car un noeud inconnu ne peut apporter aucune information ayant un lien avec la racine, sauf s'il devient lui-même connu par la suite, suite à cette démarche constructive. C'est un argument de récurrence général qui abonde pourquoi il n'est pas utile d'ouvrir les branches non explorées. Si une branche restent indéfiniment inexplorée alors elle se comporte comme un fractal en recréant un graphe orienté copie du graphe en construction mais assurément disjoint.
Puis il faut utiliser les connaissances globales portée par le graphe en construction, une information haute telle que la profondeur d'un noeud c'est à dire la taille du chemin le plus court connu entre la racine et le noeud en question. On choisira comme première heuristique le choix des noeuds de profondeur connue inférieur à une borne K que l'on incrémentera.
On reparcourt les égalités de mots à partir d'un noeud de départ quelconque. Chaque mots va se traduire dans le graphe par le parcourt d'un chemin partant du noeud de départ en question et créant les noeuds manquants, puis chaque égalité de mots va se traduire par la fusion des noeuds finaux de chaque chemin.
On concrétise la fusion de deux noeuds en redirigeant l'un vers l'autre. Un noeud x possède une redirection (Champ R de la cellule) M[x].R et une redirection finale M[x].R.R.R.... appellée son représentant. Initialement, tout noeud est redirigé sur lui-mêmeet est son propre représentant.
Quant deux noeuds fusionnent, ils sont sensés avoir été préalablement remplacés par leur représentants respectifs, et c'est donc deux représentants que l'on fusionne. La fusion de deux représentants x et y s'opère en redirigeant l'un vers l'autre M[x].R=y. La redirection pouvant s'opérer dans un sens ou dans l'autre sens, on choisie le sens allant du noeud d'adresse la plus élevé vers le noeud d'adresse la moins élevé. Ceci afin de privilègier l'usage des petites adresses de noeud.
La redirection constitue un aspect, un protocole de bas niveau, un mécanisme d'unification de complexité linéaire grâce au fait que les redirections multiples se simplifient en cours de route.
Lors d'un déplacement, on mémorise le curseur précédent b, le déplacement opéré d, le curseur c et son représentant f. Nous avons c = M[b].G[d], et f = M[c].R.R.R.... Par convention, un noeud x qui n'est pas redirigé aura une redirection sur lui-même M[x].R=x, et sera donc son propre représentant.
Lors d'un déplacement caractérisé par les données b,d,c,f, on applique l'aspect. Cela consiste à établir les racourcies suivants : Le curseur c étant redirigé jusqu'à f par une succession de redirection, on établie le lien M[b].G[d]=f et on établie les redirections M[c].R=f, M[c].R.R=f , M[c].R.R.R=f....
A chaque déplacement un second aspect va calculer la profondeur connue du noeud atteint (champ T de la cellule). C'est la valeur minimum entre la profondeur du noeud et la profondeur du noeud précédent + 1, sachant que chaque nouveau noeud créé possède initialement la profondeur maximum enregistrable 0x7FFFFFFF.
La fonction dep(i) déplace le curseur c selon le iième générateur en créant le noeud s'il n'existe pas et en appliquant les deux aspects précédents, c'est à dire en effectuant une redirection si nécessaire et en calculant la profondeur connue.
La fonction chemin("aba") déplace le curseur c sur l'élément correspondant à c*aba en crée les noeuds nécessaires.
La fonction equation(x, "ab","ba") crée les chemins ab et ba à partir du noeud x, et fusionne les deux derniers noeuds. La dernière direction prise du deuxième chemin est modifiée vers le dernier noeud du premier chemin. Cela correspond à l'égalité "ab=ba" appliquée au noeud x. On autorise également la forme suivante equation(x,"1", "aaa") qui utilise une première chaine "1". Cela va fusionner le dernier noeud du second chemin avec le noeud x. La dernière direction prise du deuxième chemin sera modifiée vers x. Cela correspond à l'égalité "aaa=1" appliquée au noeud x.
La fonction equations(x, 3, "aa","bb","abab") crée les chemins aa, bb, abab à partir du noeud x, et fusionne les derniers noeuds de chaque chemin avec le dernier noeud du premier chemin. Le chiffre 3 indique le nombre de chemins égaux. la dernière direction prise de chaque chemin est modifiée vers le dernier noeud du premier chemin. Cela fusionne 3 noeuds. Cela correspond aux égalités "aa=bb, aa=abab" appliquées au noeud x. On autorise également la forme suivante equations (x, 3, "1", "aaa", "bb") qui utilise une première chaine "1". Cela va fusionner les derniers noeuds des chemins avec le noeud x. La dernière direction prise de chaque chemin autre que le premier chemin sera modifiée vers x. Cela correspond aux égalités "aaa=1, bb=1" appliquées au noeud x.
On regroupe toutes les équations en une théorie que l'on peut appliquer sur un noeud x de son choix à l'aide de la fonction theorie(x).
A priori, ces fonctions doivent s'appliquer sur un noeud x non redirigé, un noeud qui doit être son propre représentant c'est à dire qui doit vérifier M[x].R=x.
On programme une fonction creer( ) qui crée un noeud et l'initialise. La première utilisation de cette fonction va créer le noeud racine de numéro 0, auquel on associe une profondeur 0 à l'aide de l'instruction M[0].T=0
La fonction aff(u) affiche l'arbre de racine u. Elle se décompose en deux fonctions aff1(u) et aff0(u) exécutées dans cette ordre, où aff1(u) affiche l'arbre de racine u en marquant le passage (Champ w de la cellule) afin d'éviter les boucles, et où aff0(u) parcourt l'arbre de racine u pour enlever les marques de passage.
La fonction aff1(u) appelle récurcivement les seuls fils de u qui existent aff1(M[u].G[0]), aff1(M[u].G[1])....
Lors du parcours du graphe, on compte les noeuds connus, N, et les directions non explorées, D, et on détermine la profondeur du graphe, T. (Ces 3 variables globales N, D, T, ne sont modifiées que par la fonction d'affichage.)
On fixe la profondeur K égale à la profondeur du graphe initial. Puis on parcours le graphe à l'aide du curseur en ne dépassant pas le niveau de profondeur K. Et à chaque noeud ainsi connu on applique la théorie.
Mais mieux encore, puisque à chaque telle opération le graphe s'enrichie d'informations obtenues par introspection, ce n'est pas la théorie initiale qu'il convient d'appliquer au noeud mais la théorie enrichie que constitue le graphe en cours de construction pris par sa racine. Et mieux encore, puisque la théorie s'applique pareillement à tous les éléments du monoïde, si l'on procède à deux parcours du graphe en partant pour l'un de la racine et pour l'autre d'un noeud quelconque, alors à chaque boucle rencontrée dans l'un des parcours, correspond une boucle dans l'autre parcours, en complétant le graphe si nécessaire, chaque boucles désignant une égalité déduite. Chaque parcours correspond à un graphe. Cette unification des deux graphes nécessite l'établissement d'un lien relationnel des noeuds du premier graphe vers ceux du second graphe et réciproquement d'un lien relationnel des noeuds du second graphe vers ceux du premier graphe (champ R1 et R2 des cellules).
On utilise deux curseurs évoluant de façon parallèle. L'un va parcourir le graphe en partant de la racine, l'autre va suivre les mêmes mouvement que le premier mais en partant du noeud cible, et à chaque fois que l'un des curseurs détectera une boucle, il transmettra à l'autre curseur cette information qui procèdera alors à l'unification de deux noeuds le cas échéant à l'aide du pointage de redirection (champ R de la cellule).
Le pointage de redirection constitue un aspect, un protocole de bas niveau, un mécanisme d'unification de complexité linéaire grâce au fait que les redirections multiples se simplifient en cours de route lors de l'exécution-même de l'aspect.
La réplication du graphe ainsi décrite peut partir en vrille dans un processus de construction sans fin. Pour éviter cela, on cadre le processus de construction du graphe en posant des échelons. Le processus ne parcourt qu'une profondeur maximum du graphe égale à celle du graphe initial spécifique à l'échelon. Puis on opère cette réplication sur tous les noeuds connus dans un ordre quelconque mais de profondeur inférieure ou égale à la profondeur du graphe initial spécifique à l'échelon qui constitue le cadre de cette construction.
--- 22 mars 2014 ----
Si l'alphabet est munie d'une relation d'ordre, alors il existe sur le langage de caractères, une relation d'ordre canonique appelée ordre lexicographique :
1 (représente la chaine vide)
a
b
aa
ab
ba
bb
aaa
aab
aba
abb
baa
bab
bba
bbb
aaaa
aaab
.....
Et pour passer à la chaine suivante selon cet ordre lexicographique, on applique un algorithme comparable à l'incrémentation d'un entier avec passage de retenue. La variable qui mémorise successivement les différentes chaines selon l'ordre lexicographique s'appelle un compteur.