Petri net languages and infinite subsets of Nm

被引:15
作者
Gaubert, S
Giua, A
机构
[1] Univ Cagliari, Dipartimento Elettr & Elettron, I-09123 Cagliari, Italy
[2] Inst Natl Rech Informat & Automat, F-78153 Le Chesnay, France
关键词
D O I
10.1006/jcss.1999.1634
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Families of Petri net languages are usually defined by varying the type of transition labeling and the class of subsets of N-m to be used as sets of final markings (m is the number of places). So far three main classes of subsets have been studied: the trivial class containing as single element N-m: the class of finite subsets of N-m, and the class of ideals (or covering subsets) of N-m. In this paper we extend the known hierarchy of Petri net languages by considering the classes of semi-cylindrical, star-free, recognizable, rational (or semilinear) subsets of N-m. We compare the related Petri net languages. For arbitrarily labeled and for lambda-free labeled Petri net languages, the above hierarchy collapses: one does not increase the generality by considering semilinear accepting sets instead of the usual finite ones. However, for free-labeled and for deterministic Petri net languages, we show that one gets new distinct subclasses of languages, for which several decidability problems become solvable. We establish as intermediate results some properties of star-free subsets Of general monoids. (C) 1999 Academic Press.
引用
收藏
页码:373 / 391
页数:19
相关论文
共 27 条
[1]  
Baccelli G. J. O. F., 1992, SYNCHRONIZATION LINE
[2]  
BERSTEL J, 1988, EATS MONOGRAPHS THEO
[3]  
Berstel J., 1979, TEUBNER STUDIENBUCHE, V38
[4]  
CONWAY JH, 1971, REGULAR ALGEBRA FINT
[5]  
DAVID R, 1992, PETRI NETS GRAFCETS
[6]   RATIONAL SETS IN COMMUTATIVE MONOIDS [J].
EILENBERG, S ;
SCHUTZENBERGER, MP .
JOURNAL OF ALGEBRA, 1969, 13 (02) :173-+
[7]   Deterministic weak-and-marked Petri net languages are regular [J].
Gaubert, S ;
Giua, A .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1996, 41 (12) :1802-1803
[8]  
GAUBERT S, 1996, P IEEE WODES 96 ED U, P326
[9]   DECIDABILITY AND CLOSURE-PROPERTIES OF WEAK PETRI-NET LANGUAGES IN SUPERVISORY CONTROL [J].
GIUA, A ;
DICESARE, F .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1995, 40 (05) :906-910
[10]  
GIUA A, 1994, 59 U CAGL I EL