A Kleene Theorem for a Class of Planar Acyclic Graphs

AbstractIn this paper, we study planar directed ordered connected acyclic graphs, in particular graphs that can be built over a (finite) doubly ranked alphabet by parallel and serial composition. On the one hand we introduce finite automata on graphs and, on the other hand, rational expressions that involve union, nondeterministic parallel composition, serial composition, and the iterations of these compositions. We prove a Kleene Theorem linking these two characterizations of sets of graphs