### Abstract

In this paper, we show how isomorphism checking can be used as an effective technique for symmetry reduction. Reduced state spaces are equivalent to the original ones under a strong notion of bisimilarity which preserves the multiplicity of outgoing transitions, and therefore also preserves stochastic temporal logics. We have implemented this in a setting where states are arbitrary graphs. Since no efficiently computable canonical representation is known for arbitrary graphs modulo isomorphism, we define an isomorphism-predicting hash function on the basis of an existing partition refinement algorithm. As an example, we report a factorial state space reduction on a model of an ad-hoc network connectivity protocol.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Centre for Telematics and Information Technology (CTIT) |

Number of pages | 15 |

Publication status | Published - Apr 2010 |

### Publication series

Name | CTIT Technical Report Series |
---|---|

Publisher | Centre for Telematics and Information Technology, University of Twente |

No. | TR-CTIT-10-27 |

ISSN (Print) | 1381-3625 |

### Keywords

- IR-72369
- EWI-18117
- METIS-270902

## Cite this

Rensink, A. (2010).

*Isomorphism Checking for Symmetry Reduction*. (CTIT Technical Report Series; No. TR-CTIT-10-27). Enschede: Centre for Telematics and Information Technology (CTIT).