On Rational Graphs

Abstract : Using rationality, like in language theory, we define a family of infinite graphs. This family is a strict extension of the context-free graphs of Muller and Schupp, the equational graphs of Courcelle and the prefix recogniza- ble graphs of Caucal. We give basic properties, as well as an internal and an external characterization of these graphs. We also show that their traces form an AFL of recursive languages, containing the context-free languages.
Type de document :
Rapport
[Research Report] RR-3944, INRIA. 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00072706
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:40:10
Dernière modification le : mercredi 11 avril 2018 - 01:55:47
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:21:38

Fichiers

Identifiants

  • HAL Id : inria-00072706, version 1

Collections

Citation

Christophe Morvan. On Rational Graphs. [Research Report] RR-3944, INRIA. 2000. 〈inria-00072706〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

136