License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.14
URN: urn:nbn:de:0030-drops-118752
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11875/
Go to the corresponding LIPIcs Volume Portal

Kari, Jarkko ; Moutot, Etienne

Decidability and Periodicity of Low Complexity Tilings

pdf-format:
LIPIcs-STACS-2020-14.pdf (0.6 MB)

Abstract

In this paper we study low-complexity colorings (or tilings) of the two-dimensional grid ℤ². A coloring is said to be of low complexity with respect to a rectangle if there exists m,n∈ℕ such that there are no more than mn different rectangular m× n patterns in it. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. Suppose we are given at most nm rectangular patterns of size n× m. If Nivat’s conjecture is true, one can only build periodic colorings out of these patterns - meaning that if the m× n rectangular patterns of the coloring are among these mn patterns, it must be periodic. The main contribution of this paper proves that there exists at least one periodic coloring build from these patterns. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Finally, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. The results also extend to other convex shapes in place of the rectangle.

BibTeX - Entry

@InProceedings{kari_et_al:LIPIcs:2020:11875,
  author =	{Jarkko Kari and Etienne Moutot},
  title =	{{Decidability and Periodicity of Low Complexity Tilings}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11875},
  URN =		{urn:nbn:de:0030-drops-118752},
  doi =		{10.4230/LIPIcs.STACS.2020.14},
  annote =	{Keywords: Nivat’s conjecture, domino problem, decidability, low pattern complexity, 2D subshifts, symbolic dynamics}
}

Keywords: Nivat’s conjecture, domino problem, decidability, low pattern complexity, 2D subshifts, symbolic dynamics
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

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