Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~anromash/workshop/slides/rao.pdf Äàòà èçìåíåíèÿ: Sat Jun 26 23:30:29 2010 Äàòà èíäåêñèðîâàíèÿ: Sun Sep 12 13:03:33 2010 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: images

Last Cases of Dejean's Conjecture

MichaÊl Rao
CNRS - LaBRI - UniversitÈ Bordeaux 1, France

rodlriFfr httpXGGwwwFlriFfrG¸ro

MichaÊl Rao

Last Cases of Dejean's Conjecture


Rep etitions

(p , q )

is a

repetition
and prex of

in a word

w

if :

pq is p= q is a
The

a factor of

w
.

,

pq

exponent

of the rep etition is

|| | |.

Squares are rep etitions of exp onent 2. A word is said

pq p

x -free

(resp.

rep etition of exp onent

y

x

+ -free) if it do es not contain a

with

y x

(resp.

y >x

).

MichaÊl Rao

Last Cases of Dejean's Conjecture


Rep etitions

(p , q )

is a

repetition
and prex of

in a word

w

if :

pq is p= q is a
The

a factor of

w
.

,

pq

exponent

of the rep etition is

|| | |.

Squares are rep etitions of exp onent 2. A word is said

pq p

x -free

(resp.

rep etition of exp onent

y

x

+ -free) if it do es not contain a

with

y x

(resp.

y >x

).

MichaÊl Rao

Last Cases of Dejean's Conjecture


Rep etitions

(p , q )

is a

repetition
and prex of

in a word

w

if :

pq is p= q is a
The

a factor of

w
.

,

pq

exponent

of the rep etition is

|| | |.

Squares are rep etitions of exp onent 2. A word is said

pq p

x -free

(resp.

rep etition of exp onent

y

x

+ -free) if it do es not contain a

with

y x

(resp.

y >x

).

MichaÊl Rao

Last Cases of Dejean's Conjecture


Dejean's Conjecture

Let RT

(k )

b e the smallest

word over a

k

x

such that there is an innite

-letter alphab et (

k

x

+ -free

2).

Conjecture (Dejean's conjecture, 1972)

RT(

k) =



7 4 7 5

k

-

k

1

if k = 3 if k = 4 otherwise.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Dejean's Conjecture

Already proved for:

k= k= k=
5 12

2 3 4 11 14

[Thue 1906] [Dejean 1972] [Pansiot 1984] [Moulin Ollagnier 1992] [Currie, Mohammad-No ori 2004] [Carpi 2007] [Currie, Ramp ersad 2008,2009] 38 26 [R. 2009] [Currie, Ramp ersad 2009]

k
33 27

k

k k
8 15

k

k

MichaÊl Rao

Last Cases of Dejean's Conjecture


Dejean's Conjecture

Already proved for:

k= k= k=
5 12

2 3 4 11 14

[Thue 1906] [Dejean 1972] [Pansiot 1984] [Moulin Ollagnier 1992] [Currie, Mohammad-No ori 2004] [Carpi 2007] [Currie, Ramp ersad 2008,2009] 38 26 [R. 2009] [Currie, Ramp ersad 2009]

k
33 27

k

k k
8 15

k

k

MichaÊl Rao

Last Cases of Dejean's Conjecture


k=

2 and

k=

3

Theorem (Thue 1906)

Thue-Morse word (i.e. xed point of f (a) = abcacbcabcbacbcacba f (b) = bcabacabcacbacabacb f (c ) = cabcbabcabacbabcbac
Theorem (Dejean 1972)

0



01 1

,



10

) is

2

+

-free.

A xed point of f is

7 4

+

-free.

Theorem (Brandenburg 1983)

Fixed point method does not work for k 4.
MichaÊl Rao Last Cases of Dejean's Conjecture


k=

2 and

k=

3

Theorem (Thue 1906)

Thue-Morse word (i.e. xed point of f (a) = abcacbcabcbacbcacba f (b) = bcabacabcacbacabacb f (c ) = cabcbabcabacbabcbac
Theorem (Dejean 1972)

0



01 1

,



10

) is

2

+

-free.

A xed point of f is

7 4

+

-free.

Theorem (Brandenburg 1983)

Fixed point method does not work for k 4.
MichaÊl Rao Last Cases of Dejean's Conjecture


k=

2 and

k=

3

Theorem (Thue 1906)

Thue-Morse word (i.e. xed point of f (a) = abcacbcabcbacbcacba f (b) = bcabacabcacbacabacb f (c ) = cabcbabcabacbabcbac
Theorem (Dejean 1972)

0



01 1

,



10

) is

2

+

-free.

A xed point of f is

7 4

+

-free.

Theorem (Brandenburg 1983)

Fixed point method does not work for k 4.
MichaÊl Rao Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

If a word length

k-

w

on a

k

-letter alphab et is

1 consists of

k-

1 dierent letters.

k k

-1 -2 -free, then every factor of

w

can b e enco ded by a binary word 0 1 if if

Pk (w ):
.

Pk (w )[i ] = w P6 (w )
Remark: If

w [i + k - 1] = w [i ] w [i + k - 1] {w [i ], . . . , w [i + k - 2]}
4 5 1 0 6 1 3 0 2 1 4 1 1 0
is

= =

1

2

3

5 1

... ...
}

