On the Minimal Uncompletable Word Problem
Gabriele Fici, Elena V. Pribavkina, Jacques Sakarovitch · arXiv (Cornell University) · 2010
Let S be a finite set of words over an alphabet Sigma. The set S is said to be complete if every word w over the alphabet Sigma is a factor of some element of S*, i.e. w belongs to Fact(S*). Otherwise if S is not complete, we are interested in finding bounds on the minimal length of words in Sigma* which are not elements of Fact(S*) in terms of the maximal length of words in S.