On calculation of state space for linear system of simple sequential processes with resources
Liang Hong, Xiaohua Wang, Xun Li, Zebin Su, Dan Zhang, Yufeng Chen · Advances in Mechanical Engineering · 2017
This work focuses on the calculation of state space for linear system of simple sequential processes with resources (LS3PR). The method, different from reachability graphs rendering high computational complexity, finds reachable markings by combinatorics. First, the set of invariant markings can be obtained by combinatorics if the influence of deadlocks is ignored. Unfortunately, some of reachable states in the set of invariant markings are proved to be spurious if deadlocks exist. Second, we find the spurious markings by computing a set of minimal spurious markings, which can be calculated by a proposed algorithm based on strict minimal siphons. The obtained spurious markings are proved to cover all the spurious markings of the LS3PR. Removing the spurious markings from the set of invariant markings, the left ones constitute the state space of the LS3PR. The detailed method is shaped to an algorithm. The effectiveness of the algorithm is proved by example calculation and analysis. Finally, we analyze the computational complexity of the proposed method compared with reachability graphs.