数理解析研究所講究録
第 1604 巻 2008 年 80-89

80

Place Dependency of a Petri Net Generating a Maximal Prefix Code*

Yoshiyuki KUNIMOCHI (國持良行)

Shizuoka Institute of Science and Technology (静岡理工科大学)
Abstract In this paper we deal with prefix codes, called CPN languages, defined on Petri nets. And
the family CPN of all CPN languages is included in the family of all context-sensitive languages.
The subclass $mCPN$ and NmCPN of CPN are a family of prefix codes which are maximal prefix
codes and a family of prefix codes defined on input-ordinal Petri nets. NmCPN is obviously included
in $mCPN$ . But its converse inclusion is still a opcn problem. We have already proved under some
restricted $Pe$ tri nets, for example, Petri iiets have at most two places or at most one transition. We
coiisider this pioblein in thc case that Pctri nets have more than two places.

1

Preliminaries

In this section, we state the definitions and the notations of formal languages and codes in thispaper. And wc introduce Petri net codcs and thiei relatcd codes.
Let $X$ be a nonempty finite set called an alphabet,be the free monoid generated by $X$ under
the concatenation. A elernent ofis called a word. The identity ofis called the ernpty word,
denot ed by 1. We denoteby, the concatenation of two words
and by $xy$ , and thelength of a word $w\in X$ by $|w|(especially|1|=0)$ .
If for two words $w,$ $u\in X^{*}$ there exi.sts some word $v\in X^{*}$ (resp. $v\in X^{+}$ ) with $w=u\iota f$ ,thenis called a prefix (resp. a proper prefix) of , we represent $u\leq_{p}w(resp. u<_{p}u))$ . A
language over $X$ is a subset of. The concatenation of two languagos
andis defined by$L_{1}L_{2}=\{v1_{1}w_{2}|w_{1}\in L_{1}, w_{2}\in L_{2}\}$ . A nonempty language
is a code if for any two integers $n,$ $m\geq 1$
and.
,$X^{*}$$X^{*}$$\prime t$$X^{*}$$X^{+}$$X”\backslash \{1\}$

$x$

$y$

“

$u$

$w$

$\cdot$$X^{*}$$L_{1}$$L_{2}$$L$$n_{1}$$\uparrow\prime z_{:}\cdots,$$\uparrow\iota_{t’ 1,2,)7\Gamma l}\tau jv\cdots\cdot 1\}\in L$$u_{1}u_{2}\cdots u_{r\iota}=v_{1}v_{2}\cdots v_{r’\iota}$

implies$n=m$and$u_{\iota}=v_{i}$for $i=1,$$\cdots,$$n$.

is a prefix code if $u,$ $uv\in L$ implies $v=1$ . A code $C\subset X^{+}$ is maximal (resp. maximal
prefix) in
if $C$ is not included by any other code (resp. $pre$ fix code) over $X$ .
Remark A maximal and prefix code is clearly a maximal prefix code because it is not included inany other codes by the maximality. But a maximal prefix code is a prefix code. but is not nccessarily
a maximal code.
A code$L$$X$

DEFINITION 1.1 (Petri net)$\mathcal{A}$

Petre net $PN$ is a quadruple $(P, X, W, \mu_{0})$ satisfying the fol-lowing conditions.
(1) $P$ and $X$ are finite sets with $P\cap X=\emptyset$ and.
(2) $W$ is a weighting
to(3)
is a function from $P$ tocalled an initial marking
marking.isafunction$P\cup X\neq\emptyset$$f\ell l7\iota ctio\gamma\iota f\dot{r}\cdot orr\iota(P\cross X)\cup(X\cross P)$$\mu_{0}$$N_{f}$‘This is an abstract and thc paper will \’eppcar elsewberc.

$tl\iota c6^{\cdot}c^{}tN$of all $thc$ nonnegative integers.
$\square$81$\Lambda$

tomarking i.s called positive (or zero) if it is a mapping from $P$ to, respectively .

$\{0\}$$N\backslash \{0\}$(or a mapping from $P$$)$

And $PN$ is input-ordinal if $W(t)3a)\leq 1$ for any $(p, a)\in F\cross X$ . Ill thc above Pctri net $PN$ , wc
may call $(p, a)\in P\cross X$ an arc when $W(p, a)>0$ holds, and then $W(p, a)$ is called the weight of thearc $(p, a)$ .
similar defnition is stated about $(a, p)\in X\cross P$ .
The transition $a\in X$ is callOd enable under the Petri ne $(/PN$ if $W(p, a)\leq\mu(p)$ holds tor eachplace $p\in P$ . Then the new marking
is defined as follows:$T\}_{1}e$$\mu’$$\mu’(p)=\mu(p)-W(p, a)+W(a, p)$ for $\forall p\in P$

