Parallel Independence in Attributed Graph Rewriting

Abstract

In order to define graph transformations by the simultaneous application of concurrent rules, we have adopted in previous work a structure of attributed graphs stable by unions. We analyze the consequences on parallel independence, a property that characterizes the possibility to resort to sequential rewriting. This property turns out to depend not only on the left-hand side of rules, as in algebraic approaches to graph rewriting, but also on their right-hand side. It is then shown that, of three possible definitions of parallel rewriting, only one is convenient in the light of parallel independence.

In Proceedings TERMGRAPH 2020, arXiv:2102.01804