@inproceedings{1b7f0061fad7405885d791927d19fe0c,
title = "Domino problem under horizontal constraints",
abstract = "The Domino Problem on Z2 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 DPH: given a vertical constraint, is it possible to tile the plane? We characterize the nearest-neighbor horizontal constraints where DPH is decidable using graphs combinatorics.",
keywords = "Combinatorics, Domino Problem, Dynamical Systems, Subshifts, Subshifts of Finite Type, Symbolic Dynamics, Tilings, Undecidability, Wang tiles",
author = "Nathalie Aubrun and Julien Esnay and Mathieu Sablik",
note = "Publisher Copyright: {\textcopyright} Nathalie Aubrun, Julien Esnay, and Mathieu Sablik; licensed under Creative Commons License CC-BY; 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 ; Conference date: 10-03-2020 Through 13-03-2020",
year = "2020",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.STACS.2020.26",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christophe Paul and Markus Blaser",
booktitle = "37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020",
}