On the complexity of deciding avoidability of sets of partial words |
| |
Authors: | Brandon Blakeley Josh Gunter |
| |
Affiliation: | a Department of Computer Sciences, The University of Texas at Austin, 1 University Station C0500 Taylor Hall 2.124, Austin, TX 78712-0233, USAb Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USAc Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, MB R3B 2E9, Canada |
| |
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 NP-hard F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is 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 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 words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n. |
| |
Keywords: | Automata and formal languages Computational complexity Combinatorics on words Partial words Unavoidable sets _method=retrieve& _eid=1-s2 0-S0304397510004731& _mathId=si6 gif& _pii=S0304397510004731& _issn=03043975& _acct=C000051805& _version=1& _userid=1154080& md5=e4005c21e411d69e50adc289a0a6ec4d')" style="cursor:pointer NP-hard problems" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">NP-hard problems De Bruijn graphs |
本文献已被 ScienceDirect 等数据库收录! |
|