A Kleene Theorem for a Class of Planar Acyclic Graphs
A Kleene Theorem for a Class of Planar Acyclic Graphs
复制标题
一类平面无环图的克林定理
DOI：
10.1006/inco.1995.1043
复制
发表时间：
1995
影响因子：
1
通讯作者：
Bruno Warin
中科院分区：
文献类型：
--
作者：
F. Bossut;M. Dauchet;Bruno Warin
本文研究平面有向有序连通无圈图，特别是可以通过并行和串联合成在(有限)双排序字母表上建立的图。我们一方面介绍了图上的有限自动机，另一方面介绍了涉及并集、不确定并行合成、序列合成以及这些合成的迭代的有理表达式。我们证明了一个连接这两个图集刻画的Kleene定理。
In 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.