Function Repository Resource:

MultiwaySemigroup

Simulate an arbitrary (potentially commutative) semigroup as a multiway system

Contributed by: Jonathan Gorard

ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→rel|>]

compiles the semigroup with the specified generators and relations into a specification of a multiway system.

ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→rel|>,n]

generates the results of n steps in the evolution of the multiway semigroup with the specified generators and relations.

ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→rel|>,n,"prop"]

gives the property "prop" for the specified multiway semigroup evolution.

ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→rel|>→sel,…]

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

ResourceFunction["MultiwaySemigroup"][gen,…]

specifies the free semigroup with generators gen.

ResourceFunction["MultiwaySemigroup"][gen,rel,…]

specifies the semigroup with generators gen and relations rel.

Details and Options

Argument and option patterns for ResourceFunction["MultiwaySemigroup"] largely match those of the resource function MultiwaySystem.

Rules are specified as associations of semigroup generators and relations; states are specified as words in the corresponding semigroup.

In semigroup presentation theory, the generators are the elements of the semigroup in terms of which all other elements can be expressed as products of powers and the relations are the defining equations of the semigroup.

Generators should be specified as characters, with relations being two-way rules on strings.

The event selection function sel in ResourceFunction["MultiwaySemigroup"][rules→sel,…] can be any function; additionally, it 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

ResourceFunction["MultiwaySemigroup"][gen,…] is interpreted as ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→{}|>,…] (i.e. the free semigroup).

ResourceFunction["MultiwaySemigroup"][gen,rel,…] is interpeted as ResourceFunction["MultiwaySemigroup"][<|"Generators"→gen,"Relations"→rel|>,…].

In ResourceFunction["MultiwaySemigroup"][rules,n,prop], the following properties can be requested:

"AllStatesList"

the list of all states generated at each successive step (default)

"StatesCountsList"

the number of distinct states generated at each successive step

"AllStatesListUnmerged"

the list of all states without any merging

"PredecessorRulesList"

the list of states and their corresponding predecessor states at each successive step

"EvolutionGraph"

graph formed by the evolution process, with no merging between different time steps

"EvolutionGraphStructure"

evolution graph without labeling

"EvolutionGraphFull"

graph formed by the evolution process, including equivalent events

"EvolutionGraphFullStructure"

full evolution graph without labeling

"EvolutionGraphUnmerged"

graph formed by the evolution process, with no merging of equivalent states

"EvolutionGraphUnmergedStructure"

unmerged evolution graph without labeling

"EvolutionGraphWeighted"

graph formed by the evolution process, with edges weighted by event multiplicity

"EvolutionGraphWeightedStructure"

weighted evolution graph without labeling

"StatesGraph"

graph of how each distinct state leads to other states

"StatesGraphStructure"

states graph without labeling

"AllEventsList"

the list of all events that occur at each successive step

"EvolutionEventsGraph"

graph showing the evolution process with updating events explicitly included

"EvolutionEventsGraphStructure"

evolution events graph without labeling

"CausalGraph"

graph of causal relationships between updating events

"CausalGraphStructure"

causal graph without labeling

"EvolutionCausalGraph"

combined graph of evolution process and causal relationships between events

"EvolutionCausalGraphStructure"

evolution causal graph without labeling

"CausalGraphInstances"

list of distinct causal graphs for all possible choices of event sequences

"CausalGraphStructureInstances"

causal graph instances without labeling

"EvolutionCausalGraphInstances"

list of distinct evolution causal graphs for all possible choices of event sequences

"EvolutionCausalGraphStructureInstances"

evolution causal graph instances without labeling

"BranchPairsList"

list of all branch pairs (i.e. critical pairs) generated in the states graph

"NewBranchPairsList"

list of all new branch pairs generated at each successive step

"EvolutionBranchPairsList"

list of all branch pairs generated in the evolution graph

"NewEvolutionBranchPairsList"

list of all new evolution branch pairs generated at each successive step

"BranchPairEventsList"

list of all events yielding branch pairs

"NewBranchPairEventsList"

list of all events yielding new branch pairs at each successive step

"EvolutionBranchPairEventsList"

list of all events yielding evolution branch pairs

"NewEvolutionBranchPairEventsList"

list of all events yielding new evolution branch pairs at each successive step

"BranchialGraph"

graph of branch pair ancestry at a given step

"BranchialGraphStructure"

branchial graph without labeling

"AllStatesBranchialGraph"

graph of branch pair ancestry across all steps

"AllStatesBranchialGraphStructure"

all states branchial graph without labeling

"EvolutionBranchialGraph"

graph of evolution branch pair ancestry at a given step

"EvolutionBranchialGraphStructure"

