## 2 Preliminaries
### Identify All FBMs  
In the Reachability Graph (RG) method, all reachable markings in the initial reachability graph analysis can be divided into two main groups: illegal and legal markings [35]. Illegal markings include deadlock and quasi-deadlock markings. The set of deadlock markings \(M_{D}\) is defined as follows:  
**Definition 1**[35].: _The set of deadlock markings \(\mathcal{M}_{D}\)= {M\(\in\)R(N, \(M_{0}\))} at M; no transition can be enabled}._  
The quasi-deadlock markings are defined as follows:  
**Definition 2**[35].: _The set of quasi-deadlock markings \(\mathcal{M}_{Q}\)= {M\(\in\)R(N, \(M_{0}\))} \(M\) must eventually evolve into a dead one regardless of transition firing sequences)._  
The reachable markings, not including quasi-deadlock and deadlock markings, are called legal markings. The set of legal markings \(\mathcal{M}_{L}\) is the maximal number of reachable markings of a system, from which the initial marking \(M_{0}\) is reachable without leaving \(\mathcal{M}_{L}\). Further, the set of legal markings \(\mathcal{M}_{L}\) can be defined as follows:  
**Definition 3**.: \(\mathcal{M}_{L}=\Big{\{}MR(N,\ M_{0})\wedge M\left(M_{D}\cup\ M_{Q}\right) \Big{\}}\)_._  
The \(\left(M_{D}\cap\ M_{Q}\right)\) of Definition 3 signifies the set of illegal markings. Therefore, the set of illegal markings \(\mathcal{M}_{I}\) can be defined as:  
**Definition 4**.: \(\mathcal{M}_{I}=\Big{\{}MR(N,\ M_{0})\wedge M\left(M_{D}\cup\ M_{Q}\right) \Big{\}}\)_._  
Definition 4 means that all dead and quasi-dead markings can also be viewed as the set of illegal markings. Further, \(\mathcal{M}_{I}\) can be reached directly from any legal marking in an RG of a PNM. Please note that the first-met illegal marking is the same as the first-met bad marking (FBM) [1]. In our opinion, the first-met illegal marking (FIM) seems to be superior to the FBM. Therefore, the definition of first-met illegal marking (FIM) is presented formally as follows:  
**Definition 5**.: \(\mathcal{M}_{\text{FIM}}=\{M^{\prime}\big{|}MR(N,\ M_{0}),M\in\mathcal{M}_{L},M ^{\prime}\in\mathcal{M}_{I},tT,\ s.t.\ M[tM^{\prime}\}\)__  
According to an example, one can understand the \(\mathcal{M}_{\text{FIM}}\) easily. Referring to Figure 1, the PNM has two idle places (i.e., \(p_{1}\) and \(p_{8}\), both with three tokens in them), six operation places (\(p_{2}\)\(\sim\)\(p_{6}\)), and three resource places (\(p_{3}\)\(\sim\)\(p_{11}\), all with one token in them). Figure 2 is its reachability graph. In Figure 2, there are 20 reachable markings in total. Further, according to Definitions 1\(\sim\)4, there are 15 \(\mathcal{M}_{L}\) and 5 \(\mathcal{M}_{I}\) (i.e., 2 \(\mathcal{M}_{D}\) and 3 \(\mathcal{M}_{Q}\)) in Figure 2. In this example, all \(\mathcal{M}_{Q}\) (i.e., deadlock marking \(M_{8}\), quasi-deadlock marking \(M_{10}\), quasi-deadlock marking \(M_{11}\), quasi-deadlock marking \(M_{12}\) and deadlock marking \(M_{13}\)) are FIMs since they all fit Definition 5.  
In the following section, an improved deadlock prevention policy with an enhancement of computational efficiency is proposed. In this deadlock policy, just a few FBMs need to be identified. Once the few FBMs in the reachability graph are forbidden, the system is deadlock-free. In other words, under the same number of controllers, the efficiency of our algorithm is better than the MFFP method [1]. The detailed information of the proposed policy is presented as follows.