Skip to Main content Skip to Navigation
Reports

Contextual graph grammars characterizing context-sensitive languages

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

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00366942
Contributor : Anne Jaigu <>
Submitted on : Monday, April 27, 2009 - 10:47:36 AM
Last modification on : Wednesday, April 11, 2018 - 1:54:21 AM
Long-term archiving on: : Wednesday, September 22, 2010 - 12:06:34 PM

File

PI-1926.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00366942, version 2

Collections

Citation

Christophe Morvan. Contextual graph grammars characterizing context-sensitive languages. [Research Report] PI 1926, 2009, pp.19. ⟨inria-00366942v2⟩

Share

Metrics

Record views

158

Files downloads

127