Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BranchPairs

Source Notebook

Compute branch pairs for a given multiway system

Contributed by: Jonathan Gorard

ResourceFunction["BranchPairs"][rules,init,n]

generates a list of branch pairs for the multiway system with the specified rules after n steps, starting with initial conditions init.

ResourceFunction["BranchPairs"][rules→sel,init,n]

uses the function sel to select which of the events obtained at each step to include in the evolution.

Details and Options

Rules can be specified in the following ways:
{"lhs1"->"rhs1",…}string substitution system
{{l11,l12,…}->{r11,r12,..},…}list substitution system
CellularAutomaton[rules]cellular automaton system
"type"→rulessystem of the specified type
Supported rule types include:
"StringSubstitutionSystem"rules given as replacements on strings
"ListSubstitutionSystem"rules given as replacements on lists
"CellularAutomaton"rules given as a list of CellularAutomaton rule specifications
"WolframModel"rules given as replacements on hypergraphs
When rules are specified by an explicit association, the following elements can be included:
"StateEvolutionFunction"gives the list of successors to a given state
"StateEquivalenceFunction"determines whether two states should be considered equivalent
"StateEventFunction"gives the list of events applicable to a given state
"EventApplicationFunction"applies an event to a given state
"EventDecompositionFunction"decomposes an event into creator and destroyer events for individual elements
"SystemType"gives a system type name
"EventSelectionFunction"determines which events should be applied to a given state
The event selection function sel in ResourceFunction["BranchPairs"][rules→sel,…] can have the following special forms:
"Sequential"applies the first possible replacement (sequential substitution system)
"Random"applies a random replacement
{"Random",n}applies n randomly chosen replacements
"MaxScan"applies the maximal set of spatially-separated replacements (strings only)
The initial condition for ResourceFunction["BranchPairs"] is a list of states appropriate for the type of system used.
ResourceFunction["BranchPairs"][rules,"string",…] is interpreted as ResourceFunction["BranchPairs"][rules,{"string"},…].
ResourceFunction["BranchPairs"] accepts both individual rules and lists of rules, and likewise for initial conditions.
Options for ResourceFunction["BranchPairs"] include:
"IncludeStepNumber"Falsewhether to label states and events with their respective step numbers
"IncludeStateID"Falsewhether to label states and events with unique IDs
"GivePredecessors"Falsewhether to label branch pairs with their predecessor state
In the theory of abstract rewrite systems, a critical pair (branch pair) is a pair of expressions that can be derived from a common expression by two different applications of a rewrite rule (i.e. either the same rule applied in two different places, or two different rules).
More generally, a branch pair indicates where a multiway evolution bifurcates.

Examples

Basic Examples (5) 

Generate the list of all branch pairs (i.e. critical pairs) for two string substitution systems:

In[1]:=
ResourceFunction["BranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2]
Out[1]=
In[2]:=
ResourceFunction["BranchPairs"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2]
Out[2]=

Show common predecessor states:

In[3]:=
ResourceFunction[ "BranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2, "GivePredecessors" -> True]
Out[3]=

Different event selection functions can lead to different lists of branch pairs:

In[4]:=
ResourceFunction["BranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2]
Out[4]=
In[5]:=
ResourceFunction[ "BranchPairs"][{"AA" -> "ABA", "AAA" -> "B"} -> "Sequential", "AAA", 2]
Out[5]=

BranchPairs can handle Wolfram Models and other system types:

In[6]:=
ResourceFunction["BranchPairs"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 3}, {3, 3, 2}}}, {{{2, 2, 1}, {2, 2, 3}, {2, 2, 2}, {3, 3, 3}}}, 1]
Out[6]=
In[7]:=
ResourceFunction["BranchPairs"][ CellularAutomaton[30], {0, 0, 1, 0, 0}, 2]
Out[7]=
In[8]:=
ResourceFunction[ "BranchPairs"][{{0} -> {0, 1, 0}, {1, 1} -> {1}}, {0, 1, 1}, 2]
Out[8]=

Preventing identical states from being merged, by including step numbers and/or state IDs, can change branch pair behavior:

