IEEE Transactions on Parallel and Distributed Systems · 1996 · 70 citations · 33 references
ComputingComputer EngineeringComputer ScienceFormal MethodsSchedulingSystems ArchitecturePetri NetsTask ModelsDeadlockDeadlock AnalysisDeadlock DetectionPetri Net AnalysisPetri Net ModelsReachabilityReachability AnalysisState-space Reduction
As part of our continuing research on using Petri nets to support automated analysis of Ada tasking behavior, we have investigated the application of Petri net reduction for deadlock analysis. Although reachability analysis is an important method to detect deadlocks, it is in general inefficient or even intractable. Net reduction can aid the analysis by reducing the size of the net while preserving relevant properties. We introduce a number of reduction rules and show how they can be applied to Ada nets, which are automatically generated Petri net models of Ada tasking. We define a reduction process and a method by which a useful description of a detected deadlock state can be obtained from the reduced net's information. A reduction tool and experimental results from applying the reduction process are discussed.
33
Petri nets: Properties, analysis and applications
T. Murata · Proceedings of the IEEE · 1989 · 10.5K citations
Symbolic model checking: 1020 States and beyond
Jerry R. Burch, E. M. Clarke, Kenneth L. McMillan et al. · Information and Computation · 1992 · 2.7K citations
A stubborn attack on state explosion
Antti Valmari · Formal Methods in System Design · 1992 · 575 citations