LIPIcs.RTA.2012.101.pdf
- Filesize: 0.54 MB
- 16 pages
Document
On the Decidability Status of Reachability and Coverability in Graph Transformation Systems
Authors
-
Part of:
Volume:
23rd International Conference on Rewriting Techniques and Applications (RTA'12) (RTA 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Rewriting Techniques and Applications (RTA) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-05-29
Cite As Get BibTex
Nathalie Bertrand, Giorgio Delzanno, Barbara König, Arnaud Sangnier, and Jan Stückrath. On the Decidability Status of Reachability and Coverability in Graph Transformation Systems. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 101-116, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.RTA.2012.101
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.
Subject Classification
Keywords
- decidability
- reachability
- graph transformation
- coverability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads