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


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


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


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



• Répétitions :

Chevauchement

Puissance k



• Répétitions :

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

Puissance k



• Répétitions :

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

Puissance k



• 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



• 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



• Répétitions :


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

ababab k cubeabababab k puissance 4



• Répétitions :


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

ababab k cubeabababab k puissance 4



• Répétitions :



ab ab abab ab ab k cubeabababab k puissance 4



• Répétitions :



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


• 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


carrécarré carrécarré

cubecube cubecube


puissance puissance kk puissance puissance kk


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*.


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*.


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*.


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*.


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*.


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




> 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 sans chevauchement

Morphismes uniformes sans chevauchement

Morphismes sans cube

Morphismes sans puissance k



Morphismes sans chevauchementMorphismes sans chevauchement




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 uniformes sans chevauchementMorphismes uniformes sans chevauchement



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 sans cubeMorphismes sans cube


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 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 engendrent des mots sans une Morphismes qui engendrent des mots sans une répétitionrépétition





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




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





Conclusion : Ensembles de test finis

Morphismes sans



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 sans


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 sans


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 sans


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



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 : problèmes connexes

• Puissances fractionnaires

• Sans puissance k sans puissance k 1

• Sans chevauchement sans puissance k

• Sans cube primitif (cas non binaire)

65

Documents

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