VSL Publications

Transparent Partial Order Reduction

Stephen F. Siegel, Transparent Partial Order Reduction, Technical Report UD-CIS-2011/05, Department of Computer & Information Sciences, University of Delaware, May 17, 2011. This article will appear in Formal Methods in System Design.
Partial Order Reduction (POR) techniques improve the basic model checking algorithm by reducing the numbers of states and transitions explored in verifying a property of the model. In the ample set POR framework for the verification of an LTL-X formula f, one associates to each state s a subset T_s of the set of all transitions enabled at s. The approach requires that whenever T_s is a proper subset, the transitions in T_s must be invisible, i.e., their execution can never change the truth values of the atomic propositions occurring in f. In this paper, we show that the invisibility restriction can be relaxed: for propositions that only occur negatively in f, it suffices that the transitions in T_s merely never change the truth value from true to false, and for those that occur only positively, from false to true. This opens up opportunities for reduction, in many commonly occurring scenarios, that would not be allowed by the stricter invisibility criterion.
  1. transparent_tr_2011.pdf (paper)
  2. tmc-repo.tgz (experimental archive with TMC source code)
Related Links
  1. Version on publisher's web site
  2. 2007 Version
  author = "Stephen F.\ Siegel",
  title = "Transparent Partial Order Reduction",
  institution = {Department of Computer and Information Sciences, University of Delaware},
  year = {2011},
  number = {UDEL-CIS-2011/05}

VSL | Publications