Conditions for convergence [in string rewriting] One way to guarantee that there is convergence after one step is to require as in the previous section that blocks to be replaced cannot overlap with themselves or each other. And of the 196 possible rules involving two colors and blocks of length at most three, 112 have this property. … Much as in the previous section, even if paths do not converge for every possible string, it can still be true that paths converge for all strings that are actually generated from a particular initial string.

For strings the analogous problem is straightforward, since in a string of length n one can ultimately just try each of the n possible starting points for the substring and see for which of them a match occurs.

Sequence equations One can ask whether by replacing variables by sequences one can satisfy so-called word or string equations such as Flatten[{x, 0, x, 0, y}]  Flatten[{y, x, 0, y, 1, 0, 1, 0, 0}] (with shortest solution x = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0} , y = {1, 0, 1, 0, 0, 1, 0, 1, 0, 0} ). … But in 1977 Gennadií Makanin gave a complicated algorithm that solves the problem completely in a finite number of steps (though in general triple exponential in the length of the equation).

• Can a multiway system generate a certain string in a given number of steps? … • Is there a path shorter than some given length that visits all of some set of points in the plane? … (See page 984 .) • Is there a string of some limited length that solves a correspondence problem?

Indeed, for period p , the length of blocks required is at most 2 2p (or 2 2 p r for range r rules). … Within each row a gray bar indicates that a particular period can be obtained with blocks of some length. … The possible configurations that repeat with period p then correspond to the finite complement language (see page 958 ) obtained by stringing together these blocks.

And by using rules such as s[x___, 1, 0, y___]  {s[x, 0, 1, 0, y], Length[s[x]]} one can keep track of the positions at which substitutions are made. ( StringReplace replaces all occurrences of a given substring, not just the first one, so cannot be used directly as an alternative to having a flat function.)

(In some cases it works to look at whether the limiting ratio of lengths on successive steps is a Pisot number.) … With k colors each giving a string of the same length s the recurrence relation is Thread[Map[ ϕ [#][t + 1, ω ] &, Range[k] - 1]  Apply[Plus, MapIndexed[Exp[  ω (Last[#2] - 1) s t ] ϕ [#1][t, ω ] &, Range[k] - 1 /. rules, {-1}], {1}]/ √ s ] Some specific properties of the examples shown include: (a) (Thue–Morse sequence) The spectrum is essentially Nest[Range[2 Length[#]] Join[#, Reverse[#]] &, {1}, t] .

Analytical approaches (that happened to be like 0D string theory) were also found for 2D discrete spacetimes (compare page 1038 )—but they were not successfully extended to higher dimensions. … A simple analog involves a 2D surface made out of triangles whose edges have integer lengths j i . … In 3D one imagines breaking space into tetrahedra whose edge lengths correspond to discrete quantum spin values.

Knots and string figures. For many thousands of years definite rules have been used for tying knots and presumably also for making string figures. … Patterns of rhyme involving iterated length-6 permutations (sestina) and interleaved repetitive sequences (terza rima) were in use by the 1300s, notably by Dante .