Tiling Periodicity
Juhani Karhumaki, Yury Lifshits, Wojciech Rytter
Abstract
We contribute to combinatorics and algorithmics of words by
introducing new types of periodicities in words. A tiling period of a
word w is partial word u such that w can be
decomposed into several disjoint parallel copies of u, e.g. a ⋄
b is a tiling period of aabb. We investigate properties of
tiling periodicities and design an algorithm working in O(n log(n) log
log(n)) time which finds a tiling period of minimal size, the number
of such periods and their compact representation. The combinatorics of
tiling periods differs significantly from that for classical full
periods, for example unlike the classical case the same word can have
many different primitive tiling periods. We consider also a related
new type of periods called in the paper multi-periods. As a side
product of the paper we solve an open problem posted by T. Harju.
Full Text: PDF PostScript