### Abstract

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

*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).

}

*Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010).*Electronic Communications of the EASST, no. WP 10-06, vol. 32, European Association of Software Science and Technology (EASST), Berlin, pp. 8, Fourth International Workshop on Graph-Based Tools, GraBaTs 2010, Enschede, Netherlands, 28/09/10.

**Distributed Graph-Based State Space Generation.** / Blom, Stefan; Kant, Gijs; Rensink, Arend.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Distributed Graph-Based State Space Generation

AU - Blom, Stefan

AU - Kant, Gijs

AU - Rensink, Arend

N1 - Fourth International Workshop on Graph-Based Tools (GraBaTs 2010), Enschede, The Netherlands, 28 September 2010

PY - 2010/9

Y1 - 2010/9

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

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

KW - IR-75906

KW - METIS-275864

KW - Symmetry Reduction

KW - State Space Generation

KW - EWI-19393

KW - Graph Transformation

KW - Distributed Computing

KW - GROOVE

KW - CR-D.2.4

KW - LTSMIN

M3 - Conference contribution

T3 - Electronic Communications of the EASST

SP - 8

BT - Proceedings of the Fourth International Workshop on Graph-Based Tools (GraBaTs 2010)

A2 - De Lara, J.

A2 - Varro, D.

PB - European Association of Software Science and Technology (EASST)

CY - Berlin

ER -