Partial Array Token Petri Net and P System

Abstract

The innovative model of partial array languages generated by basic puzzle partial array grammars is available in the literature. Here we define Partial array Token Petri Net Structure (PATPNS) to generate partial array languages. Further we introduce Partial Array Token Petri Net P System (PATPNPS) to generate partial array languages and compared with basic puzzle partial array grammars for generative power. PATPNS is also compared with local and recognizable partial array languages.

1 Introduction

In the context of a syntactic approach to pattern recognition, there have been several studies in the last few decades on theoretical models for generating or recognizing two-dimensional objects, pictures and picture languages [2]. Picture languages generated by several array grammars, matrix grammars have been advocated since the seventies and they have been applied in practical problems such as character recognition, pattern recognition, kolam patterns and tiling systems.

Petri nets are the models in mathematics proposed to model dynamic systems. To simulate the activity of the dynamic system tokens are used, represented by black dots. The tokens move when the transition fires. Array token Petri nets [3,4,5,6,7, 10] are proposed to generate array languages. The arrays over an alphabet are used as tokens over an alphabet not the black dots. The transitions are associated with catenation rules. Firing of transitions helps to catenate the arrays to build bigger arrays.

The class of grammars with array rewriting methods is a dynamic device to describe picture languages. The picture languages produced by such array grammars, matrix grammars have been applied in practical problems. Nivat et al. [8] proposed puzzle grammars to generate two-dimensional picture languages.

Partial words were introduced by Berstel and Boasson [1]. Later on, Partial array languages were introduced in [14] and the combinatorial properties of partial array languages were studied in [15]. Gh. Paun [9] introduced a computational model, called P system. The notion of P system related to arrays can be seen in [12]. Partial array grammars and partial array rewriting - P system were introduced in [11]. We have proposed Basic Puzzle Partial Array Grammar (BPPAG) to generate Partial array languages and studied the generative capacity of the resulting partial array P system with BPPAG [13]. Motivated by these studies, in this paper, we introduce Partial Array Token Petri Net Structure (PATPNS) and Partial Array Token Petri Net P System (PATPNPS) to generate partial array languages and we examine the generative capacity of both systems and give some comparison results. PATPNS is compared with local and recognizable partial array languages and we have proved that PATPNS has more generative power.

2 Preliminaries

The basic concepts and definitions of Partial Word, Partial Array, Basic Puzzle Partial Array Grammar and Petri Net are given here with examples.

Definition 1

[1] A partial word u of length n over $\varSigma$, is a partial function $u:N\rightarrow \varSigma$. For $1\le i\le n$, if u(i) is defined, then we say that i belongs to the domain of u (denoted by $i\in D(u)$); Otherwise, we say that i belongs to the set of holes of u (denoted by $i\in H(u)$). A word over $\varSigma$ is a partial word over $\varSigma$ with an empty set of holes. H(u) is the set of positions in which the ‘do not know’ symbol ‘$\diamondsuit$’ appears in u.

Definition 2

[1] If u is a partial word of length n over $\varSigma$, then the companion of u (denoted by $u_{\diamondsuit }$) is the total function $u_{\diamondsuit } : N \rightarrow \varSigma \cup \{\diamondsuit \}$ defined by

$$u_{\diamondsuit }(i)=\left\{ \begin{array}{ll} u(i), &{} i\in D(u); \\ \diamondsuit , &{} \hbox {otherwise.} \end{array} \right. \quad where \quad \diamondsuit \not \in \varSigma .$$

The symbol ‘$\diamondsuit$’ is viewed as a ‘do not know’ symbol and not as a ‘do not care’ symbol as in pattern matching.

Definition 3

[14] A partial array A of size $m \times n$ over $\varSigma$ is a partial function $A:Z_{+}^{2}\rightarrow \varSigma$, where Z is the set of all positive integers. For $1\le i \le m$, $1\le j \le n$, if A(i, j) is defined then we say that (i, j) belongs to the domain of A (denoted by $(i,j)\in D(A)$); Otherwise, we say that (i,j) belongs to the set of holes of A (denoted by $(i,j)\in H(A)$). An array over $\varSigma$ is partial array over $\varSigma$ with an empty set of holes. H(A) is the set of positions in which the ‘do not know’ symbol ‘$\diamondsuit$’ appears in A.

Definition 4

[14] If A is a partial array of size $m \times n$ over $\varSigma$, then the companion of A (denoted by $A_{\diamondsuit }$) is the total function $A_{\diamondsuit }:Z_{+}^{2}\rightarrow \varSigma \cup \{\diamondsuit \}$ defined by

$$A_{\diamondsuit }(i,j)=\left\{ \begin{array}{ll} A(i,j), &{} (i,j)\in D(A); \\ \diamondsuit , &{} \hbox {otherwise.} \end{array} \right. \quad where \quad \diamondsuit \not \in \varSigma .$$

Example 1

[14] The Partial array, $A_{\diamondsuit } = \left( \begin{array}{ccc} a &{} b &{} a \\ \diamondsuit &{} b &{} a \\ a &{} \diamondsuit &{} b \\ \end{array} \right)$ is a companion of a partial array A of size (3, 3) where $D(A)=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,3)\}$ and $H(A)=\{(2,1),(3,2)\}$

