Introduction
Introduction
What are String Substitution Systems?
What are String Substitution Systems?
A typical string substitution system takes in an initial string and a list of replacement rules, applying the replacement rules to the string. For example, an initial string AB and a replacement rule that changes every AB to BA will output BA. Substitution systems can take in any number of rules and apply them to the initial string. Stephen Wolfram has explored string substitutions extensively in the Wolfram Physics Project, exploring fields within string substitutions such as multiway systems and causal invariance, which I am now applying to cyclic strings so that there may be more applications of cyclic string substitutions in the Physics Project.
Multiway Systems
Multiway Systems
Multiway systems for string substitutions output all of the possible substitutions defined by the replacement rules for a string and applies the substitution for each of the string outputs for a certain number of steps that the user can specify. Multiway systems have been applied to regular string substitutions, and there exists a Multiway Systems function in the Wolfram Function Repository. Here is a simple visualization of a multiway system for 3 steps with an initial condition ABAB and a replacement rule in which AB is replaced with ABA.
In[]:=
ResourceFunction["MultiwaySystem"]["A""AB","ABAB",3,"StatesGraph"]
Out[]=
Cyclic Strings
Cyclic Strings
While patterns with multiway systems on regular string substitutions have been studied extensively, cyclic string substitution have hardly been explored. A cyclic string is one that can wrap around, meaning that all rotations of a string are equal to one another. This affects the substitution structure greatly and leads to many interesting patterns.
For example, with a replacement rule of BA being replaced by A and an initial condition of AAB, a regular string substitution would not result in a replacement. However, in the cyclic case, AAB is equivalent to ABA as they are rotations of one another, in which case the replacement rule can be applied, outputting AA.
In my project, I explore multiway systems for cyclic string substitutions and observations that stem from these systems.
Fundamental Functions
Fundamental Functions
Cyclic String Substitution Functions
Cyclic String Substitution Functions
Before I tackled multiway systems, I created a few functions that would allow for cyclic string substitution such that a single output will be based on the first instance that the replacement rule appears in the string. My function will allow for this single substitution to occur for a number of steps that the user defines. This system currently assumes string rotation to the right.
Apply the string substitution rule to the first occurrence in a cyclic string:
In[]:=
CyclicStringReplace[s_String, rule_Rule]:=If[StringContainsQ[s<>s, First@rule],If[StringContainsQ[s,First@rule], StringReplace[s,rule,1],CyclicStringReplace[StringRotateRight[s,1],rule]],s]
Allow substitution for as many steps as necessary:
In[]:=
CyclicSubSystem[s_String, rule_Rule, t_]:=NestList[CyclicStringReplace[#,rule]&,s,3]
Here is an example of a cyclic string substitution:
In[]:=
CyclicSubSystem["ABAB","BA""AB",3]
Out[]=
{ABAB,AABB,ABAB,AABB}
Cyclic String Substitution Multiway System Functions
Cyclic String Substitution Multiway System Functions
Unlike the simple cyclic string substitution system defined above, the multiway system generates all the possible substitutions and continues to branch out for any given number of steps if possible. For multiway systems, the first objective was to create functions that handle cyclic string substitution and produce lists of rules that contain the outputs for each step. For this to be possible, I needed to output all the possible substitutions for each rotation of a string for as many rules as inputted and delete any duplicates for each step. I then repeat this step for all the strings outputted in a previous step to create the multiway structure.
Output all the possible substitutions for a given string and rule:
In[]:=
singleReplace[s_String, rule_Rule]:= If[StringContainsQ[StringTake[s,-#],First@rule], {StringJoin[StringTake[s,StringLength[s]-#],StringReplace[StringTake[s,-#],rule,1]]},{}]&/@Range[StringLength[First@rule],StringLength[s]]
Implement cyclic string behavior for multiple rules and return a list of rules to map the inputted lists and the outputted lists:
In[]:=
cyclicReplaceString[strings_List, rules_List]:=DeleteDuplicates[DeleteCases[ Flatten[ Table[Flatten[ Table[j#&/@(Flatten[singleReplace[#, i]&/@(StringRotateLeft[j,#]&/@Prepend[Range[Length[Characters[j]-1]],0])]), {j,strings}]], {i, rules}]],x_x_]]
In[]:=
cyclicReplaceTestTwo[strings_List, rules_List]:= Which[!MemberQ[Head/@strings, Rule], cyclicReplaceString[strings, rules], MemberQ[Head/@strings, Rule],cyclicReplaceString[Last/@strings,rules]]
In[]:=
cyclicReplace[strings_List, rules_List, t_]:=Drop[NestList[First[Table[Flatten[Table[Print[j], {i,rules}]], {j, #}]]&,If[MemberQ[Head/@strings,Rule],Last/@strings, strings],t],1];
The final function allows for multiple iterations, effectively creating multiway systems for cyclic string substitutions with as many rules as necessary. The MultiwayList function takes in an initial condition, a list of rules, and a certain number of iterations and returns a list of lists.
Simple example of a multiway:
MultiwayList[strings_List,rules_List,t_]:=Drop[NestList[cyclicReplaceTestTwo[#,rules]&,strings,t],1]
In[]:=
MultiwayList[{"ABAB"},{"AB""BAA"},2]
Out[]=
{{ABABABBAA,ABABBAAAB,ABABBBAAA},{ABBAABAABAA,ABBAAAABAAB,ABBAAABAABA,BAAABBAABAA,BAAABAABAAB,BAAABABAABA,BBAAABAABAA,BBAAAAABAAB,BBAAAABAABA}}
Multiway System Visualization
Multiway System Visualization
I aimed to create a visualization system that works similarly to the Multiway System States Graph that is currently available in the Wolfram Function Repository.
Returns a multiway graph that utilizes the built-in LayeredGraphPlot function:
In[]:=
MultiwayGraph[strings_List, rules_List, t_]:= LayeredGraphPlot[Flatten[MultiwayList[strings,rules, t]], VertexLabelingTrue, VertexLabelStyleDirective[Black,12], PlotTheme->"WarmColor"]
Generate a multiway system graph for an initial condition of AB and two replacement rules:
In[]:=
MultiwayGraph[{"BA"},{"A""AB"},5]
Out[]=
Cyclic vs. Non-cyclic Substitutions
Cyclic vs. Non-cyclic Substitutions
Compared to their non-cyclic counterparts, the cyclic string case becomes much more complicated as evidenced by the visualization of the multiway system. A few examples with common initial conditions and rules highlight this difference. I utilized the Multiway System resource function to show the multiway system for the non-cyclic cases.
Out[]=
Observations
Observations
Condensed Multiway Systems
Condensed Multiway Systems
I quickly realized that for any given step, many of the outputs were rotations of one another. For example, a certain step that outputs ABB, BAB, and BBA is essentially returning all the rotations of the string ABB. Therefore, I wanted to see how many unique strings were created for a multiway system since it may reveal different patterns and affect the causal invariance of any given rule.
In order to condense each multiway system, I compared each string to all the possible rotations of the strings that were outputted before it in the same step, and only outputted those that were not already in the list of rotations. The following functions are modified versions of the code used for non-condensed cyclic string substitutions. the visualization function, MultiwayGraphCondense has the same functionality as the MultiwayGraph function and simply calls the MultiwayListCondense function instead of the MultiwayList function. This code currently holds for single replacement rule systems.
Visualize the condensed multiway graph:
Output the condensed multiway list:
Output unique strings (strings that are not rotations of one another) for a list of rules:
Here are a few examples to compare how much simpler the condensed multiway system is in relation to its non - condensed format.
Rules that Maintain the Same Length
Rules that Maintain the Same Length
After testing various rules, I noticed that the "AB" to "BA" replacement rule causes various steps to loop back to a previous step without branching out further, effectively creating a cyclic graph for cyclic substitutions. For example, with initial condition "ABA" and the rule "AB"mapped to "BA", the first few steps reveal the looping structure.
This behavior occurs for a variety of combinations of rules, and I hope to fully explore the bounds for which this looping quality can be observed.
Here is a more complicated example of a multiway system that loops in various regions:
Here is a more complicated example of a multiway system that loops in various regions:
Causal Invariance
Causal Invariance
Causal invariance is a property of some multiway substitutions systems which states that regardless of the order that rules are applied, the same states will occur. Currently, there exists a function in the Wolfram Function Repository that checks for causal invariance; however, it is only suited for non-cyclic substitution systems, cellular automata, and Wolfram models. I hope to adapt the function to apply to cyclic multiway systems in the near future, but I began to explore the difference in the graphs for cyclic and non-cyclic substitutions, using the causal invariance resource function for the non-cyclic case. Here is a graph that displays common rules, the cyclic and non-cyclic cases, and whether the cases are causally invariant.
Summary
Summary
To sum up the work done so far on cyclic multiway systems and to observe more patterns between the regular cyclic, condensed cyclic, and the non-cyclic multiway substitution systems, here is a chart that displays common rules and the respective outputs for each feature for initial condition AAB. Many of the rules that are used are sourced from the resource function Enumerate Substitution System Rules.
For many cases, the condensed multiway cyclic case is very similar to the non-cyclic multiway case, as there is only one path. With multiple rules, the pattern may change drastically.
Future
Future
There are a plethora of areas to explore in this field of cyclic string substitutions. First, I would like to generalize my functions into a refined format that will have more options for users to choose from. The condensed version of my multiway list only allows for one rule to be inputted, so I would like to allow as many rules as possible and explore more patterns that may appear. I would like to fully understand which conditions and rules display the looping quality that was seen for the rule in which AB was mapped to BA . Finally, testing for causal invariance in the cyclic case for string substitutions for different cases would be very intriguing. I hope to expand upon this research greatly as it is a newly developing field.
Acknowledgments
Acknowledgments
I would like to thank Wolfram Summer Camp for giving me this opportunity and my mentor Jesse Dohmann for guiding me throughout this process.
Keywords
Keywords
◼
Strings
◼
Substitution Systems
◼
Cyclic Systems
◼
Graphs
◼
Fundamental Physics