A KLEENE THEOREM FOR A CLASS OF PLANAR ACYCLIC GRAPHS

Authors
BOSSUT F DAUCHET M WARIN B
Citation
F. Bossut et al., A KLEENE THEOREM FOR A CLASS OF PLANAR ACYCLIC GRAPHS, Information and computation, 117(2), 1995, pp. 251-265
Citations number
42
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
117
Issue
2
Year of publication
1995
Pages
251 - 265
Database
ISI
SICI code
0890-5401(1995)117:2<251:AKTFAC>2.0.ZU;2-6
Abstract
In this paper, we study planar directed ordered connected acyclic grap hs, in particular graphs that can be built over a (finite) doubly rank ed alphabet by parallel and serial composition. On the one hand we int roduce finite automata on graphs and, on the other hand, rational expr essions that involve union, nondeterministic parallel composition, ser ial composition, and the iterations of these compositions. We prove a Kleene Theorem linking these two characterizations of sets of graphs. (C) 1995 Academic Press, inc.