Keywords

1 Introduction

Since seventies, the study of two dimensional languages generated by Grammars or recognized by Automata have been found in the theory of formal languages with the insight of computations in picture processing and pattern recognition [5, 12, 13]. In the quest of syntactic techniques for generation of digital picture patterns, a number of 2D Grammars have been proposed. Siromoney Matrix grammars [17], Kolam Array Grammars (KAG) [15, 16], Tabled 0L/1L grammars (T0LG/TILG) [14] are some of the classical formalisms. Pure 2D context free grammars with regular control (RP2DCFG) [18], Prusa grammars (PG) [11], Regional Tile Rewriting grammars [10] are some of the recent and more expressive grammars. Tiling systems [3, 5] is a recognizing device for a ground level class of array languages REC, which involves the projection of the languages belonging to the class of local languages (LOC). Mutual relationship between these new formalisms and also with LOC is analysed in [2].

Recently another picture generating mechanism, Array token Petri Net structure ATPNS [8], has been evolved from string generating Petri nets [1, 6]. Petri Net [9] is one of the formal models used for analyzing systems that are concurrent, distributed and parallel. Tokens are the elements used to simulate the dynamism of the Petri Net systems. The language generated by the Petri net is set of all feasible transition sequence in that net. In ATPNS model, the authors have used arrays as tokens in some of the places as initial configuration called marking and catenation rules as labels of transitions. The language generated is the set of all arrays created at final places of the net. This model along with a control feature called inhibitor arcs generate the same family of languages as generated by KAG, T0LG and P2DCFG with regular control. To increase the generative capacity of this model, adjunction rules are introduced and Adjunct Array Token Petri net systems (AATPNS) [7] is defined. This new model generates Table 1L languages and strictly included ATPNS family of Languages.

Since AATPNS has been only compared with classical formalisms, we try to study the comparison of this model with recent generating devices and also with LOC for the expressiveness with respect to its generating capacity.

This paper is organized in the following manner. In Sect. 2, basic definitions of various array grammars, Petri Nets and notions of Petri nets pertaining to arrays have been recalled. In Sect. 3, we recall the definition of adjunct array token Petri nets, in more generalized form and provide some illustrative examples. In Sect. 4, we compare this model with various classes of picture languages generated by recent grammars and also with class LOC, for the understanding of generative capacity of this model.

2 Preliminaries

The following definitions and notations are mainly from [5, 8, 10, 18].

2.1 Array Grammars

Definition 1

Let J ** denotes the set of all arrays (pictures) over the elements of a finite set J and J ++ denotes set of all non empty arrays over J. For l, m ≥ 0, J (l, m) represents the set of arrays of size (l, m). An array (picture) language is a subset of J ** . If p ∊ J ** , then p(i, j) denotes a pixel in the place of ith row and jth column of p. \( \left| p \right|_{col} \) denotes the number of columns of p and \( \left| p \right|_{row} \) denotes the number of rows of p. A B denotes a column catenation of the array A with array B which is defined when A and B have same number of rows. A B denotes row catenation of A with B provided the number of columns of A and B are same. If x ∊ J ** then (x)n (resp. (x) m ) denotes horizontal (resp. vertical) juxtaposition of m copies of x.

Pure 2D context free grammars (P2DCFG) which make use of only terminal symbols have been recently studied [18]. Pure 2D context-free grammars, unlike Siromoney matrix grammars [17], admit rewriting any row/column of pictures with no priority of columns and rows. Row/column sub-arrays of pictures are rewritten in parallel by equal length strings and by using only terminal symbols, as in a pure string grammar.

Definition 2

A pure 2D context-free grammar (P2DCFG) is a 4-tuple \( G = (\varSigma ,P_{c} ,P_{r} ,{\mathcal{M}}_{0} ) \) , where Σ is a set of symbols, \( P_{c} = \{ t_{ci} /1 \le i \le m\} \), \( P_{r} = \{ t_{rj} /1 \le j \le n\} \).

