@inproceedings{382c7ba23b72418988c84b8b4ef763c6,
title = "Partial order reduction and symmetry with multiple representatives",
abstract = "Symmetry reduction is one of the most successful techniques to cope with the state explosion problem in model-checking. One of the central issues in symmetry reduction is the problem of finding unique (canonical) representatives of equivalence classes of symmetric states. This problem is equivalent to the graph isomorphism problem, for which no polynomial algorithm is known. On the other hand finding multiple (non-canonical) representatives is much easier because it usually boils down to sorting algorithms. As a consequence, with multiple representatives one can significantly improve the verification times. In this paper we show that symmetry reduction with multiple representatives can be combined with partial order reduction, another efficient state space reduction technique. To this end we introduce a new weaker notion of independence which requires confluence only up to bisimulation.",
author = "D. Bosnacki and M. Scheffer",
year = "2015",
month = apr,
day = "8",
doi = "10.1007/978-3-319-17524-9_8",
language = "English",
isbn = "978-3-319-17523-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "97--111",
editor = "K. Havelund and G. Holzmann and R. Joshi",
booktitle = "NASA Formal Methods Symposium",
address = "Germany",
note = "7th NASA Formal Methods Symposium (NFM 2015), April 27-29, 2015, Pasadena, CA, USA, NFM 2015 ; Conference date: 27-04-2015 Through 29-04-2015",
}