Parallel Graph Rewriting with Overlapping Rules

DOI10.29007/576HMaRDI QIDQ4645743zbMATH OpenOpenAlexFDO

Authors Rachid Echahed, Aude Maignan

Publication date 10 January 2019

Published in EPiC Series in Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06790

zbMATH Keywords

confluent rewrite relations graph rewriting overlapping rewrite systems parallel rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Abstract: We tackle the problem of simultaneous transformations of networks represented as graphs. Roughly speaking, one may distinguish two kinds of simultaneous or parallel rewrite relations over complex structures such as graphs: (i) those which transform disjoint subgraphs in parallel and hence can be simulated by successive mere sequential and local transformations and (ii) those which transform overlapping subgraphs simultaneously. In the latter situations, parallel transformations cannot be simulated in general by means of successive local rewrite steps. We investigate this last problem in the framework of overlapping graph transformation systems. As parallel transformation of a graph does not produce a graph in general, we propose first some sufficient conditions that ensure the closure of graphs by parallel rewrite relations. Then we mainly introduce and discuss two parallel rewrite relations over graphs. One relation is functional and thus deterministic, the other one is not functional for which we propose sufficient conditions which ensure its confluence.

Recommendations

Cited in

(13)

This page was built for publication: Parallel Graph Rewriting with Overlapping Rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645743)