Function Repository Resource:

PetriNetNondeterministicEvolution

Evolve a Petri net configuration nondeterministically by randomly selecting one possible transition firing at each step

Contributed by: Jonathan Gorard

ResourceFunction["PetriNetNondeterministicEvolution"][pnet,n]

evolves a Petri net configuration defined by the PetriNetObject expression pnet nondeterministically for n steps, by randomly selecting one possible transition firing at each step.

ResourceFunction["PetriNetNondeterministicEvolution"][p,t,a,init,n]

evolves a Petri net defined by the list of places p, the list of transitions t and the list of arcs a, with initial token distribution init, nondeterministically for n steps, by randomly selecting one possible transition firing at each step.

ResourceFunction["PetriNetNondeterministicEvolution"][assoc,init,n]

evolves a Petri net defined by the association of places, transitions and arcs assoc, with initial token distribution init, nondeterministically for n steps, by randomly selecting one possible transition firing at each step.

ResourceFunction["PetriNetNondeterministicEvolution"][…,prop]

gives the property "prop" for the specified nondeterministic Petri net evolution.

Details and Options

A Petri net is an abstract mathematical representation of a distributed system (frequently used for describing chemical reactions, biological processes, concurrent computing, etc.) consisting of a directed bipartite graph whose vertices are classified as either "places" or "transitions". The directed edges connecting places and transitions together are known as "arcs".

Each place can contain a number of "tokens", and a given transition will "fire" if the places connected to it by input arcs all contain at least one token. When a transition fires, it redistributes tokens from places connected to it by input arcs to places connected to it by output arcs.

ResourceFunction["PetriNetNondeterministicEvolution"] supports the specification of Petri nets either by PetriNetObject expressions, a collection of three lists (places p, transitions t and arcs a), or by an explicit association of the form <|"Places"→p,"Transitions"→t,"Arcs"→a|>. The list of arcs a should be a list of either rules or DirectedEdge objects (each connecting a place to a transition, or vice versa).

PetriNetObject expressions can be constructed using the MakePetriNet resource function.

When specifying Petri nets in terms of lists or associations, the list init should be a list of integers specifying how many initial tokens to assign to each place. If a list init is not given, ResourceFunction["PetriNetNondeterministicEvolution"] will assume that each place contains no tokens.

ResourceFunction["PetriNetNondeterministicEvolution"] evolves the specified Petri net nondeterministically by randomly selecting and applying one possible transition firing at each step.

When no step count n is specified, ResourceFunction["PetriNetNondeterministicEvolution"] will evolve the Petri net nondeterministically for a single step and return a single result. When a step count n is specified, ResourceFunction["PetriNetNondeterministicEvolution"] will evolve the Petri net nondeterministically for n steps and return a list of the intermediate results at each step.

When no property prop is specified, ResourceFunction["PetriNetNondeterministicEvolution"] will assume the "PetriNetObjects" property (i.e. it will return a list of the PetriNetObject expressions obtained during the evolution).

In ResourceFunction["PetriNetNondeterministicEvolution"][…,"prop"], the following properties can be requested:

"PetriNetObjects"

list of PetriNetObject expressions obtained

"LabeledGraphs"

list of directed graph representations obtained (with token counts represented graphically)

"LabeledGraphsHighlighted"

list of directed graph representations obtained (with token counts represented graphically), and with transition firings highlighted

"WeightedGraphs"

list of directed graph representations obtained (with token counts represented as vertex weights)

"WeightedGraphsHighlighted"

list of directed graph representations obtained (with token counts represented as vertex weights), and with transition firings highlighted

"Tokens"

list of token numbers associated to each place after each firing

"TokenFirings"

list of token numbers associated to each place after each firing, with the corresponding transition firing specified

ResourceFunction["PetriNetNondeterministicEvolution"] accepts the same options as Graph.

In a PetriNetObject expression, the following properties are supported:

"AssociationForm"

Petri net represented as an association of places, transitions and arcs

"Places"

list of places in the Petri net

"PlaceCount"

number of places in the Petri net

"Transitions"

list of transitions in the Petri net

"TransitionCount"

number of transitions in the Petri net

"Arcs"

list of arcs in the Petri net

"ArcCount"

number of arcs in the Petri net

"Tokens"

list of token numbers associated to each place in the Petri net

"TokenCount"

total number of tokens across all places in the Petri net

"UnlabeledGraph"

directed graph form of the Petri net without token counts represented graphically

"LabeledGraph"

directed graph form of the Petri net with token counts represented graphically

"WeightedGraph"

directed graph form of the Petri net with token counts represented as vertex weights

By convention, ResourceFunction["PetriNetNondeterministicEvolution"] renders places as circles, transitions as squares, arcs as directed edges and tokens as black dots.

Examples

Basic Examples (3)

Construct a simple Petri net from lists of four places, three transitions and eight arcs, with an initial distribution of six tokens:

In[1]:=

Out[1]=

Evaluate one step in the nondeterministic evolution of this Petri net:

In[2]:=

Out[2]=

Evaluate the first four steps in the nondeterministic evolution of this Petri net:

In[3]:=

Out[3]=

Show the labeled graph obtained after one step of nondeterministic evolution, with the random transition firing highlighted:

In[4]:=

Out[4]=

Show the labeled graph obtained after one step of nondeterministic evolution, but without any transition firing highlighted:

In[5]:=

Out[5]=

