A substitution system is a map which uses a set of rules to transform elements of a sequence into a new sequence using a set of rules which "translate" from the original sequence to its transformation. A multiway system is a kind of substitution system in which multiple states are permitted at any stage . The optimal move for a multiway system can be defined as a singular change to the end state of a rule in a multiway system that leads to the maximal increase in the number of states . In this paper, various properties of the optimal move problem are explored . It is shown that the optimal move depends upon the number of steps of a multiway system, and an algorithm for calculating the optimal move is also provided. Furthermore, multiway systems are classed into categories depending upon their optimal move . Additionally, we discover a surprisingly useful functionality of the Optimal Move — which speeds up the traditional KnuthBendixCompletion Algorithm by more than 1000x in some cases.
Introduction to Multiway Systems
Introduction to Multiway Systems
Multiway Systems are defined as substitution systems in which multiple states are permitted at any stage. In the Wolfram Language, we can implement using Resource Function in Wolfram Language
In[]:=
ResourceFunction["MultiwaySystem"][{"A"->"AA","B"->"AB"},"ABA",5,"StatesGraph"]
Out[]=
In[]:=
ResourceFunction["MultiwaySystem"][{"AA"->"","BA"->"ABB","BB"->"A"},"BBA",5,"StatesGraph"]
Out[]=
Introduction to Causal Invariance and Confluency
Introduction to Causal Invariance and Confluency
In order to understand the main hypothesis of this project, we need to understand what confluency and causal invariance are. These may sound like scary terms, (and they probably are), but getting an intuitive grasp on them isn’t very difficult.
Causal Invariance: A property of multiway graphs whereby all possible paths yield the isomorphic causal graphs. When causal invariance exists, every branch in the multiway system must eventually merge. Causal invariance is a core property associated with relativistic invariance, quantum objectivity, etc. In a terminating system, causal invariance implies that whatever path is taken, the “answer” will always be the same.
We now demonstrate the property of Causal Invariance:
In[]:=
Manipulate[ResourceFunction["MultiwaySystem"][{"AA"->"ABA","AAA"->"B"},"AABAA",i,"StatesGraph"],{i,1,10,1}]
Out[]=
In[]:=
ResourceFunction["MultiwaySystem"][{"AA"->"ABA","AAA"->"B"},"AABAA",3,"CausalGraphInstances"]
Out[]=
Therefore, the system is Causal Invariant! We can now verify this by using the CausalInvariantQ function in the Wolfram Language.
In[]:=
Manipulate[ResourceFunction["MultiwaySystem"][{"AA"->"ABA","AAA"->"B"},"AABAA",i,"CausalInvariantQ"],{i,2,10,1}]
Out[]=
Confluence is a property of rewriting systems, describing which terms in such a system can be rewritten in more than one way, to yield the same result. Here is an example of a confluent substitution system.
Introduction to the Optimal Move
Introduction to the Optimal Move
The optimal move can be defined as a singular change to the end state of a rule in a multiway system that leads to the maximal change in the number of vertices. Essentially, it is a singular change in the right hand side of a substitution system. To visualize "moves", we show the following multiway system
The main hypothesis of the research is that the substitution system that takes the longest to attain confluency is also the substitution system grows the fastest.
In[]:=
rule={"S"->"","S"->"B","S"->"AAB"};Symbols={"S","A","B"};
The list of possible moves for rule would be
In[]:=
Column[ListOfPossibleMoves[rule,"S"]]
Out[]=
{SS,SB,SAAB} |
{S,SSB,SAAB} |
{S,SBS,SAAB} |
{S,SB,SSAAB} |
{S,SB,SASAB} |
{S,SB,SAASB} |
{S,SB,SAABS} |
As we can see, it is simply an insertion of one of the symbols used in the rule to the right hand side of the substitution system, one at a time.
Now that we have coined what constitutes a "move", we can try and explore the "optimal move" for a given substitution system. We can define the optimal move in following two ways:
1. Defining the optimal move in terms of vertices, i.e, the move which leads to maximal number of vertices
2. Defining the optimal move in terms of edges , i.e, the move which leads to the maximal number of edges
1. Defining the optimal move in terms of vertices, i.e, the move which leads to maximal number of vertices
2. Defining the optimal move in terms of edges , i.e, the move which leads to the maximal number of edges
In this paper, we define the optimal move to be one which leads to the maximal number of vertices. A further exploration on optimal moves which lead to maximal number of edges shall be done separately.
Optimal Move for Vertices
Optimal Move for Vertices
In[]:=
Helper Functions
Helper Functions
In[]:=
ReplaceStr["",insert_String]:=insert
In[]:=
ReplaceStr[base_String,insert_String]:=Table[StringInsert[base,insert,i],{i,1,1+StringLength@base}]
In[]:=
ReplaceStr[base_String,inserts:{__String}]:=ReplaceStr[base,#]&/@inserts
In[]:=
ReplaceStr[bases:{__String},inserts:{__String}]:=Rule[#,Flatten[ReplaceStr[#,inserts]]]&/@bases
In[]:=
ReplaceStr["bSSb","SA"](*SanityCheck!*)
Out[]=
{SAbSSb,bSASSb,bSSASb,bSSSAb,bSSbSA}
Now, we move onto defining the main functions
Main Functions
Main Functions
Finds the Optimal Move in terms of Vertex Count
In[]:=
ListOfPossibleMoves[rules_,startSymbol_]:=Module[{listMWS,combinations,vertexCount,maxPosition,listRules},combinations=DeleteDuplicates[Flatten[Tuples/@Replace[Table[Values[rules]/.x,{x,ReplaceStr[Values[rules],Keys[rules]]}],str_String:>{str},{2}],1]];listRules=Table[Thread[Rule[Keys[rules]//Flatten,i]],{i,combinations}]]
Introduction to Knuth Bendix Completion Algorithm
Introduction to Knuth Bendix Completion Algorithm
“Are these two real numbers (or functions, or grammars, or mathematical statements) equivalent?”
Before we introduce the readers to the Knuth Bendix Completion Algorithm, we must introduce the Word Problem—which is a very famous problem in computational mathematics. The Word Problem in mathematics is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A deep result of computational mathematics is that the Word Problem is undecidable in many cases.
In general, determining whether a substitution system is confluent or not is also undecidable! The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. It effectively solves the Word Problem in mathematics, which is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities.
Main Hypothesis + Longest Canonical Function
Main Hypothesis + Longest Canonical Function
Now, we also define LongestCanonical, which is a function that finds the substitution system that takes the longest to attain confluency (in terms of length) using the Knuth Bendix Completion Algorithm. The main hypothesis of the paper is that the substitution system that takes the longest to attain confluency is also the substitution system grows the fastest.
The following function checks if substitution system(s) yielded FindOptimalMoves and LongestCanonical are the same.
Checking the Optimal Moves for Different Substitution Systems
Checking the Optimal Moves for Different Substitution Systems
◼
Type 1: Regular Grammar
However, we also notice the fact that
But we have,
The reason for this inequivalence is simple: {SaSS,SbA,A,AcA} grows faster than {“S””aS”,”S””bAS”,”A”””,”A””cA”} , but the number of vertices produced by their MultiwaySystem is the same after 3 iterations, and {SaSS,SbA,A,AcA} overtakes {“S””aS”,”S””bAS”,”A”””,”A””cA”} only after the third iteration.
We now begin by looking at other regular grammars, and checking equivalency between LongestCanonical function and the FindOptimalMoves function
We now begin by looking at other regular grammars, and checking equivalency between LongestCanonical function and the FindOptimalMoves function
◼
Type 2: Context Free Grammars
◼
Type 3: Context Sensitive Grammars
◼
Type 4: Recursively Enumerable
Defining Pessimal Move
Defining Pessimal Move
In this section, we begin by defining the pessimal move
However, it seems as if the FindPessimalMove function does not coincide with the substitution system that takes the shortest time to attain confluency.
Plotting Growth Rate of Multiway Systems
Plotting Growth Rate of Multiway Systems
In this section we look at Multiway Systems with various growth rates. The growth rates of multiway systems have been studied extensively by Yorick Zeschke, who determined that finding the growth rate of a multiway system in general is undecidable. Furthermore, he also divided the growth rates of multiway systems into various classes such as polynomial, exponential, super-exponential and intermediate growth (faster than polynomial, slower than exponential)
The hypothesis that I currently have is that the optimal move "boosts" the growth rate of a multiway system from polynomial and intermediate growth rate to exponential growth rate, and from exponential growth rate to super-exponential growth rate.
The hypothesis that I currently have is that the optimal move "boosts" the growth rate of a multiway system from polynomial and intermediate growth rate to exponential growth rate, and from exponential growth rate to super-exponential growth rate.
This indicates that the graph has a constant growth rate. Indeed, we can verify this by plotting the multiway system.
We now plot both of them on the same graph
The growth rate for this substitution system seems to be of the form 3*2^n
A Fast Implementation of the Multiway System
A Fast Implementation of the Multiway System
Checking Equivalency for Multiway Systems of Different Signatures
Checking Equivalency for Multiway Systems of Different Signatures
We now enumerate all the rules of the signature {2->1, 2->3}, starting with 2 letters.
And we check their equivalency
We see that the cases where the equivalency breaks down when the rules are Causal Invariant. We can now modify the equivalency condition.
Therefore, we see that this hypothesis holds well for the signature {2->1, 3->2}. We now check for other signatures
And the problem here is that the Multiway System stagnates after some iterations, and therefore it poses a problem for the FindOptimalMoves function. We can now modify our hypothesis : The OptimalMove function is equivalent to the LongestCanonical function if the substitution system is
a) Not confluent
b) Not terminating
a) Not confluent
b) Not terminating
Generalizing
Generalizing
In this section, we aim to generalize the properties that we have observed so far. We now propose the question: Given a set of different substitution systems, which one takes the longest time to attain confluency?
Thus we can see that our hypothesis holds for certain small values. It is now time to test it on different signatures, and to optimize the functions!
{2->1, 2->3} with 2 characters
{2->1, 2->3} with 2 characters
{2->1, 2->3} with 3 characters
{2->1, 2->3} with 3 characters
{2->3, 2->3} with 3 characters
{2->3, 2->3} with 3 characters
Therefore, we have a good heuristic for determining the substitution system which grows the fastest out of a list of substitution systems!
Comparing with Knuth Bendix Completion Algorithm
Comparing with Knuth Bendix Completion Algorithm
This preliminary test tells us that the KnuthBendixCompletionAlgorithm is 100x slower than the Optimal Move heuristic
More than 108530 rules checked and the hypothesis still holds!
In particular, we note that the Optimal Moves Heuristic takes 3 seconds to calculate the 3rd iteration of the multiway system that takes the longest time to attain confluency, whereas the Knuth Bendix Completion Algorithm takes more 40 minutes!
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
On the optimal move problem for multiway systems
by Navvye Anand
Wolfram Community, STAFF PICKS, April 25, 2024
https://community.wolfram.com/groups/-/m/t/3164383
by Navvye Anand
Wolfram Community, STAFF PICKS, April 25, 2024
https://community.wolfram.com/groups/-/m/t/3164383