Symmetry Reduction Algorithms for Data Symmetries

Reference:

Tommi Junttila. Symmetry reduction algorithms for data symmetries. Research Report A72, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, May 2002.

Abstract:

The core problem in the symmetry reduction method for state space analysis is to decide whether two states are symmetric or to produce a symmetric representative state for a state. This report presents algorithms for the problem under data symmetries. The setting covers systems described in the Mur language or in terms of high-level Petri nets. The first two algorithms are based on refining ordered partitions by using symmetry respecting invariants. The last algorithm exploits existing graph isomorphism algorithms that are then applied on characteristic graphs of states, i.e. graphs corresponding to the states in a symmetry respecting way. Some experimental results are also reported.

Keywords:

Symmetry, reachability analysis, Petri nets, the Mur tool

Suggested BibTeX entry:

@techreport{HUT-TCS-A72,
    address = {Espoo, Finland},
    author = {Tommi Junttila},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {May},
    number = {A72},
    pages = {49},
    title = {Symmetry Reduction Algorithms for Data Symmetries},
    type = {Research Report},
    year = {2002},
}