Implementation [of multiway systems]

It is convenient to represent the state of a multiway system at each step by a list of strings, where an individual string is for example "ABBAAB". The rules for the multiway system can then be given for example as

{"AAB"  "BB", "BA"  "ABB"}

The evolution of the system is given by the functions

MWStep[rule_List, slist_List] := Union[Flatten[Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]]

MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]]

MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t]

An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as

{{x___, 0, 0, 1, y___}  {x, 1, 1, y}, {x___, 1, 0, y___}  {x, 0, 1, 1, y}}

MWStep can be rewritten as

MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]]

The case shown on page 206 is

{"AB"  "", "ABA"  "ABBAB", "ABABBB"  "AAAAABA"}

starting with {"ABABAB"}. Note that the rules are set up so that a string for which there are no applicable replacements at a given step is simply dropped.