The Tiling Problem Revisited (Extended Abstract)

DOI10.1007/978-3-540-74593-8_6zbMath1211.03062OpenAlexW1588906418MaRDI QIDQ3608470

Jarkko Kari

Publication date: 5 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74593-8_6

zbMATH Keywords

Turing machineWang tilesmortality problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Turing machines and related notions (03D10)

Related Items (16)

Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type ⋮ The periodic domino problem revisited ⋮ Two-by-Two Substitution Systems and the Undecidability of the Domino Problem ⋮ Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version) ⋮ Monadic second-order logic and the domino problem on self-similar graphs ⋮ THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE ⋮ About the Domino Problem for Subshifts on Groups ⋮ The Undecidability of the Domino Problem ⋮ On the domino problem of the Baumslag-Solitar groups ⋮ The domino problem of the hyperbolic plane is undecidable ⋮ A hierarchical strongly aperiodic set of tiles in the hyperbolic plane ⋮ On the Undecidability of the Tiling Problem ⋮ About the Garden of Eden Theorems for Cellular Automata in the Hyperbolic Plane ⋮ Regular production systems and triangle tilings ⋮ The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane ⋮ Decidability and undecidability in cellular automata

This page was built for publication: The Tiling Problem Revisited (Extended Abstract)