The undecidability of the domino problem
From MaRDI portal
Publication:5597521
DOI10.1090/memo/0066zbMath0199.30802OpenAlexW2017025480WikidataQ56225982 ScholiaQ56225982MaRDI QIDQ5597521
Publication date: 1966
Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/memo/0066
Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Turing machines and related notions (03D10)
Related Items (only showing first 100 items - show all)
On the Decidability of Elementary Modal Logics ⋮ Constraints on pure point diffraction on aperiodic point patterns of finite local complexity* ⋮ Global order from local sources ⋮ The topological strong spatial mixing property and new conditions for pressure approximation ⋮ Capacity of Higher-Dimensional Constrained Systems ⋮ Matrix Characterization of Multidimensional Subshifts of Finite Type ⋮ Tiling with arbitrary tiles ⋮ Self-stabilisation of Cellular Automata on Tilings ⋮ Effective S-adic Symbolic Dynamical Systems ⋮ Computability in Symbolic Dynamics ⋮ The Domino Problem for Self-similar Structures ⋮ Degrees of Unsolvability: A Tutorial ⋮ Tilings and quasiperiodicity ⋮ Undecidability of the Spectral Gap ⋮ Strongly aperiodic subshifts of finite type on hyperbolic groups ⋮ Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type ⋮ Tiling with Squares and Packing Dominos in Polynomial Time ⋮ A simple logic of the hide and seek game ⋮ Resiliency to multiple nucleation in temperature-1 self-assembly ⋮ The domino problem is undecidable on every rhombus subshift ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ A Topological Study of Tilings ⋮ Fixed Structure Complexity ⋮ Complex tilings ⋮ Decidability of CPC-irreducibility of subshifts of finite type over free groups ⋮ Aperiodic subshifts of finite type on groups which are not finitely generated ⋮ Garden of Eden and weakly periodic points for certain expansive actions of groups ⋮ A general approach to Ammann bars for aperiodic tilings ⋮ AN APERIODIC TILE WITH EDGE-TO-EDGE ORIENTATIONAL MATCHING RULES ⋮ Two-by-Two Substitution Systems and the Undecidability of the Domino Problem ⋮ Topological Dynamics of 2D Cellular Automata ⋮ Undecidable translational tilings with only two tiles, or one nonabelian tile ⋮ Graph subshifts ⋮ On mixing properties of Markov tree-shifts ⋮ Mixing properties of tree-shifts ⋮ On the Besicovitch-stability of noisy random tilings ⋮ Nonexpansive directions in the Jeandel-Rao Wang shift ⋮ A review of SHACL: from data validation to schema reasoning for RDF graphs ⋮ Deltoid tangents with evenly distributed orientations and random tilings ⋮ The structure of translational tilings in $\mathbb{Z}^d$ ⋮ On graph induced symbolic systems ⋮ Arithmetical hierarchy of the Besicovitch-stability of noisy tilings ⋮ About the domino problem in the hyperbolic plane from an algorithmic point of view ⋮ Satisfiability of Arbitrary Public Announcement Logic with Common Knowledge is Σ^1_1-hard ⋮ A multi-dimensional terminological knowledge representation language ⋮ About the Domino Problem for Subshifts on Groups ⋮ Automaton (Semi)groups: Wang Tilings and Schreier Tries ⋮ Unnamed Item ⋮ Fixed Point and Aperiodic Tilings ⋮ Unnamed Item ⋮ An aperiodic monotile that forces nonperiodicity through dendrites ⋮ Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems ⋮ Subshifts with sparse traces ⋮ Entropy dimension of shift spaces on monoids ⋮ Introduction to Hierarchical Tiling Dynamical Systems ⋮ The Undecidability of the Domino Problem ⋮ Periodicity of one-dimensional tilings ⋮ SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY ⋮ The undecidability of joint embedding for 3-dimensional permutation classes ⋮ A class of nonsofic multidimensional shift spaces ⋮ An aperiodic set of 11 Wang tiles ⋮ Unnamed Item ⋮ Geometric realization for substitution tilings ⋮ Constructing New Aperiodic Self-simulating Tile Sets ⋮ Effective Closed Subshifts in 1D Can Be Implemented in 2D ⋮ Framed Versus Unframed Two-Dimensional Languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strong cocycle triviality for \(Z^{2}\) subshifts ⋮ On the Undecidability of the Tiling Problem ⋮ Cutting corners ⋮ Aperiodic Tilings in Higher Dimensions ⋮ Tiling the Plane with a Fixed Number of Polyominoes ⋮ Self-correcting Self-assembly: Growth Models and the Hammersley Process ⋮ TILING WITH PUNCTURED INTERVALS ⋮ The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ Optimal state amalgamation is NP-hard ⋮ Subshifts, Languages and Logic ⋮ Branching-Time Temporal Logics with Minimal Model Quantifiers ⋮ Multidimensional Shifts And Finite Matrices ⋮ The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane ⋮ Some applications of propositional logic to cellular automata ⋮ Axiomatizing Rectangular Grids with no Extra Non-unary Relations ⋮ A generalization of the simulation theorem for semidirect products ⋮ Weak colored local rules for planar tilings ⋮ Characterizations of periods of multi-dimensional shifts ⋮ Classification of sofic projective subdynamics of multidimensional shifts of finite type ⋮ Turning decision procedures into disprovers ⋮ Verification of mixing properties in two-dimensional shifts of finite type ⋮ Undecidability of Algebras of Binary Relations ⋮ A new mathematical model for tiling finite regions of the plane with polyominoes ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ Tiling a Manhattan Polyomino with Bars ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries ⋮ Polyominoes defined by two vectors ⋮ On the solvability of domino snake problems ⋮ Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Many phases in systems without periodic ground states ⋮ Inversion of 2D cellular automata: Some complexity results ⋮ The surjectivity problem for 2D cellular automata
This page was built for publication: The undecidability of the domino problem
