Multiway graphs are a way of representing causal events whose evolutions are determined by a set of rules. The aim of this project was to use string substitution systems to find and measure so-called "holes" in these graphs, which indicate the existence of two distinct approaches to reach a final state from some initial state. Using a formalized definition of holes in multiway graphs, I created algorithms that detect the appearance of a hole, measure hole size, and generate small holes between a given initial and final state.
Introduction and Definitions
Introduction and Definitions
Defining a Hole
Let's start with a more formal definition of holes:
Definition: Consider a graph with initial state X, final state Y, and replacement rule set R. There is a hole between X and Y if and only if a graph can be partitioned into two subgraphs each with root X such that the subgraphs intersect at only X and Y.
Definition: Consider a graph with initial state X, final state Y, and replacement rule set R. There is a hole between X and Y if and only if a graph can be partitioned into two subgraphs each with root X such that the subgraphs intersect at only X and Y.
This definition is basically a long-winded way of saying that a hole indicates the existence of two distinct approaches to get from an initial state to a final state. Visually, a hole might look something like this:
In 3 Dimensions
Hole Size
Hole Size
To further describe holes, we need a way of measuring the size of a hole.
Definition: The size of a hole is the longest path length from the initial to final state. This definition is relatively arbitrary and there are a multitude of ways one could choose to define hole size. I chose this one. For the example above, there is a hole between A and BBAAABAAABBAAAB of size 5.
Definition: The size of a hole is the longest path length from the initial to final state. This definition is relatively arbitrary and there are a multitude of ways one could choose to define hole size. I chose this one. For the example above, there is a hole between A and BBAAABAAABBAAAB of size 5.
Helper Functions
Helper Functions
Throughout my exploration of holes in string substitution systems, I made many functions which made studying graphs much easier.
findReplacementRules goes through all possible substrings of the final string and checks if substituting a part of the initial string for a given substring gives the final string. By doing this, the function finds all possible rules that transform an initial string into a final string.
In[]:=
findReplacementRules[start_,final_]:=Module[{rules={}},Table[Table[If[j>=i&&StringReplacePart[start,n,{i,j}]==final,rules=Append[rules,StringTake[start,{i,j}]->n]],{n,subStrings[final]}],{i,StringLength[start]},{j,StringLength[start]}];Flatten[rules];rules/.Null->Nothing;DeleteDuplicates[rules]]
paths generates all possible paths from an initial state to a final state given a set of rules. Note that so long as the depth parameter is sufficiently large, we can input any depth parameter. This fact is true for a lot of functions here.
In[]:=
paths[rule_,initial_,final_,depth_]:=FindPath[ResourceFunction["MultiwaySystem"][rule,initial,depth,"StatesGraph"],initial,final,Infinity,All]
setOfPaths Uses the paths function from before to generate each set of all the paths to every possible final state at a certain depth.
In[]:=
setOfPaths[rule_,initial_,depth_]:= paths[rule,initial,#,depth]&/@Last@ResourceFunction["MultiwaySystem"][rule,initial,depth,"AllStatesList"]
setOfPathsGraphUsing the setOfPaths function above, setOfPathsGraph graphs all paths for each possible final state at a certain depth.
In[]:=
setOfPathsGraph[rule_,initial_,depth_] :=graphPaths[rule,initial,#,depth]&/@Last@ResourceFunction["MultiwaySystem"][rule,initial,depth,"AllStatesList"]
graphPaths graphs all paths from an initial state to a final state(The function is overloaded for an argument as a sequence and a list).
In[]:=
graphPaths[{rule_,initial_,final_,depth_}]:=Module[{a},a=FindPath[ResourceFunction["MultiwaySystem"][rule,initial,depth,"StatesGraph"],initial,final,Infinity,All];Subgraph[ResourceFunction["MultiwaySystem"][rule,initial,depth,"StatesGraph"],a]]
In[]:=
graphPaths[rule_,initial_,final_,depth_]:=Module[{a},a=FindPath[ResourceFunction["MultiwaySystem"][rule,initial,depth,"StatesGraph"],initial,final,Infinity,All];Subgraph[ResourceFunction["MultiwaySystem"][rule,initial,depth,"StatesGraph"],a]]
subStrings gives all substrings of a given string.
In[]:=
subStrings[str_]:=Module[{substrings={}},Table[If[j>=i,substrings =Append[substrings,StringTake[str,{i,j}]]],{i,StringLength[str]},{j,StringLength[str]}];substrings]
possibleNodes gives all possible nodes of a graph given its initial and final states for increasing "complexity" rules.
In[]:=
possibleNodes[initial_,final_]:=Module[{possibleNodes={}},possibleNodes=possibleNodes[possibleNodes,{final}];Table[possibleNodes=Append[possibleNodes,binaryStringsN[i]],{i,StringLength[final]-1,StringLength[initial]+1,-1}];possibleNodes=Reverse@Append[possibleNodes,{initial}]]
binaryStringsN generates all binary AB strings of length n. Credit goes to Mr.Wizard on Mathematica Stack Exchange for the generation of lists of binary numbers code.
In[]:=
binaryStringsN[n_] := Module[{strings},strings={Array[List,ConstantArray[2,n],0,##&]}/. 0 ->"A" /. 1->"B";strings=StringJoin/@strings]
binaryStrings generates all binary AB strings up to length n(inclusive). Credit again to Mr.Wizard for the generation of binary numbers code
In[]:=
binaryStrings[n_]:= Module[{strings},strings={Array[List,ConstantArray[2,n],0,##&]}/. 0 ->"A" /. 1->"B";strings=StringJoin/@strings;strings=Flatten[Append[strings,binaryStrings[n-1]]]];binaryStrings[1]={"A","B"}
Testing for and Measuring Holes
Testing for and Measuring Holes
A natural question to ask is given an initial state, final state, and rule, can we check whether or not there is a hole between the initial and final states. To approach the creation of a function that does this task, we refer back to the definition of a hole. The definition requires us to find two non-intersecting(except at the initial and final states) subgraphs by partitioning the original graph. It's sufficient to search through all possible partitions of the graph into two subgraphs and check whether the nodes of each subgraph are distinct(save for the initial and final states). This is exactly what the (overloaded)holeQ function does to determine whether a hole exists or not.
In[]:=
holeQ[rule_,initial_,final_,depth_]:=Module[{holeExists=False,g = graphPaths[rule,initial,final,depth],partitions},partitions=ResourceFunction["KSetPartitions"][FindPath[g,initial,final,Infinity,All],2];Table[If[IntersectingQ[DeleteCases[DeleteCases[DeleteDuplicates[Flatten[i[[1]]]],initial],final],DeleteDuplicates[Flatten[i[[2]]]]]==False,holeExists = True],{i,partitions}];holeExists]
In[]:=
holeQ[{rule_,initial_,final_,depth_}]:=Module[{holeExists=False,g = graphPaths[rule,initial,final,depth],partitions},partitions=ResourceFunction["KSetPartitions"][FindPath[g,initial,final,Infinity,All],2];Table[If[IntersectingQ[DeleteCases[DeleteCases[DeleteDuplicates[Flatten[i[[1]]]],initial],final],DeleteDuplicates[Flatten[i[[2]]]]]==False,holeExists = True],{i,partitions}];holeExists]
Given a rule, initial state, and all possible final states at a certain depth, using our holeQ function, selectHoles selects all the graphs which contain holes given a rule, initial state, and all possible final states that can be generated at a certain depth.
In[]:=
selectHoles[rule_,initial_,depth_]:=Select[{rule,initial,#,depth}&/@Last@ResourceFunction["MultiwaySystem"][rule,initial,depth,"AllStatesList"],holeQ]
In[]:=
selectHoles[{"A"->"AA","A"->"BAB"},"A",5]
selectHolesGraph visually graphs the aforementioned graphs
We are also now ready to quantitatively tackle the notion of hole size.
holeSize first checks if there is a hole between the initial and final states. If there is a hole, it measures the size of the hole by looking at the longest path length from the initial to final state
As expected, the size of the hole is 5, the length of the path from the initial to final state.
A Note about Multiple Holes in the Same Graph
holeSize and holeQ still work nicely if there are multiple holes between the initial and final state in the same graph. holeQ will still return True and holeSize will end up measuring the size of the largest hole. However, a major shortcoming of these functions is that they can't distinguish between the different holes.
Generating Small Holes Between an Initial and Final State
Generating Small Holes Between an Initial and Final State
For "complexity" increasing(Number of letters increases after each step) rules, we can use our previous functions to generate holes between an initial and final state. Let's start by defining a helpful new function:
generateRules allows us to generate all possible rules from an initial state to a final state
For example, we can generate all rules that take us from "A" to "ABA"
Now it's as simple as going through each possible replacement rule set and using our all-important holeQ function to determine whether a hole exists. If it does, we'll select it. Let's encapsulate this in a function.
findHoles goes through all possible rules and checks if a hole exists for that rule. In this way, it can find holes given an initial state and final state
Note that these functions work best for smaller strings and lower depths, meaning that they're mostly capable of generating small holes.
Consider a very simple system with initial state AA and final state ABAB.
Graphing each of these rule sets (see below), we see that findHoles has generated all holes with initial state A and final state ABAB. The findHole function works primarily for holes of this magnitude or slightly larger due to it being computationally expensive. However, the findHoles function has the useful feature of find all possible holes that could occur.
Miscellaneous Results
Miscellaneous Results
Pattern for Generating Holes
While studying these graphs and searching for holes, I found some extra things which I thought were interesting.
Reasoning: This result at first seems pretty arbitrary and oddly specific and I got the inspiration for this claim from an introductory page on holes in proof space. A (slightly vague) intuitive way of thinking about the high frequency of holes with these graphs is that when we make our first branch pair, we are forced into two distinct approaches: one is the "adding A's to the middle approach" and the other is "adding A's to the ends approach". For most final states these two approaches do intersect but I suspect that due to the fact that there is a way to sort of distinguish between the two methods, there end up being a lot of final states which lead to holes.
Faster Test for Disproving Holes
Earlier in my project, I incorrectly characterized the existence of a hole between initial and final states as being equivalent to the existence of at least one pair of paths from the initial state to the final state that contains no intersection (besides the initial and final states). This definition is slightly off, as the existence of the aforementioned pair of paths doesn't imply the existence of a hole. Luckily, the existence of a hole does imply the existence of such a pair of paths, making the pair of subgraphs a necessary condition for the existence of a hole. Therefore, we can make a test that rules out any system which doesn't have the path pair.
disproveHoles returns false if a hole necessarily doesn't exist due to not satisfying the pair of subgraphs condition and gives "Inconclusive" otherwise
Let's look at some examples using disproveHoles.
From the output of disproveHoles we should expect to not find a hole between "A" and "AAAABAA" in this graph.
Indeed, a hole doesn't exist. However if we look at a different rule set, the test spits out an inconclusive result
Since the result of the test is inconclusive, we have no way of knowing whether a hole exists or not (at least from this test). In this case, it does (It has 2!).
Conclusions and Future Work
Conclusions and Future Work
Overall, my work on this project has helped in exploring a part of multiway graphs that hasn't really been explored, specifically the identification and measurement of holes. In the future, I hope to improve a lot of these functions and make them more efficient, allowing them to deal with more complicated systems. I would especially like for findHoles and generateRules to be applicable to longer and more complicated strings. I also want to try and consider more types of systems, like systems with three letters or maybe even non-string systems.
References
References
All binary sequences with length N. Mathematica Stack Exchange. (1961, July 1). https://mathematica.stackexchange.com/questions/71729/all-binary-sequences-with-length-n
The topology of proof space. The Topology of Proof Space. (n.d.). https://www.wolframscience.com/metamathematics/the-topology-of-proof-space/
Wolfram Physics Project. The Updating Process for String Substitution Systems: Wolfram Physics Project Technical Background. (n.d.). https://www.wolframphysics.org/technical-introduction/the-updating-process-for-string-substitution-systems/
Acknowledgements
Acknowledgements
Huge thanks to AnneMarie Torresen, my mentor for her continual support and Jonathan Gorard for clarifying discussion.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Finding holes in multiway systems
by Ankit Muppala
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2964060
by Ankit Muppala
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2964060