Loading...
Please wait, while we are loading the content...
Construction of Occurrence Graphs with Permutation Symmetries Aided by the Backtrack Method (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Jørgensen, Jens Baek Jrgensen, Jens Baek |
| Abstract | This paper recalls the concept of occurrence graphs with permutation symmetries (OS-graphs) for Coloured Petri Nets. It is explained how so-called self-symmetries can help to speed up construction of OSgraphs. 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 computational 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. 1 Introduction Verification by occurrence graphs (also known as state spaces and reachability graphs) is obstructed by the well-known state explosion problem: Even for relatively small systems, the occurrence graphs are often so large... |
| File Format | |
| Language | English |
| Publisher Date | 1997-01-01 |
| Publisher Department | Computer Science Department, University of Aarhus |
| Access Restriction | Open |
| Subject Keyword | Occurrence Graph Backtrack Method Permutation Symmetry Aided Coloured Petri Net State Space Computational Group Theory Permutation Symmetry New Method Introduction Verification Encouraging Experimental Performance Measure Reachability Graph So-called Self-symmetries Important General Complexity Property Well-known State Explosion Problem Small System Backtrack Search So-called Backtrack Algorithm |
| Content Type | Text |
| Resource Type | Technical Report |
