ncma10

C. Morvan. Contextual graph grammars characterising Rational Graphs. In Non-Classical Models of Automata and Applications (NCMA), Pages 141-153, Jena, Germany, August 2010.

Download [help]

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

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 gram- mars. 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

Contact

Christophe Morvan http://www-igm.univ-mlv.fr/~cmorvan/

BibTex Reference

@InProceedings{ncma10,
   Author = {Morvan, C.},
   Title = {Contextual graph grammars characterising Rational Graphs},
   BookTitle = {Non-Classical Models of Automata and Applications (NCMA)},
   Pages = {141--153},
   Address = {Jena, Germany},
   Month = {August},
   Year = {2010}
}

EndNote Reference [help]

Get EndNote Reference (.ref)