The transition functionof $PN$ is defined by $\delta_{PN}(\mu, a)=\mu’$ .
is undefined if $a\in X$$PN$
is not enable under. This function is extended from $PxX\mapsto NtoPxX^{*}\mapsto N$ as follows:$\delta_{PN}(\mu, 1)=\mu$ and $\delta_{PN}(\mu)ua)=\delta_{f^{J}N}(\delta_{PN}(\mu, u), a)$ .
We llldy denotebyno corifusion ispossible.
$\delta_{PN}$$\delta_{PN}(\mu, a)$$\delta_{PN}$$\delta i\dagger$

is called a firing sequence in $PN$ if
is defined. $w\in X^{*}$ is called a positive
firing sequence in $PN$ if
is defined andis positive for any prefix of . We
denote the se ts of all firing sequences in $PN$ and all positive firing sequences in $PN$ by FSeq $(PN)$ andFSeq $+(PN)$ respectively. We dcnote$w)|w\in$ FSeq $(PN)\}$ orFSeq $+(PN)\})$$w\in X^{*}$$\delta_{PN}(\mu, w)$$\delta_{PN}(\mu, w)$$\delta_{PN}(\mu, u)$$u$$\{\delta(\mu_{0},$by${\rm Re}(PN)$(or${\rm Re}^{+}(PN)$$($$\tau\angle))|w\in$resp.).

DEFINITION 1.2 Let $PN=$ $(P, X, W. \mu_{0})$ be a Petm net,
$defir\iota e$$\{\delta(\mu_{0},$$\iota n$

be a positive marking.
the languages $C(P, X, W_{\backslash }\mu_{0})ar\iota dC_{0}(P, X, W, \mu 0)$ as follows:$C(P, X, W, /A_{0})=\{w\in FSeq(PN)|\delta(\mu,$$C_{0}(P, X, W, \mu_{0})=\{w\in$ FSeq $(PN)|\delta(\mu,$$w)$$\mu_{0}$Then weis not $p\uparrow\uparrow’,\in X^{+},$ $u\in FSeq^{+}(PN)\}$ ,is zero. $w=?4v.v\in X^{+},$ $u\in FSeq^{+}(PN)\}$ .

$w)$$\square$If $C(P, X, W, \mu_{0})$ and $C_{0}(P, X, W, \mu_{0})$ are not empty, then they are prefix codes. Because both
11, $uu$ arc thier elenicnts and $n\neq 1$ yield a contradiction siiice
is positive. And we call$C(P, X. W, \mu_{0})\neq\emptyset$ a Petri net code, $C_{0}(P, X, W, \mu_{0})\neq\emptyset$
a strict Petri net code. The families of all
the Petri net codes and all strict Petri net code ale denoted by CPN and CPNO, respectively. Notethat CPNO is a subclass of CPN Moreover a $Pe$ tri net code is saad to be maximal if it is maximal
as a prefix code. The tarnilies of all the maximal Petri net codes and all the strict Petri net codes aredenoted by $mCPN$ and mCPNO, re.spectively..
A Petri net code is said to be input-ordinal if it is generated by some input-ordinal Petri net. The
family of all the inpiit-ordinal Petri net codes is denoted bv NmCPN.
Since an input-ordinal $Pe$ tri net code is clearly a maximal Petri net code, we get the inclusion
relation NmCPN $\subset mCPN$ . In tliis paper, wc coiisider the following problcm.
$\delta(/r, \uparrow\iota)$[Probleml $mCPN\subset NmCPN$ ?

Since it is too difficult to solve this problem in general Petri nets, in the next section we prove thatthe problem is solved affirmatively in a restricted Petri net.

2

Fundamental Properties

In this section we state some fUndamental properties about strict Petri net codes and the structureof Petri iiets which generate maxilnal Petri net codes.

82

Some Properties of Strict Petri net codes

2.1

At first we show that a strict Petri net code is a full uniform code ii it is finite and maxiinal.
$p\in P$ and $u=o_{1}a_{2}$$a_{r}\in\chi*$For a Petri net
we denote $(\nu V(p, a_{1})-W(a_{1}.p))+$$(P, X, W^{\cdot}.

\mu_{0}),$bv $p(u)$ .

$(W(p. a_{2})-M^{\cdot}(a_{2},p))-\cdots+(W(p, a_{r})-W(a_{r},p))$. X. For any
LEMMA 2.1 [2] Let $C=C(P. X, W, /ro)$ be finite maximal $Pctr\tau$ net codc
$v\in C$ ,if there exists a $p\in P$ such that $\mu_{0}(p)=p(u)=p(v)$ , then $C$ is a full uniform code over$i.e$ . $C=X^{n}$for some $n.n\geq 1$ .
$u$$ove\gamma$$u,$$X_{2}$$\square$

PROPOSITION 2.1 If a finite maximal
code over $X$ .

$Pet\tau i7\iota et$code (1)$e\tau\cdot X$

is strict, then it is a full uniform$\square$

LEMMA 2.2 Let $C=C_{0}(P. X, W, \mu_{0})$ be a maximal strict Petri net code over X. And letplace in P. Then there exists a
net $(\{p\}. X, W‘. \mu_{0}’)$ such that $C(\{p\}, X, W‘, \mu_{0}’)=C$ .

$p$

be a

$Pet_{7^{\sim}}i$

Proof)

Let $W’$ be the restriction of $W$ on $\{p\}\cross X\cup Xx\{p\},$be the restriction ofon/) . letandbe transition fiinctions of $(P. X, W. /\iota_{0})$ and $(\{t)\}, X, W’, /\iota_{0}’)$ respectively. Since$C$
is maximal, $\delta(\mu_{0}, u)(q)>0,$ $\delta’(\mu 0, u)(p)>0$ and $\delta(\mu_{0}.w)(q)=\delta’(\mu 0, w)(p)=0$ for each $q\in P$ ,$n—|\iota\iota.’\in C,$ $v\in X^{+}$ . Thercfore $C(\{t)\}, X, W‘, /\lambda_{0}’)=C$ .
$\{$$\mu_{U}’$$\mu_{0}$$\delta’$$\delta^{-}$$\}$$\square$

