Ensembles de test et morphismes sans répétition Francis Wlazinski - Gwénaël Richomme

1

Ensembles de test etEnsembles de test etmorphismes sans répétitionmorphismes sans répétition

Francis Wlazinski - Gwénaël Richomme

2

IntroductionIntroduction

• Alphabet ensemble fini de symboles (lettres)Exemples : {} {0,1}

{a,b,c} {a,b}

Exemples : abaca abbabaabbaababbabaababbaabbabaabbaababbaabb a

• Mot suite finie de lettres

• C’est de l’informatique ???

(ASCII binaire) 1000011010011111001011110011111010001000

001100100110010101000001101100010011111010011101110

110011011011111110010110110111000011110100110100111

10001111010111001010100000011111101111110111111

• ADN

Applications de la combinatoire des mots :

- compression de données

- biologie : recherche de séquences

- systèmes distribués, calcul parallèle

- compilateurs

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de abaababacaba

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababaabacaba

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacabaaba

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement

Puissance k

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*

Puissance k

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou aaa

Puissance k

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : aa bcbc aa bcbc aa ou aaa

Puissance k

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou a a aa a a

Puissance k

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou aaa

Puissance k : uk avec u A+ A*\{} et k *Exemples : abab k carré

ababab k cubeabababab k puissance 4

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou aaa

Puissance k : uk avec u A+ A*\{} et k *Exemples : ab abab ab k carré

ababab k cubeabababab k puissance 4

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou aaa

Puissance k : uk avec u A+ A*\{} et k *Exemples : abab k carré

ab ab abab ab ab k cubeabababab k puissance 4

• A* monoïde libre engendré par l’alphabet A.

• u facteur de v v p u s avec p,s A*Exemple : aba est facteur de ababacaba

• Répétitions :

Chevauchement : x u x u x avec x A et u A*Exemples : abcabca ou aaa

Puissance k : uk avec u A+ A*\{} et k *Exemples : abab k carré

ababab k cubeab ab ab abab ab ab ab k puissance 4

ab abab ab ba est un mot sans chevauchement

• Mots sans chevauchement, mots sans carré, mots sans cube, mots sans puissance k.

f (bb aacacbaacacb)

f (b) f (aacacb)

f (b) f (a acacba acacb) f (b) f (a) f (acacb)

f (b) f (a) f (a) f (c) f (a) f (c) f (b)

f (baacacb)

Exemple :

• Morphisme : f : A* B* vérifiant f (u v) f (u) f (v) u,v A*

Exemple : soit f un morphisme défini sur {a,b,c}*

ababba est un mot sans chevauchementababba est un mot sans chevauchement

• Exemples de morphismes :

Le morphisme de Thue-Morse : {a,b}* {a,b}* a ab

b ba(abba) ab abbaba

Le morphisme de Fibonacci (a) ab et (b) a

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes qui préservent l’absence d’une répétitionMorphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

• Morphisme sans chevauchement : morphisme qui préserve l’absence de chevauchement

Exemples :

le morphisme (échange) E : {a,b}* {a,b}* a b b a

est sans chevauchement.

le morphisme de Thue-Morse est sans chevauchement

(Thue 1912).

le morphisme de Fibonacci n’est pas sans chevauchement :

bba sans chevauchement

(bba) a a aa a ab

chevauchementchevauchement chevauchementchevauchement

• Morphisme sans : morphisme qui préserve l’absence de

Exemples :

le morphisme (échange) E : {a,b}* {a,b}* a b b a

est sans chevauchement.

le morphisme de Thue-Morse est sans chevauchement

(Thue 1912).

le morphisme de Fibonacci n’est pas sans chevauchement :

bba sans chevauchement

(bba) a a aa a ab

• Morphisme sans : morphisme qui préserve l’absence de

carrécarré carrécarré

cubecube cubecube

• Morphisme sans : morphisme qui préserve l’absence de

puissance puissance kk puissance puissance kk

• Morphisme sans : morphisme qui préserve l’absence de

le morphisme de Thue-Morse est sans puissance k pour

tout entier k 2 (Brandenburg 1983).

Exemples :

le morphisme échange sur {a,b}* est sans puissance k

pour tout entier k 2.

le morphisme d’Istrail défini par

h(a) abc, h(b) ac et h(c) b n’est pas sans carré :

aba sans carréh(aba) abc ac ac ac abc

• T ensemble de test fini pour morphismes

