Paper Details

@InProceedings{VanderMeulenPecheur09,
  title = "{C}ombining {P}artial {O}rder {R}eduction with {B}ounded {M}odel {C}hecking",
  author= "Vander Meulen, José and Pecheur, Charles",
  editor= "Welch, Peter H. and Roebbers, Herman and Broenink, Jan F. and Barnes, Frederick R. M. and Ritson, Carl G. and Sampson, Adam T. and Stiles, G. S. and Vinter, Brian",
  pages = "29--48",
  booktitle= "{C}ommunicating {P}rocess {A}rchitectures 2009",
  isbn= "978-1-60750-065-0",
  year= "2009",
  month= "nov",
  abstract= "Model checking is an efficient technique for verifying
     properties on reactive systems. Partial-order reduction
     (POR) and symbolic model checking are two common approaches
     to deal with the state space explosion problem in model
     checking. Traditionally, symbolic model checking uses BDDs
     which can suffer from space blow-up. More recently bounded
     model checking (BMC) using SAT-based procedures has been
     used as a very successful alternative to BDDs. However,
     this approach gives poor results when it is applied to
     models with a lot of asynchronism. This paper presents an
     algorithm which combines partial order reduction methods and
     bounded model checking techniques in an original way that
     allows efficient verification of temporal logic properties
     (LTL\_X) on models featuring asynchronous processes. The
     encoding to a SAT problem strongly reduces the complexity
     and non-determinism of each transition step, allowing
     efficient analysis even with longer execution traces. The
     starting-point of our work is the Two-Phase algorithm
     (Namalesu and Gopalakrishnan) which performs partial-order
     reduction on process-based models. At first, we adapt this
     algorithm to the bounded model checking method. Then, we
     describe our approach formally and demonstrate its validity.
     Finally, we present a prototypal implementation and report
     encouraging experimental results on a small example."
}

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.