Title :
Exploiting stabilizers and parallelism in state space generation with the symmetry method
Author :
Lorentsen, Louise ; Kristensen, Lars Michael
Author_Institution :
Dept. of Comput. Sci., Aarhus Univ., Denmark
Abstract :
The symmetry method is a main reduction paradigm for alleviating the state explosion problem. For large symmetry groups deciding whether two states are symmetric becomes time expensive due to the apparent high time complexity of the orbit problem. The contribution of this paper is to alleviate the negative impact of the orbit problem by the specification of canonical representatives for equivalence classes of states in Coloured Petri Nets, and by giving algorithms exploiting stabilizers and parallelism for computing the condensed state space
Keywords :
Petri nets; computational complexity; equivalence classes; parallel algorithms; state-space methods; Coloured Petri Nets; complexity; computational complexity; concurrent systems; equivalence classes; orbit problem; parallel algorithm; state explosion; state space; state space methods; symmetry groups; Computational complexity; Computer science; Concurrent computing; Explosions; Logic; Parallel processing; Petri nets; Safety; Space exploration; State-space methods;
Conference_Titel :
Application of Concurrency to System Design, 2001. Proceedings. 2001 International Conference on
Conference_Location :
Newcastle upon Tyne
Print_ISBN :
0-7695-1071-X
DOI :
10.1109/CSD.2001.981778