Contextual graph grammars characterising Rational Graphs

Christophe Morvan 1
1 VERTECS - Verification models and techniques applied to testing and control of reactive systems
Inria Rennes – Bretagne Atlantique
Abstract : Deterministic graph grammars generate a family of infinite graphs which characterise context-free (word) languages. The present paper introduces a context-sensitive extension of these grammars. We prove that this extension characterises rational graphs (whose traces are context-sensitive languages). We illustrate that this extension is not straightforward: the most obvious context-sensitive graph rewriting systems generate non recursive infinite graphs.
Type de document :
Communication dans un congrès
Henning Bordihn and Rudolf Freund and Markus Holzer and Martin Kutrib and Friedrich Otto. Workshop on Non-Classical Models for Automata and Applications 2010, 2010, Jena, Germany. Österreichischen Computer Gesellschaft, pp.141-153, 2010, book@ocg.at
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00525409
Contributeur : Christophe Morvan <>
Soumis le : lundi 11 octobre 2010 - 17:19:44
Dernière modification le : mercredi 29 novembre 2017 - 15:09:49
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 16:51:31

Fichier

morvan.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00525409, version 1

Collections

INRIA | TDS-MACS

Citation

Christophe Morvan. Contextual graph grammars characterising Rational Graphs. Henning Bordihn and Rudolf Freund and Markus Holzer and Martin Kutrib and Friedrich Otto. Workshop on Non-Classical Models for Automata and Applications 2010, 2010, Jena, Germany. Österreichischen Computer Gesellschaft, pp.141-153, 2010, book@ocg.at. 〈inria-00525409〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

117

Contact


archive-ouverte@inria.fr