Counterexample-guided Abstraction Refinement for the Analysis of Graph Transformation Systems
In: Proceedings of the 12th International Conference of Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2006. - (Lecture Notes in Computer Science ; 3920)
Berlin [u.a.]: Springer (2006), S. 197-211
Buchaufsatz / Kapitel / Fach: Informatik
Graph transformation systems are a general specification language for systems with dynamically changing topologies, such as mobile and distributed systems. We propose a counterexample-guided abstraction refinement technique which is based on the over-approximation of graph transformation systems (GTS) by Petri nets. We show that a spurious counterexample is caused by merging nodes during the approximation. We present a technique for identifying these merged nodes and splitting them using abstraction refinement, which removes the spurious run. The technique has been implemented in the Augur tool and experimental results are discussed.