J'ai parlé un peu trop vite en effet y'a beaucoup de blabla non trivial dans les articles wikipedia, ici l'argument est tout bête je vais essayer de le raconter sans mots techniques.

Ce que tu as prouvé dans ton message, c'est que pour montrer l'unicité du mot terminal, en ayant déjà la terminaison, il suffit d'avoir la confluence.

Du coup on veut juste montrer la confluence de ton truc. On part d'un mot u tel qu'on puisse appliquer deux réécritures différentes (deux applications de f avec un k différent), qui donnent deux mots v et v'. On veut faire revenir v et v' vers un même mot w.
Si les deux réécritures avaient lieu à des endroits disjoints du mot u (par exemple u = 1001011, v = 11011 et v' = 10010) alors c'est trivial on a pas touché à l'autre doublet et on peut appliquer la même réécriture une deuxième fois (on arrive à w = 110 dans les deux cas).
Le cas qui pourrait poser problème, c'est si les deux réécritures se chevauchent. C'est ça qu'on appelle une "paire critique". Ici, les seules possibilités c'est d'avoir 000 (ou 111) dans un mot, on peut réécrire les deux premiers zéros ou bien le deuxième et le troisième (000 vs 000). Mais en fait ça donne v = v' = 0, et donc tu n'as rien à faire pour les "rejoindre".

Du coup, c'est confluent, et donc bah t'as fini

Et pour repondre TheorieDeGalois, ces trucs là par exemple ont des applications mathématiques quand on regarde des présentations de groupes (ou de monoides, etc). En gros tu vas définir un groupe en donnant un ensemble de générateurs (par exemple {a, b}), ce qui te donne le groupe libre engendré par ces générateurs, et tu vas le quotienter par certaines relations (par exemple ababa = a^-1).
Pour étudier les groupes définis de cette manière, on peut avoir recours à des techniques de systèmes de réécriture, par exemple si on a un système de réécriture confluent et qui termine, étant donnes deux mots sur l'alphabet {a, b, a^-1, b^-1}, pour savoir s'ils représentent le même élément ou non, il suffit de les réduire comme un bourrin jusqu'à obtenir une forme normale.

On tombe sur ces bestioles en topologie algébrique il me semble.

Putain ce topic m'a (re)donné le cancer

Ce génie.

Le 27 septembre 2016 à 00:24:09 AlphaCygni a écrit :
J'ai parlé un peu trop vite en effet y'a beaucoup de blabla non trivial dans les articles wikipedia, ici l'argument est tout bête je vais essayer de le raconter sans mots techniques.

Ce que tu as prouvé dans ton message, c'est que pour montrer l'unicité du mot terminal, en ayant déjà la terminaison, il suffit d'avoir la confluence.

Du coup on veut juste montrer la confluence de ton truc. On part d'un mot u tel qu'on puisse appliquer deux réécritures différentes (deux applications de f avec un k différent), qui donnent deux mots v et v'. On veut faire revenir v et v' vers un même mot w.
Si les deux réécritures avaient lieu à des endroits disjoints du mot u (par exemple u = 1001011, v = 11011 et v' = 10010) alors c'est trivial on a pas touché à l'autre doublet et on peut appliquer la même réécriture une deuxième fois (on arrive à w = 110 dans les deux cas).
Le cas qui pourrait poser problème, c'est si les deux réécritures se chevauchent. C'est ça qu'on appelle une "paire critique". Ici, les seules possibilités c'est d'avoir 000 (ou 111) dans un mot, on peut réécrire les deux premiers zéros ou bien le deuxième et le troisième (000 vs 000). Mais en fait ça donne v = v' = 0, et donc tu n'as rien à faire pour les "rejoindre".

Du coup, c'est confluent, et donc bah t'as fini

GG

voyons si j'ai compris avec le cas general d'un nombre consecutif quelquonque de lettres identiques de taille n.
Si les deux ensemble consecutif sont disjoint en considerant la composition de ces 2 processus. Sinon s'ils se chevauchent le plus petit segment contenant ces 2 ensemble est une paire critique, or l'image de cette paire critique est la meme dans le deux cas (bon a la relecture c'est exactement la meme preuve )

c'etait tout con en fait

Pour avoir des trucs moin directe il faudrait des fonctions f non "locale" (je trouve pas et je serais pas etonne que ca n'existe pas)