PROPOSITION 2.2 If a maximal Petri net code over $X$ is strict, then it is input-ordinal.

$\square$

A code in this proposition is given the formula (1) in the next chapter. Note that the Petri net codeis strict but iiot $\iota naxiuial$ .

$\{a^{3},$$xt),$

2.2$l)(\iota\}$

Structure of maximal Petri net codes

DEFINITION 2.1$w\in X$, the set

$F_{\mathfrak{u}},$Let $PN=$ $(P, X. W, \mu_{0})$ be a Petri $ntit$ and$\subset P\cross Xo\int PN$ isdefined as $follo?r$)

be a positive marking. For$\mu_{0}$$s.\cdot$$(p, a)\in F_{w}\Leftrightarrow$(i)$W(p, a)>0$ . $(\forall b\in X)(M^{r}(p, a)\geq W(p, b))$ ,(ii)$w\in FSeq^{+}(PN),$ $\mu=\delta(\mu_{0}, w)$ . $(\forall q\in P)(W(q, a)>0\Rightarrow\mu(p)/W(p, a)\leq\mu(q)/tt^{r}(q, a))$ .
$\square$means that the continuous firing of

makes the number of tokens in become zero
the maikiiig /4 obtained
reading a positive fiiing sequence . We denote thc set of all suchpairs $(p.a)$ bythat is $F^{K}=b_{w\in X}\cdot F_{w}det$ .
is called the active flow of $PN$ .
$(p.a)\inF^{*}$
A
uieanb tliat is a place where the nuiilber of toketis first becoiries zero when fires
continuously after reading a positive firing sequence .
$(p, a)\in F_{w}$$ui\iota dei$

$a$

$p$

$|)y$

$(l)$

$F^{*}$$F^{\urcorner*}$

$p$

$a$

$w$

LEMMA 2.3 (IMndamental Lemma)$C=C(P, X, \dagger V, \mu_{0})$

be

$a$

$LctF^{*}$$\max mal$ Petri net code.

be anflow of $oP_{(},tn$ net$oct\uparrow?fC$

Let $p\in P$ and $a,$ $b\in X$ .

(i)$(p, a)\in F^{\urcorner}*\Rightarrow W(\rho, a)\geq|t^{r}(p, b)$(ii)$(p_{:}a),$,$(p.b)\in F^{*}\Rightarrow W(p.a)=M^{\cdot}(p, b)$.

$(P, X, M^{\cdot}, /r_{0})$,83(Proof) (i) There exists some non-negative integer n.such that $0^{n+1}\in C$ and $\delta(\mu 0, a^{n})=W(\rho, 0)$because $(pa)\in F^{*}$ Then by the maximality of $C$ each transition $b\in X$ must be enable. Therefore$W(1).a)\geq W(p, b)$ .
(ii) Since $W(p, a)\geq W(p, b)$ and $W(p, b)\geq W(p, a)$ hold by (1), the equality $W(p, a)=W(p, b)$ istrue.

