Abstract Families of Graphs

Tanguy Urvoy


Abstract

A natural way to describe a family of languages is to use rational transformations from a generator. From these transformations, Ginsburg and Greibach have defined the Abstract Family of Languages (AFL). Infinite graphs (also called infinite automata) are natural tools to study languages. In this paper, we study families of infinite graphs that are described by rational transformations from generators. We define the Abstract Family of Graphs (AFG). We show that traces of AFG are rational cones and traces of principal AFG are AFL. We generalize some properties of prefix recognizable graphs to AFG and we apply these tools and the notion of geometrical complexity to study sub-families of prefix recognizable graphs.