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.
Periodicity properties on partial words
PDF (Portable Document Format)
357 KB
Created on 3/30/2011
Views: 2264
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