Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindCriticalPairs

Source Notebook

Find all critical pairs for a given multiway system evolution

Contributed by: Jonathan Gorard

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

finds all critical pairs after n steps in the evolution of the multiway system with the specified rules starting from initial condition init.

Details and Options

Critical pairs are pairs of terms in a rewrite system that result from overlapping rules.
In the context of multiway systems, critical pairs indicate bifurcations or ambiguities in the multiway system evolution.
ResourceFunction["FindCriticalPairs"] gives all pairs of states in the multiway system that can be reached from a single common state by valid application of the rules.
Multiway systems operate on strings, lists and WolframModel systems.
When rules are specified by an explicit association, the following elements can be included:
"StateEvolutionFunction"the list of successors for a given state
"StateEquivalenceFunction"whether two states should be considered equivalent
"StateEventFunction"the list of events obtained from a given state
"SystemType"system type name
"EventSelectionFunction"which events from a given state should be included
The initial condition can consist of a single state or a list of states.

Examples

Basic Examples (4) 

Find all critical pairs for a basic multiway system evolution:

In[1]:=
ResourceFunction[ "FindCriticalPairs"][{"A" -> "AB", "B" -> "A"}, {"A"}, 3]
Out[1]=
In[2]:=
ResourceFunction[ "FindCriticalPairs"][{{0} -> {0, 1}, {1} -> {0}}, {{0}}, 3]
Out[2]=

Find all critical pairs for a multiway system evolution with a more complicated initial condition:

In[3]:=
ResourceFunction[ "FindCriticalPairs"][{"A" -> "AA", "B" -> "AB"}, {"ABA"}, 3]
Out[3]=
In[4]:=
ResourceFunction[ "FindCriticalPairs"][{{0} -> {0, 0}, {1} -> {0, 1}}, {{0, 1, 0}}, 3]
Out[4]=

By picking a specific updating order, we can force this multiway system evolution to yield no critical pairs:

In[5]:=
ResourceFunction[ "FindCriticalPairs"][{"A" -> "AA", "B" -> "AB"} -> ({First[#], Last[#]} &), {"ABA"}, 3]
Out[5]=
In[6]:=
ResourceFunction[ "FindCriticalPairs"][{{0} -> {0, 0}, {1} -> {0, 1}} -> ({First[#], Last[#]} &), {{0, 1, 0}}, 3]
Out[6]=

FindCriticalPairs can also find critical pairs in WolframModel evolutions:

In[7]:=
ResourceFunction["FindCriticalPairs"][ "WolframModel" -> {{{1, 2}, {1, 3}, {1, 4}} -> {{1, 2}, {1, 3}, {1, 4}, {2, 3}}}, {{{1, 2}, {1, 3}, {1, 4}}}, 5]
Out[7]=
In[8]:=
ResourceFunction["FindCriticalPairs"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 3}, {1, 1, 1}, {2, 1, 2}, {3, 3, 2}}}, {{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}, 1]
Out[8]=

Scope (2) 

FindCriticalPairs gives an empty list if and only if the multiway system contains only a single evolution path:

In[9]:=
ResourceFunction["FindCriticalPairs"][{"A" -> "AA"}, {"A"}, 3]
Out[9]=
In[10]:=
ResourceFunction["FindCriticalPairs"][{{0} -> {0, 0}}, {{0}}, 3]
Out[10]=

Find all critical pairs for a non-causally-invariant multiway system evolution:

In[11]:=
ResourceFunction[ "FindCriticalPairs"][{"A" -> "AB", "AA" -> "BA"}, {"AAB"}, 3]
Out[11]=
In[12]:=
ResourceFunction[ "FindCriticalPairs"][{{0} -> {0, 1}, {0, 0} -> {1, 0}}, {{0, 0, 1}}, 3]
Out[12]=

Publisher

Jonathan Gorard

Version History

  • 1.0.0 – 04 December 2019

Related Resources

License Information