Remarks on Berger's paper on the domino problem

DOI10.1007/BF00971620MaRDI QIDQ2556400zbMATH OpenOpenAlexFDO

Authors Yuri Gurevich, I. O. Korjakov

Publication date 1972

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00971620

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Applications of computability and recursion theory (03D80)

Cites work

• The undecidability of the domino problem

Cited in

(31)

• Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results
• Logical foundations of information disclosure in ontology-based data integration
• On logics with two variables
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Logical separability of labeled data examples under ontologies
• Decidability of irreducible tree shifts of finite type
• Slopes of multidimensional subshifts
• Static analysis of navigational XPath over graph databases
• Two variable first-order logic over ordered domains
• Decidability and undecidability in cellular automata
• Small substructures and decidability issues for first-order logic with two variables
• Constructing new aperiodic self-simulating tile sets
• Effective closed subshifts in 1D can be implemented in 2D
• The classical decision problem and partial functions
• The periodic domino problem revisited
• Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen
• Fixed-point tile sets and their applications
• Mixing properties of tree-shifts
• Complexity of two-variable dependence logic and IF-logic
• On the Restraining Power of Guards
• Aperiodic points in \(\mathbb{Z}^2\)-subshifts
• On the decidability of elementary modal logics
• Disjunctive logic programs with existential quantification in rule heads
• Turning decision procedures into disprovers
• Decidability of CPC-irreducibility of subshifts of finite type over free groups
• Graph subshifts
• An aperiodic monotile
• Decision problems on geometric tilings. Wang potatoes and finite local complexity
• Tiling of toroidal arrays with pictures: uniqueness, shift-equivalence and undecidability
• Undecidability of the positive calculus of relations with transitive closure and difference: hypothesis elimination using graph loops
• Computational characterization of surface entropies for \(\mathbb{Z}^2\) subshifts of finite type

This page was built for publication: Remarks on Berger's paper on the domino problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2556400)