Composing short 3-compressing words on a 2-letter alphabet

Publication date: 30 November 2018

Abstract: A finite deterministic (semi)automaton

m a t h c a l A = (Q, S i g m a, d e l t a)

is

k

-compressible if there is some word

w i n S i g m a^{+}

such that the image of its state set

Q

under the natural action of

w

is reduced by at least

k

states. Such word, if it exists, is called a

k

-compressing word for

m a t h c a l A

. A word is

k

-collapsing if it is

k

-compressing for each

k

-compressible automaton. We compute a set

W

of short words such that each

3

-compressible automata on a two letter alphabet is

3

-compressed at least by a word in

W

. Then we construct a shortest common superstring of the words in

W

and, with a further refinement, we obtain a

3

-collapsing word of length

53

. Moreover, as previously announced, we show that the shortest

3

-synchronizing word is not

3

-collapsing, illustrating the new bounds

34 l e q c (2, 3) l e q 53

for the length

c (2, 3)

of the shortest

3

-collapsing word on a two letter alphabet.

Recommendations

Cited In (4)

This page was built for publication: Composing short 3-compressing words on a 2-letter alphabet