Each t ci (1 ≤ i ≤ m), called a column table, is a set of context free rules of the form a → α, a ∊ Σ, α ∊ Σ * such that any two rules of the form a → α, b → β in t ci , have |α| = |β| where |α| denotes the length of α.

Each t rj (1 ≤ j ≤ n), called a row table, is a set of context free rules of the form c → γ T , c ∊ Σ, γ ∊ Σ * such that any two rules of the form c → γ T , d → δ T in t rj , have |γ| = |δ|.

M 0  ⊆ Σ ** − {λ} is a finite set of axiom arrays.

Derivations are defined as follows. For any two arrays M 1 , M 2 , M 1  ⇒ M 2 denotes that M 2 is obtained from M 1 by either rewriting a column of M 1 by rules of a column table t ci in P c or a row of M 1 by rules of a row table t rj in \( P_{r \cdot } \mathop \Rightarrow \limits^{*} \) is the reflexive transitive closure of ⇒.

The picture language L(G) generated by G is the set of rectangular picture arrays {\( M/M_{0} \mathop \Rightarrow \limits^{*} M \in \varSigma^{**} \) , for some \( M_{0} \in {\mathcal{M}}_{0} \)}.

The family of picture array languages generated by pure 2D context-free grammars is denoted by P2DCFL.

Definition 3

A pure 2D context-free grammar with a regular control (RP2DCFG) is G c  = (G, Lab(G), C), where G is a pure 2D context-free grammar, Lab(G) is a set of labels of the tables of G and C ⊆ Lab(G)* is a regular string language. The words of Lab(G)* are called control words of G. Derivations \( M_{ 1} \mathop \Rightarrow \limits^{w} M_{ 2} \) in G c are done as in G, except that if w ∊ Lab(G)* and \( w = l_{ 1} l_{ 2} \ldots l_{m} \) ,then the tables of rules with labels \( l_{ 1} ,l_{ 2} \ldots l_{m} \) are successively applied starting from M 1 to yield M 2 . The picture array language generated by G c consists of all picture arrays obtained from the axiom array of G c with derivations controlled as described above. (R)P2DCFL denotes the family of all picture array languages generated by pure 2D context-free grammars with a regular control.

The family P2DCFL is strictly included in family RP2DCFL [18].

Tiling Systems, a recognizing device for the class REC, uses Local languages as projections. A local language is defined by a set of 2 × 2 arrays (tiles).

Definition 4

