## 4 Theoretical Background--Petri Net Theory
### Petri Net Theory  
In the late 1950s, [PERSON] developed an innovative approach to the theory of the concurrency and synchronisation applied to the modelling and study of concurrent distributed discrete event systems [26]. The introductory work on this new tool was his Ph.D. thesis (1962), titled Communication with Automata, and in this, PNs were given a rather qualitative than quantitative notion of time. Since then, Petri nets have changed significantly; a lot of variations, extensions, parameters and features have been added to the initial formalism in order to increase its modelling power, extend its area of application and make it suitable for problems with special features, specifications, structure and needs generally. The initial formalism, ordinary Petri nets (OPNs), is bipartite directed graphs formally defined as the five-tuple: \(PN=\{P,T,I,O,m_{0}\}\). The respective sets for the two types of nodes are \(P=\{p_{1},p_{2}\ldots,p_{np}\}\), which is a finite set of places, and \(T=\{t_{1},t_{2},\ldots,t_{nt}\}\), which is a finite set of transitions. \((P\cup T)=V\), where V is the set of vertices and \((P\cap T)=\emptyset\). In Petri nets, places describe conditions (e.g., for control purposes) or resource availability. Transitions represent events or actions and arcs direct connection (that may have weight equal or greater than one), access rights or logical connection between places and transitions. Places are the passive element of the PN, while transitions are the active ones. The element \(I\) of PN represents an input function, while \(O\) denotes an output function. Finally, \(m_{0}\) is PN's initial token distribution referred to in the literature as marking and representing the initial state of the elements of the Petri net. Places, transitions and arcs define the structure of the model and can be used explicitly for modelling purposes. Places and transitions are connected interchangeably, while \(T\) defines node partitions of the network (i.e., nodes of the same type are not linked). The most important PN properties (reachability, safeness, k-boundedness, conflicts, liveness, reversibility, persistency, deadlock-freeness, \(P\)-invariants and \(T\)-invariants) capture precedence relations and structural interactions between system components [30]. Inclusion of time delays (constant, following certain distributions, or random according to the actions) in the transitions of the initial formalism implements T-timed \(PNs\) (\(TPNs\)). An analytical presentation of different classes of \(TPNs\) (such as bounded and unbounded) can be found in [30]. In the general case, \(TPNs\) are defined as \(\{P,T,I,O,m_{0},D\}\), with the first five elements of the formal definition responding exactly to the same features as in the case of \(OPNs\) and \(D\) representing time delays that are functions from the set of non-negative real numbers [29,31]. The main structural elements (building blocks) of a Petri net are the following:  
* **Discrete Places** (\(\bigcirc\)) that describe system states (represent conditions, e.g., for control purposes) or resource availability. * **Discrete Transitions** (\(\blacksquare\)) that represent events or actions that change system states. * **Tokens** (\(\bullet\)) describe the dynamic condition of the system. Tokens reside in places, move through transitions and define the marking of the net. Tokens and their movement through transition firing enable the simulation of the models. * Standard arcs, usually drawn as (\(\longrightarrow\)), representing connections between entities, define flows of materials, sequence of events, etc. - Inhibitor arcs are represented by arcs whose end is marked with a small circle (\(\multimap\)). Inhibitor arcs disable transitions when input places connected to them contain number of tokens equal to their weight. - Test arcs are represented as arcs with dotted line (\(\multimap\)).