[2N6-GS-1] Fundamental AI, theory: Constraint satisfaction and optimization

[2N6-GS-1-01] Effective Symmetry Reduction based on Graph Automorphism in Graph-Based Model Checking

〇Yutaro Tsunekawa¹, Kazunori Ueda² (1. Graduate School of Fundamental Science and Engineering, Waseda University, 2. Faculty of Science and Engineering, Waseda University)

Keywords:Model Checking, Graph Rewriting System, State Space Search

In model checking, the state explosion problem is an important issue.
Symmetry Reduction is a state space reduction method that exploits symmetry.
SLIM, which is a model checker based on graph rewriting, reduces a state space by Symmetry Reduction that exploits the symmetry of the graph structure, but the frequently occurring graph isomorphism testing becomes a bottleneck in execution time performance.
In this research, we propose a method to achieve efficient Symmetry Reduction by reducing the number of graph isomorphism testing using graph automorphism during search. This method focuses on the fact that the result of rewriting an automorphic part in a graph is always symmetric in the state space, and reduces the number of graph isomorphism testing. We implemented this method on a model checker SLIM, and confirmed that the complexity of the number of graph isomorphism testing decreased for a highly symmetric model.