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.

- transparent_tr_2011.pdf (paper)
- tmc-repo.tgz (experimental archive with TMC source code)

@TechReport{siegel:2011:transparent-tr, 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