Full and Partial Tilings of Words
F. Blanchet-Sadri (click to visit homepage) Lisa Bromberg Karl Zipple
Abstract Implementation Paper

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, answering a conjecture by Dömösi, Horváth and Ito.
Keywords: Combinatorics on words; Partial words; Full tilings; Partial Tilings; Quasiperiods

Valid XHTML 1.0! Valid CSS!