5.4 Typical Multiway Graph Structures

Before considering further features of the updating process, it is helpful to discuss the typical kinds of multiway graphs that are generated from string substitution systems. Much as for our primary models based on general relations (hypergraphs), we can assign signatures to string substitution system rules based on the lengths of the strings in each transformation. For example, we will say that the rule {A  BBB, BB  A} has signature 2: 13, 21, where the initial 2 indicates the number of distinct possible elements (here A and B) that occur in the rule.

With a signature of the form k: n₁n₂, n₃n₄, … there are nominally k^∑n_i possible rules. However, many of these rules are equivalent under renaming of elements or reversal of strings. Taking this into account, the number of inequivalent possible rules for various cases is:

Rules with signature k: 1n must always be totally causal invariant. If they are started from strings of length 1, their states graphs can never branch. However, with strings of length more than 1, branching can (but may not) occur, as in this example of A  AB started from three strings of length 2:

With initial conditions AAA and AAAA, this rule produces the following states graphs:

Even the rule A  AA can produce states graphs like these if it has initial conditions that contain Bs as “separators”:

And as a seemingly even more trivial example, the rule A  B with an initial condition containing n As gives a states graph corresponding to an n-dimensional cube (with a total of 2ⁿ nodes):

With multiple rules, one can get tree-like structures, with exponentially increasing numbers of states. The simplest case is the 2: 01, 01 rule {  A,  B} starting with the null string:

With multiple rules, even with single-symbol left-hand sides, causal invariance is no longer guaranteed. Of the 8 inequivalent 2: 11, 11 rules, all are totally causal invariant, although the rule {A  B, B  A} achieves this through cyclic behavior:

Among the 14 inequivalent 3: 11, 11 rules, all but two are totally causal invariant. The exceptions are the cyclic rule, and also the rule {A  B, A  C}, which in effect terminates before its B and C branches can reconverge:

The 12 inequivalent 2: 12, 11 rules yield the following states graphs when run for 4 steps starting from all possible length-3 strings of As and Bs:

All but three of these rules are totally causal invariant. Among causal invariant ones are:

After more steps these yield:

Examples of non-causal invariant 2: 12, 11 rules are:

After more steps these yield:

When we look at rules with larger signatures, the vast majority at least superficially show the same kinds of behavior that we have already seen.

Like for the hypergraphs from our models that we considered in previous sections, we can study the limiting structure of states graphs generated in multiway systems, and see what emergent geometry they may have. And in analogy to V_r(X) for hypergraphs, we can define a quantity M_t(S) which specifies the total number of distinct states reached in the multiway system after t steps of evolution starting from a state S.

For the rule {A  AB} mentioned above, the geometry of the multiway graph obtained by starting from n As is effectively a regular n-dimensional grid:

M_t(Aⁿ) in this case is then an n-fold nested sum of t 1s:

Some rules create states graphs that are trees, with M_t~m^t. Other rules do not explicitly give trees, but still give exponentially increasing M_t. An example is {A  AB, B  A}, for which M_t is a sum of Fibonacci numbers, and successive states graphs can be rendered as:

Note that rules with both polynomial and exponential growth in M_t can exhibit causal invariance.

It is not uncommon to find rules with fairly long transients. A simple example is the totally causal invariant rule {A  BBB, BBBB  A}. When started from n As this stabilizes after 7n steps, with ~2.8ⁿ states, with a states graph like:

Rules typically seem to have either asymptotically exponential or asymptotically polynomial M_t. (This may have some analogy with what is seen in the growth of groups [57][58][22].) Among rules with polynomial growth, it is typical to see fairly regular grid-like structures. An example is the rule

which from initial condition ABAA gives states graph:

With the slightly different initial condition ABAAA, the states graph has a more elaborate structure

and the form of M_t is more complicated (though ~t² and ultimately quasiperiodic); the second differences of M_t in this case are:

Another example of a somewhat complex structure occurs in the rule

that was discussed in [1:p205]. Starting from BABBAAB it gives the states graph: