On the Decidability Status of Reachability and Coverability in Graph Transformation Systems

Nathalie Bertrand, Giorgio Delzanno, Barbara KöNig, Arnaud Sangnier & Jan Stückrath
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...