A Reduced State-Space Generation Method for Concurrent Systems Based on CPN-PR Model

Colored Petri nets (CPNs) provide descriptions of the concurrent behaviors for software and hardware. Model checking based on CPNs is an effective method to simulate and verify the concurrent behavior in system design. However, the model-checking method traverses the full state space, which suffers from the state-space explosion problem. A reduced state-space generation method related to the property of concurrent systems is proposed. Specifically, we extend CPNs to define a property-related model (CPN-PR) and give a property-related analysis method whose results can be used to generate the CPN-PR model. A reduced state-space generation method is developed based on enabled binding element filtering rules. The stutter trace equivalence between the state spaces of CPN and CPN-PR has been proven by showing that the reduced state space may not change the model-checking result. A comparison experiment is conducted to demonstrate the effectiveness of our method.