Definition 5

[14] If A and B are two partial arrays of equal size, then A is contained in B, denoted by $A\subset B$ if $D(A)\subseteq D(B)$ and $A(i,j)=B(i,j)$ for all $(i,j)\in D(A)$. The partial arrays A and B are said to be compatible, denoted by $A\uparrow B$ if there exists a partial array C such that $A\subset C$ and $B\subset C$.

$A_{\diamondsuit } = \left( \begin{array}{ccc} a &{} b &{} a \\ \diamondsuit &{} b &{} a \\ a &{} \diamondsuit &{} b \\ \end{array} \right)$ and $B_{\diamondsuit }=\left( \begin{array}{ccc} \diamondsuit &{} b &{} \diamondsuit \\ a &{} b &{} a \\ a &{} \diamondsuit &{} b \\ \end{array} \right)$ are the companions of two partial arrays A and B that are compatible.

The set of all partial arrays over $\varSigma$ is denoted by $\varSigma _{p}^{**}$, where $\varSigma _{p}=\varSigma \cup \{\diamondsuit \}$. We denote the empty array with no symbols by $\varLambda$ and $\varSigma _{p}^{++}=\varSigma _{p}^{**}-\{\varLambda \}$. The set of all partial arrays over $\varSigma$ of size (k, r), $k\le m,r\le n$ is denoted by $\varSigma _{p}^{(k,r)}$.

Definition 6

[13] The structure of a Basic Puzzle Partial Array Grammar (BPPAG) is $BPG_{p} = (A, B \cup \{\diamondsuit \}, P, S)$ where A is a finite non empty set of non terminal symbols and B is a finite non empty set of terminal symbols. ‘$\diamondsuit$’ is a ‘do not know’ symbol, where $\diamondsuit \not \in A\cup B$, $S \in A$ is the axiom pattern and P is a set of rules of the following forms:

where $X,Y\in A$ and $x,y\in B$.

While processing the derivations in the production rule , the nonterminal X is replaced by the right-hand member whose left-hand side is X.

The replacement is possible only if the noncircled symbol of the production rule consists of a blank symbol. The blank symbol is represented by the letter ‘#’, which is an unoccupied place where any symbol can be occupied as per the derivation. The language generated by BPPAG is denoted by ${\mathcal L}(BPPAG)$.

Example 2

[13] Consider a BPPAG $BPG_{p_{1}}=(A,B\cup \{\diamondsuit \},P,S)$ where $A=\{X,Q,R,S_1,T,U,V\}$, $B=\{z\}$, $S=X$ and P consists of the following rules:

This grammar generates square partial arrays of size $(m\times m, m\ge 2)$ with $(m-2\times m-2, m\ge 2)$ square partial array in the center consisting of only $\{\diamondsuit \}$ symbol bounded by the terminal alphabet ‘z’ on the boundary of the square, for $m=2$, the grammar generates $2\times 2$ square array $\begin{array}{cc} z &{} z \\ z &{} z \\ \end{array}$.

The first three members of the language are given below:

$$\begin{array}{cc} z &{} z \\ z &{} z \\ \end{array} \quad \begin{array}{ccc} z &{} z &{} z \\ z &{} \diamondsuit &{} z \\ z &{} z &{} z \\ \end{array} \quad \begin{array}{cccc} z &{} z &{} z &{} z \\ z &{} \diamondsuit &{} \diamondsuit &{} z \\ z &{} \diamondsuit &{} \diamondsuit &{} z \\ z &{} z &{} z &{} z \\ \end{array} \quad \dots $$

