2026-07-24T05:48:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11887 2024-03-06T10:48:56Z ddc:004 open_access

Domino Problem Under Horizontal Constraints Aubrun, Nathalie Esnay, Julien Sablik, Mathieu Dynamical Systems Symbolic Dynamics Subshifts Wang tiles Undecidability Domino Problem Combinatorics Tilings Subshifts of Finite Type 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathalie Aubrun and Julien Esnay and Mathieu Sablik 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.26 urn:nbn:de:0030-drops-118875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode