Affiliations: Institute of Computer Science, ICS PAS, Warsaw, Poland. {penczek, mszreter}@ipipan.waw.pl | Intel Microprocessor Products Group, Strategic CAD Laboratories (SCL), USA. [email protected] | Eindhoven University of Technology, Eindhoven, The Netherlands. [email protected]
Note: [] Partly supported by Esprit under the grant No. 20288 CRIT-2. Address for correspondence: Institute of Computer Science, ICS PAS, Warsaw, Poland
Note: [] The research presented in this paper was done while the author was a member of the Department of Mathematics and Computing Science, Eindhoven Univeristy of Technoogy. Address for correspondence: Intel Architecture Business Group, Strategic CAD Laboratories (SCL), 5200 NE Elam Young Parkway JFT-104, Hillsboro, OR 97124-6497, USA
Note: [] Address for correpondence: Eindhoven University of Technology, Eindhoven, The Netherlands
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:−X*, 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. Moreover, we prove that reduction for concurrency fair version of ACTL−X* is more efficient than for ACTL−X*.
