2010/02/09 by Gabriele Fici, Fici, Gabriele, Elena V. Pribavkina +3
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1002.1928
openalex publication_date 2010/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.