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 2k2, 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 5k2 - 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 in terms of the total size of S.


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

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2011-07-21 - JeffreyShallit
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback