On the Complexity of Deciding Avoidability of Sets of Partial Words

Abstract

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k ≥ 2, is ${\mathcal{NP}}$-hard [Theoret. Comput. Sci. 410 (2009) 968–972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are ${\mathcal{NP}}$-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of finite words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.

This material is based upon work supported by the National Science Foundation under Grant No. DMS–0754154. The Department of Defense is also gratefully acknowledged. We thank the referees of a preliminary version of this paper for their very valuable comments and suggestions.