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, answering a conjecture by Dömösi, Horváth and Ito.
Keywords: Combinatorics on words; Partial words; Full tilings; Partial Tilings; Quasiperiods
Acknowledgement:
This material is based upon work supported by the National Science Foundation under Grant No.
DMS-0452020.
Disclaimer:
Any opinions, findings, and conclusions or recommendations expressed in this material are those of
the authors and do not necessarily reflect the views of the National Science Foundation.
