On rational graphs

Christophe Morvan (1)

1 VERTECS - Verification models and techniques applied to testing and control of reactive systems

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.

Domaines: Algorithme et structure de données [cs.DS]

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