episciences.org_517_20230320161929591
20230320161929591
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2010
Vol. 12 no. 2
Tiling Periodicity
Juhani
Karhumaki
Yury
Lifshits
Wojciech
Rytter
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 lozenge b is a tiling period of a a b b. 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 minimal 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 multiperiods. As a side product of the paper we solve an open problem posted by T. Harju (2003).
01
01
2010
517
https://hal.science/hal00990466v1
10.46298/dmtcs.517
https://dmtcs.episciences.org/517

https://dmtcs.episciences.org/517/pdf

https://dmtcs.episciences.org/517/pdf