On non-complete sets and Restivo’s conjecture

Vladimir V. Gusev and Elena V. Pribavkina

Abstract. A finite set S of words over the alphabet Σ is called non-complete if Fact(S*) ≠ Σ*. A word w ∈ Σ* \ Fact(S*) is said to be uncompletable. We present a series of non-complete sets Sk whose minimal uncompletable words have length 5k² − 17k + 13, where k ≥ 4 is the maximal length of words in Sk. This is an infinite series of counterexamples to Restivo’s conjecture, which states that any non-complete set possesses an uncompletable word of length at most 2k².

Comments are closed.