# String Substitution Systems

String Substitution Systems

Stephen Wolfram

### (Unfinished draft as of March 28, 2006; with small updates October 2019)

(Unfinished draft as of March 28, 2006; with small updates October 2019)

## Introduction

Introduction

### Substitution Systems

Substitution Systems

A great many systems can be thought of as consisting at some level of strings of elements that are successively updated by making substitutions for particular blocks of these elements. The purpose of this [paper] is to carry out a systematic study of a large number of simple such string substitution systems, in the tradition of A New Kind of Science.

Substitution systems consist of strings of elements that are successively updated by performing substitutions for blocks of these elements. Specific classes of examples of such systems have been considered under a variety of different names for over a century. Our purpose here is for the first time to carry out a fully systematic study of substitution systems with the property of causal invariance, in the tradition of A New Kind of Science.

String substitution systems seem to capture important underlying mechanisms in many diverse areas, including computer science, foundations of mathematics, molecular biology, chemistry, linguistics and physics. The results in this [paper] should be relevant to almost any potential application of string substitution systems.

The picture below shows an example of a string substitution system.

SREvolutionGraphics[SRXEvolveList[{"AB""ABBA"},"AB",4]]

[ This particular system is defined by the rules . ]

{"A""CAB","BBC""CB"}

Grid[{{Labeled[SREvolutionGraphics[SRXEvolveList[#,"AA",7]],SRRuleGraphic[#]]&[{"A""CAB","BBC""CB"}],SRGraphicsChopped[SREvolveList[{"A""CAB","BBC""CB"},"AA",100],100]}}]

A key issue in string substitution systems is the order in which rules are applied. In general, different orders may lead to different results, as in the picture below. [[[In this picture only one update is done at each step]]]

Grid[{{Labeled[SREvolutionGraphics[RandomSRXEvolveList[#,"AA",7],ImageSize130],SRRuleGraphic[#]]&[{"A""CAB","BBC""CB"}],SRGraphicsChopped[RandomSREvolveList[{"A""CAB","BBC""CB"},"AA",100],100]}}]

One can represent all the different possible orders using a multiway system.

### Causal Invariance

Causal Invariance

In a system like a cellular automaton, there is a definite notion of time: at every step, each cell gets updated in parallel according to a fixed rule. In a substitution system, however, the situation can be more complicated.

As an example, consider the very simple rule . At each step there is an ambiguity in how to apply the rule.

"AA""AAA"

The remarkable fact, however, is that there exist what we will call causal invariant substitution systems where no such ambiguity is possible. The condition for this turns out simply to be that the strings which appear on the left-hand side of each rewrite allow no overlaps, either with themselves or with each other.

[[XXXX use a case with 2 rewrites]]]

When the rules for a substitution system have the property of causal invariance, it means that there is, in a sense, a unique standard evolution for the system—in which the maximum number of rewrites get done at each step.

One can always choose to consider other evolutions, in which fewer rewrites get done at each step. But the point is that in all cases the system in a sense maintains the same causal structure—so that a given rewrite must be preceded by the same sequence of other rewrites.

The pictures below indicate how a causal network can be constructed that shows the causal relationships between rewriting events. The causal network can conveniently be shown like a "light cone", in which events reached by successively more steps from a given event are shown on successive lines down the page.

Given a causal network, possible evolutions for the system can be obtained by taking different families of slices, or foliations, through the causal network. The standard evolution involving a maximum number of rewrites at each step corresponds to XXXXXXXXXXXXXXXXXXX.

Labeled[SREvolutionGraphicsStreamed[SRXEvolveList[#,"AAABBB",6]],SRRuleGraphic[#]]&[{"AAB""ABBBAA"}]

[[[ Dead elements are ones that will never be updated again... (Here some elements are shown without successors, but in fact would eventually get successors.) ]]]

#### [Extras]

[Extras]

### Overlap-Free Strings

Overlap-Free Strings

With two possible elements, the first few distinct overlap-free strings are (ignoring reversal and renaming):

{A,AB,AAB,AAAB,AABB,AAAAB,AAABB,AABAB,AAAAAB,AAAABB,AAABAB,AAABBB,AABABB,AABBAB}

With three possible elements, the first few overlap-free strings are:

{A,AB,AAB,ABC,AAAB,AABB,AABC,ABAC,ABBC,ABCB}

Indeed, out of all strings of length n with k possible elements, the number of overlap-free strings is given by:

n

k

a[n]

a[0]=1;a[n_]:=ka[n-1]-If[EvenQ[n],a[n/2],0]

For k=2, this approaches about 27% for large n; for k=3 it approaches about 56%. For large k (and to a good approximation even for k=3), this fraction approaches .

1--

1

k

1

2

k

If one considers pairs of strings, it becomes slightly more difficult to find overlap-free cases. Nevertheless, with two possible elements, the first few examples are:

{{A,B},{AABAB,AABB},{AABB,ABABB},{AAABB,AABAB},{AAABB,ABABB}}

With three elements, the first few examples of overlap-free pairs are:

{{A,B},{A,BC},{A,BBC},{AB,AC},{AB,CB},{AAC,AB},{AB,ACB},{AB,ACC},{AB,CBB},{AB,CCB},{AAB,AAC},{AAB,ACB},{AAB,CAB},{AAB,CCB},{AAC,ABB},{ABB,CCB},{ABC,ACB},{ABC,BAC}}

With triples of strings, the first few cases are:

{{AAABB,ABAABB,ABABB},{AAAABB,ABAABB,ABABB},{AAABB,AABABB,ABAABB},{AAABB,ABAABB,ABABBB},{AAABBB,AABAB,AABBAB},{AAABBB,ABAABB,ABABB},{AAAABB,AABABB,ABAABB},{AAAABB,ABAABB,ABABBB},{AAABAB,AAABBB,AABBAB},{AAABBB,AABABB,AABBAB},{AAABBB,AABABB,ABAABB},{AAABBB,ABAABB,ABABBB}}

[[Tables of overlap-free strings; counts of them]] [[[ Todd will generate these ]]]

FreeTest[k_,imin_,p_]:=Do[With[{w=FindOverlapFree[k,i,p]},If[w=!={},Return[w]]],{i,imin,15}]Monitor[Table[TimeConstrained[FreeTest[k,1,p],100],{k,4},{p,4}],{k,p}]Text[Grid[Prepend[MapIndexed[Prepend[#,Row[{"p=",First[#2]}]]&,{{{{"A"}},{{"A"},{"AB"},{"AAB"},{"AAAB"},"…"},{{"A"},{"AB"},{"AAB"},{"ABC"},…},{{"A"},{"AB"},{"AAB"},{"ABC"},…}},{"",{{"A","B"},{"AABAB","AABB"},…},{{"A","B"},{"A","BC"},…},{{"A","B"},{"A","BC"},…}},{"",{{"AAABB","ABAABB","ABABB"},…},{{"A","B","C"},{"AB","ACB","ACC"},…},{{"A","B","C"},{"A","B","CD"},…}},{"",{{"AAAABB","ABAABB","ABABB","ABAAABB"},"…"},{{"AAB","ACB","CAB","CCB"},…},{{"A","B","C","D"},{"AB","AC","DB","DC"},…}}}],Prepend[Table[Row[{"k=",i}],{i,1,4}],""]],ColumnLinesTrue,RowLinesTrue]]

(((((((( Number of overlap free strings vs k, n, p; what fraction of possible strings are overlap free ))))))))

#### Note: Single Overlap-Free Strings

Note: Single Overlap-Free Strings

It is straightforward to derive the recurrence

a[0]=1;a[n_]:=ka[n-1]-If[EvenQ[n],a[n/2],0]

Consider an overlap-free string s of length n-1 with first element e. Adding any element other than e to the end of s will give an overlap-free string of length n. In addition, adding e to the beginning will also give an overlap-free string. There is, however, one case where strings produced by this procedure will not be unique: the case where the resulting string is a "doubled" version of a length-n/2 overlap-free string. Thus, for example, AABB can be produced both by adding B to the end of AAB, and by adding A to the beginning of ABB.

An alternative form of the recurrence is:

{a[2n+1]ka[2n],a[2n]ka[2n-1]-a[n]}

There does not appear to be a solution for a[n] in terms of ordinary special functions.

One can enumerate strings in the order corresponding to digit sequences of successive numbers. The following show the cumulative number of overlap-free strings as a function of string enumeration number for strings of lengths 6 and 10:

Grid[{ListLinePlot[Accumulate[Boole[OverlapFreeQ/@Flatten[Table[AllTuples[i],{i,1,#}]]]],FillingAxis]&/@{6,10}}]

The following shows the lengths of overlaps for all strings of length 8. The overlap-free strings are those with overlap length 0.

ListPlot[Length[StringOverlaps[#]]&/@AllTuples[8],FillingAxis,PlotRangeAll]

#### Overlap-free pairs

Overlap-free pairs

The following show which pairs of strings are overlap-free.

Grid[{Labeled[ArrayPlot[Boole[Outer[OverlapFreeQ,#,#]&@Flatten[Table[AllTuples[i,#[[1]]],{i,1,#[[2]]}]]],FrameTicksTrue,ImageSizeSmall],Text[Row[{"k = ",#[[1]],", n = ",#[[2]]}]]]&/@{{2,6},{3,4},{4,3}}}]

The following show the relative overlap lengths for pairs of strings:

Grid[{Labeled[ArrayPlot[Outer[Length[StringOverlaps[#1,#2]]&,#,#]&@Flatten[Table[AllTuples[i,#[[1]]],{i,1,#[[2]]}]],FrameTicksTrue,ImageSizeSmall],Text[Row[{"k = ",#[[1]],", n = ",#[[2]]}]]]&/@{{2,6},{3,4},{4,3}}}]

## Neighbor-Independent Rules

Neighbor-Independent Rules

The simplest substitution systems have "neighbor-independent" rules, in which the replacement for a particular symbol depends

work by replacing

work by replacing

The very simplest possible causal-invariant substitution system just has a single rewrite of the form :

"A""AA"

In general, any "neighbor independent" substitution system—whose rewrites just have single elements on the left—must be causal invariant. An example is the Fibonacci substitution system :

{"A""AB","B""A"}

#### Growth rates and the relation to matrices

Growth rates and the relation to matrices

It is fairly straightforward to analyse many features of neighbor-independent substitution systems.

For example, the total numbers of each element always satisfy a system of linear recurrence relations. Indeed, each step just corresponds to multiplying the vector of numbers of each element by a fixed matrix.

For the Fibonacci substitution system, the evolution matrix is {{1,1},{1,0}}. This means that the total numbers of As and Bs at step t is given by:

{1,1}.MatrixPower[{{1,1},{1,0}},t]

In general, the total lengths of strings at step t must satisfy at most a k-th order linear recurrence relation:

a[t]c[i]a[t-k+i]

k-1

∑

i=0

The coefficients c[i] in this recurrence relation can be obtained directly from the characteristic polynomial of the evolution matrix m according to:

-Most[CoefficientList[CharacteristicPolynomial[m,x],x]]

In the Fibonacci substitution system case, the coefficient list is just {1, 1}. Such a coefficient list can be thought of as a kernel for the linear recurrence. Given a kernel ker, and a sequence of initial values list, the first t successive terms can be computed from:

Nest[Append[#,ker.Take[#,-Length[ker]]]&,list,t]

In a case like the Fibonacci substitution system, the successive terms, corresponding to successive strings lengths, asymptotically grow at an exponential rate. The base of the exponential is in general determined by the leading eigenvalue of the evolution matrix: after t steps, the string length is always of order . (There may always be some initial conditions for a given substitution system that lead to smaller results. For example, with the rule AA, BBB, an initial condition A will not show the maximal growth rate 2^t.)

t

Eigenvalues[m,1]

#### Growth rates for all possible matrices

Growth rates for all possible matrices

In general, any matrix of non-negative integers serves as the evolution matrix for some substitution system. With k possible elements, and at most s appearing on the right-hand side of any given rewrite, the complete set of possible evolution matrices is given by:

Tuples[Range[0,s],{k,k}]

The distribution of possible leading eigenvalues is as follows: [[[make lines in pictures go vertically]]]

Grid[Table[Labeled[ListLinePlot[Sort[Max[Re[N[Eigenvalues[#]]]]&/@Tuples[Range[0,s],{k,k}]],PlotRangeAll,FillingAxis,ImageSizeSmall],Row[{"k = ",k,", s = ",s}]],{s,1,2},{k,2,3}]]

For large k and s, the distribution of leading eigenvalues tends to a XXXXXXXX [Gaussian]. In all cases the leading eigenvalues are algebraic numbers of degree at most k. The largest leadingeigenvalue that can occur is k s—and this occurs only for the single matrix whose entries are all s. The smallest leading eigenvalues that occur are 0 and 1. (Since the matrices contain only integers, there can be no eigenvalues at all between 0 and 1, or -1 and 0.)

A largest eigenvalue of 0 occurs only in the fairly trivial case where the substitution system leads to a zero-length string.

When the largest eigenvalue is 1, it corresponds to a substitution system where the string length grows not exponentially with t, but instead as a polynomial in t. The maximum degree of the polynomial is k-1.

The following gives the multiplicities of different polynomial degrees in several cases: [[include more k and s values, and also the ∞ case: i.e. how many cases there are that are above polynomial]]

Text[Grid[Prepend[MapIndexed[Prepend[#,Row[{"s=",First[#2]}]]&,Table[{First[#],Length[#]}&/@Split[Sort[Flatten[Table[Exponent[#[[1]],t],{#[[2]]}]&/@({FullSimplify[First[#],t>0&&t∈Integers],Length[#]}&/@Split[Sort[Total[Flatten[Refine[MatrixPower[#,t],t>0]]]&/@Select[Tuples[Range[0,s],{k,k}],Max[Re[Eigenvalues[#]]]1&]]]/.{UnitStep[x_]x,KroneckerDelta[x_]0})]]],{s,1,2},{k,2,3}]],Prepend[Table[Row[{"k=",i}],{i,2,3}],""]],ColumnLinesTrue,RowLinesTrue]]

[[Each one of these corresponds to a certain kernel for a linear recurrence relation]]

For k=2, s=1, the fastest polynomial growth is , which occurs for the rule:

(t^2-t+2)/2

Labeled[SRGraphics[SREvolveList[#,"A",10]],SRRuleGraphic[#]]&[{"A""AB","B""BC","C""C"}]

The kernel in this case is {1,-3,3}.

#### Rules involving a single one-element rewrite

Rules involving a single one-element rewrite

The following tables summarize the distinct classes of rules that exist with two types of elements, but a single rewrite with progressively longer right-hand side:

rule | i.c. | # | sizes | kernel | eigen. |

AA | A | 2 | {1,1,1,1,1,1,1,1,1,1,…} | {1} | 1 |

rule | i.c. | # | sizes | kernel | eigen. |

ABB | A | 1 | {1,2,2,2,2,2,2,2,2,2,…} | {0,1} | 1 |

AAB | A | 2 | {1,2,3,4,5,6,7,8,9,10,…} | {-1,2} | 1 |

AAA | A | 1 | {1,2,4,8,16,32,64,128,256,512,…} | {2} | 2 |

BasicSRPanel[("A"#)&/@AllTuples[3],{"A"}]

The rules are classified here by the sequence of string lengths that they generate. For this case of a single rewrite, each class is defined by the number of "active" elements A and inactive elements B that appear on the right-hand side. Different orderings of A and B lead to patterns that are different in detail, but are related by simple transformations.

Adding more elements C, D, etc. has no effect on the classes of rules that can occur in this case. In effect, C, D, etc. act just like B, as "inactive elements".

#### Rules involving two one-element rewrites

Rules involving two one-element rewrites

With rewrites for both A and B elements, the following table summarizes the classes of rules that occur with right-hand sides of lengths up to 2:

BasicSRPanel[AllRHSs[{"A","B"},{0,2},2],{"A"}]

Note the appearance here of the Fibonacci substitution system. Note also the 19 different AAA substitution systems, in which the replacements for B are never used, and so are irrelevant.

[[[[ To what extent are the rules in given class equivalent ?? ]]]]

If one consider right-hand sides up to length 3, many new growth rates can occur. 11 different exponential growth rates. The kernel must still be of length 2 ....

With right-hand sides of length up to 3, [[[[ what growth rates occur ]]]]]

With right-hand sides of length up to 3, [[[[ what growth rates occur ]]]]]

The set of 2-element kernels that occur allowing right-hand sides of progressively greater lengths is:

ListPlot[#,AspectRatioAutomatic,FrameTrue,PlotStylePointSize[0.02]]&/@Table[Select[Rest[BasicSRPanel[AllRHSs[{"A","B"},{0,s},2],{"A"}][[1,1,All,5]]],Length[#]2&],{s,2,5}]

[[[ What is the analogy between these and the matrices ?? How much does it matter to start with A, rather than all possible strings ? ]]]

With three elements, A, B and C, kernels up to length 3 appear, and many other growth rates occur.

BasicSRPanel[AllRHSs[{"A","B","C"},{1,2},3],{"A"}]

[[http://www.wolframscience.com/nksonline/page-890a-text]]

Labeled[ListLinePlot[Ratios[SREvolveListCount[#,"A",15]],FillingAxis,PlotRangeAll,ImageSizeTiny],Text[#]]&/@{{"A""B","B""C","C""AA"},{"A""B","B""C","C""AB"},{"A""B","B""BC","C""AC"}}

#### Detailed patterns of strings

Detailed patterns of strings

In addition to looking at the growth of lengths of strings, one can look at the detailed patterns of each string. (An intermediate case is to look at the numbers of each color. For neighbor-independent substitution systems, these always obey a 1-step "multirecurrence".)

((The following was very slow))

BasicSRPanel[AllRHSs[{"A","B"},{0,2},2],{"A"},EvolutionFunctionSREvolveListPLength]

Labeled[SRGraphics[SREvolveList[#,"A",4]],SRRuleGraphic[#]]&[{"A""AAB"}]

Some rules give strings that are purely repetitive. Others give nested strings...... (What is required for the strings to be nested? Can the polynomial growers be nested?)

XXXX PEncode ....

Consider {"A","B",p[1,1],p[3,5],p[8,13],p[21,34],p[34,34]} creating network....

What about the vertical columns???

#### Dependence on Initial Conditions

Dependence on Initial Conditions

For neighbor-independent substitution systems, results for initial conditions containing several elements are always just pure concatenations of results for each element on its own. This means that the growth rates are always characterized by polynomials which are products of the polynomials obtained with initial conditions consisting of each element on its own.

#### Causal Networks

Causal Networks

Labeled[CNPlot[SREvolveCN[#,"A",6]],#]&/@{"A""AA","A""AAA"}

Layered causal network plots:

Labeled[LayeredCNPlot[SREvolveCN[#,"A",6]],#]&/@{"A""AA","A""AAA"}

Fibonacci rule:

Labeled[CNPlot[SREvolveCN[#,"A",7]],#]&/@{{"A""AB","B""A"}}

Labeled[LayeredCNPlot[SREvolveCN[#,"A",6]],#]&/@{{"A""AB","B""A"}}

Quadratic growth rule:

Labeled[CNPlot[SREvolveCN[#,"A",10]],#]&/@{{"A""AB","B""BC","C""C"}}

Labeled[LayeredCNPlot[SREvolveCN[#,"A",7]],#]&/@{{"A""AB","B""BC","C""C"}}

## Single-Rewrite Neighbor-Dependent Substitution Systems

Single-Rewrite Neighbor-Dependent Substitution Systems

### The Case ABX

The Case ABX

All the substitution systems in the previous section are "neighbor independent", in the sense that replacements made for a particular element are always independent of its neighbors. The simplest neighbor-dependent substitution systems involve replacement pairs of neighboring elements. Replacements for , for example, are causal invariant.

"AB"

The picture below shows an example of such a substitution system:

Here are a sequence of such systems, starting from the simplest possible initial condition:

Causal networks:

de Bruijn sequence initial conditions:

This is a summary of behaviors for rules of the form ABX, where X is a string of length 1 through 7:

BasicSRPanel[AllRHSs["AB",{0,7},2],{"AB"}]

Note that with AB as an initial condition, the transients remain short. But with longer initial conditions, there can be long transients, as in the case of ABBAA shown below.

#### Possible Growth Rates

Possible Growth Rates

With length 4 RHSs, seem to only get 1, 2, GoldenRatio growth rates. With longer RHSes, additional growth rates occur.

The maximum rates of growth for right-hand sides of successively greater length are:

{1,1,1,2,2,3}

In general, if the length of the right-hand side is n, the maximum growth rate is Quotient[n,2]. For even n, this is achieved by rules of the form ABABABAB... or ABBABABA...

It is possible to prove that any rule of the form ABX must lead to strings whose total size on successive steps satisfies a linear recurrence. The number of terms in the linear recurrence is bounded by the square of the length of the right-hand side of the rule, and the square of the length of the initial condition.

The maximum numbers of terms for all rules with right-hand sides of sizes 1 through 10 is:

{2,1,2,2,4,6,6,None,None,None}

{2,1,2,2,4,6,None,None}

[[[ This suggests a linear growth rate ]]]

#### ABBA

ABBA

This rule simply sorts all Bs in front of As. The function can be thought as "counting in unary".

Random initial condition:

Initial condition with As followed by Bs:

Causal network:

(In the cyclic case, this does more)

SRGraphics[CSREvolveList["AB""BA",StringJoin[Flatten[{Table["A",{20}],Table["B",{10}]}]],60]]

Causal network:

Causal step evolution vs. ordinary:

(A single causal step involves every element (which can be rewritten) actually being rewritten exactly once [ in the minimal way; i.e. it involves the minimal set of events necessary to have this happen].)

#### ABABAB

ABABAB

(The rule is essentially the same as AAA)

#### ABBAA

ABBAA

Labeled[SRGraphics[SREvolveList[{"AB""BAA"},"AABBBB",50,10^5],100],"AB""BAA"]

Causal network:

The final state will consist of a run Bs followed by a run of As. The number of Bs is conserved from the initial conditions. If the initial condition consists of a As followed by b Bs, then the final state will have a 2^b As.

[[ Can do the more general case; Todd knows how ]]

(The cyclic case)

#### ABBAAA

ABBAAA

Causal network:

Causal step evolution:

#### ABABBA

ABABBA

At step t, there are 2 Fibonacci[t] elements.

Drawing the final sequence by going down for an A, and up for a B gives:

In general, the string at step t is given by: s[1]="AB";s[2]="ABBA"; s[t_]:=s[t-1]<>StringDrop[s[t-2],1]<>"A". This form implies that the result must be nested.

Note that the actual operation of the rule does not make it at all obvious that its consequences would have this kind of global representation:

Causal network:

#### ABBBAA

ABBBAA

For ordinary strings, this rule does not lead to growth from an initial condition AB. (There is growth in this case for cyclic strings.)

SRGraphics[SREvolveList["AB""BBAA","ABAB",12],100]

ListLinePlot[Accumulate[Characters[Last[SREvolveList["AB""BBAA","ABAB",9]]]/.{"A"-1,"B"1}]]

LayeredCNPlot[SREvolveCN["AB""BBAA","ABAB",12]]

CNPlot[SREvolveCN["AB""BBAA","ABAB",12]]

CNPlot3D[SREvolveCN["AB""BBAA","ABAB",14]]

Causal step picture vs. ordinary:

[[[The situation is somewhat clearer for the cyclic case]]]

#### ABBBBAA

ABBBBAA

For ordinary strings, this rule does not lead to growth from an initial condition AB. (There is growth in this case for cyclic strings.)

SRGraphics[SREvolveList["AB""BBBAA","ABB",12],100]

Looking at the sequence after t steps, and corresponding for the fact that there are more Bs overall than As, one can represent the sequence by:

CNPlot[SREvolveCN["AB""BBBAA","ABB",17]]

CNPlot3D[SREvolveCN["AB""BBBAA","ABB",17]]

### The Case AABX

The Case AABX

The next possible case involves rewrites for blocks of 3 elements. AAB and its various reversals are all overlap-free, so that they can serve as left-hand sides for causal-invariant rewrites.

(With de Bruijn initial conditions:)

BasicSRPanel[AllRHSs["AAB",{1,8},2],{"AAB"}]

SRGraphicsChopped[SREvolveList[{"AAB""BAABABA"},"AAB",20],120]

CNPlot[SREvolveCN[{"AAB""BAABABA"},"AAB",10]]

LayeredCNPlot[SREvolveCN[{"AAB""BAABABA"},"AAB",10]]

SRGraphicsChopped[SREvolveList[{"AAB""BAAAABA"},"AAB",20],120]

BasicSRPanel[AllRHSs["AAB",{1,7},2],AllTuples[4]]

SRGraphics[SREvolveList[{"AAB""ABABBAA"},"AAAB",20],120]

LayeredCNPlot[SREvolveCN[{"AAB""ABABBAA"},"AAAB",15]]

CNPlot[SREvolveCN[{"AAB""ABABBAA"},"AAAB",17]]

SRGraphicsChopped[SREvolveList[{"AAB""ABAAABBA"},"AAAB",20],120]

What is the distribution of recurrence lengths??? As they get big, are there any that don't appear......

For a given growth class, is the behavior always the same?

#### AABBA

AABBA

Starting from a sequence of As followed by a sequence of Bs, the behavior is as follows (in the second picture, all initial sequences of As are removed):

Replacing AAB with X, and AB with A gives:

The following shows the result from runs of n As, followed by Bs, for n running from 1 to 50:

Note that in this picture, A's appear only in AB blocks. (Otherwise, there would be AABs, to which the rule could be applied further.) Replacing every such AB block by A yields immediately:

In effect, the rule is

LayeredCNPlot[SREvolveCN["AAB""BA",StringJoin[Flatten[{Table["A",{100}],Table["B",{20}]}]],100]]

CNPlot[SREvolveCN["AAB""BA",StringJoin[Flatten[{Table["A",{100}],Table["B",{20}]}]],100]]

CNPlot3D[SREvolveCN["AAB""BA",StringJoin[Flatten[{Table["A",{100}],Table["B",{20}]}]],100]]

Sequence of causal networks:

These networks are in effect successively nested: e.g. the networks for 4 and 5 are directly contained in the networks for 6 and 7, and so on.

### Two Colors—more complicated initial conditions

Two Colors—more complicated initial conditions

SRGraphicsChopped[SREvolveList[{"ABB""BA"},StringJoin[Join[Table["A",{20}],Table["B",{40}]]],30],120]

SRGraphicsChopped[SREvolveList[{"AAB""BA"},StringJoin[Join[Table["A",{40}],Table["B",{20}]]],30],120]

SRGraphicsChopped[SREvolveList[{"ABBB""BBA"},StringJoin[Join[Table["A",{20}],Table["B",{40}]]],30],120]

These cases give nontrivial behavior with complicated initial conditions; are there single rewrites that give nontrivial behavior forever?

Behavior of several rules of this type:

Labeled[SRGraphics[StringDrop[#,StringPosition[#,"B",1][[1,1]]-1]&/@SREvolveList[#,StringJoin[Flatten[{Table["A",{200}],Table["B",{20}]}]],100]],#]&/@{"AAB""BA","AAAB""BA","AAAAB""BA","AAAB""BAA","AAAAB""BAA","AAAAB""BAAA"}

The "functions being computed":

Mostly these get "computed" quite fast... just a few steps; these are the "halting times":

[A slightly different set of cases:]

(Time increases like the length of the input; see e.g. what happens with input 2^k+1 )

### AAABX

AAABX

#### AAABBAA

AAABBAA

The final states from initial conditions containing successively more As is:

(The following is perhaps somewhat useful...)

### The General Case of Single Substitutions

The General Case of Single Substitutions

[XXX] Many rules effectively reduce to rules like AB___. For the general case LR, the immediate condition is that L overlaps R on the left and on the right just once.

Other rules reduce to ACB___.

With left-hand side AAB, the first few right-hand sides that are not of these simplifying forms are:

{AAAA,ABAA,BAAA,BBAA,AAAAA,AABAA,ABAAA,ABBAA,BAAAA,BABAA,BBAAA,BBBAA}

With cyclic strings, the following are typical results:

SRGraphics[CSREvolveList[{"AAB""BBBAAA"},"AAB",20],100]

"AAB""BBBBAAA" has a recurrence of length 32:

{0,-1,0,1,0,-1,1,0,0,-1,1,0,0,-1,1,-1,1,0,0,0,0,0,-1,1,0,0,-1,1,0,0,0,1}

The sequence of recurrences for right-hand sides of the form BBBBAAA etc. is:

with lengths:

{2,2,1,2,2,19,32,3,3,12}

### More Colors

More Colors

Allowing more than two colors in a single rewrite does not appear to allow more complex behavior to occur. In fact, adding colors often seems to force the behavior to be simpler: in effect, the additional colors increase the rigidity of the system, by reducing the number of places where rules can apply.

Indeed, in cases like ABX, surprisingly few rules with new forms of growth appear when an additional color is allowed:

BasicSRPanel[AllRHSs["ABC",{1,6},3],{"ABC"}]

BasicSRPanel[AllRHSs["ABCD",{1,8},4],{"ABCD"}]

### Propagation of Changes

Propagation of Changes

SRGraphicsSquashed[MapThread[StringDifference,{SREvolveList[{"ABB""BBBAAA"},DeBruijnString[3,2],20],SREvolveList[{"ABB""BBBAAA"},StringFlip[DeBruijnString[3,2],5],20]}]]

With[{u=RandomString[50,2]},SRGraphicsSquashed[MapThread[StringDifference,{SREvolveList[{"ABB""BA"},u,20],SREvolveList[{"ABB""BA"},StringFlip[u,5],20]}]]]

With[{u=RandomString[50,2]},SRGraphicsSquashed[MapThread[StringDifference,{SREvolveList[{"AB""BA"},u,20],SREvolveList[{"AB""BA"},StringFlip[u,5],20]}]]]

[[[[ One really needs a dynamic-programming-based BLAST-like string difference computation system ]]]]

## Multiple Substitutions

Multiple Substitutions

BasicSRPanel[AllRHSs[{"AABAB","AABB"},{1,6}],AllTuples[4]]

BasicSRPanel[AllRHSs[{"AABAB","AABB"},{1,7}],{"AABB"}]

SRGraphicsChopped[SREvolveList[{"AABAB""BABAAA