evolution branchial graph without labeling

"AllStatesEvolutionBranchialGraph"

graph of evolution branch pair ancestry across all steps

"AllStatesEvolutionBranchialGraphStructure"

all states evolution brancial graph without labeling

"EventBranchialGraph"

graph of branch pair event ancestry at a given step

"EventBranchialGraphStructure"

event branchial graph without labeling

"AllEventsBranchialGraph"

graph of branch pair event ancestry across all steps

"AllEventsBranchialGraphStructure"

all events branchial graph without labeling

"EvolutionEventBranchialGraph"

graph of evolution branch pair event ancestry at a given step

"EvolutionEventBranchialGraphStructure"

evolution event branchial graph without labeling

"AllEventsEvolutionBranchialGraph"

graph of evolution branch pair event ancestry across all steps

"AllEventsEvolutionBranchialGraphStructure"

all events evolution branchial graph without labeling

"BranchPairResolutionsList"

association of all resolved and unresolved branch pairs up to a given step

"EvolutionBranchPairResolutionsList"

association of all resolved and unresolved evolution branch pairs up to a given step

"CausalInvariantQ"

whether the system is causal invariant (all branch pairs converge)

"EvolutionCausalInvariantQ"

whether the system is evolution causal invariant (all evolution branch pairs converge)

"KnuthBendixCompletion"

list of Knuth–Bendix completion rules required to force causal invariance

"EvolutionKnuthBendixCompletion"

list of Knuth–Bendix completion rules required to force evolution causal invariance

"StateWeights"

list of weights for all vertices in the states graph

Except for "AllStatesListUnmerged", "EvolutionGraphUnmerged" and states containing state IDs, identical states are always merged at each step.

In "StatesGraph", all instances of a given state at any step are merged. Different updating events that connect the same states will only be shown as separate edges if "IncludeEventInstances" is set to True.

Events are represented in the form {rule,input,rest}, where rule is the rule used in the updating event, input is the part of the state to which the rule is applied and rest is the remainder of the state. For substitution systems, rest is given in the form {prefix,suffix}.

Options for ResourceFunction["MultiwaySemigroup"] include:

"Commutative"

False

whether the semigroup is commutative

"StyleEdges"

True

whether to style edges according to generators, relations and commutativity

"AppendOnly"

False

whether to apply generators only to the end of the word

"IncludeStepNumber"

False

whether to label states and events with their respective step numbers

"IncludeStateID"

False

whether to label states and events with unique IDs

"IncludeInitializationEvents"

False

whether to include pseudoevents that set up initial conditions

"IncludeEventInstances"

False

whether to show distinct updating events that connect the same states as separate edges

"IncludeStateWeights"

False

whether to weight state vertices by their rate of occurrence at a particular time step

"IncludeStatePathWeights"

False

whether to weight state vertices by the number of distinct evolution paths that lead to them

"StateRenderingFunction"

Automatic

how to label states that appear in graphs

"EventRenderingFunction"

Automatic

how to label events that appear in graphs

MaxItems

Infinity

how many instances of a causal graph or evolution causal graph to return

"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

"IncludeFullBranchialSpace"

False

whether to show all possible states in a given branchial graph

"LineThickness"

absolute line thickness for graph edges

Possible settings for "StateRenderingFunction" and "EventRenderingFunction" include:

Inherited

use the explicit vertex name as the label

None

use no label for the vertex

"shape"

use a shape from the VertexShapeFunction collection

func

apply the function func to the name of the vertex

For "CausalGraphInstances" and "EvolutionCausalGraphInstances", the option MaxItems→n can be used to get only the first n possible instances of causal graphs.

By default, states graphs are styled using red edges to indicate the application of a generator, green edges to indicate the application of a relation and blue edges to indicate the application of commutativity.

Examples

Basic Examples (18)

Show basic semigroup compilation (compiling semigroups on one, two and three generators to MultiwaySystem rules):

In[1]:=

Out[1]=

In[2]:=

Out[2]=

In[3]:=

Out[3]=

When only the generators are specified, the free semigroup is assumed by default:

In[4]:=

Out[4]=

In[5]:=

Out[5]=

Generate a graph showing how each state is obtained from the others for a semigroup on two generators:

In[6]:=

Out[6]=

Show the structure of the graph, without labels:

In[7]:=

Out[7]=

Generate the states graph for the free commutative semigroup on 3 generators:

In[8]:=

Out[8]=

Compare to the free non-commutative semigroup on 3 generators (default):

In[9]:=

Out[9]=

Generate the (reduced) states graph for a semigroup on 3 generators, where generators are only applied to the end of the word:

