1Petri nets analysis: Complexity and finite coverability graph in modular design

Summary: The Petri net is a very efficient model to describe and analyse the behaviour of Discrete Event Systems. However, faced to the complexity, modular design is needed to deal with large systems. The coverability graph is a useful tool allowing to analyse system’s properties. But its capacities are limited to finite coverability graph merging for modular design. This paper studies the temporal complexity of finite coverability graph construction using the minimal coverability graph algorithm. It focuses on modular design using shared transitions and concludes on the advantages and drawbacks of this class of approach