w

validates Dejean's conjecture then

Pk (w

)

{00,

111 -free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

Let i.e.

Mk ()

b e inverse of

Pk ().

(s.t.

Mk (w

)[1.. - 1] =

k

1

...

k

-

1)

Pk (Mk (w )) = w w
4

for every binary word

w

.

Let

b e a xed p oint of

h4 : 0

101101, 1



10.

Theorem (Pansiot 1984)

M4 (w4 ) is

7 5

+

-free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Pansiot's Co ding

Let i.e.

Mk ()

b e inverse of

Pk ().

(s.t.

Mk (w

)[1.. - 1] =

k

1

...

k

-

1)

Pk (Mk (w )) = w w
4

for every binary word

w

.

Let

b e a xed p oint of

h4 : 0

101101, 1



10.

Theorem (Pansiot 1984)

M4 (w4 ) is

7 5

+

-free.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Pansiot's co ding can also b e viewed by the way of an action on the symmetric group Let

Sk

:



b e the morphism b etween 12

{0, 1}

and

(0) = (
For all

. . . k - 1)

Sk
2

such that: 1

and

(1) = (1

...k -

k)
.

i

0 and 1

j k-

1,

Mk (w )[i + j ] = (w [1..i ])(j ) j >i

i

Mk (w )[i .. i + k - 1] = Mk (w )[j .. j + k - 1] (w [i + 1 .. j ]) = Idk .

(for

)

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Pansiot's co ding can also b e viewed by the way of an action on the symmetric group Let

Sk

:



b e the morphism b etween 12

{0, 1}

and

(0) = (
For all

. . . k - 1)

Sk
2

such that: 1

and

(1) = (1

...k -

k)
.

i

0 and 1

j k-

1,

Mk (w )[i + j ] = (w [1..i ])(j ) j >i

i

Mk (w )[i .. i + k - 1] = Mk (w )[j .. j + k - 1] (w [i + 1 .. j ]) = Idk .

(for

)

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Pansiot's co ding can also b e viewed by the way of an action on the symmetric group Let

Sk

:



b e the morphism b etween 12

{0, 1}

and

(0) = (
For all

. . . k - 1)

Sk
2

such that: 1

and

(1) = (1

...k -

k)
.

i

0 and 1

j k-

1,

Mk (w )[i + j ] = (w [1..i ])(j ) j >i

i

Mk (w )[i .. i + k - 1] = Mk (w )[j .. j + k - 1] (w [i + 1 .. j ]) = Idk .

(for

)

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Pansiot's co ding can also b e viewed by the way of an action on the symmetric group Let

Sk

:



b e the morphism b etween 12

{0, 1}

and

(0) = (
For all

. . . k - 1)

Sk
2

such that: 1

and

(1) = (1

...k -

k)
.

i

0 and 1

j k-

1,

Mk (w )[i + j ] = (w [1..i ])(j ) j >i

i

Mk (w )[i .. i + k - 1] = Mk (w )[j .. j + k - 1] (w [i + 1 .. j ]) = Idk .

(for

)

MichaÊl Rao

Last Cases of Dejean's Conjecture


A picture...

|u | = k -

1.

u
w
:

u

Pk (w ):
(v ) =

v
Id .

Then

k

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

A rep etition

(p , q )

is

short

if

|q | < k -
if

1.

(Note: if forbidden A rep etition is a



b ounded size.)

kernel repetition

|q | k -

1.

On Pansiot's co des:

(p , q ) is (p ) =

a

Id .

k

-kernel repetition

if

(p , q )

is a rep etition, and

Lemma (Moulin Ollagnier)

Mk (w ) has a kernel repetition (p , q ) w has a -kernel repetition (p , q ) with |p | = |p | and |q | = |q | - k + 1 .

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

A rep etition

(p , q )

is

short

if

|q | < k -
if

1.

(Note: if forbidden A rep etition is a



b ounded size.)

kernel repetition

|q | k -

1.

On Pansiot's co des:

(p , q ) is (p ) =

a

Id .

k

-kernel repetition

if

(p , q )

is a rep etition, and

Lemma (Moulin Ollagnier)

Mk (w ) has a kernel repetition (p , q ) w has a -kernel repetition (p , q ) with |p | = |p | and |q | = |q | - k + 1 .

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

A rep etition

(p , q )

is

short

if

|q | < k -
if

1.

(Note: if forbidden A rep etition is a



b ounded size.)

kernel repetition

|q | k -

1.

On Pansiot's co des:

(p , q ) is (p ) =

a

Id .

k

-kernel repetition

if

(p , q )

is a rep etition, and

Lemma (Moulin Ollagnier)

Mk (w ) has a kernel repetition (p , q ) w has a -kernel repetition (p , q ) with |p | = |p | and |q | = |q | - k + 1 .

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

To prove Dejean's conjecture for

k

5, nd a morphism

h

s.t.:

Mk (w ) w
where

has no forbidden short rep etition,

has no

-kernel

rep etition

(p , q )

with

|

p q |+ k |p |

-1

>

k

-1 .

k

w

is a xed p oint of

h

.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Idea: Limit us to

h

such that:

(h(0)) = · (0) · (h(1)) = · (1) ·
for a

-1 and -1 ,

Sk

.

Lemma (Moulin Ollagnier)

Let (p , q ) be a -kernel repetition in w . If q is long enough, then (p , q ) is an image by h of a smaller -kernel repetition in w .

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's ideas

Idea: Limit us to

h

such that:

(h(0)) = · (0) · (h(1)) = · (1) ·
for a

-1 and -1 ,

Sk

.

Lemma (Moulin Ollagnier)

Let (p , q ) be a -kernel repetition in w . If q is long enough, then (p , q ) is an image by h of a smaller -kernel repetition in w .

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's results

Let

w

b e a xed p oint of

h

. -free is decidable:

Checking if check

k Mk (w ) is k - if Mk (w ) has

+
1

no small forbidden rep etition,

check if iterated images of small kernel rep etitions in not forbidden.

w

are

Moulin Ollagnier gives morphisms

Mk (wk )


is

k

-

k

+

1

-free (where

w

k

h

k

for 5

k

11 such that

is a xed p oint of

Dejean's conjecture holds for 5

k

hk

).

11.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's results

Let

w

b e a xed p oint of

h

. -free is decidable:

Checking if check

k Mk (w ) is k - if Mk (w ) has

+
1

no small forbidden rep etition,

check if iterated images of small kernel rep etitions in not forbidden.

w

are

Moulin Ollagnier gives morphisms

Mk (wk )


is

k

-

k

+

1

-free (where

w

k

h

k

for 5

k

11 such that

is a xed p oint of

Dejean's conjecture holds for 5

k

hk

).

11.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Moulin Ollagnier's morphisms

h5 : h6 : h7 : h8 : h9 : h10 : h11 :

( 0 1 ( 0 1 ( 0 1 ( 0 1 ( 0 1 ( 0 1 ( 0 1

010101101101010110110 101010101101101101101 010101101101011010110 101011010110110101101 0110110110110101101101101010 1010110110110101101101101101 1011010101101011010110101010 1011010101011011011010101101 101011010110110101011010110110101010 101010110110110101011011010110101101 1010101011011011011010101011011011010110 1010101011011011010110101010101011010101 1010101010101101101011010110101010110110 1010101010101011011011011011011010101101

MichaÊl Rao

Last Cases of Dejean's Conjecture


New results

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Moulin Ollagnier ideas can b e extended to HDOLs.

It is sucient to work of a sp ecial case of HDOLs: Image by a morphism of the Thue-Morse sequence.

Let

w

i.e. xed p oint of Let

TM

b e the Thue-Morse sequence on

g : a ab, b ba

a, b

.

h : {a, b} {0, 1}

b e a morphism.

Question Is

Mk (h(wTM ))

k

-1

k

+

-free ?

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Moulin Ollagnier ideas can b e extended to HDOLs.

It is sucient to work of a sp ecial case of HDOLs: Image by a morphism of the Thue-Morse sequence.

Let

w

i.e. xed p oint of Let

TM

b e the Thue-Morse sequence on

g : a ab, b ba

a, b

.

h : {a, b} {0, 1}

b e a morphism.

Question Is

Mk (h(wTM ))

k

-1

k

+

-free ?

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Moulin Ollagnier ideas can b e extended to HDOLs.

It is sucient to work of a sp ecial case of HDOLs: Image by a morphism of the Thue-Morse sequence.

Let

w

i.e. xed p oint of Let

TM

b e the Thue-Morse sequence on

g : a ab, b ba

a, b

.

h : {a, b} {0, 1}

b e a morphism.

Question Is

Mk (h(wTM ))

k

-1

k

+

-free ?

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Moulin Ollagnier ideas can b e extended to HDOLs.

It is sucient to work of a sp ecial case of HDOLs: Image by a morphism of the Thue-Morse sequence.

Let

w

i.e. xed p oint of Let

TM

b e the Thue-Morse sequence on

g : a ab, b ba

a, b

.

h : {a, b} {0, 1}

b e a morphism.

Question Is

Mk (h(wTM ))

k

-1

k

+

-free ?

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Let Let

a = (h(a))

and

b = (h(b)),
s.t.

: {a, b} Sk

(a) =

a

and

(b) = b

.

Idea b ehind this: Find a

h such that: h(wTM ) has to avoid forbidden short -kernel wTM has to avoid forbidden long -kernel rep
We obtain results for smaller

rep etitions etitions.

h

.

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Following Moulin Ollagnier's idea: Limit us to

h

such that:

(g (a)) = a · b = · a ·
for a

-1 and -
1

(g (b)) = b · a = · b · Sk
.

Remark:

a
h

and is

b

have to b e conjugate. and the last letters dier.

Moreover:

uniform, synchronizing,

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Following Moulin Ollagnier's idea: Limit us to

h

such that:

(g (a)) = a · b = · a ·
for a

-1 and -
1

(g (b)) = b · a = · b · Sk
.

Remark:

a
h

and is

b

have to b e conjugate. and the last letters dier.

Moreover:

uniform, synchronizing,

MichaÊl Rao

Last Cases of Dejean's Conjecture


Image of the Thue-Morse sequence

Following Moulin Ollagnier's idea: Limit us to

h

such that:

(g (a)) = a · b = · a ·
for a

-1 and -
1

(g (b)) = b · a = · b · Sk
.

Remark:

a
h

and is

b

have to b e conjugate. and the last letters dier.

Moreover:

uniform, synchronizing,

MichaÊl Rao

Last Cases of Dejean's Conjecture


Let

(p , q )
If

be a

-kernel

rep etition of

h(w

TM

)

.

q

is long enough, then

rep etition in

wTM

(p , q )

is an image by

h

of a



-kernel

.

Let

(p , q )
If

be a



-kernel rep etition of

w

TM

.

q

is long enough, then

rep etition in

w

TM


(p , q )

is an image by

g

of a



-kernel

.

An image by

g

of a

-kernel rep etition has a smaller exp onent.

This is decidable : Check only small

-kernel



-kernel rep etitions in

w

TM

rep etitions in .

h(wTM )

and small

MichaÊl Rao

Last Cases of Dejean's Conjecture


Let

(p , q )
If

be a

-kernel

rep etition of

h(w

TM

)

.

q

is long enough, then

rep etition in

wTM

(p , q )

is an image by

h

of a



-kernel

.

Let

(p , q )
If

be a



-kernel rep etition of

w

TM

.

q

is long enough, then

rep etition in

w

TM


(p , q )

is an image by

g

of a



-kernel

.

An image by

g

of a

-kernel rep etition has a smaller exp onent.

This is decidable : Check only small

-kernel



-kernel rep etitions in

w

TM

rep etitions in .

h(wTM )

and small

MichaÊl Rao

Last Cases of Dejean's Conjecture


Let

(p , q )
If

be a

-kernel

rep etition of

h(w

TM

)

.

q

is long enough, then

rep etition in

wTM

(p , q )

is an image by

h

of a



-kernel

.

Let

(p , q )
If

be a



-kernel rep etition of

w

TM

.

q

is long enough, then

rep etition in

w

TM


(p , q )

is an image by

g

of a



-kernel

.

An image by

g

of a

-kernel rep etition has a smaller exp onent.<