### Abstract

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

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

}

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

**Isomorphism Checking for Symmetry Reduction.** / Rensink, Arend.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Isomorphism Checking for Symmetry Reduction

AU - Rensink, Arend

PY - 2010/4

Y1 - 2010/4

N2 - 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.

AB - 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.

KW - IR-72369

KW - EWI-18117

KW - METIS-270902

M3 - Report

T3 - CTIT Technical Report Series

BT - Isomorphism Checking for Symmetry Reduction

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -