Wolfram Research

Function Repository Resource:

CanonicalBranchPairs

Source Notebook

Compute canonical branch pairs for a given multiway system

Contributed by: Jonathan Gorard

ResourceFunction["CanonicalBranchPairs"][rules]

generates a list of canonical (i.e. initial condition-independent) branch pairs for the multiway system with the specified rules.

ResourceFunction["CanonicalBranchPairs"][rules,n]

generates an association of resolved and unresolved canonical branch pairs for the multiway system with the specified rules after n steps.

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"rules system 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
ResourceFunction["CanonicalBranchPairs"] accepts both individual rules and lists of rules.
Options for ResourceFunction["CanonicalBranchPairs"] include:
"GivePredecessors" False whether to label branch pairs with their predecessor state
"GiveResolvents" False whether to label branch pairs with their resolvent state
"IncludeSelfPairs" False whether to include trivial branch pairs
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

Generate the list of all canonical branch pairs (i.e. critical pairs) for a string substitution system:

In[1]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}]
Out[1]=

Generate the association showing which branch pairs converge after 2 steps and which do not:

In[2]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, 2]
Out[2]=

Show common predecessor states:

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

Show common resolvent states for resolved canonical branch pairs:

In[4]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, 2, "GiveResolvents" -> True]
Out[4]=

Show both common predecessors and common resolvents, where appropriate:

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

CanonicalBranchPairs can handle Wolfram Models and other system types:

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

Scope

System Types

CanonicalBranchPairs supports both string and list substitution systems:

In[9]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"BB" -> "AA", "ABB" -> "BA"}]
Out[9]=
In[10]:=
ResourceFunction[
 "CanonicalBranchPairs"][{{1, 1} -> {0, 0}, {0, 1, 1} -> {1, 0}}]
Out[10]=

CanonicalBranchPairs also supports multiway generalizations of cellular automata:

In[11]:=
Take[ResourceFunction["CanonicalBranchPairs"][
  CellularAutomaton[{170, 240}]], 20]
Out[11]=

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

In[12]:=
ResourceFunction["CanonicalBranchPairs"][
  CellularAutomaton[{170, 240}], 5]["Resolved"]
Out[12]=

Determine that the rule 30 cellular automaton is not causal invariant:

In[13]:=
ResourceFunction["CanonicalBranchPairs"][CellularAutomaton[30], 5]["Unresolved"]
Out[13]=

CanonicalBranchPairs also supports multiway generalizations of Wolfram Models:

In[14]:=
ResourceFunction["CanonicalBranchPairs"][
 "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 2}, {2, 2, 2}}}]
Out[14]=

Determine that this Wolfram Model rule has unresolved branch pairs, and thus is not causal invariant:

In[15]:=
ResourceFunction["CanonicalBranchPairs"][
  "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 2}, {2, 2, 2}}}, 5]["Unresolved"]
Out[15]=

Options

Predecessors and Resolvents

By default, CanonicalBranchPairs returns only a list of canonical branch pairs:

In[16]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}]
Out[16]=

Common predecessor states can be shown using "GivePredecessors":

In[17]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, "GivePredecessors" -> True]
Out[17]=

Similarly, CanonicalBranchPairs with a step count by default lists only resolved and unresolved canonical branch pairs:

In[18]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2]
Out[18]=

Common resolvents of resolved branch pairs can be shown using "GiveResolvents":

In[19]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2, "GiveResolvents" -> True]
Out[19]=

Show both common predecessors and common resolvents, where appropriate:

In[20]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2, "GivePredecessors" -> True, "GiveResolvents" -> True]
Out[20]=

Self Pairs

By default, CanonicalBranchPairs does not include self pairs (i.e. trivial critical pairs):

In[21]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "AB", "BAA" -> "BA"}]
Out[21]=

Self pairs can be included using “IncludeSelfPairs”:

In[22]:=
ResourceFunction[
 "CanonicalBranchPairs"][{"AA" -> "AB", "BAA" -> "BA"}, "IncludeSelfPairs" -> True]
Out[22]=

Applications

Causal Invariant Rules

Prove that the Xor and And functions are total causal invariant (due to associativity):

In[23]:=
ResourceFunction[
  "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, 1]["Unresolved"]
Out[23]=
In[24]:=
ResourceFunction[
  "CanonicalBranchPairs"][{"TT" -> "T", "TF" -> "F", "FT" -> "F", "FF" -> "F"}, 1]["Unresolved"]
Out[24]=

On the other hand, the Nand function is not associative, so it is not total causal invariant:

In[25]:=
ResourceFunction[
  "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, 1]["Unresolved"]
Out[25]=

Properties and Relations

CanonicalBranchPairs returns an empty list of unresolved canonical branch pairs if and only if the rule is total causal invariant:

In[26]:=
ResourceFunction[
  "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, 1]["Unresolved"]
Out[26]=
In[27]:=
ResourceFunction[
  "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, 1]["Unresolved"]
Out[27]=

Resource History

Source Metadata

Related Resources

License Information