Contextual graph grammars characterising Rational Graphs

Abstract : Deterministic graph grammars generate a family of infinite graphs which characterise context-free (word) languages. The present paper introduces a context-sensitive extension of these grammars. We prove that this extension characterises rational graphs (whose traces are context-sensitive languages). We illustrate that this extension is not straightforward: the most obvious context-sensitive graph rewriting systems generate non recursive infinite graphs.