A Petri Net [10] is an abstract formal model of information flow. Petri nets have been used for analyzing systems that are concurrent, asynchronous, distributed, parallel, non-deterministic and/or stochastic. Tokens are used in Petri Nets to simulate dynamic and concurrent activities of the system. A language can be associated with the execution of a Petri Net. By defining a labeling function for transitions over an alphabet, the set of all firing sequences, starting from a specific initial marking leading to a finite set of terminal markings, generates a language over the alphabet. Petri Net structure to generate rectangular arrays are found in [3,4,5]. The two models have different firing rules and catenation rules. In [6], Column Row Catenation Petri Net Structure (CRCPNS) has been defined. Several input places having different arrays is associated with a catenation rules label. The label of the transition decides the order in which the arrays are joined (column wise or row wise) provided the condition for catenation is satisfied. In CRCPNS a transition with a catenation rule as label and different arrays in the input places is enabled to fire. In ATPNS [15] the catenation rule involves an array language. All the input places of the transition with a catenation rule as label, should have the same array as token, for the transition to be enabled. The size of the array language to be joined to the array in the input place, depends on the size of the array in the input place.

Definition 7

[5] A Petri Net structure is a four tuple $C=(P,T,I,O)$ where $P=\{p_{1},p_{2},\dots ,p_{n}\}$ is a finite set of places, $n > 0$, $T=\{t_{1},t_{2},\dots ,t_{m}\}$ is a finite set of transitions, $m > 0$, $P\cap T=\phi$, $I:T\rightarrow P^{\infty }$ is the input function from transitions to bags of places and $O:T\rightarrow P^{\infty }$ is the output function from transitions to bags of places, where $P^{\infty }$ is the bags of places.

Definition 8

[5] A Petri Net marking is an assignment of tokens to the places of Petri Net. The tokens are used to define the execution of a Petri Net. The number and position of tokens may change during the execution of a Petri Net, arrays over an alphabet are used as tokens.

3 Partial Array Token Petri Net Structure

In this section, we define Partial Array Token Petri Net Structure (PATPNS) with an example and compare it with basic puzzle partial array languages.

Definition 9

If $C=(P,T,I,O)$ is a Petri Net structure with partial arrays over $\left( \varSigma \cup \{\diamondsuit \}\right) ^{**}$ as initial markings. $\mu _{0}:P\rightarrow (\varSigma \cup \{\diamondsuit \})^{**}$ label of at least one transition being catenation rule and a finite set of final places $F\subset P$, then the Petri net structure C is defined as a Partial Array Token Petri Net Structure (PATPNS).

Definition 10

If C is a PATPNS, then the Partial array language generated by the Petri Net C is defined as

$$PL(C)=\{A_{\diamondsuit }\in (\varSigma \cup \{\diamondsuit \})^{**} \ / \ A_{\diamondsuit } \ is \ in \ p \ for \ some \ p \ in \ F\}$$

with partial arrays over $(\varSigma \cup \{\diamondsuit \})^{**}$ in some places as initial marking when all possible sequences of transitions are fired. The set of all partial arrays collected in the final places F is called the partial array language generated by C. Let ${\mathcal L}(PATPNS) = \{PL(C) / C \text { is a } PATPNS\}$.

$\left( \varSigma \cup \{\diamondsuit \}\right) ^{**}$ denotes the partial arrays made up of elements of $\varSigma \cup \{\diamondsuit \}$. If A and B are two partial arrays having same number of rows then is the column wise catenation of A and B. If two partial arrays have the same number of columns then is the row wise catenation of A and B. $(x)^{n}$ denotes a horizontal sequence of n ‘x’ and $(x)_{n}$ denotes a vertical sequence of n ‘x’ where $x\in \left( \varSigma \cup \{\diamondsuit \}\right) ^{**}$, and .

The Petri Net model defined here has places and transitions connected by directed arcs. Rectangular partial arrays over an alphabet are taken as tokens to be distributed in places. Variation in firing rules and labels of the transition are listed out below.

Fig. 1.

Position of partial array before firing

Fig. 2.

Position of partial array after firing

Firing Rules in PATPNS

We define three different types of enabled transition in PATPNS. The pre and post condition for firing the transition in all the three cases are given below:

• 1. When all the input places of $t_{1}$ (without label) have the same partial array as token.

  • Each input place should have at least the required number of partial arrays.

  • Firing $t_{1}$ removes partial array from all the input places and moves the partial array to all its output places.

  The graph in Fig. 1 shows the position of the partial array before the transition fires and Fig. 2 shows the position of the partial array after transition $t_{1}$ fires.

• 2. When all the input places of $t_{1}$ have different partial arrays as token

  • The label of $t_{1}$ designates one of its input places.

  • The designated input place has sufficient number of partial arrays as tokens.

  • Firing $t_{1}$ removes partial array from all the input places and moves the partial array from the designated input place to all its output places.

  The graph in Fig. 3 shows the position of the partial array before the transition fires and Fig. 4 shows the position of the partial array after transition $t_{1}$ fires. Since the designated place is $P_{1}$, the partial array in $P_{1}$ is moved to the output place.

