Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

Download [help]

Download paper Adobe portable document format (pdf)

Copyright noticeThis 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.

Abstract

Deterministic graph grammars generate a family of infinite graphs which characterize context-free (word) languages. In this paper we presents a context-sensitive extension of these grammars. We achieve a characterization of context-sensitive (word) languages. We show that this characterization is not straightforward and that unless having some rigorous restrictions, contextual graph grammars generate non-recursive graphs.

Contact

Christophe Morvan
christophe.morvan@irisa.fr

BibTex Reference

@TechReport{morvan09,
   Author = {Morvan, C.},
   Title = {Contextual graph grammars characterizing context-sensitive languages},
   Number = {1926},
   Institution = {IRISA},
   Month = {March},
   Year = {2009}
}

EndNote Reference [help]

Get EndNote Reference (.ref)