10.4230/LIPICS.STACS.2020.26
Aubrun, Nathalie
Nathalie
Aubrun
Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP, F-69342, LYON Cedex 07, France
Esnay, Julien
Julien
Esnay
Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France
Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP, F-69342, Lyon Cedex 07, France
Sablik, Mathieu
Mathieu
Sablik
Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France
Domino Problem Under Horizontal Constraints
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
ConferencePaper
Dynamical Systems
Symbolic Dynamics
Subshifts
Wang tiles
Undecidability
Domino Problem
Combinatorics
Tilings
Subshifts of Finite Type
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France
Markus Bläser
Institut de Mathématiques de Toulouse, Université Paul Sabatier, 118 route de Narbonne, F-31062 Toulouse Cedex 9, France
10.4230/LIPIcs.STACS.2020
978-3-95977-140-5
1868-8969
https://doi.org/10.1007/978-3-319-69152-7_9
https://doi.org/10.4230/LIPIcs.MFCS.2019.46
https://doi.org/10.1007/s10440-013-9808-5
https://doi.org/10.1007/978-3-319-40189-8_21
http://arxiv.org/abs/1412.4572
http://arxiv.org/abs/1510.06439
https://doi.org/10.1016/j.jcss.2011.11.001
https://doi.org/10.1007/s00222-008-0161-7
http://arxiv.org/abs/1506.06492
https://doi.org/10.4204/EPTCS.90.6
https://doi.org/10.1007/978-3-540-74593-8_6
http://arxiv.org/abs/1904.01267
https://doi.org/10.1007/BF02793412
https://doi.org/10.1007/s11854-015-0014-4
https://doi.org/10.1007/BF01418780
https://doi.org/10.1002/j.1538-7305.1961.tb03975.x
Creative Commons Attribution 3.0 Unported license
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.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 26:1-26:15