Tiling Periodicity

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 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).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.237-248
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990466
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:50
Dernière modification le : jeudi 28 décembre 2017 - 08:32:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:10:30

Fichier

1352-5055-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990466, version 1

Collections

Citation

Juhani Karhumaki, Yury Lifshits, Wojciech Rytter. Tiling Periodicity. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.237-248. 〈hal-00990466〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

197