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.26
URN: urn:nbn:de:0030-drops-118875
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11887/
Go to the corresponding LIPIcs Volume Portal

Aubrun, Nathalie ; Esnay, Julien ; Sablik, Mathieu

Domino Problem Under Horizontal Constraints

pdf-format:
LIPIcs-STACS-2020-26.pdf (0.5 MB)

Abstract

The Domino Problem on ℤ² asks if it is possible to tile the plane with a given set of Wang tiles; it is a classical decision problem which is known to be undecidable. The purpose of this article is to parameterize this problem to explore the frontier between decidability and undecidability. To do so we fix some horizontal constraints H on the tiles and consider a new Domino Problem DP_H: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DP_H is decidable using graphs combinatorics.

BibTeX - Entry

@InProceedings{aubrun_et_al:LIPIcs:2020:11887,
  author =	{Nathalie Aubrun and Julien Esnay and Mathieu Sablik},
  title =	{{Domino Problem Under Horizontal Constraints}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{26:1--26:15},
  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/11887},
  URN =		{urn:nbn:de:0030-drops-118875},
  doi =		{10.4230/LIPIcs.STACS.2020.26},
  annote =	{Keywords: Dynamical Systems, Symbolic Dynamics, Subshifts, Wang tiles, Undecidability, Domino Problem, Combinatorics, Tilings, Subshifts of Finite Type}
}

Keywords: Dynamical Systems, Symbolic Dynamics, Subshifts, Wang tiles, Undecidability, Domino Problem, Combinatorics, Tilings, Subshifts of Finite Type
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