### Abstract

LTSMIN provides a framework in which state space generation can be distributed easily over many cores on a single compute node, as well as over multiple compute nodes. The tool works on the basis of a vector representation of the states; the individual cores are assigned the task of computing all successors of states that are sent to them. In this paper we show how this framework can be applied in the case where states are essentially graphs interpreted up to isomorphism, such as the ones we have been studying for GROOVE. This involves developing a suitable vector representation for a canonical form of those graphs. The canonical forms are computed using a third tool called BLISS. We combined the three tools to form a system for distributed state space generation based on graph grammars. We show that the time performance of the resulting system scales well (i.e., close to linear) with the number of cores. We also report surprising statistics on the memory
consumption, which imply that the vector representation used to store graphs in LTSMIN is more compact than the representation used in GROOVE.

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

Title of host publication | Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010) |

Editors | J. De Lara, D. Varro |

Place of Publication | Berlin |

Publisher | European Association of Software Science and Technology (EASST) |

Pages | 8 |

Number of pages | 12 |

Publication status | Published - Sep 2010 |

Event | Fourth International Workshop on Graph-Based Tools, GraBaTs 2010: Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010) - University of Twente, Enschede, Netherlands Duration: 28 Sep 2010 → 28 Sep 2010 Conference number: 4 |

### Publication series

Name | Electronic Communications of the EASST |
---|---|

Publisher | European Association of Software Science and Technology (EASST) |

Number | WP 10-06 |

Volume | 32 |

ISSN (Print) | 1863-2122 |

ISSN (Electronic) | 0929-0672 |

### Conference

Conference | Fourth International Workshop on Graph-Based Tools, GraBaTs 2010 |
---|---|

Abbreviated title | GraBaTs 2010 |

Country | Netherlands |

City | Enschede |

Period | 28/09/10 → 28/09/10 |

Other | 28 September 2010 |

### Keywords

- IR-75906
- METIS-275864
- Symmetry Reduction
- State Space Generation
- EWI-19393
- Graph Transformation
- Distributed Computing
- GROOVE
- CR-D.2.4
- LTSMIN

## Cite this

Blom, S., Kant, G., & Rensink, A. (2010). Distributed Graph-Based State Space Generation. In J. De Lara, & D. Varro (Eds.),

*Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010)*(pp. 8). (Electronic Communications of the EASST; Vol. 32, No. WP 10-06). Berlin: European Association of Software Science and Technology (EASST).