License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1334
URN: urn:nbn:de:0030-drops-13343
Go to the corresponding LIPIcs Volume Portal

Ballier, Alexis ; Durand, Bruno ; Jeandal, Emmanuel

Structural aspects of tilings

22011.BallierAlexis.Paper.1334.pdf (0.3 MB)


In this paper, we study the structure of the set of tilings
produced by any given tile-set. For better understanding this
structure, we address the set of finite patterns that each tiling

This set of patterns can be analyzed in two different contexts:
the first one is combinatorial and the other topological. These
two approaches have independent merits and, once combined, provide
somehow surprising results.

The particular case where the set of produced tilings is countable
is deeply investigated while we prove that the uncountable case
may have a completely different structure.

We introduce a pattern preorder and also make use of
Cantor-Bendixson rank. Our first main result is that a tile-set
that produces only periodic tilings produces only a finite number
of them. Our second main result exhibits a tiling with exactly
one vector of periodicity in the countable case.

BibTeX - Entry

  author =	{Alexis Ballier and Bruno Durand and Emmanuel Jeandal},
  title =	{{Structural aspects of tilings}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{61--72},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-13343},
  doi =		{10.4230/LIPIcs.STACS.2008.1334},
  annote =	{Keywords: Tiling, domino, patterns, tiling preorder, tiling structure}

Keywords: Tiling, domino, patterns, tiling preorder, tiling structure
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI