Graph Grammar Verification through Abstraction

Graph Transformations and Process Algebras for Modeling Distributed and Mobile Systems

计算机科学;物理学

Paolo Baldan ; Barbara König ; Arend Rensink

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/29/pdf/04241.SWM4.Paper.pdf
PID  :  7278

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Until now there have been few contributions concerning the verification of graph grammars, specifically of infinite-state graph gram- mars. This paper compares two existing approaches, based on abstrac- tions of graph transformation systems. While in the unfolding approach graph grammars are approximated by Petri nets, in the partitioning ap- proach graphs are abstracted according to their local structure. We describe differences and similarities of the two approaches and explain the underlying ideas.