$\square$Fig. 1: $(\rho,a)\in F.$$\Rightarrow n\geq n_{\grave{A}},$$n_{2}$.

LEMMA 2.4 (Deletion of useless places)

Let $PN=(P, X, \dagger/l_{t}^{\vee}\mu_{0})$ be a Petri net andbe apositive
Let $C=C(P, X, W^{r}.\mu_{0})$ be a
imal Petri net code. Let $p\in P$ be a place suchthat $\delta(\mu_{0}, w)(\rho)\neq 0\int or$ any $w\in C$ . And the Petrt $nelPN’=(P’, X’. W’, \mu_{0}’)$ isdefined as follows,which is obtained by removing the place and the arcs from and the arcs to .
$\mu_{0}$$mar\cdot kirig$ .

$rna\prime x$$p$$P’=P\backslash \{\rho\},$

$p$

$p$

$X^{t}=X$

is a restriction of Won $(P’\cross X)\cup(XxP‘)$ ,is a restriction of
on $P’$ .

$iV’$$\mu_{0}’$$\mu 0$$c().$

Then,.
$\square$We called such a plac in the Iemma a useless place in $PN$ . Generally set $P_{0}=\{q\in P|\exists u’\in$. Applying the above theorem repeatedly, the theorem holds even if we replace ‘in the theorem by. Thc maximality in the theorcm is needed as the following examplc shows.
$e$$C,$ $\delta(\mu 0, w)(q)=0\}$$P$$P_{0}$

EXAMPLE 2.1 Let $P=\{p.q\},$ $X=\{a, b\},$ $W(p, a)=W(p.b)=1,$ $W(q, b)=2,$ $\mu_{0}(p)=$The other arcs weigh . Then $C=C(P, X, W, \mu_{0})=\{a\}$ is not maximal. For$an?/1l’CC_{f}\delta(/A_{0}.?l^{1})(q)\neq 0$ , where
the transition functio of $(P$, X. $W,$
. However, Since$\mu 0(q)=1$ .

$0$$\delta i_{b}$$P’=P\backslash \{q\}=\{p\},$$/l_{0)}$$7l$$11^{f\prime}(\rho.a)=W’(p\rangle b)=1$ . $\mu_{0}^{l}(p)=1$ . theother arcs weigh ,This means that $C=C’$ does not necessarily hold.

$X’=\{a, b\},$$C’=C(P’. X’.W’, \mu_{0}’)=\{a, b\}$ .

$0$$\square$By
next propositioii 2.3, It is decidablc whether a place in a givcn Petii nct is a uscless placeor not. We need the old famous result on the reachability of a Petri net to show this decidability.
Next two definitions are old farnous decision probleiris. In case of considering a Petri net code, it isimportant to judge whether $p\in P$ is one of the places where tokens can be exhausted
first. So wesuggest the decision problem in the third definition.
$tl\iota e$

DEFINITION 2.2 (The Reachability Problem)
and a given marking$\mu_{J}$is $\mu\in{\rm Re}(PN)$

For a given$Petr^{v}i$?

net $PN=(P, X, W, \mu 0)$$\square$

DEFINITION 2.3 (The Single-Place Zero-Reachability Problem)$PN=(P.$ $X$ , VLI$\mu_{0})$For a given Petri net
and a given $pla$ ce $\rho\in P$ , does there exist $\mu\in{\rm Re}(PN)$ with $\mu(\rho)=0$ ?
$\square$

84

