On the Minimal Uncompletable Word Problem

Abstract

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.

5 pages; added references, corrected typos

References in corpus (2)

• Slowly synchronizing automata with zero and incomplete sets
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages