On Deadlock Analysis and Characterization of Labeled Petri Nets with Undistinguishable and Unobservable Transitions

This work addresses the analysis and characterization of deadlocks in discrete-event systems modeled by labeled Petri nets (LPNs) with undistinguishable and unobservable transitions. To provide a solution for the notorious problem, it is essential to present an effective characterization such that deadlock control and synthesis are technically and methodologically possible. To this end, we introduce the notion of dangerous implicit vectors (DIVs) which implicitly threaten the system deadlock-freedom. The set of dead markings is divided into two subsets: dead basis markings (DBMs) and dangerous implicit markings (DIMs). An algorithm is designed to compute the sets of DIVs and DIMs at a given basis state of a system. Moreover, by virtue of linear algebraic equations, we formulate sufficient conditions to identify the existence of blocking markings in an LPN. Finally, an algorithm is developed to construct an observed graph that is a compact representation of the reachability graph of a Petri net with respect to the existence of dead reaches. At the end of this paper, experiment results that illustrate the correctness and effectiveness of the reported solution are presented.