Multiway System

[GroupbyCompany]

[federicopfund]

[GroupbyCompany]

A multiway system is a kind of substitution system in which multiple states are permitted at any stage. This accommodates rule systems in which there is more than one possible way to perform an update.
A simple example is a string substitution system. For instance, take the rules {AB->A,BA->B} and the initial condition ABA. There are two choices for how to proceed. Applying the first rule yields the evolution ABA toAA, while applying the second rule yields the evolution ABA->AB->A. So at the first step, there is a single state ({ABA}), at the second step there are two states {AA,AB}, and at the third step there is a single state {A}.

A path through a multiway system arising from a choice of which substitutions to make is called an evolution. Typically, a multiway system will have a large number of possible evolutions. For example, consider strings of As and Bs with the rule AB->BA. Then most strings will have more than one occurrence of the substring AB, and each occurrence leads down another path in the multiway system.