Construction of Occurrence Graphs with Permutation Symmetries Aided by the Backtrack Method

Abstract

This paper recalls the concept of occurrence graphs with permuta- tion symmetries (OS-graphs) for Coloured Petri Nets. It is explained how so-called self-symmetries can help to speed up construction of OS- graphs. The contribution of the paper is to suggest a new method for calculation of self-symmetries, the Backtrack Method. The method is based on the so-called Backtrack Algorithm, which originates in com- putational group theory. The suggestion of the method is justified, both by identifying an important general complexity property and by obtaining encouraging experimental performance measures.

Topics. Coloured Petri Nets, reduced state spaces, occurrence graphs with permutation symmetries, self-symmetries, computational group theory, backtrack searches.