On Rational Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

On Rational Graphs

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3944.pdf (349.47 Ko) Télécharger le fichier

Dates et versions

inria-00072706 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072706 , version 1

Citer

Christophe Morvan. On Rational Graphs. [Research Report] RR-3944, INRIA. 2000. ⟨inria-00072706⟩
36 Consultations
88 Téléchargements

Partager

Gmail Facebook X LinkedIn More