Адм. здание Докукина, 12 Dokukina 12;pdf

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