• 3. When all the input places of $t_{1}$ (with catenation rule as label) have the same partial array as token

  • Each input place should have at least the required number of partial arrays.

  • The condition for catenation should be satisfied.

  • The designated input place has sufficient number of partial arrays as tokens.

  • Firing $t_{1}$ removes partial array from all the input places P and the catenation is carried out in all its output places.

Fig. 3.

Transition with label before firing

Fig. 4.

Transition with label after firing

Catenation Rule as Label for Transitions

Column catenation rule is in the form . Here the partial array A denotes the $m\times n$ partial array in the input place of the transition. B is a partial array whose number of rows will depend on ‘m’, the number of rows of A. The number of columns of B is fixed. For example adds two columns of x after the last column of the partial array A which is in the input place. But would add two columns of x before the first column of A. ‘m’ always denote the number of rows of the input partial array A. Row catenation rule is in the form . Here again the partial array A denotes the $m\times n$ partial array in the input place of the transition. B is a partial array whose number of columns will depend on ‘n’, the number of columns of A. The number of rows of B is always fixed. For example adds two rows of x after the last row of the array A which is in the input place. But would add two rows of x before the first row of the partial array A. ‘n’ always denotes the number of columns of the input partial array A.

An example to explain row catenation rule is given below. The position of the partial array before the transition fires is shown in Fig. 5 and Fig. 6 shows the position of the partial array after transition $t_{1}$ fires. Since the catenation rule is associated with the transition, catenation takes place in $P_{3}$.

Fig. 5.

Transition with catenation rule before firing

Fig. 6.

Transition with catenation rule after firing

In $A_\diamondsuit = \begin{array}{ccc} a &{} a &{} a \\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \end{array}$, the number of columns of A is 3, $n-1$ is 2, firing $t_1$ adds the row $\begin{array}{ccc} x&x&y \end{array}$ as the last row. Hence $A_{1\diamondsuit } = \begin{array}{ccc} a &{} a &{} a \\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \\ x &{} x &{} y \end{array}$

Example 3

Let $\varSigma = \{a\}$, $F=P_{1}$, where $S_{\diamondsuit }= \begin{array}{ccc} a &{} a &{} a \\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \\ \end{array}$,    $Q_{1}=(\diamondsuit )_{m}$, $Q_{2}=(\diamondsuit )^{n}$    $Q_{3}=(a)_{m}$,    $Q_{4}=(a)^{n}$

S is the initial partial array placed in $P_{1}$. The PATPNS is shown in Fig. 7. Derivations in PATPNS is given in the following tabular column.

