Rob Gerth, Ruurd Kuiper, Wojciech Penczek

Partial Order Reductions Preserving Simulations

843

Abstract

The "state explosion problem" can be alleviated by using partial order reduction techniques. These methods rely on expanding only a fragment of the full state space of a program, which is sufficient for verifying the formulas of temporal logics LTL-X or CTL*-X (i.e., LTL or CTL* without the next state operator). This is guaranteed by preserving either a stuttering maximal trace equivalence or a stuttering bisimulation between the full and the reduced state space. Since a stuttering bisimulation is much more restrictive than a stuttering maximal trace equivalence, resulting in less powerful reductions for CTL*-X, we study here partial order reductions that preserve equivalences "in-between", in particular a stuttering simulation which is induced by the universal fragment of CTL*, called ACTL*-X. The reductions generated by our method preserve also branching simulation and weak simulation, but surprisingly, they do not appear to be included into the reductions obtained by Peled's method for verifying LTL-X properties. Therefore, in addition to ACTL*-X reduction method we suggest also an improvement of the LTL-X reduction method.

Key words: distributed systems, automated verification, state explosion, partial order reductions, temporal logic, stuttering simulations.