sans de A* vers B*: chevauchement

f sans chevauchement f (T) sans chevauchement

 f : A* B*,

Exemple : {a,aa} est un ensemble de test pour les morphismes sans chevauchement de {a}* vers B*.

• T ensemble de test fini pour morphismes

sans de A* vers B*: chevauchement

f sans chevauchement f (T) sans chevauchement

 f : A* B*,

Exemple : {aa} est un ensemble de test pour les morphismes sans chevauchement de {a}* vers B*.

• T ensemble de test fini pour morphismes

sans de A* vers B*: chevauchementchevauchement

f sans chevauchementchevauchement f (T) sans chevauchementchevauchement

 f : A* B*,

Exemple : {aa} est un ensemble de test pour les morphismes sans chevauchement de {a}* vers B*.

• T ensemble de test fini pour morphismes

sans de A* vers B*: carrécarré

f sans carrécarré f (T) sans carrécarré

 f : A* B*,

Exemple : {a} est un ensemble de test pour les morphismes sans carré de {a}* vers B*.

• T ensemble de test fini pour morphismes

sans de A* vers B*: cubecube

f sans cubecube f (T) sans cubecube

 f : A* B*,

Exemple : {aa} est un ensemble de test pour les morphismes sans cube de {a}* vers B*.

• T ensemble de test fini pour morphismes

sans de A* vers B*: puissance puissance kk

f sans puissance puissance kk f (T) sans puissance puissance kk

 f : A* B*,

Exemple : {a k} est un ensemble de test pour les

morphismes sans puissance k de {a}* vers B*.

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 Lec 85 ? ?

Card B = Card A Cro 82 Cro 82 RS 99 ? Lec 85 ? ? ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? ? ?

Nombre fini de mots et/ou de morphismes

Inexistence d'ensemble de test fini

Existence d'un ensemble de test fini

Caractérisation de tous les ensembles de test finis

Ensembles de test finis

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 Lec 85 ? ?

Card B = Card A Cro 82 Cro 82 RS 99 ? Lec 85 ? ? ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? ? ?

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

Ensembles de test finis

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance k

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes sans chevauchementMorphismes sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance k

37

Morphismes sans chevauchementMorphismes sans chevauchement

PropositionSi Card(B) Card(A) 3, il n'y a pas d'ensemble de test fini pour morphismes sans chevauchement de A* vers B*.

Idée de la preuve u{a,b}* tel que a u a sans chevauchement.f u : {a,b,c}* {a,b,c}* f u(a) abc, f u(b) bca et f u(c) cababc f u(u) abccaab.

w mot sans chevauchement sur {a,b,c},

f u(w) contient un chevauchement c a u a c facteur de w.

Proposition

f : {a,b}* B* non-effaçant.f (TB) sans chevauchement f sans chevauchement

TB {aba, bab, abba, baab}.

ThéorèmeCard(B) 3 et T {a,b}*.T ensemble de test pour morphismes sans chevauchement non-effaçants de {a,b}* vers B*

• wT, w sans chevauchement • TB Fact(T).

Corollaire

Card(B) 3 et T {a,b}*.T ensemble de test pour morphismes sans chevauchement de {a,b}* vers B*

Corollairef : {a,b}* B* avec Card(B) 3.f sans chevauchement

sans chevauchement

• wT, w sans chevauchement. • TB Fact(T). • uT / |u|a 3. • vT / |v|b 3.

TB {aba, bab, abba, baab}.

f (abbabaab)f (abbabaabaab)f (abbabbabaab)f (abbaabbabaab)f (abbabaabbaab)f (abbabaab)

• wT, w sans chevauchement. • TB Fact(T).

• • uuTT / | / |uu||aa 3. 3.

• • vvTT / | / |vv||bb 3. 3.

• wT, w sans chevauchement. • TB Fact(T). • uT / |u|a 3. • vT / |v|b 3.

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes sans chevauchement

Morphismes uniformes sans chevauchementMorphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance k

41

Morphismes uniformes sans Morphismes uniformes sans chevauchementchevauchement

Théorème

Card(B) Card(A) 3 et T A*.T ensemble de test pour morphismes uniformes sans chevauchement de A* vers B*

• wT, w sans chevauchement. • TU Fact(T).

TU1 { xw0x | x A, w0 A* et a A, |xw0|a 1}

x,y, A et w1,w2 A*

TU2 xw1w2y a A, |w1w2 |a 1

