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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...