数理解析研究所講究録 1222 巻 2001 年 46-49

46
CPN Languages and Codes
Masami Ito
Kyoto Sangyo University京都産業大学)(伊藤 正美Yoshiyuki Kunimochi
Shizuoka Institute of Science and Technology(国持 良行

静岡理工科大学)

where $P$ is
Let $D=(P,X,\delta,\mu_{0})$ be aPetri net with ainitial marking
the set of places, $X$ is the set of transitions, is the transition function andis apositive marking, i.e. $\pi_{p}(\mu_{0})>0$ for any $p\in P$ . Notice thatis meant the number of tokens at of the marking . Alanguage $C$
is called a $CPN$ language over $X$ generated by $D$ and denoted by $C=\mathcal{L}(D)$, and,
if $C=\{u\in X^{+}|\exists p\in P$, $\pi_{p}(\delta(\mu,u))=0$ ,is the set of allwherefor$C=\mathcal{L}(D)$is aprefix code over $X$ . If
prefixes of }. Then it is obvious that
$C$ is amaximal prefix code over $X$ , thenis called an mCPN langauge over$\mu_{0}$$\delta$$\mu_{0}\in N_{+}^{P}$$\pi_{p}(\mu_{0})$$p$$\mu_{0}$$\forall q\in P$ $\pi_{q}(\delta(\mu_{0}, u))\geq 0$$\forall q’\in P,\pi_{\phi}(\delta(\mu_{0},u’))>0$$u’\in P_{r}(u)\backslash \{u\}$$P_{r}(u)$$u$$C$$X$.

be finite maimal prefix codes over X. If AB isTheorem 1Let ,$X$
an mCPN language over , then , are full unifom codes over $X$ .
$A$$B\subseteq X^{+}$

$A$

$B$

Remark 1In the above theorem, the condition for and $B$ to be finite
is necessary. For instance, let $X=\{a,b\}$ and let $A=B=b^{*}a$ . Then$AB=b^{*}ab^{*}a$ is an mCPN language over $X$ but neither
nor is afull
uniform code over $X$ .
$A$

$A$

$B$

Now we consider some constructions of mCPN languages.
Definition 1Let$A$,

$B\subseteq X^{+}$. Then by$A\oplus B$

we denote the language$( \bigcup_{b\in X}\{(P_{r}(A)\backslash A)\mathrm{o}Bb^{-1}\}b)\cup(\bigcup_{a\in X}\{(P_{f}(B)\backslash B)\mathrm{o}Aa^{-1}\}a)$where is meant$0$

the shuffle operation.

. If
Proposition 1Let $X=\mathrm{Y}\cup Z$ where ,is an mCPN language overmCPN language over and$X$$A\oplus B$ is an mCPN language over.
$\mathrm{Y}$$\mathrm{Y}$$B\subseteq Z^{+}$$Z\neq\emptyset,\mathrm{Y}\cap Z=\emptyset$

is an
$Z$ ,
then

$A\subseteq \mathrm{Y}^{+}$

47. ThenExample 1Let X{a,b}. Consider A {a} and B
and {b}, respectively. Henceboth A and B are mCPN languages overA Cf) B {a, ba,bb} is an mCPN language over X.
$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}$$\{/\mathrm{t}\}$$\{\ovalbox{\tt\small REJECT}\}$$\ovalbox{\tt\small REJECT}$

Proposition 2Let ,be finite mCPN languages over X. Then
$A\oplus B$ is an mCPN language over $X$
if and only if $A=B=X$ .
$A$$B\subseteq X^{+}$

Remark 2For the class of infinite mCPN languages over $X$ , the situation
is different. For instance, let $X=\{a, b\}$ and let $A=B=b^{*}a$ . Then
$A\oplus B=b^{*}a$ and $A,B$ and $A\oplus B$ are mCPN languages over $X$ .
Proposition 3Let $A$ ,be mCPN languages over X. Then there:an mPCN language over and a homomorexist an alphabet ,phism ofonto
such that $A\oplus B=h(D)$ .
$B\subseteq X^{+}$$\mathrm{Y}$$h$$D\subseteq \mathrm{Y}^{+}$$\mathrm{Y}$$X^{*}$$\mathrm{Y}^{*}$. By $m(A)$ , we denote the language $\{v\in A|\forall u,v\in$$A,\forall x\in X^{*},v--ux\Rightarrow x=1\}$ . Obviously, $m(A)$ is aprefix code over $X$ . Let, we denote the language $m(A\cup B)$ .
. By,Definition 2Let$A$

$B\subseteq X^{+}$$A\subseteq X^{+}$$A\otimes B$

Proposition 4Let , $B$ be mCPN languages over X. Then, $A\otimes B$ is anmCPN language over $X$ .
$A$

Example 2It is obvious thatand $(a\cup b)^{3}$ are mCPN languages over$\{a, b\}$ .
Hence $a^{*}b\otimes(a\cup b)^{3}=$ { , ab, $aaa,aab$ } is an mCPN language over$\{a,b\}$ .
$a^{*}b$$b$