|w1| |w2| 1, |w2|x 0 |w1|y

TU TU1 TU2

où A alphabet

Corollaire

Card(B) Card(A) 3 et f : A* B* uniforme.

f sans chevauchement f sans chevauchement jusqu'à Card(A) 2.

Théorème

T {a,b}*.T ensemble de test pour morphismes uniformes sans chevauchement de {a,b}* vers B*

(si Card(B) 2)

• {ab,ba} Fact(T) • {aa,bb} Fact(T) • {aab,bba,ababb,babaa} Fact(T) • {baa,abb,bbaba,aabab} Fact(T)

(si Card(B) 2)

• {aa,bb,aba,bab} Fact(T) • {aab,bba,ababb,babaa} Fact(T) • {baa,abb,bbaba,aabab} Fact(T)

CorollaireCard(B) Card(A) 2 et f : A* B* uniforme.

f sans chevauchement f sans chevauchement jusqu'à 3.

Corollairef : {a,b}* {a,b}* uniforme.f sans chevauchement f (abba) sans chevauchement

Corollairef : {a,b}* B* uniforme et Card(B) 3.f sans chevauchement

f (aababb) sans chevauchement

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cubeMorphismes sans cube

Morphismes sans puissance k

46

w mot sans cube sur A,

f u,v(w) contient un cube a v a u a facteur de w.

Morphismes sans cubeMorphismes sans cube

PropositionSi Card(A) 3 et Card(B) 2, il n'y a pas d'ensemble de test fini pour morphismes sans cube de A* vers B*.

Idée de la preuve aA, x,y,zA et u,v(A\{a})* sans cube tels que (u,v) . f u,v : A* (A\{a} {x,y,z})* f u,v(a) x (z y u x y v x)2 z y et f u,v(b) b b A\{a}.

w mot sans cube sur A,

f u,v(w) contient un cube aa vv aa uu aa facteur de w.

Tmin {abbabba, ababba, abbaba, aabba, abbaa, ababa, baabaab, babaab, baabab, bbaab, baabb, babab}

ThéorèmeT {a,b}*.T ensemble de test pour morphismes sans cube de {a,b}* vers B*

• wT, w sans cube • Tmin Fact(T).

Corollairef : {a,b}* B*

f sans cube f (aabbababbabbaabaababaabb) sans cube

Corollaire (Leconte 85)f : {a,b}* B*

f sans cube

f sans cube jusqu’à 7.

Les images par f de tous les mots sans cube de longueur 7 sont sans cube.

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une répétition

Morphismes sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance Morphismes sans puissance kk

50

Morphismes sans puissance Morphismes sans puissance kk

Proposition

Si Card(A) 3 et Card(B) 2, il n'y a pas d'ensemble de

test fini pour morphismes sans puissance k de A* vers B*.

Idée de la preuve

aA, x,y,zA et u,v(A\{a})* sans puissance k

f u,v : A* (A\{a} {x,y,z})*

a x(z y u x y v x)k1 z y

b b b A\{a}.

• (tk)k 2 est la suite d'entiers définie par :

t2 3 tk si k 4 est pair

t3 4 tk si k 5 est

impair

Définitions

• w mot primitif si w v n n 1

k2

2k (k 1) 2

Proposition

Un morphisme binaire sans puissance k ( 2) jusqu’à tk est

primitif.

• f morphisme primitif si f préserve les mots primitifs

Théorèmef morphisme primitif binaire et k 2.

f sans puissance k f sans puissance k jusqu'à 2k 1.

Corollairef morphisme binaire et k 2.

f sans puissance k f sans puissance k jusqu'à t'k

avec t'2 3, t'3 7 et t'k tk si k 4.

CorollaireA alphabet binaire et k 2.{wA* / |w| k2 et w sans puissance k} est un ensemble de test pour morphismes sans puissance k sur A.

Morphismes qui préservent l’absence d’une répétition

Morphismes qui engendrent des mots sans une Morphismes qui engendrent des mots sans une répétitionrépétition

Morphismes sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance k

54

Rappel : morphisme de Thue-Morse : {a,b}* {a,b}*a abb ba (a)

ab2(a ) ((a)) (ab)

3(a ) (2(a)) (abba) 4(a ) abbabaabbaababba5(a ) abbabaabbaababbabaababbaabbabaab

abba

abba abba

Mots engendrés par morphismesMots engendrés par morphismes

