Exploring the scope for partial order reduction
Date
2009
Authors
Geldenhuys J.
Hansen H.
Valmari A.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Partial order reduction methods combat state explosion by exploring only a part of the full state space. In each state a subset of enabled transitions is selected using well-established criteria. Typically such criteria are based on an upper approximation of dependencies between transitions. An additional heuristic is needed to ensure that currently disabled transitions stay disabled in the discarded execution paths. Usually rather coarse approximations and heuristics have been used, together with fast, simple algorithms that do not fully exploit the information available. More powerful approximations, heuristics, and algorithms had been suggested early on, but little is known whether their use pays off. We approach this question, not by trying alternative methods, but by investigating how much room the popular methods leave for better reduction. We do this via a series of experiments that mimic the ultimate reduction obtainable under certain conditions. © 2009 Springer-Verlag Berlin Heidelberg.
Description
Keywords
Alternative methods, Execution paths, Partial order reductions, SIMPLE algorithm, State explosion, State space, Upper approximation, Heuristic methods, Approximation algorithms
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
5799 LNCS
5799 LNCS