# Dealing with Deadlocks in Industrial Multi Agent Systems
## 2 Preliminaries  
Firstly, it is necessary to introduce several basic definitions. First, one is the author own definition extracted from knowledge published in [7; 16], next three are the standard elementary definitions of \(P\)-invariants, siphons, and traps from the classical literature about Petri nets [4; 5]. Last two definitions are taken over from [7]. **Definition 1**. : _A Petri net is a bipartite directed graph (BDG). It may be formally described by the quadruplet \(N=(P,T,F,W)\). Here, \(P\) and \(T\) are finite nonempty sets, namely \(P\) is a set of places (\(|P|=n\)), representing the first kind of BDG nodes, and \(T\) is a set of transitions (\(|T|=m\)), representing the second kind of BDG nodes. It is valid that \(P\cup T\
eq\emptyset\) and \(P\cap T=\emptyset\). The set \(F=(P\times T)\cup(T\times P)\) is the flow relation of the net \(N\). It is expressed by directed arcs from places to transitions and vice versa. The mapping \(W:(P\times T)\cup(T\times P)\to\mathbb{N}\) assigns weights to directed arcs. The weight of an arc \(f:W(f)>0\) if \(f\in F\) and \(W(f)=0\) otherwise. Here \(\mathbb{N}=\{0,1,2,...\}\), i.e., it contains natural numbers plus zero. The Petri net \(N=(P,T,F,W)\) is named ordinary and denoted as \(N=(P,T,F)\) if \(\forall f\in F\), \(W(f)=1\). \(N\) is called generalized if \(\exists f\in F\), \(W(f)>1\). Petri net is called a state machine if, and only if, (iff) \(\forall t\in T\), \(|^{\bullet}t|=|t^{\bullet}|=1\), i.e., when each transition has only one input place and only one output place._  
A mapping from \(P\) to \(\mathbb{N}\) is a marking \(M\) of \(N\). The marking \(M(p)\) means the number of tokens located in the place \(p\). Thus, we may say that the place \(p\) is marked by a marking \(M\)_iff_\(M(p)>0\). In case of a subset \(S\subseteq P\) we say that it is marked by \(M\)_iff_ at least one place in \(S\) is marked by \(M\). The sum of tokens located in all places of \(S\) is \(M(S)=\sum_{p\in S}M(p)\). \(S\) is empty at \(M\)_iff_\(M(S)=0\). The pair \((N,M_{0})\) is called the marked net or a net system. Here, \(M_{0}\) is an initial marking of \(N\). PN marking is evolved as follows  
\[\mathbf{M}_{k+1}=\mathbf{M}_{k}+\mathbf{N}.\vec{\sigma}_{k},\ k\in\mathbb{N}, \tag{1}\]  
with \(\mathbf{M}_{0}=(M_{0}(p_{1}),M_{0}(p_{1}),\ldots,M_{0}(p_{n})^{T}\) being the \((n\times 1)\) initial marking. Here, \(\mathbf{N}\) is the \((n\times m)\)-dimensional incidence matrix based on the set \(F\) and \(\vec{\sigma}_{k}\) is a \((m\times 1)\)-dimensional firing vector (the binary vector, where its entry with the value \(1\) denotes the corresponding transition \(t\in T\) able to be fired). \(M(p)\) denotes (as it was already mentioned above) the number of tokens in place \(p\). \((n\times 1)\) marking vectors \(\mathbf{M}\) are sometimes named also as _state vectors_. \(\mathbf{N}=\mathbf{N}^{+}-\mathbf{N}^{-}\), where \(\mathbf{N}^{+}=\mathbf{Post}\) and \(\mathbf{N}^{-}=\mathbf{Pre}\) are, respectively, the output flow matrix and the input flow matrix. In other words, the matrix representing the output of transitions to places and the matrix representing the input of places to transitions. For economy of space, in general, markings and vectors can be described by the formal sum notation. Thus, \(\sum_{p\in P}M(p)p\) denotes the vector \(\mathbf{M}\). For example, in a net with \(P=\{p_{1},\ldots,p_{5}\}\) a marking where in \(p_{2}\) are \(3\) tokens and in \(p_{3}\) are \(2\) tokens may be written as \(3p_{2}+2p_{3}\) instead of the vector notation \((0,3,2,0,0)^{T}\). Definition 2: A vector \(\mathbf{I}\) is a place invariant \(P\) (shortly, \(P\)-invariant) of PN iff \(\mathbf{I}\
eq\mathbf{0}\) and \(\mathbf{I}^{T}.\mathbf{N}=\mathbf{0}^{T}\). Here, \(\mathbf{N}\) is the incidence matrix of \(N\). Definition 3: Any set \(S\subseteq P\), \(S\
eq\emptyset\) with \({}^{\bullet}S\subseteq S^{\bullet}\) is said to be a siphon. [PERSON] said, if every transition having an output place in \(S\) has an input place in \(S\).