Let J be a finite alphabet, θ be a finite set of tiles over J ∪ {#} The local language defined by \( L = \{ p \in J^{ + + } |[[\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{p} ]] \subseteq \varTheta \} \) where \( [[\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{p} ]] \) denotes the set of all tiles contained in p surrounded by a special symbol \( \# \notin J \) . The family of all local languages is denoted by LOC.

Prusa Grammar device admits parallel application of rules so that non terminal symbols can be substituted with rectangular subpictures simultaneously. This model has more generative power than context free KAG [11].

Definition 5

Prusa Grammar (PG) is a tuple (J, N, R, S), where J is the finite set of terminal symbols, disjoint from the set N of non terminal symbols; S ∊ N is the start symbol; and R ⊆ N × (N ∪ J)++ is the set of rules.

Let G = (J, N, R, S) be a PG. We define a picture language L(G, A) over J for every A ∊ N. The definition is given by the following recursive descriptions:

  1. 1.

    if A → w is in R, and w ∊ Σ ++ , then w ∊ L(G, A);

  2. 2.

    let A → w be a production in R, w = (N ∪ Σ)(m ,n) , for some m, n ≥ 1, and p i, j , with 1 ≤ i ≤ m, 1 ≤ j ≤ n, be pictures such that:

    1. (a)

      if w(i, j) ∊ Σ, then p i, j  = w(i, j);

    2. (b)

      if w(i, j) ∊ N, then p i,j  ∊ L(G, w(i, j));

    3. (c)

      if \( P_{k} = p_{k,1} \) \( p_{k,2} \) … \( p_{k,n} \) , for any \( 1 \le i \le m \), \( 1 \le j \le n \), \( |p_{i,j} |_{col} = |p_{i + 1,j} |_{col} \) and \( P = P_{1} \,{ \ominus }\,P_{2} \,{ \ominus } \ldots { \ominus }\,P_{m} \) ; then P ∊ L(G, A).

The set L(G, A) contains exactly the pictures that can be obtained by applying a finite sequence of rules (1) and (2). The language L(G) generated by grammar G is denoted as L(G, S).

Tile Grammars (TG) [4] perform an isometric derivation process for which homogeneous subpictures are replaced with isometric pictures of the local language defined by the right part of the rules.

Definition 6

A tile grammar (TG) is a tuple (J, N, S, R), where J is the terminal alphabet, N is a set of non terminal symbols, S ∊ N is the starting symbol, R is a set of rules. Let A ∊ N. There are two kinds of rules:

  1. 1.

    fixed size: A → t, where t ∊ Σ;

  2. 2.

    variable size: A → ω, ω is a set of tiles over N ∪ {#}.

At each step of the derivation, an A-homogeneous sub picture is replaced with an isometric picture of the local language defined by the right part α of a rule A → α, where α admits a strong homogeneous partition. The process terminates when all non terminals have been eliminated from the current picture.

Regional Tile Grammars (RTG) [10] are the Tile Grammars with specified set of tiling.

Definition 7

A homogeneous partition is regional (HR) iff distinct (not necessarily adjacent) subdomains have distinct labels. A picture p is regional if it admits a HR partition. A language is regional if all its pictures are so. A regional tile grammar (RTG) is a tile grammar (see Definition 6), in which every variable size rule A → ω is such that LOC(ω) is a regional language.

2.2 Petri Nets

Definition 8

Petri Net is one of the mathematical modeling tools for the description of distributed systems involving concurrency and synchronization. It is a weighted directed bipartite graph consisting of two kinds of nodes called places (represented by circles) and transitions (represented by bars). Places represents conditions and transition represents events. The places from which a directed arc runs to a transition are called input places of the transition and the places to which directed arcs run from a transition are called output places. Places in Petri nets may contain a discrete number of marks called tokens. Any distribution of tokens over the places will represent a configuration of the net called a marking. In the abstract sense, a transition of a Petri net may fire if it is enabled; when there are sufficient tokens in all of its input places.

Definition 9

A Petri net structure is a four tuple \( C = \left\langle {Q,T,I,O} \right\rangle \) where \( Q = \{ q_{1} ,q_{2} , \ldots ,q_{n} \} \) is a finite set of places, n ≥ 0, T = {t 1 , t 2 , … , t m } is a finite set of transitions \( m \ge 0 \), \( Q \cap T = \phi \) , I:T → Q ∞ is the input function from transitions to bags of places and O:T → Q ∞ is the output function from transitions to bags of places.

Definition 10

An inhibitor arc from a place q l to a transition t k has a small circle in the place of an arrow in regular arcs. This means the transition t k is enabled only if q l has no tokens in it. In other words a transition is enabled only if all its regular arc input places have required number of tokens and all its inhibitor arc (if exists) input places have zero tokens.

2.3 Array Token Petri Nets

In the array generating Petri Net structure, arrays over an alphabet J are used as tokens in some input places.

Definition 11

Row (resp. column) catenation rules in the form of \( A\,{\ominus}\,B \) (resp. A  B) can be associated with a transition t as a label, where A is a m × n array in the input place and B is an array language whose number of columns (resp. rows) depends on the number of columns (resp. rows) of A. Three types of transitions can be enabled and fired

  1. (1)

    When all the input places of transition t (without label) having the same array as tokens

    • Each input place should have at least the required number of tokens (arrays)

    • Firing t removes arrays from all its input places and moves the array to all its output places

  1. (2)

    When all the input places of transition t have the different arrays as tokens

    • The label of t designates one of its input places which has sufficient number of same arrays as tokens

    • Firing t removes arrays from all its input places and moves the array from the designated input place to all its output places.

  1. (3)

    When all the input places of transition t (with row or column catenation rule as label) have the same array as tokens

    • Each input place should have at least the required number of tokens (arrays)

    • Firing t removes arrays from all its input places and creates the catenated array as per the catenation rule, in all its output places

In all the three types, firing of a transition t is enabled only if all the input places corresponding to inhibitor arcs (if exist) does not have any tokens in it.

Definition 12

An Array Token Petri net structure (ATPNS) is a five tuple \( N = \left\langle {J,C,M_{0} ,\rho ,F} \right\rangle \) where J is a given alphabet, \( C = \left\langle { Q, \, T, \, I, \, O } \right\rangle \) is a Petri net structure with tokens as arrays over J, \( M_{0} :Q \to J^{**} \) , is the initial marking of the net, ρ:T → L, a mapping from the set of transitions to set of labels of transitions and \( F \subset Q \) , is a finite set of final places.

Definition 13

If P is an ATPNS then the language generated by P is defined as \( L(P) = \{ X \in J^{**} /X \) is in the place q for some q in F}. Starting with arrays (tokens) over a given alphabet as initial marking, all possible sequences of transitions are fired. Set of all arrays created in final places of F is called the language generated by Petri Net structure.

3 Adjunct Array Token Petri Net Structure

In this section, we recall the notions of adjunct array token Petri net structure [7] in generalized form and give some examples.

Definition 14

Adjunction is a generalization of catenation. In the row catenation \( A\,{ \ominus }\,B \) , the array B is joined to A after the last row. But row adjunction can join the array B into array A after any row of A. Similarly column adjunction can join the array B into array A after any column of A. Let A be an m × n array in J ** called host array; B ⊂ J ** be an array language whose members, called adjunct arrays have fixed number of rows. A row adjunct rule (RAR) joins an adjunct array B into a host array A in two ways : By post rule denoted by (A, B, ar j ), array B is juxtaposed into Array A after jth row and by pre rule denoted by (A, B, br j ), array B is juxtaposed into Array A before jth row. The number of columns of B is same as the number of columns of A. In the similar notion column adjunct rule (CAR) can also be defined in two ways : post rule (A, B, ac j ) and pre rule (A, B, bc j ) joining B into A, after jth column of A and before jth column of A respectively. It is obvious that a row catenation rule \( A{ \ominus }B \) in ATPNS is a post RAR rule (A, B, ar m ) and column catenation rule A  B is a post CAR rule (A, B, ac n ). Transitions of a Petri net structure can also be labeled with row or column adjunct rules.

Definition 15

An Adjunct Array Token Petri Net Structure (AATPNS) is a five tuple \( N = \left\langle {J,C,M0,\rho ,F} \right\rangle \) where J is a given alphabet, \( C = \left\langle {Q,T,I,O} \right\rangle \) is a Petri net structure with tokens as arrays over J, M 0 :Q → J ** , is the initial marking of the net, ρ:T → L, a mapping from the set of transitions to set of labels where catenation rules of the labels are either RAR or CAR and F ⊂ Q, is a finite set of final places.

In AATPNS, the types of transitions which can be enabled and fired are similar to that of Definition 11 except the type (3) where labels of transitions may be RAR or CAR rules instead of row or column catenation rules.

When all the input places of a transition t (with RAR or CAR rule as label) have the same array as tokens.

Each input place should have at least the required number of tokens (arrays)

  • Firing t removes arrays from all its input places and creates the array through adjunction as per the RAR or CAR rule, in all its output places In all the three types, firing of a transition t is enabled only if all the input places corresponding to inhibitor arcs (if exists) does not have any tokens in it.

Definition 16

If P is an AATPNS then the language generated by P is defined as L(P) = {X ∊ J ** /X is in the place q for some q in F}. Starting with arrays (tokens) over a given alphabet as initial marking, all possible sequences of transitions are fired. Set of all arrays created in final places F is called the language generated by AATPNS Petri Net structure.

Example 1

Consider the Adjunct Array token Petri net structure \( P_{2} = \left\langle {J,C,M_{0} ,\rho ,F} \right\rangle \) where J = {0, 1}, C = (Q, T, I, O), Q = {q 1, q 2}, T = {t 1, t 2}, I(t 1) = {q 1}, I(t 2) = {q 2}, O(t 1) = {q 2}, O(t 2) = {q 1}, M 0 is the initial marking: the array S is in q 1 and there is no array in q 2, ρ(t 1) = (A, B 1, ac n ) and ρ(t 2) = (A, B 2, ar m ) and F = {q 1}.

Where \( S = \begin{array}{*{20}c} 1 & 0 \\ 0 & 1 \\ \end{array} \), and B 1 = (0) m and B 2 = (0)n−11. Initially t 1 is the only enabled transition. Firing of t 1 adjoins a column of 0’s after the last column of array S and puts the derived array in q 2, making t 2 enabled. Firing t 2 adjoins a row of 0’s ending with 1 after the last row of the array in q 2 and puts the derived array in q 1. When the transitions t 1, t 2 fire the array that reaches the output place q 1 is shown as \( \begin{array}{*{20}c} 1 & 0 \\ 0 & 1 \\ \end{array} \quad \mathop \Rightarrow \limits^{{t_{1} }} \quad \begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \quad \mathop \Rightarrow \limits^{{t_{2} }} \quad \begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \). Firing the sequence (t 1 t 2)2 generates the output array as \( \begin{array}{*{20}c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \). The language generated by Petri net is set of square pictures over {0, 1} with 1’s in the main diagonal and other elements are 0’s (Fig. 1).

Fig. 1
figure 1

Adjunct array token Petri net generating unit matrix pictures

Full size image

Example 2

Consider the Adjunct Array token Petri net structure \( P_{ 1} = \left\langle {J, C, M_{0} , \rho , F } \right\rangle \) where J = {a}, C = (Q, T, I, O), Q = {q 1, q 2}, T = {t 1, t 2}, I(t 1) = {q 1}, I(t 2) = {q 2}, O(t 1) = {q 2}, O(t 2) = {q 1}, M 0 is the initial marking: the array S is in q 1 and there is no array in q 2, ρ(t 1) = (A, B 1, ac n ) and ρ(t 2) = (A, B 2, ar m ) and F = {q 1}.

Where S = a, B 1 = (a) m , B 2 = (a)n. On firing the sequence (t 1 t 2)n n ≥ 0 set of all square pictures over a is generated (Fig. 2).

Fig. 2
figure 2

AATPNS to generate square pictures of a’s

Full size image

Example 3

Consider the Adjunct Array token Petri net structure \( P_{3} = \left\langle {J,C,M_{0} ,\rho ,F} \right\rangle \) where J = {a}, the Petri net structure is C = (Q, T, I, O) with Q = {p 1, p 2, p 3, p 4, p 5, p 6, p 7}, T = {t 1, t 2, t 3, t 4, t 5, t 6}, I(t 1) = {p 1, p 2}, I(t 2) = {p 3}, I(t 3) = {p 4}, I(t 4) = {p 1, p 5}, I(t 5) = {p 5, p 6}, I(t 6) = {p 1, p 2}, O(t 1) = {p 3}, O(t 2) = {p 4}, O(t 3) = {p 2, p 5}, O(t 4) = {p 6}, O(t 5) = {p 1}, O(t 6) = {p 7, p 2}.

ρ:T → L is defined as follows: ρ(t 1) = p 2, ρ(t 2) = (A, B 1, ac n ), ρ(t 3) = (A, B 2, ar m ), ρ(t 4) = λ, ρ(t 5) = λ, ρ(t 6) = λ, ρ(t 7) = λ, F = {p 7}. The Petri net graph is given in Fig. 3. The arrays used are \( S = \begin{array}{*{20}c} a & a \\ a & a \\ \end{array} \), B 1 = (aa) m , \( B_{2} = \left( {\begin{array}{*{20}c} a \\ a \\ \end{array} } \right)^{n} \).

Fig. 3
figure 3

AATPNS to generate square picture of a’s of size 2n

Full size image

To start with only t 1 is enabled. Firing of sequence of transitions t 1 t 2 t 3 results in a square of a’s of size 4 × 4 in p 2 and p 5. At this stage both t 6 and t 4 are enabled. Firing the sequence t 1 t 2 t 3 t 6 puts a square of size 4 × 4 in p 7. Firing t 4 pushes the array to p 6, emptying p 5. In this position t 5 is enabled. Firing t 5 puts two copies of same array in p 1. Since at this stage there are two tokens in p 1, the sequence t 1 t 2 t 3 has to fire two times to empty p 1. The firing of sequence t 4 t 5(t 1 t 2 t 3)2 t 6 puts a square of a’s of size 8 × 8 in p 7. The inhibitor input p 1 make sure that a square of size 6 × 6 does not reach p 7. This AATPNS generates the language of squares of a’s of size 2n, n ≥ 1.

Example 4

The AATPNS \( P_{ 4} = \left\langle {J, C, M_{0} , \rho , F } \right\rangle \) with J = {a, b}, F = {p} given in Fig. 4, where \( S \in \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} a & b & b & a \\ \end{array} } & {\begin{array}{*{20}c} b & b & b & b \\ \end{array} } & {\begin{array}{*{20}c} b & a & a & b \\ \end{array} } & {\begin{array}{*{20}c} a & a & a & a \\ \end{array} } \\ {\begin{array}{*{20}c} b & b & b & {b^{\prime}} \\ \end{array} } & {\begin{array}{*{20}c} b & b & b & {b^{\prime}} \\ \end{array} } & {\begin{array}{*{20}c} a & a & a & {a^{\prime}} \\ \end{array} } & {\begin{array}{*{20}c} a & a & a & a \\ \end{array} } \\ \end{array} } \right\}, \) B 1 = (aa) m , B 2 = (a)n, B 3 = (bb) m , B 4 = (b)n generates the language of pictures composed by symmetrical L shaped strings of same character over the alphabet J = {a, b}.