DEFINITION 2.4 (The Single-Place First Zero-Reachability Problem) For a qive
net $PN=(P, T, W, \mu_{0})$ and a given place $p\in P.$ let be the transition function of $PN$ , then does
$Petr\uparrow$$\delta$th $C7^{\cdot}Cex\iota st1l)\in X^{K}$ such that$\delta(t^{x}0,$$(v)(/)=0$ and$\delta(\mu 0\cdot\uparrow l|’)(q)>0for\cdot\forall\uparrow\perp|’\in P_{r}(n)\backslash \{w\},$$\forall q\in Pj$$\square$Fact 2.1 (1) The reachability problem and the single-place zero-reachobilitv pro blem are equivalent.
[7](2) The reachability problem is decidable.[8],[9] Any algo rnthm to solve the problem require at leaston exponentiol amovnt $0\int space$ for storage and on exponenlial $amo$ im of trme. [10]$f$

PROPOSITION 2.3 [11]$reachabili/?/probtem$ are

The single-place first $ze\tau 0- r\cdot eachability$ proble$lha/is_{r}$ decidable.

$\square$$rn$

and the$sir\iota gle$

-place zero-$eq?\prime i_{?\prime}olen/,$$\square$

LEMMA 2.5 (Reduction rule of two-way arcs)
Let $PN=$ $(P. X, W, \mu_{0})$ be a Petm net and$p_{oS7/i?^{1}emorl}\gammanq$
be a. Let $C=C(P.X, W, \mu 0)$ be a maximal Petri net code. $Lclp\in P,$ $a\in X?ifi/h$$W(\rho.a)>0$ and $W(a, p)>0$ . Then the Petri net $PN’=(P, X, W‘, \mu 0)$ isdefined as follows, which$\mu_{0}$$7_{\iota}S$obtained by replocinq$the\uparrow l$) $c$qhts of the two arcs $(p. a)$ and $(a.p)$ .

$M^{r}(\rho, a)>W(a, p)$$\Rightarrow W’(p, a)=W(p, a)-W(a, p),$ $W$ ‘ $(a, p)=0$$W(\rho, a)=W(a,p)$$\Rightarrow M^{r/}(p, a)=W’(a,p)=0$$W(p, a)<W(a, p)$$\Rightarrow W’(a, p)=W(a.p)-W(p, a),$ $W’(p, a)=0$$q\neq p$

or $b\neq a$$\Rightarrow W’(b, q)=W(b, q),$ $W’(q, b)=W(q, b)$

Then$C(P. X, W, \mu_{0})=C(P, X, W’, \mu 0)$ .
$\square$3

Maximal Petri net codes and input-ordinal Petri net code

Here we solve the problem whether $mCPN\subset NmCPN$ holds or not under some conditions.
In a Petri net $PN=(P, X, W, \mu_{0})$ , for a transition
set $I(a)=\{\rho\in P|W(\rho, a)>0\}$ and$O((r)=\{J)\in P|W((i,I))>0\}$ . If
, thenandis called a consuming transition. If
and, then is called transporting transition. If $I(a)=\emptyset$ and, theniscalled a supplying transition. If $I(a)=O(n)=\emptyset$ , then is called an isolated transition.
Through this section, without the loss of generality we may assume that a Petri net $PN=$$(P, X. W, \mu 0)$ with a positive iiarking} a Petri net is calledsatisfies the following coriditions.
a slim maximal Petri net.
(i) $C(P.X, W, \mu_{0})$ is a maximal Petri net code,(ii)
lemma 2.4, there is no useless place in $PN$ .
(iii) By lemma 2.5, for any $p\in P$ and any $a\in X$ , both the weight of $(a, p)$ and the weight of $(p\}a)$are not positive.
(iv) $PN$ has no isolated rransitions.
$a\in X_{\rangle}$$I(a)\neq\emptyset$$J(a)\neq\emptyset$$O(a)\neq\emptyset$$a$$O((x)=\mathfrak{U}$$a$$O(a)\neq\emptyset$

$a$

$a$

$a$

$\iota$$S_{UC}$$\mu_{0}$$i$$B\gamma$

3.1

Case of $|P|\leq 2$ or $|X|=1$

At filst we consider tlictransitions equals 1.

$c$}$\iota s\mathfrak{c}$. the nuinber$|P|$of places equals 1 and the case the nurnber $|X|$ of

85

$>|$

$\nearrow^{\backslash :}|<$(a) consuming(b) transporting$|<$(c) supplying$|$(d) isolated

Fig. 2: Classification of transitions

THEOREM 3.1 Let $PN=(P, X, W, \mu_{0})$ be a Petri net andbe a positive marking.
that$|X|=1$ or $|P|=1$ . If $C=C(P, X, W, /x_{0})$ is a maxirnal Petri net code, thenan input-ordinal$\mathcal{A}ssume$$\mu_{0}$$C\iota s$$Petri$ net code.

$\square$Assume that $|P|=1$ , that is $P=\{\rho\}$ in this theorem. Setting $X_{1}=\{a\in X|W(p, a)>0,$ $W(a,p)=$$0\}$

and $X_{2}=X-X_{1}$ , Then

