2
$\begingroup$

A classic tiling problem with Wang tiles has the form: Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints $H,V\subseteq T\times T$, is there a way to tile a $w\times h$ rectangular grid with $t_1$ at the SW corner, $t_n$ at the NE corner, and such that any two horizontally or vertically adjacent tiles are in $H$ or $V$ respectively.

In this problem, $T,H,V$ are given and the question asks for the existence of some $w,h>0$ such that the rectangle can be tiled. This is undecidable and in fact $\Sigma_1^0$-complete.

A variant problem is the following: Given the same $T,H,V$, are there some dimensions $0<w<\ell$ and a sequence $d_1,...,d_\ell$ of tiles such that $d_1=t_1$, $d_\ell=t_n$, $(d_i,d_{i+1})\in H$ for all $1\leq i\leq\ell-1$ and $(d_i,d_{i+w})\in V$ for all $1\leq i\leq \ell-w$. This is similar to the rectangular grid problem with $w$ being the width but the $H$ constraint wraps around the lines of the grid and the last line is maybe not full. The classic problem is easily reduced to the variant problem (use several copies of the original tiles so that positional information can be encoded and checked by the H and V constraints) so the variant problem is undecidable.

My question: is this variant mentioned in the literature? Where? If not, is there a similar problem mentioned somewhere?

Motivation: I am using the classic problem in a reduction showing that some (unrelated) problem is undecidable and the reduction will be simpler/more elegant if I start from the variant problem.

$\endgroup$
  • $\begingroup$ Just a note: perhaps the variant you defined is similar to a 1D tag system $S$ in which every production rule doesn't change the length of the string (i.e. every production is of the form: $t_i \to t_{j_1} ... t_{j_m}$ and $m$ matches the deletion number) and you ask if there is a string $t_1 t_{empty} .... t_{empty} t_n $ that is accepted by $S$. $\endgroup$ – Marzio De Biasi Nov 7 '15 at 10:58
  • $\begingroup$ In the problem you describe, is $m$ fixed or existentially quantified upon ? $\endgroup$ – phs Nov 7 '15 at 11:39
  • $\begingroup$ $m$ is fixed; the length of the input string is existentially quantified (does there exist a string $t_1 ...$ accepted by $S$ )? ... but it is only an idea and it should be refined. Can you provide more details on the unrelated problem that you proved undecidable using your variant of the Wang tiling problem? $\endgroup$ – Marzio De Biasi Nov 8 '15 at 1:32
  • $\begingroup$ @Marzio: thanks for your interest! Since $m$ is fixed then the tag system does not look like the 2-dimensional problem that underlies the variant tiling problem. Really I use a 2-dimensional tiling problem represented as a 1-dim structure because it simplifies my reduction. The unrelated problem is a decision problem on strings, in the spirit of a recent ToCS paper. $\endgroup$ – phs Nov 8 '15 at 10:14
  • $\begingroup$ in the 1D tag system m represents only the length of the productions (how many tiles are appended to the current string);the "exists w" of your problem is "captured" by "exists an initial string - made of $t_1$ followed by a repeated dummy $t_{empty}$ tile- long enough that is accepted by the tag system. However I don't see too much differences between your variant and the original Wang problem: if you drop the constraint at the "border wrap": $(t_{i*w-1},t_{i*w}) \in H$ your problem is exactly the original Wang problem,so in your reduction you needs only to take care about that "wrap". $\endgroup$ – Marzio De Biasi Nov 8 '15 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.