Periods in Partial Words: An Algorithm
- 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: Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q) such that if a partial word of length at least L with h holes has periods p and q, then it also has period gcd(p,q). In this paper, we associate a graph with each p - and q -periodic word, and study two types of vertex connectivity on such a graph: modified degree connectivity and r -set connectivity where r = q mod p. As a result, we give an algorithm for computing L(h,p,q) in the general case and show how to use it to derive the closed formulas.
Periods in Partial Words: An Algorithm
PDF (Portable Document Format)
646 KB
Created on 6/26/2014
Views: 2043
Additional Information
- Publication
- Journal of Discrete Algorithms, 16, 113-128
- Language: English
- Date: 2012
- Keywords
- Automata and formal languages, Combinatorics on words, Partial words, Fine and Wilf's theorem, Strong periods, Graph connectivity, Optimal lengths