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.
Type de document :
Rapport
[Research Report] PI 1926, 2009, pp.19
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00366942
Contributeur : Anne Jaigu <>
Soumis le : lundi 27 avril 2009 - 10:47:36
Dernière modification le : mercredi 11 avril 2018 - 01:54:21
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 12:06:34

Fichier

PI-1926.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

105