Technical Report Details
| Date |
20-7-2011 |
| Number |
DISI-TR-11-04 |
| Title |
On the Decidability Status of Reachability and Coverability in Graph Transformation Systems |
| Authors |
Natalie Bertrand, Giorgio Delzanno, Barbara Koenig, Arnaud Sangnier, Jan Stuckrath |
| Bibtex Entry |
|
| E-mail |
delzanno@disi.unige.it |
| Link |
http://www.disi.unige.it/person/DelzannoG/Papers/gts.pdf |
| 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.
26/3/2012
Updated version of a previous version
Viewing Graph Transformation through the Algorithmic Lens
Old version |
|
|
 |
