A tag system in which a list of n tag rules (each of a special form) is applied to a system in sequential order and then starting again from the first rule. In a cyclic tag system, each set of tag rules has the special structure that a pattern is appended if (and only if) the first element of the current pattern is a 1 and that independent of whether the first element is 0 or 1, the first element is then deleted. For example, consider a state consisting of white and black cells, labeled 0 and 1, respectively, and the cyclic tag system {(1, ...)->(..., 1, 1), (0, ...)->(...)} and {(1, ...)->(..., 1, 0), (0, ...)->(...)} with initial state (1), illustrated above. As required, this system always removes the first element and appends specific patterns iff the first cell is black.

string rewriting system | substitution system | tag system