A Static Analysis Technique for Graph Transformation Systems
Reference
Paolo Baldan, Andrea Corradini, and Barbara König. A static analysis technique for graph transformation systems. In Proc. of CONCUR '01, pages 381–395. Springer-Verlag, 2001. LNCS 2154.
Abstract
In this paper we introduce a static analysis technique for graph transformation systems. We present an algorithm which, given a graph transformation system and a start graph, produces a finite structure consisting of a hypergraph decorated with transitions (Petri graph) which can be seen as an approximation of the Winskel style unfolding of the graph transformation system. The fact that any reachable graph has an homomorphic image in the Petri graph and the additional causal information provided by transitions allow us to prove several interesting properties of the original system. As an application of the proposed technique we show how it can be used to verify the absence of deadlocks in an infinite-state Dining Philosophers system.
Suggested BibTeX entry:
@inproceedings{BCK01,
author = {Paolo Baldan and Andrea Corradini and Barbara K{\"o}nig},
booktitle = {Proc. of CONCUR '01},
note = {{LNCS} 2154},
pages = {381--395},
publisher = {Springer-Verlag},
title = {A Static Analysis Technique for Graph Transformation Systems},
year = {2001}
}
