Implementation [of generalized substitution systems]

Sequential substitution systems in which only one replacement is ever done at each step can just be implemented using /. as described on page 893. Substitution systems in which all replacements are done that are found to fit in a left-to-right scan can be implemented as follows

GSSEvolveList[rule_, s_, n_] := NestList[GSSStep[rule, #] &, s, n]

GSSStep[rule_, s_] := g[rule, s, f[StringPosition[s, Map[First, rule]]]]

f[{ }] = { }; f[s_] := Fold[If[Last[Last[#1]] ≥ First[#2], #1, Append[#1, #2]]&, {First[s]}, Rest[s]]

g[rule_, s_, { }] := s; g[rule_, s_, pos_] := StringReplacePart[s, Map[StringTake[s, #] &, pos] /. rule, pos]

with rules given as {"ABA"  "BAAB", "BBBB"  "AA"}.