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,First/@rule]]]

f[{ }]={ }; f[s_]:= Fold[If[Last[Last[#1]]>=First[#2], #,Append[#,#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"}.