Next: Defining a Torus of Up: Consistency of - is Previous: Consistency of - is

## Domino Systems

Definition 3.1   For , let denote the set and denote the addition modulo n. A domino system is a triple , where D is a finite set (of tiles) and are relations expressing horizontal and vertical compatibility constraints between the tiles. For , let U(s,t) be the torus , and let be a word over D of length n (with ). We say that tiles U(s,t) with initial condition w iff there exists a mapping such that, for all ,
• if and , then (horizontal constraint);
• if and , then (vertical constraint);
• for (initial condition).

Bounded domino systems are capable of expressing the computational behaviour of restricted, so-called simple, Turing Machines (TM). This restriction is non-essential in the following sense: Every language accepted in time T(n) and space S(n) by some one-tape TM is accepted within the same time and space bounds by a simple TM, as long as  [BGG97].

Theorem 3.2 ([BGG97], Theorem 6.1.2)
Let M be a simple TM with input alphabet . Then there exists a domino system and a linear time reduction which takes any input to a word with |x| = |w| such that
• If M accepts x in time t0 with space s0, then tiles U(s,t) with initial condition w for all ;
• if M does not accept x, then does not tile U(s,t) with initial condition w for any .

Corollary 3.3
There is a domino system such that the following is a -hard problem:

Given an initial condition of length n. Does tile the torus U(2n+1,2n+1) with initial condition w?

Proof. Let M be a (w.l.o.g. simple) non-deterministic TM with time- (and hence space-) bound 2n deciding an arbitrary -complete language over the alphabet . Let be the according domino system and the reduction from Theorem 3.2. The function is a linear reduction from to the problem above: For with |v| = n, it holds that iff M accepts v in time and space 2|v| iff tiles U(2n+1,2n+1) with initial condition .

Next: Defining a Torus of Up: Consistency of - is Previous: Consistency of - is

Stephan Tobies
May 02 2000