(a ) lim n(a ) n

Proposition (Thue 12)f endomorphisme sur {a,b} sans chevauchement

f i ou f E i pour un entier i.

Proposition (Séébold 84)f endomorphisme sur {a,b} prolongeable en a.

f engendre un mot sans chevauchement f sans chevauchement

Proposition (Karhumäki 81)f endomorphisme sur {a,b} prolongeable en a.

f engendre un mot sans chevauchement

f 7(a) sans chevauchement

Proposition (Crochemore 82)f endomorphisme sur {a,b,c} prolongeable en a.

f engendre un mot sans carré

1. f ({abc, acb, bac, bca, cab, cba}) sans carré 2. f (xyx) ou f (xzx) ou f (xyzx) sans carré pour toute permutation 3. f (w) sans carré wFact(f (a)) et |w| 5

Proposition (Crochemore 82)f endomorphisme sur {a,b,c} prolongeable en a.

f engendre un mot sans carré f sans carré

Proposition (Berstel 79 - Crochemore 82)f endomorphisme sur {a,b,c} prolongeable en a.

f engendre un mot sans carré f p(a) sans carré

Propositionf endomorphisme sur {a,b} prolongeable en a.

f engendre un mot sans cube f sans cube

Proposition (Karhumäki 83)f endomorphisme sur {a,b} prolongeable en a.

f engendre un mot sans cube

f 10(a) sans cube

Contre-exemple :

f (a) abba

f (b) baababaababbaabbabaabbaababbaabbabaababaababbaab

babaabbaababbaabbabaababaab

Propositionf endomorphisme sur {a,b} prolongeable en a.

f engendre un mot sans cube

1. f ({abba, baab, aba, bab}) sans cube 2. f (w) sans cube wFact(f (a)) et |w| 7

longueur de f 4 6 8 10 12méthode Kar : 1 mot de longueur 65536 279936 2097152 10000000 35831808méthode RW : 36 mots de longueur 28 42 56 70 84

Exemple :

Dans le cas d’un endomorphisme uniforme f tel que :

| f(a)|a | f(a)|b | f(b)|a | f(b)|b,

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 Lec 85 ? ?

Card B = Card A Cro 82 Cro 82 RS 99 ? Lec 85 ? ? ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? ? ?

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

Conclusion : Ensembles de test finis

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 Lec 85 ? ?

Card B = Card A Cro 82 Cro 82 RS 99 RW 02a Lec 85 ? ? ?

> Card A Cro 82 Cro 82 RW 02a RW 02a Lec 85 ? ? ?

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

Conclusion : Ensembles de test finis

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 RW 00 RW 00 ?

Card B = Card A Cro 82 Cro 82 RS 99 RW 02a RW 00 RW 00 ? ?

> Card A Cro 82 Cro 82 RW 02a RW 02a RW 00 RW 00 ? ?

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

Conclusion : Ensembles de test finis

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 RW 00 RW 00 Wla 01 RW 02b

Card B = Card A Cro 82 Cro 82 RS 99 RW 02a RW 00 RW 00 Wla 01 RW 02b

> Card A Cro 82 Cro 82 RW 02a RW 02a RW 00 RW 00 Wla 01 RW 02b

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 ? ? Lec 85 ? Lec 85 ?

Conclusion : Ensembles de test finis

Morphismes sans

Carré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2 > 2 1 2 > 2< Card A Cro 82 Cro 82 RW 00 RW 00 Wla 01 RW 02b

Card B = Card A Cro 82 Cro 82 RS 99 RW 02a RW 00 RW 00 Wla 01 RW 02b

> Card A Cro 82 Cro 82 RW 02a RW 02a RW 00 RW 00 Wla 01 RW 02b

Morphismes uniformes sansCarré Chevauchement Cube Puissance k

Card A < 3 3 > 3 1 2 > 2 1 2&3 > 3 1 2&3 > 3< Card A Cro 82 Cro 82 Lec 85 ? Lec 85 ?

Card B = Card A Cro 82 Cro 82 RW 02a RW 02a Lec 85 ? Lec 85 ?

> Card A Cro 82 Cro 82 RW 02a RW 02a Lec 85 ? Lec 85 ?

Conclusion : Ensembles de test finis

Conclusion : problèmes connexes

• Puissances fractionnaires

• Sans puissance k sans puissance k 1

• Sans chevauchement sans puissance k

• Sans cube primitif (cas non binaire)

65