id: 05934297
dt: a
an: 05934297
au: Gusev, Vladimir V.; Pribavkina, Elena V.
ti: On non-complete sets and Restivo’s conjecture.
so: Mauri, Giancarlo (ed.) et al., Developments in language theory. 15th
    international conference, DLT 2011, Milan, Italy, July 19‒22, 2011.
    Proceedings. Berlin: Springer (ISBN 978-3-642-22320-4/pbk). Lecture
    Notes in Computer Science 6795, 239-250 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-22321-1_21
ab: Summary: A finite set $S$ of words over the alphabet $Σ$ is called
    non-complete if $\text{Fact}(S^*)\neΣ^*$. A word $w \in Σ^* \setminus
    \text{Fact}(S^*)$ is said to be uncompletable. We present a series of
    non-complete sets $S _{k }$ whose minimal uncompletable words have
    length $5k ^{2} - 17k + 13$, where $k \geq 4$ is the maximal length of
    words in $S _{k }$. 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 ^{2}$.
rv: