The undecidability of the domino problem

1966/01/01 by Robert Berger, Robert E. Berger · 60 citations
Mathematics · #History and Theory of Mathematics

paper · doi:10.1090/memo/0066

Cited by

• Undecidability of Tiling with a Tromino
• Self-simulable groups
• Characterization and Topological Behavior of Homomorphism Tree-Shifts
• Is the injectivity of the global function of a cellular automaton in the hyperbolic plane undecidable?
• Pattern avoidance is not P-recursive
• It's a Tough Nanoworld: in Tile Assembly, Cooperation is not (strictly) more Powerful than Competition
• An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
• Matching Rules for the Sphinx Tiling Substitution
• The complexity of generalized domino tilings
• 1D Effectively Closed Subshifts and 2D Tilings
• Infinite games with finite knowledge gaps
• Periodicity in tilings
• Complexity Results and Practical Algorithms for Logics in Knowledge Representation
• Approximating entropy for a class of zz² Markov Random Fields and\n pressure for a class of functions on zz² shifts of finite type
• A linear algorithm for Brick Wang tiling
• Construction of infinite finitely presented nilsemigroup
• Seas of squares with sizes from a Π⁰₁ set
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• On the cohomology of homshifts
• Tilings and Submonoids of Metabelian Groups
• Translational tilings: structured or wild?
• Parametrized complexity of relations between multidimensional subshifts
• A primer on substitution tilings of the Euclidean plane
• On Decidability of Expressive Description Logics with Composition of Roles in Number Restrictions
• Fixed-point tile sets and their applications
• Constructions with Countable Subshifts of Finite Type
• Tessellations and Positional Representation
• The computation of overlap coincidence in Taylor-Socolar substitution tiling
• The Quantum and Classical Complexity of Translationally Invariant Tiling\n and Hamiltonian Problems
• Subshifts with sparse traces
• Solving Pictorial Jigsaw Puzzle by Stigmergy-inspired Internet-based Human Collective Intelligence
• Undecidability of Translational Tiling with 2 Polycubes
• Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
• Undecidability of Tiling the Plane with a Set of 5 Polyominoes
• Hard Tiling Problems with Simple Tiles
• An Application of Topological Multiple Recurrence to Tiling
• The structure of translational tilings in ℤ^d
• Universality in symbolic dynamics constrained by Medvedev degrees
• Algorithms for translational tiling
• Three characterizations of a self-similar aperiodic 2-dimensional subshift
• Pattern Complexity of Aperiodic Substitutive Subshifts
• Undecidability of the spectral gap
• Rectangular tileability and complementary tileability are undecidable
• On physical problems that are slightly more difficult than QMA
• Simulation of minimal effective dynamical systems on the Cantor sets by minimal tridimensional subshifts of finite type
• Decidability of plane edge coloring with three colors
• Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping
• Strongly aperiodic subshifts of finite type on hyperbolic groups
• Combinatorial substitutions and sofic tilings
• Limit Sets and Internal Transitivity in Free Group Actions
• Minimal sofic shift on a group that is not finitely-generated
• Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants
• Tiling simply connected regions with rectangles
• Fixed Point Constructions in Tilings and Cellular Automata
• Complexity of two-variable Dependence Logic and IF-Logic
• Undecidability of Translational Tiling of the Plane with Four Tiles
• Diamonds and Dominoes: Impossibility Results for Associative Modal Logics
• SHACL Satisfiability and Containment (Extended Paper)
• Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
• Two Tiling is Undecidable