2026-07-20T05:47:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3487 2024-03-06T10:34:16Z ddc:004 open_access

On the Decidability Status of Reachability and Coverability in Graph Transformation Systems Bertrand, Nathalie Delzanno, Giorgio König, Barbara Sangnier, Arnaud Stückrath, Jan decidability reachability graph transformation coverability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathalie Bertrand and Giorgio Delzanno and Barbara König and Arnaud Sangnier and Jan Stückrath 2012 Is Part Of LIPIcs, Volume 15, 23rd International Conference on Rewriting Techniques and Applications (RTA'12) (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2012.101 urn:nbn:de:0030-drops-34871 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2012.101 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode