-
Selection by year
-
Selection by authors
-
Complete lists
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
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)