Periodicity properties on partial words

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: The concept of periodicity has played over the years a centra1 role in the development of combinatorics on words and has been a highly valuable too1 for the design and analysis of algorithms. Fine and Wilf’s famous periodicity result, which is one of the most used and known results on words, has extensions to partia1 words, or sequences that may have a number of “do not know” symbols. These extensions fal1 into two categories: the ones that relate to strong periodicity and the ones that relate to weak periodicity. In this paper, we obtain consequences by generalizing, in particular, the combinatoria1 property that “for any word u over {a, b}, ua or ub is primitive,” which proves in some sense that there exist very many primitive partia1 words.

Additional Information

Publication
Information and Computation, Vol. 206, 2008, pp 1057-1064.
Language: English
Date: 2008
Keywords
Formal languages, Combinatorics on words, Fine and Wilf’s periodicity result, Partial words, Primitive partial words, Periods, Weak periods

Email this document to