Abstract | ||
---|---|---|
Symmetry reduction is a technique to counter state explo- sion for systems of regular structure. It relies on idealistic assumptions about indistinguishable components, which in practice may only be sim- ilar. In this paper we present a flexible algebraic approach to symmetry reduction for exploring a structure without any prior knowledge about its global symmetry. The more behavior is shared among the components, the more compression takes effect. The idea is to annotate each encoun- tered state with information about how symmetry is violated along the path leading to it. Previous solutions only allow specific types of asymme- try, such as up to bisimilarity, or seem to require expensive preprocessing of the structure. In contrast, our method appeals through its balance be- tween generality and simplicity. We include analytic and experimental results to document its efficiency. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-73368-3_43 | Computer Aided Verification |
Keywords | Field | DocType |
global symmetry,method appeal,generalized algebraic approach,large overhead,symmetry reduction,state explosion,adaptive symmetry reduction,indistinguishable component,regular structure,idealistic assumption | Kripke structure,Global symmetry,Algebraic number,Computer science,Algorithm,Symmetry reduction,Asymmetry,Generality | Conference |
Volume | ISSN | Citations |
4590 | 0302-9743 | 5 |
PageRank | References | Authors |
0.45 | 10 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thomas Wahl | 1 | 103 | 10.21 |