On the solvability of domino snake problems

DOI10.1016/0304-3975(94)90174-0zbMath0808.03028OpenAlexW2019073153WikidataQ127008574 ScholiaQ127008574MaRDI QIDQ1331945

Dale Myers, Yael Etzion-Petruschka, David Harel

Publication date: 15 March 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90174-0

zbMATH Keywords

undecidabilityconnectivitytiling problemscomplexity lower boundscomplexity classificationPSPACE- algorithmunrestricted snake problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (8)

On the solvability of domino snake problems ⋮ Complexity of tile rotation problems ⋮ Undecidability of domino games and hhp-bisimilarity. ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ Path finding in the tile assembly model ⋮ Perfectly quilted rectangular snake tilings ⋮ Connecting the Dots: Molecular Machinery for Distributed Robotics ⋮ Tiling allowing rotations only

Cites Work

• On the solvability of domino snake problems
• Undecidability and nonperiodicity for tilings of the plane
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Domino Games and Complexity
• Undecidability Of Some Domino Connectability Problems
• Undecidability principle and the uncertainty principle even for classical systems
• The undecidability of the domino problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the solvability of domino snake problems