The Tiling Problem Revisited (Extended Abstract)

DOI10.1007/978-3-540-74593-8_6MaRDI QIDQ3608470zbMATH OpenOpenAlexFDO

Authors 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

mortality problemTuring machineWang tiles

Mathematics Subject Classification ID

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

Recommendations

• On the Undecidability of the Tiling Problem
• The domino problem of the hyperbolic plane is undecidable
• Undecidable tiling problems in the hyperbolic plane
• THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE
• About the domino problem in the hyperbolic plane from an algorithmic point of view

Cited in

(39)

• The 4-way deterministic tiling problem is undecidable
• Regular production systems and triangle tilings
• Undecidable tiling problems in the hyperbolic plane
• On two questions concerning tilings
• Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
• On tiling under tomographic constraints.
• Some open problems in polyomino tilings
• Holey matrimony: marrying two approaches to a tiling problem
• Tiling problems and undecidability in the cluster variation method.
• On the domino problem of the Baumslag-Solitar groups
• A hierarchical strongly aperiodic set of tiles in the hyperbolic plane
• Tiling algebra for constraint-based layout editing
• Monadic second-order logic and the domino problem on self-similar graphs
• On the discretization of problems involving periodic planar tilings
• About the Garden of Eden theorems for cellular automata in the hyperbolic plane
• Decidability and undecidability in cellular automata
• Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
• About the domino problem in the hyperbolic plane from an algorithmic point of view
• THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE
• High Complexity Tilings with Sparse Errors
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane
• The complexity of generalized domino tilings
• Aspects of a multivariate complexity analysis for rectangle tiling
• The periodic domino problem revisited
• scientific article; zbMATH DE number 1062022 (Why is no real title available?)
• scientific article; zbMATH DE number 1460255 (Why is no real title available?)
• About the domino problem for subshifts on groups
• On the Steinhaus tiling problem
• scientific article; zbMATH DE number 781272 (Why is no real title available?)
• scientific article; zbMATH DE number 806590 (Why is no real title available?)
• scientific article; zbMATH DE number 1445361 (Why is no real title available?)
• The undecidability of the domino problem
• On the Undecidability of the Tiling Problem
• Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
• The Tiling Book
• Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version)
• Metallic mean Wang tiles. II: The dynamics of an aperiodic computer chip
• Fusion: a general framework for hierarchical tilings of \(\mathbb{R }^d\)
• The domino problem of the hyperbolic plane is undecidable

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

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