Warshall Based Detection of Conflicts and Dependencies in Graph Transformation System
Junbing Chen, Zhijian Wang, Si Yu Qian, Bo Chen · 2009
The main idea of graph grammars and graph transformation is the rule-based graph rewriting, where the application of every rule graph rule leads to a graph transformation step. Graph grammars can be used to generate graph languages which is similar to Chomsky grammars in formal language theory. Moreover, graphs can be used to model the states of all kinds of systems, which allows one to use graph transformation to model state changes in these systems. A rule-based transformation system may show two kinds of nondeterminism: (1) for each rule can exist several matches, and (2) several rules can be applicable. This paper concentrates on the second non-determinism, studying a method to detect the rules which are not applicable in graph transformation systems, proposing a backward graph transformation conflict detecting algorithm. At first the computation of conflict and dependency of two rules is available by use of AGG . Secondly the set of dependencies has to be tested by Warshall algorithm and the set of conflicts has to be computed by backward algorithm. At last, the termination of graph transformation systems and validity of rules can be detected as well.