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.

Additional Information

Publication
International Journal of Foundations of Computer Science
Language: English
Date: 2008
Keywords
Combinatorics on words, Full tilings, Partial tilings, Quasiperiods