New Canonical Representative Marking Algorithms for Place/Transition-Nets

Reference:

Tommi Junttila. New canonical representative marking algorithms for place/transition-nets. Research Report A75, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, October 2002.

Abstract:

Symmetries of a Place/Transition-net can be exploited during the reachability analysis by considering only one representative marking in each orbit induced by the symmetries. In this report, three new algorithms for transforming a marking into a symmetric canonical representative marking are described. All the algorithms depend on the precalculation of a Schreier-Sims representation for the symmetry group of the net in question. The first algorithm uses a black box graph canonizer algorithm to produce a canonical version of the characteristic graph associated with a marking and then derives the canonical representative marking from it. The second algorithm is a backtrack search in the Schreier-Sims representation, pruning the search with the marking in question and its stabilizers found during the search. The third algorithm combines the first and second one by pruning the search in the Schreier-Sims representation with an ordered partition obtained with a standard preprocessing technique applied in graph isomorphism algorithms.

Keywords:

Reachability analysis, Place/Transition-nets, symmetry

Suggested BibTeX entry:

@techreport{HUT-TCS-A75,
    address = {Espoo, Finland},
    author = {Tommi Junttila},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {October},
    number = {A75},
    pages = {37},
    title = {New Canonical Representative Marking Algorithms for Place/Transition-Nets},
    type = {Research Report},
    year = {2002},
}

PostScript (1 MB)
GZipped PostScript (545 kB)
PDF (460 kB)