Testing Primitivity on Partial Words

F. Blanchet-Sadri, Arundhati R. Anavekar, and
Margaret Moorefield

Abstract

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinational result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm.

Keywords: Combinatorical Problems, Algorithms on Words, Primitive Words, Primitive Partial Words.

Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. CCF-0207673. Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.