Rectangular tileability and complementary tileability are undecidable |
| |
Institution: | School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA |
| |
Abstract: | Does a given 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|