In[9]:=
ResourceFunction["BranchPairs"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2]
Out[9]=
In[10]:=
ResourceFunction[ "BranchPairs"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[10]=

Scope (10) 

System Types (5) 

BranchPairs supports both string and list substitution systems:

In[11]:=
ResourceFunction["BranchPairs"][{"BB" -> "AA", "AB" -> "BA"}, "ABBA", 3]
Out[11]=
In[12]:=
ResourceFunction[ "BranchPairs"][{{1, 1} -> {0, 0}, {0, 1} -> {1, 0}}, {0, 1, 1, 0}, 3]
Out[12]=

Lists can contain arbitrary symbolic elements:

In[13]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/e03e0eb9-af2c-4a29-adeb-74b699f5d829"]
Out[13]=

Give an explicit substitution system rule:

In[14]:=
ResourceFunction["BranchPairs"][ SubstitutionSystem[{{0} -> {0, 0}, {0} -> {0, 1}}], {{0}}, 3]
Out[14]=

An alternative method of specifying that a substitution system should be used:

In[15]:=
ResourceFunction["BranchPairs"][ "SubstitutionSystem" -> {{0} -> {0, 0}, {0} -> {0, 1}}, {{0}}, 3]
Out[15]=

BranchPairs also supports multiway generalizations of cellular automata:

In[16]:=
ResourceFunction["BranchPairs"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 1]
Out[16]=

Generate all branch pairs from left- and right-shift cellular automaton rules after 3 steps:

In[17]:=
ResourceFunction["BranchPairs"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 3]
Out[17]=

Determine branch pairs of the rule 30 cellular automaton:

In[18]:=
ResourceFunction["BranchPairs"][ CellularAutomaton[30], {0, 0, 1, 0, 0}, 1]
Out[18]=

BranchPairs also supports multiway generalizations of Wolfram Models:

In[19]:=
ResourceFunction["BranchPairs"][ "WolframModel" -> {{{0, 1}, {1, 0}} -> {{1, 2}, {2, 1}, {0, 1}}}, {{{0, 1}, {1, 0}, {0, 1}, {2, 3}}}, 1]
Out[19]=
In[20]:=
ResourceFunction["BranchPairs"][ "WolframModel" -> {{{0, 1}} -> {{1, 2}, {2, 1}}}, {{{0, 1}, {1, 0}}}, 1]
Out[20]=

Construct a multiway evolution by explicitly specifying an association:

In[21]:=
ResourceFunction[ "BranchPairs"][<| "StateEvolutionFunction" -> (StringReplaceList[#, {"A" -> "AA", "B" -> "AB"}] &), "StateEquivalenceFunction" -> SameQ, "StateEventFunction" -> Identity, "EventDecompositionFunction" -> Identity, "EventApplicationFunction" -> Identity, "SystemType" -> "None", "EventSelectionFunction" -> Identity|>, {"ABA"}, 3]
Out[21]=

Rules and Initial Conditions (2) 

BranchPairs accepts both individual rules and lists of rules:

In[22]:=
ResourceFunction["BranchPairs"]["A" -> "AA", "AAA", 1]
Out[22]=
In[23]:=
ResourceFunction["BranchPairs"][{"A" -> "AB", "B" -> "BA"}, "AAABA", 1]
Out[23]=

Likewise for initial conditions:

In[24]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AB", "B" -> "BA"}, {"ABA", "AAB"}, 2]
Out[24]=

Event Selection Functions (3) 

Apply only the first possible event at each step:

In[25]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AAB", "BA" -> "A"} -> "Sequential", "A", 2]
Out[25]=

Apply the first and last possible events at each step:

In[26]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AAB", "BA" -> "A"} -> ({First[#], Last[#]} &), "ABA", 1]
Out[26]=

Use a greedy-style algorithm to apply the maximal set of non-conflicting events at each step (strings only):

In[27]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AA", "BA" -> "AB"} -> "MaxScan", "ABA", 4]
Out[27]=

Options (5) 

Explicitly specify the type of rule:

In[28]:=
ResourceFunction["BranchPairs"][ "SubstitutionSystem" -> {"A" -> "AA", "A" -> "AB"}, {"ABA"}, 2]
Out[28]=
In[29]:=
ResourceFunction["BranchPairs"][ "SubstitutionSystem" -> {{0} -> {0, 0}, {0} -> {0, 1}}, {{0, 1, 0}}, 2]
Out[29]=

Step Numbers and State IDs (3) 

By default, equivalent states are merged across all time steps:

In[30]:=
ResourceFunction["BranchPairs"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 1]
Out[30]=

Merging of equivalent states across different time steps can be prevented by including step numbers:

In[31]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 1, "IncludeStepNumber" -> True]
Out[31]=

Merging of equivalent states at the same time step can be prevented by also including state IDs:

In[32]:=
ResourceFunction[ "BranchPairs"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 1, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[32]=

Predecessor States (2) 

By default, BranchPairs returns only a list of branch pairs:

In[33]:=
ResourceFunction[ "BranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, "AAABAAA", 1]
Out[33]=

Common predecessor states can be shown using "GivePredecessors":

In[34]:=
ResourceFunction[ "BranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, "AAABAAA", 1, "GivePredecessors" -> True]
Out[34]=

Publisher

Jonathan Gorard

Version History

  • 1.0.0 – 14 April 2020

Source Metadata

  • Citation:
    • Stephen Wolfram (2002), “A New Kind of Science”
    • Stephen Wolfram (2020), “A Class of Models with Potential to Represent Fundamental Physics”
    • Jonathan Gorard (2020), “Some Relativistic and Gravitational Properties of the Wolfram Model”
    • Jonathan Gorard (2020), “Some Quantum Mechanical Properties of the Wolfram Model”

Related Resources

License Information