Remark 3Proposition 4does not hold for the classe of $CPN$ languages
is a $CPN$ language
over $X$ . The reason is the following: Suppose thatover $X$ for any two $CPN$ languages $A$ and $B$ over $X$ . Then we can show
that, for agiven finite $CPN$ language $A$ over $X$ , there exists afinite mCPN
as folows. Let
be afinite $CPN$
language $B$ over $X$ such that
language over $X$ which is not an mCPN language. Let $n= \max\{|u||u\in A\}$ .
which is an mCPN language over $X$ . By assumption,Considerbecomes a $CPN$ language (in fact, an mCPN language) over $X$ . By the. Noticedefinition of the operation , it can be also proved thatthat there exists afinite $CPN$ language over $X$ such that there exists no. Hence, Proposition 4does not holdmCPN language over $X$ withfor the class of all $CPN$ languages over $X$ .
$A\otimes B$$A\subseteq X^{+}$$A\subseteq B$$A\otimes X^{n}$$X^{n}$$A\subseteq A\otimes X^{n}$$\otimes$

$A$

$B$

$A\subseteq B$

48
Remark 4The set of all mCPN languages over $X$ forms asemigroup underO. Moreover, the operation ahas the following properties:(1) $A\otimes B=B\otimes A$ , (2) $A\otimes A=A$ , (3) $A\otimes X=X$ .
Consequently, the set of aU mCPN languages over $X$ forms acommutative
band with zero under O.
be a $CPN$ language over $X$ . By $r(A)$ we denote
Definition 3Let
the value $\min\{|P||D=(P,X,\delta,\mu_{0}),\mathcal{L}(D)=A\}$ .
$A\subseteq X^{+}$

be a finite $CPN$ language over $X$ . Then $r(A)\leq|A|$ .
Remark 5Let
be mCPN languages over $X$ . Then $r(A\otimes B)\leq$Moreover, let ,, $|B|$ are finite, then $|A \otimes B|\leq\max(|A|, |B|)$ .
$r(A)+r(B)$ . In the above, if$A\subseteq X^{+}$$A$$B\subseteq X^{+}$$|A|$We define three language claesae
follows: $\mathcal{L}_{CPN}=\{A\subseteq X^{+}|A$ is$CPN$ language over $X$ }, $\mathcal{L}_{mCPN}=\{A\subseteq X^{+}|A$ is an mCPN language
over $X$ }, $\mathcal{L}_{NmCPN}=\{A\subseteq X^{+}|A$ :an mCPN language over $X$ ,$(P,X,\delta,\mu_{0}),\forall p\in P,\forall a\in X$, $\#(parrow a)\leq 1,\mathcal{L}(D)=A\}$ . Then it is obvious.
that we have the following inclusion relations:
It is also obvious that $\mathcal{L}_{mCPN}\neq mCPN$$\mathrm{a}$$\mathrm{a}\mathrm{e}$$\exists D=$$\mathcal{L}_{NmCPN}\subseteq \mathcal{L}_{mCPN}\subseteq \mathcal{L}_{CPN}$Problem 1 CmCPN$\neq \mathcal{L}_{NmCPN}$?

and let $r(A)=k$ . Then there exist
Proposition 5Let
andsuch that $r(\mathrm{A}.)=1,i=1,2$ ,,are inMoreover, in the above, if $A\in CNmCPN$ , then ,A2,
and context-ffee.

$A_{1},A_{2}$$A\in \mathcal{L}cPN$$\ldots,k$$A_{k}\in \mathcal{L}_{CPN}$$A_{1}$,$\ldots$$A=A_{1}\otimes A_{2}\otimes\ldots\otimes A_{k}$$\ldots$$A_{k}$,.

$\mathcal{L}_{NmCPN}$

For mCPN languages with rank 1, we have the following:
be a finite mCPN language with $r(A)=1$ over
Proposition 6Let
X. Then is a fall unifom code over $X$ .
$A\subseteq X^{+}$$A$

be an mCPN language with $r(A)=1$ over
Proposition 7Let
$X$ and let
is an mCPN language withbe a positive integer. Then$A\subseteq X^{+}$$k$$r(A^{k})=1$$A^{k}$over $X$ .

Proposition 8Let $A\in \mathcal{L}_{NmCPN}$ and let $r(A)=k$ . Then there exist
such that $r(\mathrm{A}.)=1,i=1,2$ , , and $A=$,,$A_{1},A_{2}$$\ldots$$A_{k}\in \mathcal{L}_{NmCPN}$$\ldots$

$k$

49

$A_{1}$(g $A_{2}$ (g$\ldots$$\ovalbox{\tt\small REJECT}$C&$A_{\mathit{1}\ovalbox{\tt\small REJECT}}.$. Let$n_{\mathit{1}}$,$n_{2}$,\ldots ,$n_{\ovalbox{\tt\small REJECT}}$be positive integers. Then

$A’ j^{1}g(A\ovalbox{\tt\small REJECT};\mathit{2}$C?
&$C_{NmCPN}\ovalbox{\tt\small REJECT}$Finally, we can prove the following main theorem by two different ways, i.e.
the first one is an indirect proof and the second one is adirect proof.

Theorem 2Let
be a $CPN$ language over X. Then $C$ is a contdsensitive language over $X$ .
$C\subseteq X^{+}$