10.4230/LIPICS.RTA.2012.101
Bertrand, Nathalie
Nathalie
Bertrand
Delzanno, Giorgio
Giorgio
Delzanno
König, Barbara
Barbara
König
Sangnier, Arnaud
Arnaud
Sangnier
Stückrath, Jan
Jan
Stückrath
On the Decidability Status of Reachability and Coverability in Graph Transformation Systems
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2012
Article
decidability
reachability
graph transformation
coverability
Tiwari, Ashish
Ashish
Tiwari
2012
2012-05-29
2012-05-29
2012-05-29
en
urn:nbn:de:0030-drops-34871
10.4230/LIPIcs.RTA.2012
978-3-939897-38-5
1868-8969
10.4230/LIPIcs.RTA.2012
LIPIcs, Volume 15, RTA 2012
23rd International Conference on Rewriting Techniques and Applications (RTA'12)
2013
15
10
101
116
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Tiwari, Ashish
Ashish
Tiwari
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2012
15
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
16 pages
576013 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 15, 23rd International Conference on Rewriting Techniques and Applications (RTA'12), pages 101-116