DocumentCode :
2211695
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
fYear :
2001
fDate :
2001
Firstpage :
211
Lastpage :
220
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/CSD.2001.981778
Filename :
981778
Link To Document :
بازگشت