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.
https://hal.inria.fr/inria-00525409 Contributor : Christophe MorvanConnect in order to contact the contributor Submitted on : Monday, October 11, 2010 - 5:19:44 PM Last modification on : Friday, February 4, 2022 - 3:17:39 AM Long-term archiving on: : Thursday, October 25, 2012 - 4:51:31 PM