In[10]:=

ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b", "c"}, "Relations" -> {"ab" <-> "bc", "bc" <-> "ca", "ca" <-> "ab"}|>, 3, "StatesGraphStructure", "AppendOnly" -> True]

Out[10]=

Compare to the full states graph for the same semigroup:

In[11]:=

ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b", "c"}, "Relations" -> {"ab" <-> "bc", "bc" <-> "ca", "ca" <-> "ab"}|>, 3, "StatesGraphStructure", "AppendOnly" -> False]

Out[11]=

Generate a graph of the evolution history, with updating events included:

In[12]:=

Out[12]=

Show the structure of the graph, without labels:

In[13]:=

Out[13]=

Generate the causal graph, showing dependencies between updating events:

In[14]:=

Out[14]=

Show the structure of the graph, without labels:

In[15]:=

Out[15]=

Generate the evolution events graph, with causal connections included:

In[16]:=

Out[16]=

Show the structure of the graph, without labels:

In[17]:=

Out[17]=

Specify an event selection function that picks a random pair of events at each step:

In[18]:=

Out[18]=

Generate causal graphs for all possible choices of event sequences:

In[19]:=

Out[19]=

Show the structures of the graphs, without labels:

In[20]:=

Out[20]=

Generate the list of all branch pairs (i.e. critical pairs):

In[21]:=

Out[21]=

Generate the association showing which branch pairs converged and which did not:

In[22]:=

Out[22]=

Prove that the system is causal invariant:

In[23]:=

Out[23]=

Generate a graph showing branch pair ancestry:

In[24]:=

Out[24]=

Show the structure of the graph, without labels:

In[25]:=

Out[25]=

Generate a graph showing branch pair event ancestry:

In[26]:=

Out[26]=

Prevent identical states from being merged by including step numbers and state IDs:

In[27]:=

Out[27]=

In[28]:=

Out[28]=

Generate a graph of full evolution history, with all events included:

In[29]:=

Out[29]=

Show the structure of the graph, without labels:

In[30]:=

Out[30]=

Generate a graph of full evolution history, with no merging of equivalent states:

In[31]:=

Out[31]=

Show the structure of the graph, without labels:

In[32]:=

Out[32]=

Generate a graph of evolution history, with edges weighted by event multiplicity:

In[33]:=

Out[33]=

Show the structure of the graph, without labels:

In[34]:=

Out[34]=

Generate a states graph with vertices weighted by their rate of occurrence on each time step:

In[35]:=

Out[35]=

Show the structure of the graph, without labels:

In[36]:=

Out[36]=

Generate a states graph with vertices weighted by the number of distinct evolution paths that lead to them:

In[37]:=

Out[37]=

Show the structure of the graph, without labels:

In[38]:=

Out[38]=

Scope (4)

Generators and relations (1)

MultiwaySemigroup accepts both partial and full (association) specifications of semigroups in terms of generators and relations:

In[39]:=

Out[39]=

In[40]:=

Out[40]=

In[41]:=

Out[41]=

Commutativity (1)

MultiwaySemigroup can handle both commutative and non-commutative (default) semigroups:

In[42]:=

Out[42]=

In[43]:=

Out[43]=

Event selection functions (2)

Apply only the first possible event at each step:

In[44]:=

Out[44]=

Apply the first and last possible events at each step:

In[45]:=

Out[45]=

Options (31)

Commutativity (2)

By default, all semigroups are non-commutative:

In[46]:=

semiGroup = ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b", "c"}, "Relations" -> {"ab" <-> "bc", "bc" <-> "ca"}|>, 2, "StatesGraph"]

Out[46]=

In[47]:=

Out[47]=

Make the semigroup commutative:

In[48]:=

semiGroup2 = ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b", "c"}, "Relations" -> {"ab" <-> "bc", "bc" <-> "ca"}|>, 2, "StatesGraph", "Commutative" -> True]

Out[48]=

In[49]:=

Out[49]=

Append only (2)

By default, MultiwaySemigroup evolves by applying generators at all possible places within a word:

In[50]:=

Out[50]=

Apply generators only at the end of the word:

In[51]:=

Out[51]=

Edge styling (2)

By default, edges are styled in red if they correspond to the application of a generator, green if they correspond to the application of a relation and blue if they correspond to an application of commutativity:

In[52]:=

Out[52]=

Use no styling for edges:

In[53]:=

ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b", "c"}, "Relations" -> {"ab" <-> "bc", "bc" <-> "ca"}|>, 2, "StatesGraph", "Commutative" -> True, "StyleEdges" -> False]

Out[53]=

State node rendering (5)

By default, states are labeled by their contents:

In[54]:=

Out[54]=

Use no labeling for states:

In[55]:=

Out[55]=

