Deterministi Weak-and-Marked Petri Net Languages are Regular Stephane Gaubert INRIA, Roquenourt BP 105, 78153 Le Chesnay Cedex, Frane, email: Stephane.Gaubertinria.fr Alessandro Giua Dip. di Ingegneria Elettria ed Elettronia, Universita di Cagliari, Piazza d'Armi, 09123 Cagliari, Italy Phone: +39-070-675-5892 { Fax: +39-070-675-5900 { Email: giuadiee.unia.it Abstrat The intersetion of the lass of deterministi weak and the lass of deterministi marked Petri net languages is the lass of regular languages. We prove this result using a lemma that haraterizes regular deterministi Petri net languages. Published as: S. Gaubert, A. Giua, \Deterministi Weak-and-Marked Petri Net Languages Are Regular," IEEE Trans. on Automati Control, Vol. 41, No. 12, pp. 1802{1803, Deember,1996. 1 1 Introdution The extension of the supervisory ontrol theory to Disrete Event Systems modeled by Petri nets (PN) leads to non trivial deision problems for PN languages [2, 5℄. For instane, heking the ontrollability of a PN speiation with respet to a PN behavior requires more or less testing the inlusion of PN languages, a well known undeidable problem for general PN languages. This naturally leads to the investigation of appropriate sublasses of PN speiations and behaviors in whih these basi problems beome deidable. To this end, the sublass Ld of deterministi marked Petri net languages and the sublass Gd of deterministi weak Petri net (PN) languages were used in [2℄. It is known that the set of regular languages R satises R Gd \ Ld . Moreover, the lass Ld is inomparable with Gd . It was onjetured in [2℄ that R = Ld \ Gd . We prove here that this is the ase. Thus, Ld and Gd provide proper and distint extensions of regular languages. Let us rst reall some notation (the reader is refered to [2℄ for more details). Let denote a nite alphabet. A -labeled PN is a 4-uple G = (N; `; M ; F ), where: N is a PN (whose sets of transitions and plaes are denoted respetively by T and P ); ` is a labeling funtion T ! ; M 2 N P denotes the initial marking; F N P is a nite set of nal markings. The labelling funtion ` is extended to a morphism T ! in the anonial way. The marked behavior Lm (G) is the `-image of the set of ring sequenes leading to a nal marking, namely: Lm (G) = f`( ) j 2 T ; M [ iM; with M 2 F g : The weak behavior Lw (G) is dened by taking as aepting set the overing set CF , i.e.: Lw (G) = f`( ) j 2 T ; M [ iM; with M 2 CF g where CF = fM 0 2 N P j 9M 00 2 F; M 0 M 00 g : (1) In more general terms given a (possibly innite) set of aepting markings F , we set L(G; M; F ) = f`( ) j 2 T ; M [ iM 0 ; with M 0 2 Fg. We note that Lm (G) is obtained from L(G; M ; F ) by the speialization F = F , while Lw (G) is obtained from L(G; M ; F ) by the speialization F = CF as dened by (1). The set of reahable markings starting from a marking M will be denoted by R(N; M ). We say that G is deterministi if the marking reahed after ring a sequene is uniquely dened from the sequene label, i.e., if M [iM , M [0 iM 0 , and `() = `(0) implies M = M 0 . 0 0 0 0 def 0 0 0 0 2 Charaterization of regular Petri net languages We begin with a lemma of general interest whih haraterizes all lasses of regular deterministi PN languages. This extends a result of Ginzburg and Yoeli ([1℄, Theorem 1) 2 for free-labeled losed PN languages. The regularity of Petri net languages has also been disussed by Valk and Vidal [6℄. This lemma should be seen as the transription in terms of reahable markings of the well known Myhill-Nerode haraterization of a regular language by the niteness of its set of residuals [3℄. Given a language L and a string w 2 , the residual of L with respet to w is the language w L = fz j wz 2 Lg. The language L is regular i the set of its residuals as w ranges over is nite, i.e., i the set fw L j w 2 g is nite. Lemma 1. Let F denote an arbitary set of aepting markings. If fL(G; M; F ) j M 2 R(N; M )g is nite, then L(G; M ; F ) is regular. The onverse holds when G is deter1 1 0 0 ministi. Proof. The proof is based on the following obvious observation: 8w 2 ; w 1L(G; M0 ; F ) = [ 2 T ; `()=w; M0 [iM L(G; M; F ) : (2) If there are only nitely many L(G; M; F ) for M 2 R(N; M ), we get readily from (2) that there are nitely many w L(G; M ; F ) for all w 2 (sine (2) writes w L(G; M ; F ) as a nite union of distint subsets). Thus L(G; M ; F ) is regular. Conversely, let M 2 R(N; M ), with M [ iM . Obviously, 0 1 1 0 0 0 0 0 L(G; M; F ) `( ) 1 L(G; M0 ; F ) (3) We prove that the onverse inlusion holds for deterministi nets. Indeed, let w 2 `( ) L(G; M ; F ). Then, there exist 0 ; 00 2 T suh that `( 0 ) = `( ), `( 00 ) = w and M [0 iM 0[00 iM 00 2 F . Sine G is deterministi, M = M 0 , hene M [00 iM 00 2 F , and thus w = `(00) 2 L(G; M; F ). This shows the equality in (3), and implies that there are nitely many L(G; M; F ) as M 2 R(N; M ). 1 0 0 0 We show how the onverse of the lemma depends on the determinism of G with an example. Example 1. Let G be the nondeterministi labeled net in Figure 1, with initial marking M = (0) and set of nal markings F = f(0)g. The set of reahable markings of this net is R(N; M ) = N . The language aepted starting from Mi = (i) is L(G; Mi; F ) = fai j j j 0g. Hene the set fL(G; M; F ) j M 2 R(N; M )g is innite, while the language L(G; M ; F ) = (a ) is regular. 0 0 +2 0 0 2 3 Main result We an then state the main result of this note. Theorem 1. R = Gd \ Ld . 3 a a Figure 1: Non deterministi labeled net in Example 1. The other inlusion being known [2℄, we prove that Ld \Gd R, by ontradition. Let G = (N ; ` ; M ; ; F ) and G = (N ; ` ; M ; ; F ) be two deterministi labeled nets suh that Lw (G ) = Lm (G ) and assume that Lw (G ) is not regular. By Lemma 1, there must exist an innite set of markings M R(N ; M ; ) suh that for all M; M 0 2 M, M 6= M 0 ) L(G ; M; CF1 ) 6= L(G ; M 0 ; CF1 ). From this innite set we an extrat a (stritly) inreasing innite sequene M ; M ; : : : (see, e.g., [4, Theorem 2.5℄). Hene L(G ; Mi ; CF1 ) ( L(G ; Mi ; CF1 ), for all i. For eah marking Mi, let i be a ring sequene suh that M ; [i iMi , and let be a ring sequene suh that M [ iMf 2 CF1 . Now, let us onsider the net G . There exists a ring sequene i0 rable from M ; and suh that ` (i0 ) = ` (i ) for all i. Let Mi0 2 R(N ; M ; ) be suh that M ; [i0 iMi0 . It follows from the equality in (3) for deterministi nets that L(G ; Mi0 ; F ) = L(G ; Mi ; CF1 ), hene Mi0 6= Mj0 for i 6= j . There must exist a ring 0 with ` ( 0 ) = ` ( ) suh that M 0 [ 0 iM 0 and M 0 2 F for all i. Sine ` sequene f;i i f;i f;i f;i f;i 0 is xed. Thus, there are nitely many suh 0 , and M 0 is non erasing, the length of f;i f;i f;i diers from Mi0 from a bounded quantity. Hene, being the set of all Mi0 innite, the set 0 must be innite as well. This ontradits the hypothesis that the set of nal of all Mf;i markings F of G be nite. Proof. 1 1 1 01 1 1 2 2 2 02 2 2 1 1 1 1 1 1 01 1 2 +1 01 1 2 02 2 1 2 02 02 2 2 1 2 2 1 2 2 2 Referenes [1℄ A. Ginzburg, M. Yoeli, \Vetor Addition Systems and Regular Languages," Computer and System Sienes , Vol. 20, pp. 277{284, 1980. J. of [2℄ A. Giua, F. DiCesare, \Deidability and Closure Properties of Weak Petri Net Languages in Supervisory Control," IEEE Trans. on Automati Control , Vol. 40, No. 5, pp. 906{910, May, 1995. [3℄ J.E. Hoproft, J.D. Ullman, Introdution to Automata Theory, Languages, and Computation, Addison-Wesley, 1979. [4℄ C. Reutenauer, \The Mathematis of Petri Nets," Masson and Prentie-Hall Intern., 1990. 4 [5℄ R.S. Sreenivas, \A Note on Deiding the Controllability of a Language K with Respet to a Language L," IEEE Trans. on Automati Control, Vol. 38, No. 4, pp. 658{662, April, 1993. [6℄ R. Valk, G. Vidal, \Petri Nets and Regular Languages," J. of Computer and System Sienes , Vol. 23, pp. 299{325, 1981. 5

© Copyright 2021 DropDoc