Présentation

• Soient u et v deux mots distincts. Un mot w est un séparateur de u et v si w est sous-mot d'un et un seul des deux mots u et v.
• Le texte étudie quelques propriétés de l'ensemble sepmin(u,v) des séparateurs minimaux de u et v.
• L'article d'Emmanuelle Garel, intitulé Minimal Separators of two words, a été présenté au congrès CPM~94, et publié dans le numéro 684 des Lecture Notes in Computer Sciences (ed. Springer). Le but de l'article est la construction d'un automate reconnaissant sepmin(u,v).
• Sur le thème des sous-mots, cliquez ici pour voir un texte qui étudie des aspects combinatoires de l'ensemble des sous-mots communs à deux mots sur l'alphabet {a,b}, puis propose une démonstration du théorème de Higman.