Reachability analysis of a class of Petri nets using place invariants and siphons

Abstract

This paper proposes a novel and computationally efficient approach to deal with the reachability problem by using place invariants and strict minimal siphons for a class of Petri nets called pipe-line nets (PLNs). First, in a PLN with an appropriate initial marking, the set of invariant markings and the set of strict minimal siphons are enumerated. Then a sufficient and necessary condition is developed to decide whether a marking is spurious by analysing the number of tokens in operation places of any strict minimal siphon and their bounds. Furthermore, an algorithm that generates the reachable markings by removing all the spurious markings from the set of invariant markings is proposed. Finally, experimental results show the efficiency of the proposed method.

Keywords

• Petri nets
• strict minimal siphons
• place invariants
• reachability analysis
• flexible manufacturing system