is emulated by a cyclic tag system with m*n productions (Q₁, ..., Q_n, -, -, ..., -), where all but the first n productions are the empty string (denoted by ). The Q_k are encodings of the respective P_k, obtained by replacing each symbol of the tag system alphabet by a length-n binary string as follows (these are to be applied also to the initial word of a tag system computation):

a₁ = 100...00 a₂ = 010...00 . . . a_n = 000...01

That is, a_k is

1.Previous
3.Next