On rational graphs

Abstract : Using rationality, like in language theory, we de ne a family of in nite graphs. This family is a strict extension of the context-free graphs of Muller and Schupp, the equational graphs of Courcelle and the pre x recognizable 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620062
Contributor : Christophe Morvan <>
Submitted on : Thursday, February 20, 2014 - 4:53:46 PM
Last modification on : Wednesday, November 29, 2017 - 3:06:42 PM
Long-term archiving on : Tuesday, May 20, 2014 - 3:45:50 PM

Files

morvan.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620062, version 2

Collections

Citation

Christophe Morvan. On rational graphs. Fossacs 2000, 2000, France. pp.252-266. ⟨hal-00620062v2⟩

Share

Metrics

Record views

258

Files downloads

168