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
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, Finite state automata representing two-dimensional subshifts, Tiling figures of the plane with two bars, Fast domino tileability, Random \(\mathbb{Z}^d\)-shifts of finite type, Aperiodic tilings, Tiling rectangles with polyominoes, Fractal tilings based on successive adjacent substitution rule, Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices, Dominoes and the complexity of subclasses of logical theories, Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and Turing machines, Independence entropy of \(\mathbb{Z}^{d}\)-shift spaces, Simulation of effective subshifts by two-dimensional subshifts of finite type, An aperiodic set of 13 Wang tiles, A small aperiodic set of Wang tiles, Subshifts as models for MSO logic, Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues, On the shape of permutomino tiles, On simplification of schema mappings, Packing polyominoes clumsily, Enumeration approach to computing chemical equilibria, Turing degrees of multidimensional SFTs, Erratum to: Function iteration logics and flowchart schemata, The complexity of generalized domino tilings, The periodic domino problem revisited, Tile invariants: New horizons., A codicity undecidable problem in the plane., Random subshifts of finite type, Extended RDF: computability and complexity issues, Tilings and submonoids of metabelian groups., Some results on one-dimensional tilings, Aperiodic tilings with one prototile and low complexity atlas matching rules, Fixed-point tile sets and their applications, On time-symmetry in cellular automata, Groups, graphs, languages, automata, games and second-order monadic logic, Breaking of periodicity at positive temperatures, Polyominoes simulating arbitrary-neighborhood zippers and tilings, The computation of overlap coincidence in Taylor-Socolar substitution tiling, On keys and functional dependencies as first-class citizens in description logics, Packing, covering and tiling in two-dimensional spaces, Complexity of two-variable dependence logic and IF-logic, Tilings of the plane and Thurston semi-norm, A decidable two-sorted quantified fragment of set theory with ordered pairs and some undecidable extensions, Cellular automata, \(\omega{} \omega\)-regular sets, and sofic systems, Computational aspects of M. C. Escher's ribbon patterns, Reconstructing convex polyominoes from horizontal and vertical projections, Rigidity of planar tilings, A Random NP-complete problem for inversion of 2D cellular automata, Polyomino tilings, cellular automata and codicity, A notion of effectiveness for subshifts on finitely generated groups, On the entropy of \(\mathbb{Z}^d\) subshifts of finite type, The large scale geometry of strongly aperiodic subshifts of finite type, A multiparameter analysis of domino tiling with an application to concurrent systems, A primer of substitution tilings of the Euclidean plane, The domino problem of the hyperbolic plane is undecidable, Translation invariant extensions of finite volume measures, Approximating the hard square entropy constant with probabilistic methods, On periodicity of perfect colorings of the infinite hexagonal and triangular grids, Topological dynamics of cellular automata: dimension matters, Rewriting of regular expressions and regular path queries, The emerging discipline of biomolecular computation in the US, A characterization of the entropies of multidimensional shifts of finite type, A strongly aperiodic set of tiles in the hyperbolic plane, Two-dimensional cellular automata, Undecidable tiling problems in the hyperbolic plane, Complexity classes as mathematical axioms, On complete one-way functions, On the tiling by translation problem, Rectangular tileability and complementary tileability are undecidable, Path finding in the tile assembly model, Fusion: a general framework for hierarchical tilings of \(\mathbb{R }^d\), The 4-way deterministic tiling problem is undecidable, Regular production systems and triangle tilings, The hexagonal parquet tiling: \(k\)-isohedral monotiles with arbitrarily large \(k\)., On the dynamics and recursive properties of multidimensional symbolic systems, Polyominoes which tile rectangles, Aperiodic tilings of the hyperbolic plane by convex polygons, Mass problems associated with effectively closed sets, On the complexity of deadlock detection in families of planar nets, Frontier between decidability and undecidability: A survey, A decidable class of problems for control under partial observation, Tiling allowing rotations only, The word and order problems for self-similar and automata groups, Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results, Undecidability of PDL with \(L=\{a^{2^ i}| i\geq 0\}\), Some undecidable problems involving the edge-coloring and vertex-coloring of graphs, A linear algorithm to tile the trapezes with \(h_ m\) and \(v_ n\), Computation theoretic aspects of cellular automata, Reversibility of 2D cellular automata is undecidable, From logic to tiling, Reversibility and surjectivity problems of cellular automata, The structure of the models of decidable monadic theories of graphs, Simple sentences that are hard to decide, On the undecidability of logics with converse, nominals, recursion and counting, Decidability of SHIQ with complex role inclusion axioms, Rohlin properties for $\mathbb{Z}^{d}$ actions on the Cantor set, Small polyomino packing, Automatic generation of nonperiodic patterns from dynamical systems, Tiling a polygon with parallelograms, Entropy dimension of shifts of finite type on free groups, Tilings: recursivity and regularity, The lattice structure of the set of domino tilings of a polygon, Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity, Modular-topology optimization of structures and mechanisms with free material design and clustering, Aperiodic SFTs on Baumslag-Solitar groups, On the subtle nature of a simple logic of the hide and seek game, Small substructures and decidability issues for first-order logic with two variables, Rauzy induction of polygon partitions and toral \(\mathbb{Z}^2\)-rotations, Conway and aperiodic tilings, Pattern-equivariant homology, Topological entropy for shifts of finite type over \(\mathbb{Z}\) and trees, Smooth column convex polyominoes, The undecidability of arbitrary arrow update logic, Lots of aperiodic sets of tiles, Nonemptiness problems of Wang cubes with two colors, Substitutive structure of Jeandel-Rao aperiodic tilings, Quantifier extensions of multidimensional sofic shifts, \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\), Quasiperiodicity and Non-computability in Tilings, The complexity of regex crosswords, A counterexample to Thiagarajan's conjecture on regular event structures, Seas of squares with sizes from a \(\Pi_{1}^{0}\) set, Full sets of pictures to encode pictures, Mixing properties for hom-shifts and the distance between walks on associated graphs, Symmetry-induced quasicrystalline waveguides, Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible, Forcing nonperiodicity with a single tile, Monadic second-order logic and the domino problem on self-similar graphs, Simulations and the lamplighter group, Tile complexity of approximate squares, Computational complexity of theories of a binary predicate with a small number of variables, Decidability and periodicity of low complexity tilings, Representability is not decidable for finite relation algebras, Logical foundations of information disclosure in ontology-based data integration, On logics with two variables, Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus, Tilings and quasiperiodicity., Relation algebras can tile, Computational complexity of \(k\)-block conjugacy, Building a Stationary Stochastic Process From a Finite-Dimensional Marginal, Characterization and topological behavior of homomorphism tree-shifts, Epistemic horizons and the foundations of quantum mechanics, Plane-Filling Properties of Directed Figures, Snakes and Cellular Automata: Reductions and Inseparability Results, $\it \Pi^0_1$ Sets and Tilings, Necessary conditions for tiling finitely generated amenable groups, On the domino problem of the Baumslag-Solitar groups, Nonemptiness problems of Wang tiles with three colors, A linear algorithm for brick Wang tiling, A hierarchical strongly aperiodic set of tiles in the hyperbolic plane, Automatic generation of aesthetic patterns on fractal tilings by means of dynamical systems, Local rules and global order, or aperiodic tilings, Theory of cellular automata: a survey, Forbidden substructures and combinatorial dichotomies: WQO and universality, A model-theoretic characterisation of clique width, Wang tiling aided statistical determination of the representative volume element size of random heterogeneous materials, Spatial chaos of Wang tiles with two symbols, Decidability of irreducible tree shifts of finite type, Lamplighters admit weakly aperiodic SFTs, On covering by translates of a set, Triangular Tile Self-assembly Systems, Nilpotency and periodic points in non-uniform cellular automata, Nonemptiness problems of plane square tiling with two colors, Sturmian ground states in classical lattice-gas models, Tilings, substitution systems and dynamical systems generated by them, Tiling with polyominoes and combinatorial group theory, The price of universality, Algebraic numbers, free group automorphisms and substitutions on the plane, Undecidability and nonperiodicity for tilings of the plane, A self-similar aperiodic set of 19 Wang tiles, Domino-tiling games, Translationally invariant universal classical Hamiltonians, On column-convex and convex Carlitz polyominoes, Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly, A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings, Finite transducers and rational transductions, Remarks on Berger's paper on the domino problem, Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter, Markov partitions for toral \(\mathbb{Z}^2\)-rotations featuring Jeandel-Rao Wang shift and model sets, The multinomial tiling model, Theory of computation of multidimensional entropy with an application to the monomer-dimer problem, Sandpile toppling on Penrose tilings: identity and isotropic dynamics, Domino problem for pretty low complexity subshifts, Gardens of Eden in the game of life, Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type, Cyclotomic aperiodic substitution tilings, Logical separability of labeled data examples under ontologies, The undecidability of iterated modal relativization, When periodicities enforce aperiodicity, Graph encoding of 2D-gon tilings, Undecidability of Multi-modal Hybrid Logics, An aperiodic tiles machine, Complexity analysis of propositional concurrent programs using domino tiling, An integral representation for topological pressure in terms of conditional probabilities, Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type, 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
