Encoding Incremental NACs in Safe Graph Grammars using Complementation

Andrea Corradini
(Dipartimento di Informatica, University of Pisa, Italy)
Maryam Ghaffari Saadat
(Department of Informatics, University of Leicester, UK)
Reiko Heckel
(Department of Informatics, University of Leicester, UK)

In modelling complex systems with graph grammars (GGs), it is convenient to restrict the application of rules using attribute constraints and negative application conditions (NACs). However, having both attributes and NACs in GGs renders the behavioural analysis (e.g. unfolding) of such systems more complicated. We address this issue by an approach to encode NACs using a complementation technique. We consider the correctness of our encoding under the assumption that the grammar is safe and NACs are incremental, and outline how this result can be extended to unsafe, attributed grammars.

In Berthold Hoffmann and Mark Minas: Proceedings of the Eleventh International Workshop on Graph Computation Models (GCM 2020), Online-Workshop, 24th June 2020, Electronic Proceedings in Theoretical Computer Science 330, pp. 88–107.
Published: 3rd December 2020.

ArXived at: https://dx.doi.org/10.4204/EPTCS.330.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org