A kernel language for programmed rewriting of (hyper)graphs

摘要

The paper presents a formalism for rewriting (hyper)graphs in a controlled manner. This formalism is essentially a simple programming language with productions, that is rewriting rules, playing the role of basic instructions. Programs in this language are built from productions by means of rather standard constructors, including a parallel composition. They may contain parameters to point to specific elements of graphs to which they are supposed to be applied. Programs are intended to describe how to transform a graph and a valuation of parameters in this graph in order to reach a resulting graph and a resulting valuation of parameters.