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

https://hal.inria.fr/inria-00366942
Contributor : Anne Jaigu <>
Submitted on : Tuesday, March 10, 2009 - 9:42:45 AM
Last modification on : Wednesday, November 29, 2017 - 4:22:58 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:27:24 PM

Files

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

Identifiers

  • HAL Id : inria-00366942, version 1

Citation

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

Share

Metrics

Record views

3

Files downloads

34