Geodesic
Tiling Periodicity
Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 2.

Voir la notice de l'article provenant de la source Episciences

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 multi-periods. As a side product of the paper we solve an open problem posted by T. Harju (2003). 
@article{DMTCS_2010_12_2_a12,
     author = {Karhumaki, Juhani and Lifshits, Yury and Rytter, Wojciech},
     title = {Tiling {Periodicity}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2010},
     doi = {10.46298/dmtcs.517},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.517/}
}
TY  - JOUR
AU  - Karhumaki, Juhani
AU  - Lifshits, Yury
AU  - Rytter, Wojciech
TI  - Tiling Periodicity
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.517/
DO  - 10.46298/dmtcs.517
LA  - en
ID  - DMTCS_2010_12_2_a12
ER  - 
%0 Journal Article
%A Karhumaki, Juhani
%A Lifshits, Yury
%A Rytter, Wojciech
%T Tiling Periodicity
%J Discrete mathematics & theoretical computer science
%D 2010
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.517/
%R 10.46298/dmtcs.517
%G en
%F DMTCS_2010_12_2_a12
Karhumaki, Juhani; Lifshits, Yury; Rytter, Wojciech. Tiling Periodicity. Discrete mathematics & theoretical computer science, Tome 12 (2010) no. 2. doi : 10.46298/dmtcs.517. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.517/

Cité par Sources :