Remarks on Two Nonstandard Versions of Periodicity in 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: In this paper, we study some periodicity concepts on words. First, we extend the notion of full tilings which was recently introduced by Karhumäki, Lifshits, and Rytter to partial tilings. Second, we investigate the notion of quasiperiods and show in particular that the set of quasiperiodic words is a context-sensitive language that is not context-free, answering a conjecture by Dömösi, Horváth and Ito.
Remarks on Two Nonstandard Versions of Periodicity in Words
PDF (Portable Document Format)
326 KB
Created on 6/27/2011
Views: 1720
Additional Information
- Publication
- International Journal of Foundations of Computer Science
- Language: English
- Date: 2008
- Keywords
- Combinatorics on words, Full tilings, Partial tilings, Quasiperiods