Tiling an Interval of the Discrete Line

Abstract : We consider the problem of tiling a segment {0, . . . , n} of the discrete line. More precisely, we ought to characterize the structure of the patterns that tile a segment and their number. A pattern is a subset of N. A tiling pattern or tile for {0, . . . , n} is a subset A P(N) such that there exists B P(N) and such that the direct sum of A and B equals {0, . . . , n}. This problem is related to the di cult question of the decomposition in direct sums of the torus Z/nZ (proposed by Minkowski). Using combinatorial and algebraic techniques, we give a new elementary proof of Krasner factorizations. We combinatorially prove that the tiles are direct sums of some arithmetic sequences of speci c lengths. Besides, we show there are as many tiles whose smallest tilable segment is {0, . . . , n} as tiles whose smallest tilable segment is {0, . . . , d}, for all strict divisors d of n. This enables us to exhibit an optimal linear time algorithm to compute for a given pattern the smallest segment that it tiles if any, as well as a recurrence formula for counting the tiles of a segment.
Type de document :
Communication dans un congrès
Springer. CPM: Combinatorial Pattern Matching, Jul 2006, Barcelona, Spain. Springer Verlag, 17th Annual Symposium on Combinatorial Pattern Matching, LNCS (4009), pp.117-128, 2006, 〈10.1007/11780441_12〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00120188
Contributeur : Eric Rivals <>
Soumis le : mercredi 13 décembre 2006 - 15:24:25
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 20:57:27

Identifiants

Collections

Citation

Olivier Bodini, Eric Rivals. Tiling an Interval of the Discrete Line. Springer. CPM: Combinatorial Pattern Matching, Jul 2006, Barcelona, Spain. Springer Verlag, 17th Annual Symposium on Combinatorial Pattern Matching, LNCS (4009), pp.117-128, 2006, 〈10.1007/11780441_12〉. 〈lirmm-00120188〉

Partager

Métriques

Consultations de la notice

164

Téléchargements de fichiers

82