摘要：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.
关键词：Dynamical Systems; Symbolic Dynamics; Subshifts; Wang tiles; Undecidability; Domino Problem; Combinatorics; Tilings; Subshifts of Finite Type
