Questions tagged [tilings]
The tilings tag has no usage guidance.
3 questions
5
votes
0
answers
201
views
Reference request: Undecidability of tiling problem of finite octant
I am seeking a reference/citation for the undecidability of the following (or a similar) tiling problem. While proving its undecidability seems to be an (under)graduate student exercise, I would like ...
- 1,422
0
votes
0
answers
34
views
Reduction from any succinct language to tiling
Given a set of colors $T = \{1, \ldots, k\}$, a set of horizontal or vertical rules $H, V \subseteq T \times T$ of ordered pairs, and a chosen color $b = 1$, the tiling language is defined as follows:
...
- 11
0
votes
0
answers
47
views
For which k can we decide whether an input k-gon tiles?
Can we decide whether a given polygon can tile the whole plane?
First, let me briefly summarize what is known about this problem.
If we only allow translations, then the problem is always decidable in ...
- 14.2k