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

Wang tilesTuring machinemortality problem

Mathematics Subject Classification ID

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

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

(37)

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

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)