Fig. 4
figure 4

AATPNS to generate symmetric L shaped strings

Full size image

A typical picture in this language is \( \begin{array}{*{20}c} a & b & a & a & a & a & b & a \\ b & b & a & a & a & a & b & b \\ a & a & a & a & a & a & a & a \\ a & a & a & a & a & a & a & a \\ \end{array} \)

4 Comparative Results

In the following results \( {\mathcal{L}}(X) \) denotes the family of all languages generated by X.

Theorem 1

\( {\mathcal{L}}(RP2DCFG) \subset {\mathcal{L}}(AATPNS) \)

Proof

In [8] the authors have proved that \( {\mathcal{L}}(RP2DCFG) \subseteq {\mathcal{L}}(ATPNS) \). By the result \( {\mathcal{L}}(ATPNS) \subset {\mathcal{L}}(AATPNS) \) [7], we have \( {\mathcal{L}}(RP2DCFG) \subseteq {\mathcal{L}}(AATPNS) \). For strict inclusion the language generated by AATPNS in Example 3 cannot be generated by any RP2DCFG [2].

Theorem 2

\( {\mathcal{L}}(AATPNS) \) and \( {\mathcal{L}}(RTG) \) are incomparable but not disjoint.

Proof

The language of squares over a, in Example 2, can be generated by an RTG \( G = \left\langle {J, N, S, R } \right\rangle \), where \( N = \{ S, A, B, A^{\prime}, B^{\prime}, C\} \), J = {a} and R consists of variable size rules:

$$ \begin{aligned} S & \to \left[ {\left[ {\begin{array}{*{20}c} \# & \# & \# & \# & \# \\ \# & S & S & A & \# \\ \# & S & S & A & \# \\ \# & B & B & C & \# \\ \# & \# & \# & \# & \# \\ \end{array} } \right]} \right],\quad A \to \left[ {\left[ {\begin{array}{*{20}c} \# & \# & \# \\ \# & A & \# \\ \# & {A^{\prime}} & \# \\ \# & \# & \# \\ \end{array} } \right]} \right], \\ B & \to \left[ {\left[ {\begin{array}{*{20}c} \# & \# & \# & \# \\ \# & B & {B^{\prime}} & \# \\ \# & \# & \# & \# \\ \end{array} } \right]} \right] \\ \end{aligned} $$

Fixed size rules as \( S, A, A^{\prime}, B, B^{\prime} \to a \)

Therefore \( {\mathcal{L}}(AATPNS) \) and \( {\mathcal{L}}(RTG) \) are non disjoint.

The language L +b of pictures consists of a horizontal and a vertical string of b’s (not in the border) in the background of a’s can be generated by RTG [10]. A typical member of L +b is given in Fig. 5. This language cannot be generated by any AATPNS, as the number of transitions in the net cannot depend on the size of the array. In an m × n array of a’s a column of b’s can be adjuncted in n − 1 ways and a row of b’s can be adjuncted in m − 1 ways. To insert both a column of b’s and a row of b’s the net requires (m − 1)(n − 1) transitions with corresponding adjunction rules. Hence it is not feasible to generate these arrays using AATPNS.

Fig. 5
figure 5

A picture in the language \( {\text{L}}\_\left\{ { + {\text{b}}} \right\} \)

Full size image

The language in Example 4 cannot be generated by any RTG grammar G [2].

Theorem 3

\( {\mathcal{L}}(AATPNS) \) and \( {\mathcal{L}}(PG) \) are incomparable but not disjoint.

Proof

The language of squares over a, in Example 2 can also be generated by a Prusa Grammar [11]. Again the language L +b in the proof of Theorem 2 can also be generated by a PG [11]. Since \( {\mathcal{L}}(PG) \subset {\mathcal{L}}(RTG) \) [10], the language in Example 4 cannot be generated by Prusa grammar also.

Theorem 4

\( {\mathcal{L}}(AATPNS) \) and LOC are incomparable but not disjoint.

Proof

The language of squares over a, in Example 2 is not a local language [5]. In [2] the authors have proved that the language L diag of pictures containing arbitrary number of diagonals of 1 (no single 1 are admitted at corners) that are separated by at least one diagonal of 0’s is in LOC. But L diag cannot be generated by any AATPNS. The only 2 × 2 array in the language is \( \left( {\begin{array}{*{20}c} 0 & 0 \\ 0 & 0 \\ \end{array} } \right) \). But there are four 3 × 3 arrays with the property belonging to the language. To generate four 3 × 3 arrays from the start array we need 8 transitions with different array languages involved in the labels of the transitions. Hence it is impossible to construct a net with finite number of transitions. Finally the language of square pictures over {0, 1} with 1’s in the main diagonal and other elements are 0’s in LOC [5] and it can also be generated by an AATPNS given in Example 1.

5 Conclusion

In this work, we consider Adjunct array token Petri net structure, recently introduced by Lalitha et al. [7]. We compare this model with recent context free array grammars and the class LOC. The future works concern the study of hierarchy of AATPNS with the other existing generating devices. The relationship of AATPNS with context free and context sensitive controlled pure two dimensional grammars is to be investigated.