On Parallel and Sequential Independence in Attributed Graph Rewriting
Thierry Boy de la Tour · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
We use graphs where vertices and arrows are attributed with sets of values, and rules that allow to delete data from a graph, to create new vertices or arrows, and to include values in attributes. Rules may be applied simultaneously, yielding a notion of parallelism that generalizes cellular automata in particular by allowing infinite matchings of rules in a graph. This is first used to define a notion of sequential independence of a set M of matchings of rules, even when M is infinite. Next, a notion of parallel independence of matchings is defined that accounts for the particular treatment of attributes, and it is proven that it characterizes sequential independence. Last, the effective deletion property, a condition that ensures that rules can be applied in parallel without conflicts, is proven to generalize parallel independence.