inria-00366942, version 2
Contextual graph grammars characterizing context-sensitive languages
N° PI 1926 (2009)
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.
- a – Université Paris-Est
- 1 : VERTECS (INRIA)
- INRIA
- Domaine : Informatique/Mathématique discrète
- Mots-clés : Graph grammars – Context-sensitive languages – Contextual graph grammars
- Référence interne : PI 1926
- Versions disponibles : v1 (10-03-2009) v2 (27-04-2009)
- inria-00366942, version 2
- http://hal.inria.fr/inria-00366942
- oai:hal.inria.fr:inria-00366942
- Contributeur : Anne Jaigu
- Soumis le : Lundi 27 Avril 2009, 10:47:36
- Dernière modification le : Lundi 27 Avril 2009, 11:20:30
Documents associés
Exporter