Input place	Transition	Output place
S		$\begin{array}{cccc} a &{} a &{} a &{} \diamondsuit \\ a &{} \diamondsuit &{} a &{} \diamondsuit \\ a &{} a &{} a &{} \diamondsuit \end{array}$
$\begin{array}{cccc} a &{} a &{} a &{} \diamondsuit \\ a &{} \diamondsuit &{} a &{} \diamondsuit \\ a &{} a &{} a &{} \diamondsuit \end{array}$		$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \end{array}$
$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \end{array}$		$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$
$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$		$\begin{array}{ccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$
$\begin{array}{ccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$		$\begin{array}{cccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$
$\begin{array}{cccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$		$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$
$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$		$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$
$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$		$\begin{array}{ccccccc} a &{} a &{} a &{} a &{} a &{} a &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$

Fig. 7.

PATPNS generating square partial arrays of size $4k+3$, $k \ge 0$

The firing of sequence $(t_{1}t_{2}t_{3}t_{4}t_{5}t_{6}t_{7}t_{8})^{k}$, $k\ge 0$ puts a square partial arrays of size $4k+3$ in $P_{1}$, where the boundaries of the squares are alternatively $\diamondsuit$’s and a’s. The partial array language generated by the PATPNS is a square partial array of size $4k+3$, $k\ge 0$ where the boundaries are alternatively $\diamondsuit$’s on the odd numbered boundaries and a’s on the even numbered boundaries.

Theorem 1

The family of languages generated by PATPNS is properly contained in the family of languages generated by Basic Puzzle Partial Array Grammars.

Proof

The row catenation in PATPNS can be handled by the following Basic Puzzle Partial Array Grammar rules:

The column catenation in PATPNS can be handled by the following Basic Puzzle Partial Array Grammar rules:

Hence ${\mathcal L}(PATPNS)$ is a subset of ${\mathcal L}(BPPAG)$, this is also evident from the following example.

Consider a partial array language of square partial arrays of size $4k+3$, $k\ge 0$ whose boundaries are alternatively $\diamondsuit$’s on the odd numbered boundaries and a’s on the even numbered boundaries given in Example 3. This partial array language is generated by both systems PATPNS and BPPAG.

Now let us consider a BPPAG generating this partial array language.

$$BPG_{P_{2}}=(A,B\cup \{\diamondsuit \},P,S)$$

where $A=\{X,Q_{1},Q_{2},Q_{3},Q_{4},Q_{5},Q_{6}\}$, $B=\{a\}$, $S=X$ and P consists of the following rules:

The first member of the language generated is shown below:

The partial array language given in Example 2 generated by BPPAG cannot be generated by PATPNS, since the axiom array $\begin{array}{cc} z &{} z \\ z &{} z \\ \end{array}$ can only be concatenated either row wise or column wise, but $\diamondsuit$ cannot be inserted, which proves a proper containment.

4 Partial Array Token Petri Net P System

In this section, Partial Array Token Petri Net P System (PATPNPS) is introduced and it is compared with PATPNS and BPPAG.

Definition 11

A Partial Array Token Petri Net P System (PATPNPS) $\pi =(V,T\cup \{\diamondsuit \},\#,\mu ,F_{1},F_{2},\dots ,F_{m},R_{1},R_{2},\dots ,R_{m},i_{0})$ where V is a finite set of column partial arrays and row partial arrays of the form $Q_{1}=(a)^{n}$ and $Q_{2}=(a)_{m}$ where $a\in T\cup \{\diamondsuit \}$. T is a finite set of terminal alphabets. ‘$\#$’ is a blank symbol not in $T\cup \{\diamondsuit \}$. $\mu$ is a membrane structure with ‘m’ membranes, $F_{1},F_{2},\dots ,F_{m}$ are finite set of partial arrays over $T\cup \{\diamondsuit \}$ associated with the ‘m’ regions. $R_{1},R_{2},\dots ,R_{m}$ are rules associated with the m regions of the form , where $tar \in \{here, in, out\}$ and P is the output obtained after the catenation rule is applied.

If the target indication is ‘here’, the output partial array ‘P’ remains in the same region, if the target indication is ‘in’, ‘P’ goes to the immediate inner region and if the target indication is ‘out’ it goes to the outer membrane, $i_{0}$ is the elementary membrane of $\mu$.

A computation in a partial array token petri net P system is defined in the same way as in array rewriting P system. The set of all partial arrays computed by $\pi$ with ‘m’ membranes is denoted by $PATPNPL_{m}(\pi )$.

Example 4

Consider the Partial Array Token Petri Net P System PATPNPS

$$\pi _{1}=(\{Q_{1},Q_{2},Q_{3},Q_{4}\},\{a,\diamondsuit \},\#,[_{1}[_{2}[_{3}]_{2}]_{1},F_{1\diamondsuit },F_{2\diamondsuit },F_{3\diamondsuit },R_{1},R_{2},R_{3},3)$$

where $Q_{1}=(\diamondsuit )_{m}$, $Q_{2}=(\diamondsuit )^{n}$, $Q_{3}=(a)_{m}$, $Q_{4}=(a)^{n}$, $F_{1\diamondsuit }=\begin{array}{ccc} a &{} a &{} a\\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \\ \end{array}$, $F_{2\diamondsuit }=F_{3\diamondsuit }=\phi$,

The content of region 1 is $F_{1\diamondsuit }=\begin{array}{ccc} a &{} a &{} a \\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \\ \end{array}$. The derivations in PATPNPS is given in the following tabular column:

Region(i)	Content($F_{i\diamondsuit }$)	Rule($R_i$)	Target	Resultant partial array ($P_i$)
1	$\begin{array}{ccc} a &{} a &{} a \\ a &{} \diamondsuit &{} a \\ a &{} a &{} a \end{array}$		here	$\begin{array}{cccc} a &{} a &{} a &{} \diamondsuit \\ a &{} \diamondsuit &{} a &{} \diamondsuit \\ a &{} a &{} a &{} \diamondsuit \end{array}$
1	$\begin{array}{cccc} a &{} a &{} a &{} \diamondsuit \\ a &{} \diamondsuit &{} a &{} \diamondsuit \\ a &{} a &{} a &{} \diamondsuit \end{array}$		here	$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \end{array}$
1	$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \end{array}$		here	$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$
1	$\begin{array}{ccccc} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$		in	$\begin{array}{ccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$
2	$\begin{array}{ccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit \end{array}$		here	$\begin{array}{cccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$
2	$\begin{array}{cccccc} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$		here	$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$
2	$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \end{array}$		here	$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$
2	$\begin{array}{ccccccc} a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$		$\begin{array}{c} \text {in} \\ \text {or} \\ \text {out} \end{array}$	$\begin{array}{ccccccc} a &{} a &{} a &{} a &{} a &{} a &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$
$\begin{array}{c} 3 \\ \text {(If tar=in)} \end{array}$	$\begin{array}{ccccccc} a &{} a &{} a &{} a &{} a &{} a &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$	$\phi$	-	$\begin{array}{c} \begin{array}{ccccccc} a &{} a &{} a &{} a &{} a &{} a &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}\\ \begin{array}{c} \text {The output is} \\ \text {collected in the} \\ \text {elementary} \\ \text {membrane} \end{array} \end{array}$
$\begin{array}{c} 1 \\ \text {(If tar=out)} \end{array}$	$\begin{array}{ccccccc} a &{} a &{} a &{} a &{} a &{} a &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} \diamondsuit &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} a &{} a &{} a &{} \diamondsuit &{} a \\ a &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} \diamondsuit &{} a \\ a &{} a &{} a &{} a &{} a &{} a &{} a \end{array}$		here	$\begin{array}{c} \text {Procedure} \\ \text {continues} \end{array}$

Thus the partial array language of square partial arrays of size $4k+3$, $k\ge 0$, where the boundaries are alternatively $\diamondsuit$’s on the odd numbered boundaries and a’s on the even numbered boundaries is generated by this PATPNPS $\pi _{1}$.

Theorem 2

${\mathcal L}(PATPNPL_{m}(\pi )) \cap \mathcal L(PATPNS) \ne \phi$.

Proof

The partial array language of square partial arrays of size $4k+3$, $k\ge 0$ is generated by both systems. It is evident from Examples 3 and 4.

Theorem 3

${\mathcal L}(PATPNPL_{m}(\pi )) \cap {\mathcal L}(BPPAG) \ne \phi$.

Proof

${\mathcal L}(PATPNS)$ is a subclass of the family of Basic Puzzle Partial Array Languages by Theorem 1. By Theorem 2, we get that ${\mathcal L}(PATPNPL_{m}(\pi ))$ intersects ${\mathcal L}(PATPNS)$. Thus the two families intersects.

5 Comparative Study with Local and Recognizable Partial Array Languages

In this section, we recall Local and Recognizable Partial Array Languages and compare with PATPNS.

Definition 12

[14] Let $\varGamma _p = \varGamma \cup \{\diamondsuit \}$ be a finite alphabet. A two dimensional partial array language $PL \subseteq \varGamma _p^{**}$ is local if there exists a finite set $\theta$ of tiles over the alphabet $\varGamma _p \cup \{\#\}$ such that $PL = \{A \in \varGamma _p^{**} / B_{2,2}(\hat{A}) \subseteq \theta \}$, where $\hat{A}$ is a partial array surrounded by a special boundary symbol $\# \not \in \varGamma$.

The partial array language PL is local if given such a set $\theta$, we can exactly retrieve the language PL. We call the set $\theta$ a representation by tiles for the local language PL and write $PL = L(\theta )$. The family of all local partial array languages is denoted by PAL-LOC.

Example 5

[14] Let $\varGamma _p = \{a, b\} \cup \{\diamondsuit \}$, and $\theta$ be the following set of tiles over $\varGamma _p \cup \{\#\}$.

$$\begin{aligned} \theta&= \left\{ \begin{array}{|c|c|} \hline \# &{} \# \\ \hline \# &{} b \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} \# \\ \hline b &{} b \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} \# \\ \hline b &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} b \\ \hline \# &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} b \\ \hline a &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} b \\ \hline \diamondsuit &{} b \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} \# \\ \hline b &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \diamondsuit \\ \hline a &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} b \\ \hline a &{} b \\ \hline \end{array}, \right. \\&\left. \quad \begin{array}{|c|c|} \hline a &{} a \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} b \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} \# \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} b \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \diamondsuit \\ \hline a &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} \diamondsuit \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} b \\ \hline \diamondsuit &{} b \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} \diamondsuit \\ \hline a &{} a \\ \hline \end{array} \right\} \end{aligned}$$

Then $L(\theta )$ is a partial array language over $\varGamma _p$ with equal sides of length, the symbols along the top row (the last row) and right most column (the last column are b’s, the symbols along the first row (the bottom row) and the left most column (the first column) except the first and last elements of the principal diagonals are a’s. The remaining elements of the array are holes.

The first two members of this language are given below:

$$\begin{matrix} b &{} b &{} b \\ a &{} \diamondsuit &{} b \\ a &{} a &{} b \end{matrix}, \quad \begin{matrix} b &{} b &{} b &{} b \\ a &{} \diamondsuit &{} \diamondsuit &{} b \\ a &{} \diamondsuit &{} \diamondsuit &{} b \\ a &{} a &{} a &{} b \end{matrix}, \quad \dots $$

Definition 13

[14] Let $\varSigma$ be a finite alphabet. A partial array language $PL \subseteq \varSigma _p^{**}$ is called recognizable if there exists a local partial array language $PL'$ over $\varGamma _p$ and a mapping $\pi : \varGamma _p \rightarrow \varSigma _p$ such that $PL = \pi (PL')$, where $\varSigma _p = \varSigma \cup \{\diamondsuit \}$. The family of all recognizable partial array languages is denoted by PAL-REC.

Example 6

[14] The set of all partial array languages over one letter alphabet ‘a’ with all sides of equal length and the symbols along the first row, first column, the last row and last column are holes is not a local partial array language, but it is a recognizable partial array language. This language is obtained from Example 5 by taking a mapping $\pi : \varGamma _p \rightarrow \varSigma _p$ where $\varGamma = \{a, b\}$, $\varSigma = \{a\}$ such that $\pi (b) = \pi (a) = \diamondsuit$ and $\pi (\diamondsuit ) = a$.

Theorem 4

$PAL-LOC \subsetneq PATPNS$.

Every local partial language can be easily generated by some PATPNS. Let PL be a partial array language over $\varGamma _p$ in PAL-LOC with a finite set of tiles $\theta$ such that $PL = L(\theta )$.

Consider the PATPNS, $C = (P, T, I, O)$ with partial arrays over $\varGamma _p^{**}$, $S_\diamondsuit = \begin{array}{|c|c|} \hline \# &{} \# \\ \hline \# &{} a \\ \hline \end{array}$, $a \in \varGamma _p$. T, the set of all transitions, they can be either row or column catenations.

• (i) For all $\begin{array}{|c|c|} \hline \# &{} \# \\ \hline \# &{} a \\ \hline \end{array} \in \theta$, where $a \in \varGamma _p$ we define , where $Q_1 = \begin{pmatrix} \# \\ b \end{pmatrix}$, $b \in \varGamma _p$.

• (ii) For all $\begin{array}{|c|c|} \hline \# &{} \# \\ \hline a &{} b \\ \hline \end{array} \in \theta$, $a, b \in \varGamma _p$, we define , where $Q_1 = \begin{pmatrix} \# \\ b \end{pmatrix}$, $b \in \varGamma _p$. This transition is repeated till the tile of the form $\begin{array}{|c|c|} \hline \# &{} \# \\ \hline b &{} \# \\ \hline \end{array} \in \theta$ is reached and let this process be repeated ‘r’ $r \ge 0$, no. of times.

• (iii) For all $\begin{array}{|c|c|} \hline \# &{} \# \\ \hline b &{} \# \\ \hline \end{array} \in \theta$, $b \in \varGamma _p$, we define , where $Q_2 = \begin{pmatrix} \# \\ \# \end{pmatrix}$.

• (iv) For all $\begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} b \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} c \\ \hline b &{} d \\ \hline \end{array}, \begin{array}{|c|c|} \hline c &{} \# \\ \hline d &{} \# \\ \hline \end{array} \in \theta$, $a, b, c, d \in \varGamma _p$, we define , where $Q_3 = \begin{pmatrix} \#&B&\# \end{pmatrix}$, $B \in \varGamma _p^{(1 \times n)}$, where $\varGamma _p^{(1 \times n)}$ is a partial array of size $1 \times n$.

• (v) For all tiles of the form $\begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} b \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline b &{} \# \\ \hline \# &{} \# \\ \hline \end{array} \in \theta$, $a, b \in \varGamma _p$, we define , $Q_4 = (\#)_m$, $m \ge 2$. Here, A represents the partial array collected in the output place by the previous transition.

$$P = \{P_1, \underbrace{P_2, P_3, \dots P_k}_{t_2}, \underbrace{P_{k+1}}_{t_3}, \underbrace{P_{k+2}, P_{k+3}, \dots P_{k+s+1}}_{t_4}, \underbrace{P_{k+s+2}}_{t_5}\},$$

where P is the set of places, $S_\diamondsuit$ is placed in $P_1$ initially and then transition $t_1$ is applied, the resultant partial array is stored in $P_2$, and then transition $t_2$ is applied ‘r’ no. of times. After applying ‘r’ times the transition $t_2$, the partial array reaches the place $P_k$, where $k = r+2$. After transition $t_3$ is applied the partial array reaches $P_{k+1}$. The transition $t_4$ is repeated ‘s’ $s \ge 0$ number of times until the tile $\begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} \# \\ \hline \end{array}$ is reached. After this transition, the partial array reaches the place $P_{k+s+1}$. After transition $t_5$ is applied the partial array reaches the final place $F = P_{k+s+2}$.

The PATPNS generating the local language PL is given in Fig. 8.

Fig. 8.

PATPNS generating any PAL-LOC

Clearly PATPNS can generate any partial array language in PAL-LOC and hence $PAL-LOC \subseteq PATPNS$.

Now, to prove the proper inclusion, we consider the partial array language given in Example 3, the square partial arrays of size $4k+3$, $k \ge 0$. This language is not local, since the $\theta$ set of this language can also generate any array over one letter alphabet ‘a’ of size $1 \times n$, $n \ge 1$, where $\theta$ is given as follows.

$$\begin{aligned} \theta&= \left\{ \begin{array}{|c|c|} \hline \# &{} \# \\ \hline \# &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} \# \\ \hline a &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} \# \\ \hline a &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline \# &{} a \\ \hline \# &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} a \\ \hline a &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} a \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} a \\ \hline \diamondsuit &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \# \\ \hline a &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \diamondsuit \\ \hline a &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} \diamondsuit \\ \hline \diamondsuit &{} a \\ \hline \end{array}, \right. \\ {}&\quad \left. \begin{array}{|c|c|} \hline \diamondsuit &{} \diamondsuit \\ \hline a &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} \diamondsuit \\ \hline a &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} a \\ \hline \diamondsuit &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \diamondsuit \\ \hline a &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} a \\ \hline a &{} a \\ \hline \end{array}, \begin{array}{|c|c|} \hline \diamondsuit &{} a \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} a \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \diamondsuit \\ \hline \diamondsuit &{} \diamondsuit \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} a \\ \hline \# &{} \# \\ \hline \end{array}, \begin{array}{|c|c|} \hline a &{} \# \\ \hline \# &{} \# \\ \hline \end{array} \right\} \end{aligned}$$

Hence PAL-LOC is properly contained in PATPNS.

Example 7

Consider a PATPNS $C = (P, T, I, O)$, generating a local partial array language given in Example 5.

Let $S_\diamondsuit = \begin{array}{|c|c|} \hline \# &{} \# \\ \hline \# &{} b \\ \hline \end{array}$, $Q_1 = \begin{bmatrix} \# \\ b \end{bmatrix}$, $Q_2 = \begin{bmatrix} \# \\ \# \end{bmatrix}$, $Q_3 = \begin{bmatrix} \#&B&\# \end{bmatrix}$, $B \in \varGamma _p^{1 \times n}$, where $B = a \ (\diamondsuit )_r \ b$, $Q_4 = (\#)_m$.

PATPNS generating the 2$^{nd}$ member of the partial array language namely $\begin{matrix} \# &{} \# &{} \# &{} \# &{} \# &{} \# \\ \# &{} b &{} b &{} b &{} b &{} \# \\ \# &{} a &{} \diamondsuit &{} \diamondsuit &{} b &{} \# \\ \# &{} a &{} \diamondsuit &{} \diamondsuit &{} b &{} \# \\ \# &{} a &{} a &{} a &{} b &{} \# \\ \# &{} \# &{} \# &{} \# &{} \# &{} \# \end{matrix}$ is given in Fig. 9 as an example.

Fig. 9.

PATPNS generating PAL-LOC given in Example 5

Theorem 5

PATPNS is closed under projection.

We consider a partial array token Petri Net structure $C = (P, T, I, O)$ generating the partial array language PL. Let $\pi : \varGamma _p \rightarrow \varSigma _p$ be a projetion such that $\pi (a) = \alpha$, $a \in \varGamma _p$, $\alpha \in \varSigma _p$. Without loss of generality $\varGamma _p \cap \varSigma _p = \phi$. We can construct a PATPNS $C' = (P', T', I', O')$ such that $PL(C') = PL$, where $T' = \{t_1', t_2', \dots t_k'\}$, , $1 \le i \le k$, $A, Q_i \in \varGamma _p^{**}$, $A', Q_i' \in \varSigma _p^{**}$. $I'$ and $O'$ are input and outplaces of the transitions. $P'$ is the set of places.

Hence we can clearly say that PATPNS is closed under projection.

Theorem 6

$PAL-REC \subsetneq PATPNS$.

Proof

$PAL-REC \subseteq PATPNS$ follows from Theorems 4 and 5, since every recognizable partial array language is a projection of a local partial array language.

Now the proper inclusion can be proved easily by giving an example of a partial array language which is not in PAL-REC but in PATPNS.

6 Conclusion

In this paper we have proposed PATPNS and PATPNPS. PATPNS is compared with PAL-LOC, PAL-REC and BPPAG. It is also compared with PATPNPS. The properties of PATPNS and PATPNPS can be studied further by introducing inhibitor arc to increase the generative capacity of PATPNS. This is our future work.