2015/11/03 by Arend Rensink, Rensink, Arend
Computer Science · #Embedded Systems Design Techniques #Formal Methods in Verification #Model-Driven Software Engineering Techniques
paper · doi:10.14279/tuj.eceasst.1.77
openalex publication_date 2024/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/01
In this paper we show how isomorphism checking can be used as an effective technique for symmetry reduction in graph-based state spaces, despite the inherent complexity of the isomorphism problem. In particular, we show how one can use /element-based graph certificate mappings/ to help in recognising non-isomorphic graphs. These are mappings that assign to all elements (edges and nodes) of a given graph a number that is invariant under isomorphism, in the sense that any isomorphism between graphs is sure to preserve this number. The individual element certificates of a graph give rise to a certificate for the entire graph, which can be used as a hash key for the graph; hence, this yields a heuristic to decide whether a graph has an isomorphic representative in a previously computed set of graphs. We report some experiments that show the viability of this method.