$C(P, X. W, \mu 0)=(X_{1}^{n-1}o(\bigcup_{a_{\tau}\in X_{2}}a_{i}X_{1}^{n_{i}})^{\text{く}\rangle})X_{1}$where $n_{t}=W(a_{i},p)/n,$$\bigcup_{\tau\in/}\lrcorner,v\in\kappa;i0\uparrow/,$$L^{\theta}$(1)

is the shuffie product over two languages $L,$ $K\subset X^{*}$ defined by $LoK=$$\langle\rangle y=\{\prime J^{\cdot}\perp y_{1^{J}2?/2}’\cdot$

for $x,$ $y\in X^{*}$ and$L^{o(i+1)}=L^{\langle\rangle l}oL$

$0$

,

.

$x_{n}y_{n}|x=\prime J^{\cdot}\perp x_{2}$.

$x_{n}$

is the shuflle closure of a language,$y=y_{1}y_{2}$$L$.

$?1n’:I_{i,/i}’|\in X^{*}$, defined by

for $1\leq i\leq n\}$$L^{o}= \bigcup_{i\geq 0}L^{oi},$$L^{o0}=\{1\}$ ,Especially, in the above example setting
and $X_{2}=X,$ $C=X^{k}=\{w\in X^{*}||w|=k\}$ .
is called a (full) uniform code over $X$ . Therefore a uniform code becomes an iriput-ordinal
Petri netcode.
In case that Petri net has only a place or only a transition, we have proven
NmCPN $=mCPN$ .
we gct the following result in the asc that a Petri net has two places. Th first proposition isfor thecase without supplying transitions, the second is for the case with with supplying
transitions.
$X_{1}=\emptyset$$X^{k}$$a$$c$$(\backslash$

PROPOSITION 3.1 Let $PN=(P, X, W, \mu_{0})$ be a Petn net without supplying transitions,
positive and $|P|=2$ .

Petri ne code.

If $C=C(P. X, W, \mu_{0})$ is a maximal Petri net code, then$C$$\mu 0$beis an input-ordinal$f$$\square$

PROPOSITION 3.2 $LctPN=$ $(P, X. W, \mu_{0})$ be a Pctri net with supplying transitions,be positive and $|P|=2$ . If $C=C(P, X, W, \mu 0)$ is a maximal Petri net code, thenis an input-o rdinal Petri$/\iota_{0}$$C$$r\iota et$code.

$\square$

We obtain the final result of this paper from the theorems 3.1 and 3.2.

THEOREM 3.2 Let $PN=(P, X, W, \mu 0)$ be a Petri net,
$C(P)X,$ $W,$ $\mu 0)$ is a maximal$Petr\cdot i_{7}\iota et$

be positive and $|P|=2$ .
code, then $C$ is an input-ordinal Petri net code.
$\mu 0$

If $C=$$\square$86

Some results in case of $|P|>2$

4

In this section, first we introduce some notation and define some dependency of places in a Petrinet. Secondly wc invastigate the maximalitv of a specilof Petri nct.
$\uparrow ypc$

4.1

Place dependency

We introduce the following notations:

DEFINITION 4.1 Let $a\in X.\uparrow l’\in X$ “, $U\subset X$ , andas follows:$|u^{1}|_{U^{d}}=^{ef} \sum_{a\in L}$.

$C_{\zeta\}}(w)^{d}=^{cf}$where$|\uparrow)|_{a}$rncans. Then, The’$n\uparrow$mber$C_{\Omega}(?1))$is defined$|w|_{a}(\leq|w|)$

rnax $\{|w|_{U}|U\in tl\}$ ,number of occurcnceb of a letter$tt\iota c$$\Omega\subset 2^{X}$$a$in $w$ .

$\square$

Then the following properties hold:(1)(2)$0\leq C_{\Omega}(lA))\leq|_{l1)}|$.

Let $k\geq 1$ and $L_{\Omega.k}=\{w\in X^{*}|C_{\Omega}(w)=k\}\neq\emptyset$ .
is commutative and regular.
is finite $\Leftrightarrow X=\cup\Omega$ .
$X\in\Omega\Rightarrow L_{f1,k}=X^{k}$
The converse is not necessarily true.
(3)
for any
if $k>l$ .
(4) $L_{11,k}\cap X^{k}=X^{k}$ iff$L_{\Omega,k}$$L_{\Omega,k}$$L_{\Omega,k}\cap X’=\emptyset$$\Omega\subset 2^{X}$$k\geq|X|\Rightarrow X\in\Omega$$k<|X|\Rightarrow(\forall w\in X^{*})(|w|=k\Rightarrow\exists U\in\Omega(alph(w)\subset U))$alph $(w)$ means the number of the distinct letters in$w$.

