rta12

N. Bertrand, G. Delzanno, B. König, A. Sangnier, J. Stückrath. On the Decidability Status of Reachability and Coverability in Graph Transformation Systems. In 23rd International Conference on Rewriting Techniques and Applications, LIPIcs 15, Pages 101-116, Nagoya, Japan, May 2012.

Download [help]

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

We study decidability issues for reachability problems in graph transformation systems, a powerful infinite-state model. For a fixed initial configuration, we consider reachability of an entirely specified configuration and of a configuration that satisfies a given pattern (coverability). The former is a fundamental problem for any computational model, the latter is strictly related to verification of safety properties in which the pattern specifies an infinite set of bad configurations. In this paper we reformulate results obtained, e.g., for context-free graph grammars and concurrency models, such as Petri nets, in the more general setting of graph transformation systems and study new results for classes of models obtained by adding constraints on the form of reduction rules

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/

BibTex Reference

@InProceedings{rta12,
   Author = {Bertrand, N. and Delzanno, G. and König, B. and Sangnier, A. and Stückrath, J.},
   Title = {On the Decidability Status of Reachability and Coverability in Graph Transformation Systems},
   BookTitle = {23rd International Conference on Rewriting Techniques and Applications},
   Pages = {101--116},
   Series = {LIPIcs 15},
   Address = {Nagoya, Japan},
   Month = {May},
   Year = {2012}
}

EndNote Reference [help]

Get EndNote Reference (.ref)