Multiway circular-string rewrite systems​
​by Joseph Crowley

Searching for Oscillating Systems

String Rewriting Systems are an important toy model for demonstrating the behavior of rules applied to directed hypergraphs. To search for systems that oscillate, two genera of rules were explored: sorting and “growth-decay” rules. These types of rules can be classified by the way they transform the initial state into the final state. A sorting rule will take an input, say “ABBABAA”, and rewrite it to “AAAABBB” after some number of iterations.
Sort the string “ABBABAA” in alphabetical order using string rewriting rules {“BA” “AB”,”ABA”  “AAB”}
In[]:=
ResourceFunction["MultiwaySystem"][{"BA""AB","ABA""AAB"},{"ABBABAA"},8,"StatesGraph"]
Out[]=
Systems that increase in size until a maximum, then decrease in size until a minimum, would be intuitive candidates for an oscillating system. Such systems are shown below with two and three such “growth-decay” rules.
Display the StatesGraph of the String Rewrite System with two "growth rules" and two "decay rules" with initial condition "A" after 6 evolution steps.
In[]:=
ResourceFunction["MultiwaySystem"][{"A""BB","B""CC","CC""D","DD""E","E""A"},{"A"},6,"StatesGraph"]
Out[]=
Display the StatesGraph of the String Rewrite System with three “growth rules” and three “decay rules” with initial condition “A” after 6 evolution steps
LayeredGraphPlot@ResourceFunction["MultiwaySystem"][{"A""BB","B""CC","C""DD","DD""E","EE""F","FF""G"},{"A"},14,"StatesGraph",ImageSizeFull]
Out[]=

A feature of String Rewriting Systems that Prevents Symmetric Growth and Decay

There are features in each of the graphs above where the decay steps cannot be completed, because each of the decay rules is of the form “CC”-> “D”, and it does not allow for replacements on states that look like “CDC”. Even when the initial condition is varied, the directed cycles are interrupted by a stagnant state in which the rule may apply at the boundary. This prevents any sort of “time reversal symmetry”, a property of oscillating systems where if all of the rules were reversed, the graph would be unchanged aside from direction.
To deal with a feature like this, it is useful to reduce the spatial structure of the string. If the absolute positions of characters were able to be replaced by relative positions, this system could be more symmetric.

Circular-String Rewriting System

A circular string can be thought of as a string which has the beginning and end glued together. This gives the string orientation, but the characters have no absolute position. When this is the case, the sorting system from earlier reduces to fewer states, and alternates between them.
Compare the graphs of alphabetical sorting rules for a SRS and a circular SRS
In[]:=
GraphicsGrid[{{MultiwaySystem[{"BA""AB"},{"BBBAAA"},9,"StatesGraph"],CircularStringMultiwaySystem[{"BA""AB"},{"BBBAAA"},9,"StatesGraph","IncludeEventInstances"True]}},ImageSizeLarge]
Out[]=
As for growth-decay rules, the figure below demonstrates how features of the form “CDC” are now part of the directed cycle. This remains true, independent of where the initial condition is in the cycle. Note that this was not the case with SRS, the figure above with the initial condition “CDC” selected shows that no graph is generated. In the circular string system “CDC” is an equivalent state to “DCC”, and the rule “CC””D” can be applied.
Display the StatesGraph of the Circular SRS with two "growth rules" and two "decay rules" with various initial conditions within the directed cycle.
In[]:=
Table[LayeredGraphPlot@CircularStringMultiwaySystem[{"A""BB","B""CC","CC""D","DD""E","E""A"},{init},12,"StatesGraph"],{init,{"A","BB","BCC","CCB","BD","CCCC","DB","CCD","CDC","DCC","DD","E"}}]
Out[]=

,
,
,
,
,
,
,
,
,
,
,


Visualizing the flux of causal edges at each evolution step

By counting the multiplicity of edges leading into each state, we can determine whether the system is growing, or shrinking. Below, the edge multiplicities are plotted for sorting SRS, growth-decay SRS, and the circular versions of each of the models
Plot the flux of causal edges for each iteration of the SRS with rule {“BA””AB”} and initial condition {“BBBBBBBBAAAAAAA”} for 100 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux@MultiwaySystem[{"BA""AB"},{"BBBBBBBBAAAAAAA"},100,"StatesGraph"]
Out[]=
10
20
30
40
50
200
400
600
800
1000
1200
Plot the flux of causal edges for each iteration of the circular SRS with rule {"BA" -> "AB"} and initial condition {"BBBBBBBBAAAAAAA"} for 100 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux@CircularStringMultiwaySystem[{"BA""AB"},{"BBBBBBBBAAAAAAA"},22,"StatesGraph"]
Out[]=
5
10
15
20
50
100
150
Plot the flux of causal edges for each iteration of the SRS with rules {“A” “BB”, “B” “CC”,”CC””D”, “DD” “E”, “E” “A”} and initial condition {“A"} for 8 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux[MultiwaySystem[{"A""BB","B""CC","CC""D","DD""E","E""A"},{"A"},8,"StatesGraph"],"A"]
Out[]=
2
4
6
8
1
2
3
4
5
Plot the flux of causal edges for each iteration of the circular SRS with rules {“A” “BB”, “B” “CC”,”CC””D”, “DD” “E”, “E” “A”} and initial condition {“A"} for 8 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux[CircularStringMultiwaySystem[{"A""BB","B""CC","CC""D","DD""E","E""A"},{"A"},8,"StatesGraph"],"A"]
Out[]=
2
4
6
8
0.5
1.0
1.5
2.0
Plot the flux of causal edges for each iteration of the SRS with rules {“A” “BB”, “B” “CC”, “C””DD”,”DD” “E”, “EE” “F”, “FF””G”} and initial condition {“A”} for 15 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux[MultiwaySystem[{"A""BB","B""CC","C""DD","DD""E","EE""F","FF""G"},{"A"},15,"StatesGraph"],"A"]
Out[]=
2
4
6
8
10
12
14
20
40
60
80
Plot the flux of causal edges for each iteration of the circular SRS with rules {“A” “BB”, “B” “CC”, “C””DD”,”DD” “E”, “EE” “F”, “FF””G”} and initial condition {“A”} for 15 evolution steps
In[]:=
ListLinePlot@MeasureMultiwayFlux[CircularStringMultiwaySystem[{"A""BB","B""CC","C""DD","DD""E","EE""F","FF""G"},{"A"},15,"StatesGraph"],"A"]
Out[]=
2
4
6
8
10
12
14
5
10
15
20

Future Work

This work introduces Circular-String Rewriting Systems, which are an intuitive generalization of SRS with less spatial structure. This work lends itself to an exploration of energy as a flux of causal edges through a spacelike hypersurface. I am particularly interested in oscillatory behaviour in a finitely bounded graph, because such a simple structure could aid in forming intuitions about larger systems. An interesting way to seek out an oscillating system is to measure the flux of causal edges through each application of the rules.