<p>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. </p>

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

<p>A variant problem is the following: Given the same $T,H,V$, are there some dimensions $0&lt;w&lt;\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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-11-07T10:58:27.227Z
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$.
Marzio De Biasi
CC BY-SA 3.0
2015-11-07T11:39:38.927Z
In the problem you describe, is $m$ fixed or existentially quantified upon ?
phs
CC BY-SA 3.0
2015-11-08T01:32:07.010Z
$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?
Marzio De Biasi
CC BY-SA 3.0
2015-11-08T10:14:00.260Z
@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](http://dx.doi.org/10.1007/s00224-014-9561-9).
phs
CC BY-SA 3.0
2015-11-08T17:38:02.307Z
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".
Marzio De Biasi
CC BY-SA 3.0
2015-11-08T18:20:45.023Z
Yes there is  not much difference between the two problems, and it is easy to reduce the original one to the variant (I have modified the original question to mention that). My question is about referencing a problem defined in the literature rather than having to introduce a new version.
phs
<reference-request><computability><cellular-automata>
A variant of the tiling problem
phs
# A variant of the tiling problem

(Asked by: username_0 on 2015-11-07)

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

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.

**Tags:** reference-request, computability, cellular-automata

> **Comments:**
> **username_1**: 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$.  
> **username_0**: In the problem you describe, is $m$ fixed or existentially quantified upon ?  
> **username_1**: $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?  
> **username_0**: @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](http://dx.doi.org/10.1007/s00224-014-9561-9).  
> **username_1**: 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".  
> **username_0**: Yes there is  not much difference between the two problems, and it is easy to reduce the original one to the variant (I have modified the original question to mention that). My question is about referencing a problem defined in the literature rather than having to introduce a new version.  

---

## 0 answers

