Implementation [of sequential substitution systems]

Sequential substitution systems can be implemented quite directly by using Mathematica's standard mechanism for applying transformation rules to symbolic expressions. Having made the definition

Attributes[s] = Flat

the state of a sequential substitution system at a particular step can be represented by a symbolic expression such as s[1, 0, 1, 0]. The rule on page 82 can then be given simply as

s[1, 0]  s[0, 1, 0]

while the rule on page 85 becomes

{s[0, 1, 0]  s[0, 0, 1], s[0]  s[0, 1, 0]}

The Flat attribute of s makes these rules apply not only for example to the whole sequence s[1, 0, 1, 0] but also to any subsequence such as s[1, 0]. (With s being Flat, s[s[1, 0], 1, s[0]] is equivalent to s[1, 0, 1, 0] and so on. A Flat function has the mathematical property of being associative.) And with this setup, t steps of evolution can be found with

SSSEvolveList[rule_, init_s, t_Integer] := NestList[(# /. rule)&, init, t]

Note that as an alternative to having s be Flat, one can explicitly set up rules based on patterns such as s[x___, 1, 0, y___]  s[x, 0, 1, 0, y]. 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.)