Reference:
Tommi Junttila. Computational complexity of the place/transitionnet symmetry reduction method. Research Report A59, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, April 2000.
Abstract:
Computational complexity of the subtasks appearing in the symmetry reduction method for Place/Transitionnets is studied. The first task of finding the automorphisms (symmetries) of a net is shown to be polynomial time manyone equivalent to the problem of finding the automorphisms of a graph. The problem of deciding whether two markings are symmetric is shown to be equivalent to the graph isomorphism problem. Surprisingly, this remains to be the case even if the generators for the automorphism group of the net are known. The problem of constructing the lexicographically greatest marking symmetric to a given marking (a canonical representative for the marking) is classified to belong to the lower levels of the polynomial hierarchy, namely to somewhere between FP^NP[log n] and FP^NP. It is also discussed how the selfsymmetries of a marking can be exploited. Calculation of such symmetries is classified to be as hard as computing graph automorphism groups. Furthermore, the coverability version of testing marking symmetricity is shown to be an NPcomplete problem. It is shown that unfortunately canonical representative markings and the symmetric coverability problem cannot be combined in a straightforward way.
Keywords:
Petri nets, symmetry
Suggested BibTeX entry:
@techreport{HUTTCSA59,
address = {Espoo, Finland},
author = {Junttila, Tommi},
institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
month = {April},
number = {A59},
pages = {17},
title = {Computational Complexity of the Place/TransitionNet Symmetry Reduction Method},
type = {Research Report},
year = {2000},
}
