Rectangular tileability and complementary tileability are undecidable

DOI10.1016/J.EJC.2014.03.008MaRDI QIDQ740261zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: Does a given a set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.

Recommendations

• Tiling the Plane with a Fixed Number of Polyominoes
• A codicity undecidable problem in the plane.
• Isohedral polyomino tiling of the plane
• Fixed parameter undecidability for Wang tilesets
• Tiling simply connected regions with rectangles

Cites work

• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• scientific article; zbMATH DE number 3503269 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256699 (Why is no real title available?)
• scientific article; zbMATH DE number 1327765 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1510511 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 3222108 (Why is no real title available?)
• A codicity undecidable problem in the plane.
• A variant of a recursively unsolvable problem
• An algorithm for deciding if a polyomino tiles the plane
• An aperiodic hexagonal tile
• An aperiodic set of 13 Wang tiles
• Aperiodic tilings
• Checker Boards and Polyominoes
• Conway's Tiling Groups
• Decision problems for semi-Thue systems with a few rules
• Hard tiling problems with simple tiles
• Isohedral polyomino tiling of the plane
• Matching theory
• On translating one polyomino to tile the plane
• Packing a rectangle with congruent N-ominoes
• Polyominoes of order 3 do not exist
• Polyominoes which tile rectangles
• Quaquaversal tilings and rotations
• Ribbon tile invariants
• Successful visual human-computer interaction is undecidable
• The complexity of generalized domino tilings
• The undecidability of the domino problem
• Tiling a polygon with two kinds of rectangles
• Tiling figures of the plane with two bars
• Tiling simply connected regions with rectangles
• Tiling the Plane with a Fixed Number of Polyominoes
• Tiling with polyominoes and combinatorial group theory
• Tiling with sets of polyominoes
• Tilings
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(1)

• Tiling simply connected regions with rectangles

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

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