RestivoConjecture < CoWiki

CoWiki Web>AdditionalOpenProblems>RestivoConjecture (2011-07-21, JeffreyShallit) (raw view)

Let S be a finite set of words over a finite alphabet &Sigma;.  We say that S is complete if Fact(S<sup>*</sup>) = &Sigma;<sup>*</sup>, where Fact(L) denotes the set of all factors of all words of L.  
A word in &Sigma;<sup>*</sup> - Fact(S<sup>*</sup>) is called uncompleteable.  Restivo conjectured in 1981 that for any non-complete set S there is an uncompleteable word of length at most 2k<sup>2</sup>, 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<sup>2</sup> - 17k + 13 for k &ge; 4.

A related open problem is the computational complexity of determining, given a finite set S of words over &Sigma;, if Fact(S<sup>*</sup>) = &Sigma;<sup>*</sup>.  Here the complexity is measured  in terms of the total size of S.

References:

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

-- Main.JeffreyShallit - 20 Jul 2011

Topic revision: r2 - 2011-07-21 - JeffreyShallit

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit