A KLEENE THEOREM FOR A CLASS OF PLANAR ACYCLIC GRAPHS

被引：13
作者：
BOSSUT, F [1 ]
DAUCHET, M [1 ]
WARIN, B [1 ]
机构：
[1] IUT LITTORAL, DEPT INFORMAT, LIFL, CNRS, URA 369, F-62100 CALAIS, FRANCE
来源：
INFORMATION AND COMPUTATION | 1995年 / 117卷 / 02期
关键词：
D O I：
10.1006/inco.1995.1043
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. (C) 1995 Academic Press, inc.
引用
收藏
页码：251 / 265
页数：15
相关论文
共 42 条
[1]   ALGEBRA AUTOMATA .I. PARALLEL PROGRAMMING AS A PROLEGOMENA TO CATEGORICAL APPROACH [J].
ARBIB, MA ;
GIVEON, Y .
INFORMATION AND CONTROL, 1968, 12 (04) :331-&
[2]  
ARNOLD A, 1979, RAIRO-INF THEOR APPL, V13, P135
[3]  
ARNOLD A, 1978, RAIRO-INF THEOR-TH C, V12, P235
[4]  
BENSON DB, 1974, MATH SYST THEORY, V8, P105
[5]  
BOSSUT F, 1988, LECT NOTES COMPUT SC, V324, P190, DOI 10.1007/BFb0017142
[6]  
BOSSUT F, 1986, THESIS U LILLE FRANC
[7]  
BOSSUT F, 1992, LECTURE NOTES COMPUT, V581, P76
[8]  
BUCHI JR, 1961, LOGIC METHODOLOGY PH, P1
[9]  
BUTTELMAN HW, 1973, INFORM CONTR, V29, P29
[10]  
Claus V., 1971, Acta Informatica, V1, P64, DOI 10.1007/BF00264292
12345