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)
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
This page was built for publication: The undecidability of the domino problem
