Partial order reduction and Compositionality

Henri Hansen ( Tampere University of Technology )

Partial order reduction, in explicit state space generation, refers to a set of techniques that allow the exploration of only a part of the state space, while preserving all the relevant executions of a system. The most common methods achieve this by eliminating part of the outgoing transitions in each state.

The effectiveness of partial order reduction depends on how accurately depencies and causalities between transitions are mapped. I discuss an approach of using compositional analysis to cut the cost in analysing global dependencies and causalities.