"StatesGraphStructure" yields the same result:

In[56]:=

Out[56]=

Use raw state names as node labels:

In[57]:=

Out[57]=

Use a named shape as each state label:

In[58]:=

Out[58]=

Event node rendering (4)

By default, both states and events are labeled by their contents:

In[59]:=

Out[59]=

Use no labels for states or events:

In[60]:=

ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b"}, "Relations" -> {"abb" <-> "bba"}|>, 3, "EvolutionEventsGraph", "StateRenderingFunction" -> None, "EventRenderingFunction" -> None]

Out[60]=

"EvolutionEventsGraphStructure" yields an equivalent result:

In[61]:=

Out[61]=

Use raw event expressions as their labels:

In[62]:=

Out[62]=

Initialization events (2)

By default, "AllEventsList" does not include initialization events:

In[63]:=

Out[63]=

The option "IncludeInitializationEvents" allows one to override this default:

In[64]:=

Out[64]=

Initialization events have special default rendering:

In[65]:=

Out[65]=

Graph layout options (2)

Place arrows in the middle of edges:

In[66]:=

ResourceFunction[
"MultiwaySemigroup"][<|"Generators" -> {"a", "b"}, "Relations" -> {"abb" <-> "bba"}|>, 3, "StatesGraph", EdgeShapeFunction -> GraphElementData["ShortFilledArrow", "ArrowSize" -> 0.03]]

Out[66]=

Generate an example of a multiway semigroup:

In[67]:=

Out[67]=

Force the initial state nodes to be at the top:

In[68]:=

Out[68]=

Step numbers and state IDs (2)

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

In[69]:=

Out[69]=

In[70]:=

Out[70]=

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

In[71]:=

Out[71]=

List the states:

In[72]:=

Out[72]=

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

In[73]:=

Out[73]=

List the states:

In[74]:=

Out[74]=

Step numbers and IDs also apply to events:

In[75]:=

Out[75]=

See the events:

In[76]:=

Out[76]=

Event instances (2)

By default, multiple instances of equivalent updating events are merged in the states graph:

In[77]:=

Out[77]=

Merging of equivalent events can be prevented by including event instances:

In[78]:=

Out[78]=

State (path) weights (2)

Vertices of a states graph can be weighted by their relative rate of occurrence at each time step:

In[79]:=

Out[79]=

Vertices can also be weighted by the number of distinct evolution paths that lead to them:

In[80]:=

Out[80]=

MaxItems (2)

By default, "CausalGraphInstances" returns all possible causal graphs:

In[81]:=

Out[81]=

The number of causal graphs can be limited using MaxItems:

In[82]:=

Out[82]=

Predecessors and resolvents (2)

By default, "BranchPairsList" returns only a list of branch pairs:

In[83]:=

Out[83]=

Common predecessor states can be shown using "GivePredecessors":

In[84]:=

Out[84]=

Similarly, "BranchPairResolutionsList" by default lists only resolved and unresolved branch pairs:

In[85]:=

Out[85]=

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

In[86]:=

Out[86]=

Show both common predecessors and common resolvents, where appropriate:

In[87]:=

Out[87]=

Full branchial space (2)

By default, non-branch pair states are not shown as part of the branchial graph:

In[88]:=

Out[88]=

They can be shown using "IncludeFullBranchialSpace":

In[89]:=

Out[89]=

Publisher

Jonathan Gorard

Version History

1.0.0 – 02 September 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

This work is licensed under a Creative Commons Attribution 4.0 International License

Wolfram Function Repository

MultiwaySemigroup

Details and Options

Examples

Basic Examples (18)

Scope (4)

Generators and relations (1)

Commutativity (1)

Event selection functions (2)

Options (31)

Commutativity (2)

Append only (2)

Edge styling (2)

State node rendering (5)

Event node rendering (4)

Initialization events (2)

Graph layout options (2)

Step numbers and state IDs (2)

Event instances (2)

State (path) weights (2)

MaxItems (2)

Predecessors and resolvents (2)

Full branchial space (2)

Publisher

Related Links

Version History

Source Metadata

Related Resources

License Information

MultiwaySemigroup

Details and Options

Examples

Basic Examples (18)

Scope (4)

Generators and relations (1)

Commutativity (1)

Event selection functions (2)

Options (31)

Commutativity (2)

Append only (2)

Edge styling (2)

State node rendering (5)

Event node rendering (4)

Initialization events (2)

Graph layout options (2)

Step numbers and state IDs (2)

Event instances (2)

State (path) weights (2)

MaxItems (2)

Predecessors and resolvents (2)

Full branchial space (2)

Publisher

Related Links

Version History

Source Metadata

Related Resources

Related Symbols

License Information