Husnu Yenigun

Bell Labs


Static Partial Order Reduction

Room 2C-542
January 8, 1998 at 12:30 PM

Abstract:

We describe an algorithm which computes a partial order reduction of an asynchronous model statically, from the model transition relation. The reduction is implemented by a constraint on the model's transition relation. The constraint is computed through a data flow analysis of the transition relation, prior to state reachability analysis. The constrained transition relation then can be analyzed by any conventional model-checking algorithm, in particular, model-checking implemented by symbolic state enumeration.