Symmetry Reduction Algorithms for Data Symmetries

摘要

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 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.