Contextual graph grammars characterizing context-sensitive languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Contextual graph grammars characterizing context-sensitive languages

Résumé

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.
Fichier principal
Vignette du fichier
PI-1926.pdf (502.93 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00366942 , version 1 (10-03-2009)
inria-00366942 , version 2 (27-04-2009)

Identifiants

  • HAL Id : inria-00366942 , version 2

Citer

Christophe Morvan. Contextual graph grammars characterizing context-sensitive languages. [Research Report] PI 1926, 2009, pp.19. ⟨inria-00366942v2⟩
40 Consultations
94 Téléchargements

Partager

Gmail Facebook X LinkedIn More