. The equivalence is due to $[1|$ .

EXAMPLE 4.1 Let $X=\{a.b, c\}$ and $\Omega=\{\rho_{7}q\cdot, r\cdot\}=\{\{a, b\}, \{a, c\}, \{b, c\}\}$ . Then
$L_{\Omega,2}\cap X^{2}=X^{2}$. Bat$L_{\Omega_{c}3}\cap X^{3}\neq X^{3}$abecausc$ab_{(}:\not\in L_{\Omega,3}$.

$\square$

$c$

$b$

Fig. 3: A Petri net generating$L_{\Omega,k}$.

Now we iritroduce soine riotations to prepare to dcscribc the following leunnas.
NOTATIONS Let $PN=$ $(P, X. W_{\mu 0})$ be a PN and
be a positive marking. Let $\rho\in P$ be a$\mu 0$place.

87$(y(p)^{d}=^{ef} \max\{W(r), (r)|0\in X\}$,$\rho\cdot=\{a\in X|W(pdefa)>0\}$ ,

d ef
$=$

$p\star$$\{a\in X|W(l), a)=\alpha(\oint))>0\}(\subset p\cdot)$,

lst $(E_{w})^{d}=^{ef}\{p\in P|(p.a)\in F_{w}\}t$$\#_{w}(\rho)def=\mu(p)/\alpha(p)$and $\mu=\delta(\mu 0, w)$ .

In only a slim maximal Petri net, the following fandamental lemmas are true.

LEMMA 4.1 Let $(P, X, W, \mu_{0})$ be a $sl,m$ morimal$(\rho, a)\in F^{*}$$\Leftrightarrow$$\Gamma N$. Let ) $\in P$ and $a\in X$ . Then,$i$$W(p, a)=\alpha(\rho)>0$ .
$\square$

LEMMA 4.2 Let $(P, X, W, \mu_{0})$ be a slim maximal $PN$. Let $p\in P$ and $b\in X.$ $I \int p\in 1$ stforsome $w\in X^{*}$ and $0<\dagger V(p, b)<cv(p)$ hold, there $t^{p}msfsq\in$ lst
sa tisfying the $follo?\downarrow inq(i)$ or$(F_{w})$$(F_{1l},)$(ii) :(i) IV $(q, b)=c\iota(q)\wedge$$\#_{w}(q)=1$

for$\forall w\in X^{*}$

with $p\in$ lst$(F_{w})$,(ii) $W(q, b)=W(q,$ $(r)=(z(q)\wedge$$\#_{w}(p)=\# w(q)$for$\forall w\in X^{*}$

with $p\in$ lst

If (i) (or (ii)) holds, It is said that$p\triangleright wq)$$p$$(F_{w}^{\gamma})$.

$\square$strongly (or weakly) depends on , we write$q$

EXAMPLE 4.2 In the Petri net in Fig. 4,$\rho\triangleright sq,$$\#_{w}(p)=\#_{w}(q)=1.\cdot$a$b$

Fig. 4: Explanation of the dependency

LEMMA 4.3 Let $(P. X, W\mu_{0})$ be a slim maximal $PN$ code. Letiis transitive
is not nece sb arily transitivc .
(ii)
andare $in\omega mpatible$ .
$($

$)$

$\triangleright s$$(\triangleright w$$p\triangleright wq$

(iii)

4.2

$p\triangleright sq$.

$p\triangleright sq$$\triangleright_{-S}$.

$p,$ $q,$ $r\in

P$ .

$)$

$q\triangleright wp$

and$q\triangleright wr\cdot\Rightarrow q\triangleright sr$.

$\square$Petri net of the special type

We define a Petri net of the special type.

DEFINITION 4.2 A Petri net $(P. X, lt’. \mu_{0})$ is called to be of type(i) $P=t_{l})\}+Q$ and $X=Z+Y$ .

$D$

if it satisfies:

(or

88

(ii) $W(f),$ $a)=\alpha(\gamma)),$ $0<W(p, b)<\alpha(I’)$ . $W(q. c\iota)=W(q, b)=\alpha(q)$ for all $q\in Q,$ $a\in Z$ and $b\in Y$ .

