License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2012.101
URN: urn:nbn:de:0030-drops-34871
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3487/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Delzanno, Giorgio ; König, Barbara ; Sangnier, Arnaud ; Stückrath, Jan

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

pdf-format:
10.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2012:3487,
  author =	{Nathalie Bertrand and Giorgio Delzanno and Barbara K{\"o}nig and Arnaud Sangnier and Jan St{\"u}ckrath},
  title =	{{On the Decidability Status of Reachability and Coverability in  Graph Transformation Systems}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12) },
  pages =	{101--116},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Ashish Tiwari},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3487},
  URN =		{urn:nbn:de:0030-drops-34871},
  doi =		{10.4230/LIPIcs.RTA.2012.101},
  annote =	{Keywords: decidability, reachability, graph transformation, coverability}
}

Keywords: decidability, reachability, graph transformation, coverability
Collection: 23rd International Conference on Rewriting Techniques and Applications (RTA'12)
Issue Date: 2012
Date of publication: 29.05.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI