Let S be a finite set of words over a finite alphabet Σ. We say that S is complete if Fact(S^*) = Σ^*, where Fact(L) denotes the set of all factors of all words of L. A word in Σ^* - Fact(S^*) is called uncompleteable. Restivo conjectured in 1981 that for any non-complete set S there is an uncompleteable word of length at most 2k², where k is the length of the longest word in S.

Restivo's conjecture is false, but the correct bound is still not known. Recently Gusev and Pribavkina have produced a set of counterexamples for which the bound is 5k² - 17k + 13 for k ≥ 4.

A related open problem is the computational complexity of determining, given a finite set S of words over Σ, if Fact(S^*) = Σ^*. Here the complexity is measured not in terms of the total size of S, but rather, the length of the longest word in S.

References:

V. V. Gusev and E. V. Pribavkina, On non-complete sets and Restivo's conjecture, in G. Mauri and A. Leporati, eds., Developments in Language Theory, 15th International conference, DLT 2011, Lect. Notes in Comp. Sci., Vol. 6795, Springer, 2011, pp. 239-250.

-- JeffreyShallit - 20 Jul 2011