Rectangular tileability and complementary tileability are undecidable

DOI10.1016/j.ejc.2014.03.008zbMath1300.05058arXiv1212.3380OpenAlexW2017701503MaRDI QIDQ740261

Jed Yang

Publication date: 2 September 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.3380

zbMATH Keywords

polyominoes

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Polyominoes (05B50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Successful visual human-computer interaction is undecidable
• The complexity of generalized domino tilings
• An aperiodic hexagonal tile
• Polyominoes which tile rectangles
• An aperiodic set of 13 Wang tiles
• Quaquaversal tilings and rotations
• On translating one polyomino to tile the plane
• Polyominoes of order 3 do not exist
• Isohedral polyomino tiling of the plane
• Tiling figures of the plane with two bars
• Aperiodic tilings
• A codicity undecidable problem in the plane.
• Decision problems for semi-Thue systems with a few rules
• Tiling with polyominoes and combinatorial group theory
• Tiling simply connected regions with rectangles
• Undecidability and nonperiodicity for tilings of the plane
• Tiling a polygon with two kinds of rectangles
• Conway's Tiling Groups
• Tiling the Plane with a Fixed Number of Polyominoes
• Tiling with sets of polyominoes
• Ribbon tile invariants
• An algorithm for deciding if a polyomino tiles the plane
• Packing a rectangle with congruent N-ominoes
• The undecidability of the domino problem
• Checker Boards and Polyominoes
• A variant of a recursively unsolvable problem
• Tilings
• Hard tiling problems with simple tiles

This page was built for publication: Rectangular tileability and complementary tileability are undecidable