Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00525409
Contributor : Christophe Morvan Connect 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

File

morvan.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00525409, version 1

Collections

Citation

Christophe Morvan. Contextual graph grammars characterising Rational Graphs. Workshop on Non-Classical Models for Automata and Applications 2010, 2010, Jena, Germany. pp.141-153. ⟨inria-00525409⟩

Share

Metrics

Record views

42

Files downloads

56