Show the labeled graphs obtained after four steps of nondeterministic evolution, with the random transition firings highlighted:

In[6]:=

Out[6]=

Evolve a Petri net (representing a reversible chemical reaction) specified by an association of three places, two transitions and six arcs, with an initial distribution of twelve tokens, for four steps nondeterministically:

In[7]:=

ResourceFunction[
"PetriNetNondeterministicEvolution"][<|
"Places" -> {"O2", "H2O", "H2"}, "Transitions" -> {"Hydrolysis", "Combination"}, "Arcs" -> {"Hydrolysis" -> "O2", "O2" -> "Combination", "Combination" -> "H2O", "H2O" -> "Hydrolysis", "Hydrolysis" -> "H2", "H2" -> "Combination"}|>, {1, 4, 7}, 4]

Out[7]=

Show the list of token numbers obtained after each of the four steps:

In[8]:=

Out[8]=

Show the list of token numbers obtained after each of the four steps, along with the corresponding random transition firings:

In[9]:=

Out[9]=

Show the labeled graphs obtained after four steps of nondeterministic evolution, with the random transition firings highlighted:

In[10]:=

Out[10]=

Show the weighted graphs obtained after four steps of nondeterministic evolution, with the random transition firings highlighted:

In[11]:=

Out[11]=

Show the weighted graphs obtained after four steps of nondeterministic evolution, but without any transition firings highlighted:

In[12]:=

Out[12]=

Evolve a more complicated Petri net representing a concurrent communications protocol between two agents (specified as lists of places, transitions, arcs and tokens) for four steps nondeterministically:

In[13]:=

ResourceFunction[
"PetriNetNondeterministicEvolution"][{p1, p2, p3, p4, p5, p6, p7, p8}, {"Person 1", "Person 2", "Send Message", "Receive Message", "Receive Acknowledgement", "Send Acknowledgement"}, {"Person 1" -> p1, p1 -> "Send Message", "Send Message" -> p3, "Send Message" -> p4, p3 -> "Receive Message",
p4 -> "Receive Acknowledgement", "Receive Acknowledgement" -> p7, p7 -> "Person 1", "Receive Message" -> p5, p5 -> "Send Acknowledgement", "Send Acknowledgement" -> p6, "Send Acknowledgement" -> p8, p8 -> "Person 2", "Person 2" -> p2, p2 -> "Receive Message", p6 -> "Receive Acknowledgement"}, {0, 2, 0,
6, 1, 1, 2, 1}, 4]

Out[13]=

Show the list of token numbers obtained after each of the four steps, along with the corresponding random transition firings:

In[14]:=

Out[14]=

Scope (2)

If PetriNetNondeterministicEvolution is called without an explicit list of token numbers, it is assumed that each place contains no tokens:

In[15]:=

Out[15]=

Construct a Petri net representing a simple producer-consumer problem in concurrency theory:

In[16]:=

petriNet = ResourceFunction["MakePetriNet"][{p1, p2, p3, "Buffer", p4}, {"Produce", t1, t2, "Consume"}, {p1 -> "Produce", "Produce" -> p3, p3 -> t2, t2 -> p1, t2 -> "Buffer", "Buffer" -> t1, t1 -> p4, p4 -> "Consume", "Consume" -> p2, p2 -> t1}, {1, 3, 0, 6, 2}]

Out[16]=

Show the list of Petri net objects obtained after four steps of nondeterministic evolution:

In[17]:=

Out[17]=

Show the list of directed graph representations (with token counts represented graphically) after four steps of nondeterministic evolution:

In[18]:=

Out[18]=

Show the list of directed graph representations (with token counts represented graphically, and with transition firings highlighted) after four steps of nondeterministic evolution:

In[19]:=

Out[19]=

Show the list of directed graph representations (with token counts represented as vertex weights) after four steps of nondeterministic evolution:

In[20]:=

Out[20]=

Show the list of directed graph representations (with token counts represented as vertex weights, and with transition firings highlighted) after four steps of nondeterministic evolution:

In[21]:=

Out[21]=

Show the list of token numbers associated to each place after each firing, following four steps of nondeterministic evolution:

In[22]:=

Out[22]=

Show the list of token numbers associated to each place after each firing (with the corresponding transition firings specified), following four steps of nondeterministic evolution:

In[23]:=

Out[23]=

Options (1)

PetriNetNondeterministicEvolution supports the same options as Graph:

In[24]:=

ResourceFunction[
"PetriNetNondeterministicEvolution"][{p1, p2, p3, p4}, {t1, t2, t3}, {p1 -> t1, t1 -> p1, p2 -> t1, p3 -> t1, t2 -> p2, p3 -> t3, t3 -> p4, p4 -> t2}, {1, 2, 1, 2}, "LabeledGraphs"]

Out[24]=

In[25]:=

ResourceFunction[
"PetriNetNondeterministicEvolution"][{p1, p2, p3, p4}, {t1, t2, t3}, {p1 -> t1, t1 -> p1, p2 -> t1, p3 -> t1, t2 -> p2, p3 -> t3, t3 -> p4, p4 -> t2}, {1, 2, 1, 2}, "LabeledGraphs", VertexSize -> 0.1]

Out[25]=

Publisher

Jonathan Gorard

Version History

1.0.0 – 13 December 2021

Source Metadata

Citation:
- Gzregorz Rozenberg and Joost Engelfriet (1998), "Elementary Net Systems"
- 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

PetriNetNondeterministicEvolution

Details and Options