(iii) $\mu 0(\rho)=k\alpha(\rho)$ and $\mu 0(q)=k\alpha(q)$ for all $q\in Q$ .
andcode it gcnerates by
this Petri net by (J), $Q,$ $Z,$ $Y,$ $W,$
$Q=\{q_{1},$. . ,. $Z=\{a_{1}, a_{2}, , a_{s}\}$ and $Y=\{b_{1},$ , . , .
$Wcdcr\downarrow otc^{J}$$q_{2},$$h\cdot)$$tt\iota c^{J}$$q_{n}\}$

EXAMPLE 4.3 The$follo\uparrow i$ )$mg$each $q_{i}\in Q=\{q_{1}, q_{2}, , q_{n}\},$$\uparrow l)=(l_{1’2}$

(X

$”,$

$\square$$\square$$p\triangleright wq_{i}$$D$with parameter$k$.

. . $a_{1}\in X^{*},$ $0_{i}\in X(1\leq i\leq 7l_{l})$ .

$\pi_{\rho}(\tau v)^{d}=^{c(}\sum_{i=1}^{n}IV(l),$ $(x_{i})$$\pi_{\rho}$$wf\iota c^{}rc^{}$fiqure is an $e\tau ample$ of a Petn net $(\rho, Q, Z:Y, W, k)$ of type D. For
holds there.

Fig. 5: A Petri iiet of typc

Let

$C(p;Q, Z_{\backslash }\cdot Y_{\backslash }W, k),$$b_{t}\}$$b_{2}$.

) $rightarrow(\{0,1,2, \ldots\}, +)$ is the monoid morphism. The next lemma is the main result of thispaper.

LEMMA 4.4 Let $(p.Q, Z;Y, W, k)$ be a Petri net of type D. If $C(\rho;Q, Z;Y, W, k)$ is a maximal prefix
code, the condition;
For all$\cdot$$11^{1}\in X^{*},$$\pi_{p}(\iota\iota)\geq(k-1)rr’+1\Rightarrow C_{\Omega}(l1))\geq k$holds, where $m=\alpha(p)$ . $X=Y\cup Z$ and $ll=\{Z\}\cup\{\cdot q|q\in Q\}$ . The $\omega nverse$ is also true.

EXAMPLE 4.4 Let

be the Petri net code with the number of tokens in
not a ma.
then $C_{k}=\{a, a’, b\}^{2}$ is a maximal codc. But If $k=3$ , then$k$

$C_{k}$$C_{k}i_{b}$a$D$wii,h parameterin Fig.6. If $k=2$ ,cfix code. Becausc$xi_{7}r\iota alp\tau$$\pi_{p}(aa’b)=5>(3-1)2+1$ but $C_{p}(aa’b)=C_{q}(aa’b)=C_{q’}(aa’b)=2<k=3$

Fig. 6. Pet ri net 01’ type$\rho$$k$.

$\square$89

References[1] G. Tanaka. Prefix codes determined by Petri nets, Algebla Colloquim 5, pp.255-264, (1998)[2] M.Ito and Y.Kunimochi. Some Pctri nets languages and codes, Lecture Note in Computer
Science 2295, pp.69-80,[3] H. J. Shyr, Free Monoids and Languages, Lcctiire Notes (IIonBook Company, Taichung1991).
[4] J. L. Pctcrson, Pctri Net Theory and the Modeling of Systerns, (Prentice-Hall, 1981).
[5] G. Rozenberg and A. Salom aa, Handbook of Formal Languages Vol.1 WORD LANGUAGE,
GRAMMAR, (Springer, 1997).
[6] J. Berstel and D. Perrin, Theory of Codes, Pure aiid Applied Mathematics (Academic Press,
1985).
[7] M. Hack, Decidability Questions for Petri nets, Ph.D. dissertation, Department of Electrical$\backslash (2002)$${\rm Min}$

Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts, (1975).
[8] S. R. Kosaraju, Decidability of Reachability in Vector Addition Systcms, Procs. of the 14th
Annual ACM Symp. on Theory of Computing, pp.267-281, (1982).
[9] E. W. Mayr, An Algorithm for the General Petri Net Reachability Problem, SIAM J. Comput.,
13, 3, $pp.441-460,(19S4)$ .
[10] J.L. Petcrson, Pctri
Thcory and the Modeling of Systerns, Printicc-HaJl, Ncw Jerscy,1981.
[11] Y.Kunimochi and M.Ito, Some problems on maximal CPN languages, Proceedings of the 5th
Symposium on Algebra, Languages and Computation, pp56-62, Nov. 17-18, 2001$\backslash _{\perp^{T}}et$