1 Introduction

Based on pure context-free grammars [15] which have been extensively investigated for their language generating power, a simple but effective non-isometric 2D grammar model, called pure 2D context-free grammar (P2DCFG) was introduced in [29, 30] in the area of two-dimensional picture languages [12, 20, 21, 33], to generate rectangular picture array languages. In a P2DCFG,  all symbols in any column or any row of the rectangular array are rewritten at a time by equal length strings, thus maintaining the array to be rectangular. Several properties [1, 2] and variants [14, 31] of P2DCFG have been studied.

On the other hand, in the area of membrane computing [18, 19], a computing model based on the membrane structure and the functioning of living cells, was introduced by Păun in [17] and is now referred to as P system. This area of membrane computing has seen a vast growth both in terms of theoretical results [19] and application studies [34].

Formal language theory [22, 23], which is a classical area of theoretical computer science, has close connections with membrane computing. The two areas of membrane computing and two-dimensional picture array grammars were linked in [4] by developing an array P system for dealing with the problem of generation of two dimensional (2D) objects or picture arrays based on Chomsky type array grammars of the isometric variety. Several models of array P systems (see, for example, [5, 28, 32]) have been subsequently introduced and studied in the area of two-dimensional picture languages.

Freund [10] has given a very clear and detailed description of different derivation modes in P systems as well as a discussion of the role of halting conditions in the context of computational power of P systems. Here we consider pure 2D context-free grammars (P2DCFG), which belong to the non-isometric variety of array grammars, with a variation in the mode of rewriting of a picture array, which we call as independent mode. In a P2DCFG,  at a step of a derivation, all the symbols in a column or in a row of a rectangular array are to be rewritten but in the independent mode, a single symbol but any symbol in each of the columns or in each of the rows is rewritten at a step of a derivation. The resulting class of picture languages is shown to be incomparable with the family of picture languages generated by P2DCFG. We then consider an array P system with objects in the regions of this P system as rectangular picture arrays and rules to generate picture arrays as P2DCFG kind of rules but with an independent mode of rewriting. We show that the use of two membranes gives more picture array generative power. We also provide an application of this array P system in generating certain floor designs, referred to as “kolam” patterns.

2 Preliminaries

Let T be a finite alphabet. A word or a string \(w = w_1w_2 \cdots w_n,\) \((n \ge 1)\) over T is a finite sequence of symbols from T. We denote by len(w),  the length of the word w. The set of all words over T, including the empty word \(\lambda\) with no symbols, is denoted by \(T^{*}\). We call words of \(T^{*}\) also as row words. For any word \(w = a_1a_2 \cdots a_n\), we denote by \(w^t\) the word w written vertically as follows and call \(w^t\) as a column word:

$$\begin{aligned} \begin{array}{c} a_1\\ a_2\\ \vdots \\ a_n \end{array}. \end{aligned}$$

Since the transpose of a row is a column and vice versa, we have \((w^t)^t = w.\)

A rectangular \(m \times n\) array M over T,  called picture array, is of the form

$$\begin{aligned} M = \begin{array}{ccc} p_{11} &{} \cdots &{} p_{1n} \\ \vdots &{} \ddots &{} \vdots \\ p_{m1} &{} \cdots &{} p_{mn} \\ \end{array} \end{aligned}$$

where each \(p_{ij} \in T, 1\le i \le m, \, 1 \le j \le n\). The set of all picture arrays over T is denoted by \(T^{**}\), which includes the empty array \(\lambda\). We write \(T^{++} = T^{**}-\{\lambda \}.\)

We refer to [22, 23] for concepts related to formal languages and to [20, 21] for array grammars. For notions related to P Systems we refer to [17, 18]. We now recall a pure 2D context-free grammar introduced in [29, 30].

Definition 1

A pure 2D context-free grammar (P2DCFG) is a 4-tuple \(G = (T,P_1,P_2,I)\) where

  1. i)

    T is a finite set of symbols;

  2. ii)

    \(P_1\) is a finite set of column tables c, where c is a finite set of context-free rules of the form \(a \rightarrow \alpha , a \in T, \alpha \in T^*\) satisfying the property that for any two rules \(a \rightarrow \alpha ,\) \(b \rightarrow \beta\) in c, we have \(len(\alpha ) = len(\beta )\); i.e. the words \(\alpha\) and \(\beta\) have equal length;

  3. iii)

    \(P_2\) is a finite set of row tables r, where r is a finite set of rules of the form \(d \rightarrow \gamma ^t, d \in T, \gamma \in T^*\) such that for any two rules \(d \rightarrow \gamma ^t, e \rightarrow \delta ^t\) in r, we have \(len(\gamma ) = len(\delta )\);

  4. iv)

    \(I \subseteq T^{**} - \{ \lambda \}\) is a finite set of initial (axiom) arrays.

A derivation in a P2DCFG G is defined as follows: For \(p,q \in T^{**},\) q is derived in G from a picture p,  written \(p \Rightarrow q,\) either (i) by rewriting in parallel all the symbols in a column of p,  rewriting each symbol by a rule in some column table or (ii) by rewriting in parallel all the symbols in a row of p,  rewriting each symbol by a rule in some row table. All the rules used to rewrite a column (or a row) of symbols should belong to the same table. The reflexive, transitive closure of \(\Rightarrow\) is denoted by \(\Rightarrow ^*.\)

The picture language generated by G is the set of picture arrays \(L(G) = \{M \in T^{**} \mid M_0 \Rightarrow ^* M\) for some \(M_0 \in I \}.\) The family of picture languages generated by P2DCFGs is denoted by P2DCFL.

Example 1

Consider the P2DCFG \(G_1 = (T, P_1, P_2, \{M_0\})\) where \(T = \{a,b,d,e \}\), \(P_1 = \{c_1, c_2 \}, P_2 = \{r \}\) where \(c_1 = \{a \rightarrow ab, d \rightarrow da \},\) \(c_2 = \{a \rightarrow a, d \rightarrow e \},\) \(r = \left\{ d \rightarrow \begin{array}{c} a\\ d \end{array}, a \rightarrow \begin{array}{c} b\\ a \end{array} \right\}\), and \(M_{0} = \begin{array}{ccc} a&{}b&{}b \\ a&{}b&{}b \\ d&{}a&{}a \end{array}\).

\(G_1\) generates a picture language \(L_1\) consisting of picture arrays p of size (m, n), \(m,n \ge 3\) with \(p(i,1) = p(m,j) = a,\) for \(1 \le i \le m-1,\) \(2 \le j \le n ;\) \(p(m,1) = d\) or \(p(m,1) = e;\) \(p(i,j) = b,\) otherwise. We note that a derivation in \(G_1,\) starting from the axiom array \(M_0,\) generates picture arrays of the forms

$$\begin{aligned} \begin{array}{ccccccccccccc} a&{} b &{}\cdots &{}b&{}&{}&{}&{}&{}&{} a&{} b &{}\cdots &{}b\\ \vdots &{} \vdots &{}\ddots &{} \vdots &{}&{}&{} \text{ and } &{}&{}&{} \vdots &{} \vdots &{}\ddots &{} \vdots \\ a&{} b &{}\cdots &{}b&{}&{}&{}&{}&{}&{} a&{} b &{}\cdots &{}b \\ d&{} a &{}\cdots &{}a &{}&{}&{}&{}&{}&{} e&{} a &{}\cdots &{}a\\ \end{array} \end{aligned}$$

since the column table \(c_1\) is applicable to only the leftmost column \((a \cdots ad)^t,\) rewriting in parallel all the symbols a and d in that column, thereby adding the symbol b to the immediate right of each a while adding the symbol a to the immediate right of d. Likewise, the row table r is applicable to only the bottommost row and adds a row of the form \(a b \cdots b\) just above it. Likewise the column table \(c_2\) is applicable to only the leftmost column \((a \cdots ad)^t,\) rewriting in parallel all the symbols a as a itself but changing d in that column as e,  and after this no table of rules is applicable.

3 Pure 2D context-free grammar in independent mode

We now introduce a different mode of rewriting in a pure 2D context-free grammar, which we call as independent mode, based on a corresponding notion in the study of two-dimensional insertion systems considered in [11].

Definition 2

A pure 2D context-free grammar in independent mode (abbreviated as IP2DCFG), \(G_I = (T, P_1, P_2,I)\) has its components \(T, P_1, P_2,I\) as in the P2DCFG in Definition 1, with a difference in the mode of rewriting of a picture array, which we call as independent mode, and which is done as described below:

A direct derivation of a picture array \(M_2\) from an \(m \times n\) picture array \(M_1,\) written as \(M_1 \Rightarrow _i M_2,\) is done in the following manner: In applying the rules of a row (respy. column) table r (respy. c) to the \(m \times n\) picture array \(M_1,\) only one symbol in each of the m rows (respy. n columns) is rewritten at a time and it can be any symbol in that row (respy. column). All the symbols (chosen for rewriting) should have rules in the row table r (respy. column table c). Otherwise, the table of rules is not applicable. If a picture array Y is obtained from a picture array X using a IP2DCFG,  through a sequence of direct derivation steps, we write \(X \Rightarrow ^*_i Y.\) Note that the lengths of the right sides of all the rules in a column table (respy. a row table), are the same and so the derived array is also a rectangular array.

The picture language generated by a IP2DCFG \(G_I\) is the set of picture arrays \(L(G) = \{M \in T^{**} \mid M_0 \Rightarrow ^*_i M\) for some \(M_0 \in I \}.\) The family of picture languages generated by IP2DCFGs is denoted by IP2DCFL.

We illustrate with an example.

Example 2

Consider the IP2DCFG \(G_{2} = (T, P_1, P_2, \{M_0\})\) where \(T = \{a,b,d,e,x \}\), \(P_1 = \{c_1, c_2 \}, P_2 = \{r \}\) where \(c_1 = \{a \rightarrow ab, x \rightarrow xx, d \rightarrow bd \},\) \(c_2 = \{a \rightarrow a, x \rightarrow x, d \rightarrow e \},\) \(r = \left\{ a \rightarrow \begin{array}{c} a\\ b \end{array}, x \rightarrow \begin{array}{c} x\\ x \end{array}, d \rightarrow \begin{array}{c} b\\ d \end{array} \right\}\), and

\(M_{0} = \begin{array}{ccc} a&{}b&{}b \\ b&{}x&{}b \\ b&{}b&{}d \end{array}\).

\(G_{2}\) generates a picture language \(L_2\) consisting of picture arrays p of size \(m \times n,\) \(m,n \ge 3\) with \(p(1,1) = a,\) \(p(1,j) = p(i,1) = b,\) for \(2 \le j \le n\) and \(2 \le i \le m ,\) \(p(m,j) = p(i,n) = b,\) for \(2 \le j \le n-1\) and \(2 \le i \le m-1,\) \(p(m,n) = d \quad \text{ or } \quad e,\) \(p(i,j) = x,\) otherwise. We note that a derivation in \(G_2,\) starting from the axiom array \(M_0,\) generates picture arrays of the forms

$$\begin{aligned} \begin{array}{ccccccccccccccc} a&{} b &{}\cdots &{}b&{}b&{}&{}&{}&{}&{}&{}a&{} b &{}\cdots &{}b&{}b \\ b&{} x &{}\cdots &{} x &{}b&{}&{}&{}&{}&{}&{}b&{} x &{}\cdots &{} x &{}b\\ \vdots &{} \vdots &{}\ddots &{} \vdots &{} \vdots &{}&{}&{} \text{ and } &{}&{}&{} \vdots &{} \vdots &{}\ddots &{} \vdots &{} \vdots \\ b&{} x &{}\cdots &{} x &{}b &{}&{}&{}&{}&{}&{} b&{} x &{}\cdots &{} x &{}b\\ b&{} b &{}\cdots &{}b&{}d &{}&{}&{}&{}&{}&{} b&{} b &{}\cdots &{}b&{}e \end{array}. \end{aligned}$$

A sample derivation \(M_0 \Rightarrow _i^* M\) using the tables \(c_1, r, r, c_2\) in this order in independent mode is shown in Fig. 1.

Fig. 1
figure 1

Derivation \(M_{0} \Rightarrow _i^* M\)

Full size image

We have indicated the symbols rewritten by enclosing these in rectangular boxes. Note that when a column table of rules is used, a symbol in each row (not necessarily in the same column) is rewritten while a symbol in each column (not necessarily in the same row) is rewritten when a row table of rules is used.

Theorem 1

The families of P2DCFL and IP2DCFL are incomparable but not disjoint.

Proof

That the families are not disjoint can be seen from the picture language consisting of \(m \times n\) \((m,n \ge 2)\) picture arrays p over \(\{a \}\) where \(p(i,j) = a ,\) for all \(1 \le i \le m, 1 \le j \le n,\) which is generated by a P2DCFG as well as a IP2DCFG with a column table of rules \(c = \{a \rightarrow aa\},\) a row table of rules \(\left\{ a \rightarrow \begin{array}{c} a\\ a \end{array} \right\}\) and axiom array \(\begin{array}{cc} a&{}a \\ a&{}a \end{array}.\)

The incomparability can be seen as follows: Consider the picture language \(L_{abd}\) consisting of \(3 \times n, (n \ge 3)\) picture arrays \(p_1, p_2\) such that (i) \(p_1(1,1) = p_1(2,1) = a,\) \(p_1(3,1) = d,\) \(p_1(3,j) = a, 2 \le j \le n\) and \(p_1(i,j) = b,\) otherwise and (ii) \(p_2(1,1) = p_2(2,1) = b,\) \(p_2(3,1) = d,\) \(p_2(3,j) = b, 2 \le j \le n\) and \(p_2(i,j) = a,\) otherwise. Two arrays \(M_1\) and \(M_2\) of \(L_{abd}\) are shown below.

$$\begin{aligned} M_1 = \begin{array}{cccc} a&{}b&{} \cdots &{}b \\ a&{}b&{} \cdots &{}b \\ d&{}a &{} \cdots &{}a \end{array} \qquad \text{ and } \qquad M_2 = \begin{array}{cccc} b&{}a&{} \cdots &{}a \\ b&{}a&{} \cdots &{}a \\ d&{}b &{} \cdots &{}b \end{array}. \end{aligned}$$

The picture language \(L_{abd}\) is in P2DCFL generated by a P2DCFG with two column tables of rules \(c_1 = \{ a \rightarrow ab, d \rightarrow da\},\) \(c_2 = \{ b \rightarrow ba, d \rightarrow db\}\) and axiom arrays

$$\begin{aligned} \begin{array}{ccc} a&{}b&{}b \\ a&{}b&{}b \\ d&{}a&{}a \end{array} \qquad \text{ and } \qquad \begin{array}{ccc} b&{}a&{}a \\ b&{}a&{}a \\ d&{}b&{}b \end{array}. \end{aligned}$$

But it can be seen that this picture language \(L_{abd}\) is not in IP2DCFL. In fact, if we assume that \(L_{abd}\) can be generated by a IP2DCFG,  then arrays of the form \(p_1\) can be generated in the independent mode only by a column table of rules \(c = \{ b \rightarrow bb, d \rightarrow da\},\) since rules for rewriting a can not be included in such a table as it will result in picture arrays not in the language. But then the column table c could be applied to a picture array of the form \(p_2\) in the independent mode, again resulting in picture arrays not in the language. Similar reasoning can be done for picture arrays \(p_2.\) This shows that \(L_{abd}\) cannot be generated by any IP2DCFG.

On the other hand, consider the picture language \(L^\prime\) consisting of \(2 \times n, (n \ge 4)\) picture arrays q such that \(q(1,2) = q(2,3) = a,\) \(q(i,j) = b,\) otherwise. An array in \(L^\prime\) is shown below:

$$\begin{aligned} \begin{array}{cccccc} b&{}a&{}b&{}b&{} \cdots &{}b \\ b&{}b&{}a&{}b&{} \cdots &{}b \end{array}. \end{aligned}$$

The picture language \(L^\prime\) is in IP2DCFL generated by a IP2DCFG with an axiom array \(\begin{array}{cccc} b&{}a&{}b&{}b \\ b&{}b&{}a&{}b \end{array}\) and a column table \(c = \{a \rightarrow ab\}.\) It cannot be generated by any P2DCFG. If there is such a P2DCFG,  then due to the requirement that in a P2DCFG, all symbols in a single column should be rewritten at a time, this grammar should have column tables of rules to rewrite one or more of the columns \(\begin{array}{c} b \\ b \end{array},\) \(\begin{array}{c} a \\ b \end{array}\) and \(\begin{array}{c} b \\ a \end{array}.\) This means that the grammar should have a column table having a pure context-free rule to rewrite only b and / or a column table of pure context-free rules to rewrite a and b. But it is clear that having such column tables of rules, the grammar will generate picture arrays not in the language \(L^\prime .\) For instance a column table with rule for b will allow rewriting of the first column of \(b's\) as well, yielding picture arrays not in the language. \(\square\)

4 Array P system based on IP2DCFG

We now introduce an array P system model with the membranes of the P system containing picture array objects and column or row tables of rules as in IP2DCFG in the sense that the rewriting is in independent mode.

Definition 3

An array P system (of degree \(m \ge 1\)) with IP2DCFG kind of rules is a construct

$$\begin{aligned} \Pi =(T, \mu , A_1,\cdots , A_m, R_1,\cdots , R_m,i_o), \end{aligned}$$

where T is the alphabet consisting of terminal symbols, \(\mu\) is a membrane structure with m membranes labelled in a one-to-one manner with \(1,2, \cdots , m\); \(A_1,\cdots , A_m\) are finite sets (can be empty) of rectangular picture arrays over T with \(A_i\) in the membrane or region labelled i for \(1 \le i \le m\) ; \(R_1, \cdots , R_m\) are finite sets of column tables or row tables of context-free rules over T (as in a IP2DCFG) with \(R_i\) in the membrane or region labelled i for \(1 \le i \le m.\) A region can contain both column tables of rules and row tables of rules. The application of a column or row table is as done in a IP2DCFG. The tables have attached targets here, out, in, \(in_j\) (in general, here is omitted) and \(i_o\) is the label of the output membrane which is an elementary membrane of \(\mu\).

A computation in \(\Pi\) is done as in an array-rewriting P system [4] with the successful computations being the halting ones; each rectangular picture array in each region of the system, which can be rewritten by a column table of rules or a row table of rules, associated with that region, should be rewritten. This means that a region can contain column tables of rules and/or row tables of rules but one table (column or row) of rules is applied at a time to a picture array and the rewriting is done as in a IP2DCFG. The picture array obtained by rewriting is retained in the same region if the target associated with the table used is here or sent to an immediate outer region (respy. directly inner region, nondeterministically chosen), if the target is out (respy. in). If the target is \(in_j\) then the array is immediately sent to a directly inner membrane with label j. If no internal membrane exists in a region, then a table with the target indication in cannot be used.

A computation is successful only if it stops, that is, a configuration, called a halting configuration, is reached where no table of rules can be applied to the existing arrays in the regions. The result of a successful computation consists of rectangular picture arrays over T collected in the output membrane with label \(i_o\) in the halting configuration. Note that all the picture arrays that stay at the output membrane in the halting configuration will belong to the picture language since there are only one kind of symbols, namely terminal symbols.

The set of all picture arrays generated by such a system \(\Pi\) is denoted by \(IAL(\Pi )\). The family of all array languages \(IAL(\Pi )\) generated by such systems \(\Pi\) as above, with at most m membranes, is denoted by \(IAP_m(IP2DCFG)\).

Example 3

Consider the picture language \(L_{sq}\) consisting of square sized \(n \times n, n \ge 3,\) picture arrays p with \(p(1,1) = a,\) \(p(1,j) = p(i,1) = b,\) for \(2 \le j \le n\) and \(2 \le i \le n ,\) \(p(n,j) = p(i,n) = b,\) for \(2 \le j \le n-1\) and \(2 \le i \le n-1,\) \(p(n,n) = e,\) \(p(i,j) = x,\) otherwise. A picture array in \(L_{sq}\) is shown below.

$$\begin{aligned} \begin{array}{ccccc} a&{}b&{} \cdots &{} b&{}b \\ b&{}x &{} \cdots &{}x&{}b \\ b&{}x &{} \cdots &{}x&{}b \\ \vdots &{} \vdots &{} \ddots &{}\vdots &{} \vdots \\ b&{}x &{} \cdots &{}x&{}b \\ b&{}b&{} \cdots &{}b&{}e \end{array} \end{aligned}$$

We construct an array P system \(\Pi _{sq}\) with only one membrane and with the only region containing tables having IP2DCFG kind of rules applied in independent mode. \(\Pi _{sq}\) is given by

$$\begin{aligned} \Pi _{sq} = (T, \mu , A_1, R_1, 1), \end{aligned}$$

where

  1. i)

    \(T = \{a,b,d_1,d_2,e,x\}\)

  2. ii)

    \(\mu = [_1 \, ]_1\)

  3. iii)

    \(A_1 = \{\begin{array}{ccc} a&{}b&{}b \\ b&{}x&{}b \\ b&{}b&{}d_1 \end{array} \},\)

  4. iv)

    \(R_1\) consists of a row table r and two column tables \(c_1\) and \(c_2\), each with target here. The tables of rules are given as follows:

    $$\begin{aligned} c_1 = \{a \rightarrow ab, d_1 \rightarrow bd_2, x \rightarrow xx \}, c_2 = \{a \rightarrow a, d_1 \rightarrow e, x \rightarrow x \}, \end{aligned}$$
    $$\begin{aligned} r = \{a \rightarrow \begin{array}{c} a \\ b \end{array}, x \rightarrow \begin{array}{c} x \\ x \end{array}, d_2 \rightarrow \begin{array}{c} b \\ d_1 \end{array}\}. \end{aligned}$$

In the array P system \(\Pi _{sq},\) the only membrane or region labelled 1 which is also the output membrane, initially, contains the array

$$\begin{aligned} \begin{array}{ccc} a&{}b&{}b \\ b&{}x&{}b \\ b&{}b&{}d_1 \end{array}. \end{aligned}$$

If the applicable column table \(c_2\) is applied, then the array generated is

$$\begin{aligned} \begin{array}{ccc} a&{}b&{}b \\ b&{}x&{}b \\ b&{}b&{}e \end{array} \end{aligned}$$

which is collected in the language as membrane 1 is the output membrane and no table of rules is applicable in the region at this moment with the computation coming to a halt. If the column table \(c_1\) (instead of \(c_2\)) is applied to the axiom array in region 1, then the array generated is

$$\begin{aligned} \begin{array}{cccc} a&{}b&{}b&{}b \\ b&{}x&{}x&{}b \\ b&{}b&{}b&{}d_2 \end{array}. \end{aligned}$$

The row table r can be applied now which generates the array

$$\begin{aligned} \begin{array}{cccc} a&{}b&{}b&{}b \\ b&{}x&{}x&{}b \\ b&{}x&{}x&{}b \\ b&{}b&{}b&{}d_1 \end{array} \end{aligned}$$

and the process can be repeated. Application of the rules of \(c_1\) followed by the rules of r with both the tables of rules applied an equal number of times yields the \(n \times n\) array (for some \(n \ge 3\) )

$$\begin{aligned} \begin{array}{ccccc} a&{}b&{}\cdots &{}b&{}b \\ b&{}x&{}\cdots &{}x&{}b \\ \vdots &{}\vdots &{}\ddots &{}\vdots &{}\vdots \\ b&{}x&{}\cdots &{}x&{}b \\ b&{}b&{}\cdots &{}b&{}d_1 \end{array} \end{aligned}$$

If the column table \(c_2\) is applied during the process instead of \(c_1\) in region 1, the array

$$\begin{aligned} \begin{array}{ccccc} a&{}b&{}\cdots &{}b &{}b\\ b&{}x&{}\cdots &{}x&{}b \\ \vdots &{}\vdots &{}\ddots &{}\vdots &{}\vdots \\ b&{}x&{}\cdots &{}x&{}b \\ b&{}b&{}\cdots &{}b&{}e \end{array} \end{aligned}$$

is generated changing the symbol \(d_1\) to e in the array. The computation comes to a halt and the array is collected in the language generated by \(\Pi _{sq}.\) Note that the generated array at the halting configuration will have an equal number of rows and columns and will be an element of \(L_{sq}.\) Thus the system \(\Pi _{sq}\) generates the language \(L_{sq}.\)

We now examine the generative power of the array-rewriting P system with IP2DCFG kind of rules in independent mode of derivation.

Theorem 2

\(IP2DCFL \subset IAP_1(IP2DCFG) \subset IAP_2(IP2DCFG).\)

Proof

The inclusion \(IP2DCFL \subseteq IAP_1(IP2DCFG)\) can be seen as follows: Let \(L \in IP2DCFL\) and \(G_I = (T, P_1, P_2, I)\) be an IP2DCFG generating L. We construct an array P system of degree 1 with IP2DCFG kind of rules, \(\Pi = (T \cup {\overline{T}}, [_1 \, ]_1, A, R, 1)\) where \({\overline{T}} = \{{\overline{a}} \mid a \in T\}.\) In other words the alphabet of \(\Pi\) contains all the symbols of the alphabet T of \(G_I\) and in addition contains the “barred” version of every symbol of T; A contains all the picture arrays of I but every symbol in each picture array of I is replaced by its barred version. Likewise R contains all the column tables of \(P_1\) and all the row tables of \(P_2\) but each symbol in the right and left sides of every rule in the tables, is replaced by the corresponding barred symbol. In addition R contains a new column table \(c = \{{\overline{a}} \rightarrow a \mid a \in T \}.\) We denote by \({\overline{M}}\) the array obtained from the array M by replacing each symbol of M by the corresponding barred symbol. It can be seen that for every direct derivation \(M_1 \Rightarrow _i M_2\) in \(G_I,\) there is a computation in \(\Pi\) with the array \(\overline{M_1}\) generating \(\overline{M_2}\) which then generates \(M_2\) by the application of the rules of the column table c as many times as needed and the computation halts. Hence every picture array in L generated in \(G_I\) from an axiom array in I is also computed by \(\Pi\). Thus \(L \in IAP_1(IP2DCFG).\) \(\square\)

The proper inclusion follows from the picture array language \(L_{sq}\) in Example 3 which shows that \(L_{sq} \in IAP_1(IP2DCFG).\) On the other hand this picture language cannot be generated by any IP2DCFG since we need to have some control on the application of column table of rules and row table of rules to maintain the square shape of the picture arrays generated by a IP2DCFG. We can use some “intermediate” symbols to alternate the application of the column and row tables of rules but then this will result in picture arrays not in the language.

The inclusion \(IAP_1(IP2DCFG) \subseteq IAP_2(IP2DCFG)\) in the statement of the theorem follows from the definition of the family \(IAP_m(IP2DCFG).\) For the proper inclusion we consider the language \(L_{ab}\) consisting of picture arrays p of size \(m \times (4n+2),\) \(m \ge 2\), \(n \ge 1,\) where p is such that every row of p is of the form \(xa^nb^na^nb^ny\) \((n \ge 1)\) over the terminal symbols \(\{x,y,a,b\}\). The language \(L_{ab}\) belongs to \(IAP_2(IP2DCFG)\) generated by the P system with two membranes having the membrane structure \([_1 \, [_2 \, ]_2 \, ]_1\) and the only axiom array

$$\begin{aligned} \begin{array}{cccc} x&{}d&{}e&{}y \\ x&{}d&{}e&{}y \end{array} \end{aligned}$$

in membrane 1 initially. Membrane 1 has a row table r with target here and two column tables \(c_1, c_2\) with target in. Membrane 2, which is the output membrane, has a column table \(c_3\) with target out and another column table \(c_4\) with target here.

The tables of rules are given below:

\(r = \{x \rightarrow \begin{array}{c} x \\ x \end{array}, a \rightarrow \begin{array}{c} a \\ a \end{array}, b \rightarrow \begin{array}{c} b \\ b \end{array}, y \rightarrow \begin{array}{c} y \\ y \end{array}, d \rightarrow \begin{array}{c} d \\ d \end{array}, e \rightarrow \begin{array}{c} e \\ e \end{array}\},\) \(c_1 = \{d \rightarrow adb \}\), \(c_2 = \{e \rightarrow ab \}\), \(c_3 = \{e \rightarrow aeb \}\), \(c_4 = \{d \rightarrow ab \}\).

A computation can start with an application of the rules of the column table \(c_1\) or \(c_2\) in membrane 1 to the axiom array. If the rules of the column table \(c_1\) in membrane 1 are applied to the axiom array, then the generated array

$$\begin{aligned} \begin{array}{cccccc} x&{}a&{}d&{}b&{}e&{}y \\ x&{}a&{}d&{}b&{}e&{}y \end{array} \end{aligned}$$

will be sent to membrane 2 and if the rules of the column table \(c_3\) are applied, then the generated array is

$$\begin{aligned} \begin{array}{cccccccc} x&{}a&{}d&{}b&{}a&{}e&{}b&{}y \\ x&{}a&{}d&{}b&{}a&{}e&{}b&{}y \end{array} \end{aligned}$$

which is sent back to membrane 1. This process can repeat. The rules of the row table r in membrane 1 can be applied any number of times when the array is in membrane 1 at any step of a computation. The application of the rules of the row table r will increase the number of rows of the array by one and the array will remain in membrane 1 itself. After the application of the rules of \(c_1\) in membrane 1 and the rules of \(c_3\) in membrane 2, with both the tables of rules applied an equal number of times, say, \(n-1\) times \((n \ge 1)\) with the rules of the row table r applied \(m+2, (m \ge 0)\) times during the process, the array arriving in membrane 1 will have \(m+2\) rows and will be of the form given below:

$$\begin{aligned} \begin{array}{cccccccc} x&{}a^{(n-1)}&{}d&{}b^{(n-1)}&{}a^{(n-1)}&{}e&{}b^{(n-1)}&{}y \\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ x&{}a^{(n-1)}&{}d&{}b^{(n-1)}&{}a^{(n-1)}&{}e&{}b^{(n-1)}&{}y \end{array} \end{aligned}$$

If the rules of the column table \(c_2\) are now applied in membrane 1 to the array mentioned above (instead of \(c_1\)), the generated array

$$\begin{aligned} \begin{array}{ccccccc} x&{}a^{(n-1)}&{}d&{}b^{(n-1)}&{}a^{n}&{}b^{n}&{}y \\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ x&{}a^{(n-1)}&{}d&{}b^{(n-1)}&{}a^{n}&{}b^{n}&{}y \end{array} \end{aligned}$$

is sent to membrane 2. Here only the column table \(c_4\) is applicable generating the array

$$\begin{aligned} \begin{array}{cccccc} x&{}a^{n}&{}b^{n}&{}a^{n}&{}b^{n}&{}y \\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ x&{}a^{n}&{}b^{n}&{}a^{n}&{}b^{n}&{}y \end{array} \end{aligned}$$

which is collected in the language as the computation halts.

On the other hand, if in membrane 1 at any step of a computation, the rules of the column table \(c_1\) are applicable and applied, then the generated array is sent to the inner membrane 2 and if the rules of the column table \(c_4\) are applied which replaces the symbol d by ab in the rows, then the array remains there but the computation does not halt as the rules of the column table \(c_3\) are applicable generating and sending the resulting array to membrane 1. Here the rules of the column table \(c_2\) are only applicable with the resulting array sent to the region 2 and the computation halts. Here again it is collected in the language. Note that no other sequence of application of the rules of the tables will be a correct sequence. Thus the picture language \(L_{ab}\) is generated and hence belongs to \(IAP_2(IP2DCFG).\) This picture language cannot belong to \(IAP_1(IP2DCFG)\) as there is only one membrane and so the technique of alternately generating the first “block” of \(a^ndb^n\) and the second “block” of \(a^neb^n\) using “intermediate” symbols, cannot be managed for ever as the number of rows can keep increasing, thus forcing the cardinality of the alphabet of “intermediate” symbols to grow infinitely.

Remark

Analogous to the statement in Theorem 2, in the case of P2DCFL [29, 30], we have \(P2DCFL \subset AP_1(P2DCFG) \subset AP_2(P2DCFG),\) which corrects the erroneous statements in [32, Theorem 1, Page 1905]. The proof of this statement is similar to the proof of Theorem 2.

Based on splicing system, which is a theoretical model of DNA recombination proposed by Head [13], Berstel et al. [3] introduced flat splicing system, which is a variant of splicing system and which involves the operation known as flat splicing on words. A picture array generating model, called array flat splicing system (AFS), was introduced and investigated in [16] by defining the operation of flat splicing to picture arrays. Informally expressed, the idea is that between two adjacent columns (or to the left / right of a column) in a rectangular array M, a rectangular array N having the same number of rows as M and with a specific “prefix array” and / or a specific “suffix array” gets inserted by the “flat splicing rules”. The family of picture array languages generated by AFS is denoted by L(AFS). Now we exhibit a picture array language that cannot be generated by any AFS but can be generated by an array P system as in Definition 3, with IP2DCFG kind of rules and only one membrane. For a formal definition of AFS and for an illustration of how this system works, we refer to [16].

Theorem 3

\(IAP_1(IP2DCFG) \setminus L(AFS) \ne \emptyset .\)

Proof

We consider the picture language \(L_{xy}\) consisting of \(n \times n, (n \ge 3)\) picture arrays p such that each of the first \((n-1)\) rows of p has the word \(xa^ny,\) \((n \ge 1)\) and the last row has the word \(pa^{n}q,\) \((n \ge 3)\) over the terminal symbols \(\{x,y,p,q,a\}\). This picture language \(L_{xy}\) is not in L(AFS) as it cannot be generated by any AFS. In fact if we assume that there is an AFS generating \(L_{xy}\), then the array \(\begin{array}{ccc} x&{}a&{}y \\ x&{}a&{}y \\ p&{}a&{}q \end{array}\) should be an axiom array. An \(n \times n\) array in \(L_{xy}\) has \((n-2), n \ge 3\) middle columns of \(a's\) and to generate such arrays, the AFS needs to insert an array over a but such arrays are not members of the picture language \(L_{xy}\). On the other hand, inserting the axiom array \(\begin{array}{ccc} x&{}a&{}y \\ x&{}a&{}y \\ p&{}a&{}q \end{array}\) into itself, or an array of the language into this axiom array, will yield an array with more than one column of the form \((x \cdots xp)^t\) as well as column of the form \((y \cdots yq)^t\) and hence such an array cannot be an element of \(L_{xy}\). \(\square\)

5 Array P systems and extended 2D grammars

An earliest two-dimensional picture array generating model introduced by the Siromoney group [25], originally called context-free matrix grammar [26] and subsequently referred to as 2DCFG in [22], involves two phases of rewriting. The first phase generates strings over “intermediate” symbols using context-free string grammar rules and in the second phase, these strings are rewritten by groups of normal form regular grammar rules such as a group of nonterminal rules of the form \(A \rightarrow aB\) or a group of terminal rules of the form \(A \rightarrow a\) in the vertical direction to produce the columns of a rectangular picture array over a set of terminal symbols. The “intermediate” symbols of the first phase will be the start nonterminal symbols in the second phase. This model has been extensively used in 2D grammar studies.

An extension of this 2D grammar was introduced in [27]. We do not give here the formal definition of this extended 2D grammars but informally mention the details in the extended model. The first phase is similar to the Siromoney matrix grammar [26] but the second phase has tables of rules which are sets of normal form regular nonterminal rules or sets of normal form regular terminal rules. An applicable table of rules is used (applied) for the rewriting in the second phase. We will call the extended 2D grammar model as T2DCFG or T2DCSG depending on whether the first phase involves a context-free grammar or a context-sensitive grammar. The corresponding families of picture languages are denoted by T2DCFL and T2DCSL. We now compare the array P system considered here with these extended 2D grammars.

Theorem 4

(i) \(IAP_2(IP2DCFG) \cap T2DCSL \ne \emptyset .\)

(ii) \(IAP_2(IP2DCFG) \setminus T2DCFL \ne \emptyset .\)

Proof

We consider the picture language L consisting of \(m \times (4n+2), (m \ge 4, n \ge 1)\) picture arrays p such that the first row of p is of the form \(xa^nb^na^nb^ny\) \((n \ge 1)\) and the next few rows are of the form \(xz^{4n}y\) \((n \ge 1)\) followed by a row of the form \(qz^{4n}r(n \ge 1)\) and the remaining rows are of the form \(sz^{4n}t\) \((n \ge 1)\) over the terminal symbols \(\{x,y,q,r,s,t,z,a,b\}\). This picture language is in T2DCSL but is not in T2DCFL since the first row is a strictly context-sensitive language. In fact the corresponding T2DCSG will generate in the first phase the CSL \(\{XA^nB^nA^nB^nY \mid n \ge 1 \}\) where X, Y, A, B are “intermediate” symbols which will serve as the start symbols for the second phase. The tables of rules in the second phase are \(t_1 = \{X \rightarrow xX, A \rightarrow aZ, B \rightarrow bZ, Y \rightarrow yY \},\) \(t_2 = \{X \rightarrow xX_1, Z \rightarrow zZ, Y \rightarrow yY_1 \},\) \(t_3 = \{X_1 \rightarrow xX_1, Z \rightarrow zZ, Y_1 \rightarrow yY_1 \},\) \(t_4 = \{X_1 \rightarrow qU, Z \rightarrow zZ, Y_1 \rightarrow rV \},\) \(t_5 = \{U \rightarrow sU, Z \rightarrow zZ, V \rightarrow tV \},\) and \(t_6 = \{U \rightarrow s, Z \rightarrow z, V \rightarrow t\}.\) Application of the rules of the table \(t_1\) will generate the first row \(xa^nb^na^nb^ny\) of the array p. This can be followed by the application of the rules of the table \(t_2\) once and \(t_3\) certain number of times, yielding the rows of the form \(xz^{4n}y\) till the rules of the table \(t_4\) are applied. This will yield the row \(qz^{4n}r.\) Likewise using the table \(t_5\) the rows of the form \(sz^{4n}t\) are generated and the derivation ends when the table \(t_6\) is used generating the required array. \(\square\)

The language L belongs to \(IAP_2(IP2DCFG)\) generated by the P system with two membranes having the membrane structure \([_1 \, [_2 \, ]_2 \, ]_1\) and the only axiom array

$$\begin{aligned} \begin{array}{cccc} x&{}d&{}e&{}y \\ x&{}z&{}z&{}y \\ q&{}z&{}z&{}r \\ s&{}z&{}z&{}t \end{array} \end{aligned}$$

in membrane 1 initially. Membrane 1 has two row tables \(r_1,r_2\) with target here and two column tables \(c_1,c_3\) with target in. Membrane 2 has a column table \(c_2\) with target out and another column table \(c_4\) with target here. The output membrane is 2.

The tables of rules are given below: \(r_1 = \{x \rightarrow \begin{array}{c} x \\ x \end{array}, z \rightarrow \begin{array}{c} z \\ z \end{array}, y \rightarrow \begin{array}{c} y \\ y \end{array}\},\) \(r_2 = \{s \rightarrow \begin{array}{c} s \\ s \end{array}, z \rightarrow \begin{array}{c} z \\ z \end{array}, t \rightarrow \begin{array}{c} t \\ t \end{array}\},\) \(c_1 = \{d \rightarrow adb, z \rightarrow zzz \}\), \(c_2 = \{e \rightarrow aeb, z \rightarrow zzz \}\), \(c_3 = \{e \rightarrow ab, z \rightarrow zz \}\), \(c_4 = \{d \rightarrow ab, z \rightarrow zz \}\). At any step of a computation, application of the rules of the row tables \(r_1,r_2\) will add the rows \(xz^{4n}y\) and \(sz^{4n}t\) independently any number of times above and below the row \(qz^{4n}r\) with the array remaining in membrane 1. A computation starts with an application of the rules of the column table \(c_1\) in membrane 1 to the axiom array, sending the generated array

$$\begin{aligned}\begin{array}{cccccc} x&{}a&{}d&{}b&{}e&{}y \\ x&{}z&{}z&{}z&{}z&{}y \\ q&{}z&{}z&{}z&{}z&{}r \\ s&{}z&{}z&{}z&{}z&{}t \end{array} \end{aligned}$$

to membrane 2. If the rules of the column table \(c_2\) in membrane 2, are applied, then the generated array

$$\begin{aligned}\begin{array}{cccccccc} x&{}a&{}d&{}b&{}a&{}e&{}b&{}y \\ x&{}z&{}z&{}z&{}z&{}z&{}z&{}y \\ q&{}z&{}z&{}z&{}z&{}z&{}z&{}r \\ s&{}z&{}z&{}z&{}z&{}z&{}z&{}t \end{array}\end{aligned}$$

will be sent back to membrane 1. This process can repeat. If in membrane 1, the rules of the column table \(c_3\) (instead of \(c_1\)) are applied, then the generated array is sent to the inner membrane 2 where the rules of the column table \(c_4\) are applied which replaces the symbol d by ab in the first row and replaces one symbol z in each of the remaining rows by zz. The resulting array is in the form of the picture array p,  which remains in the output region 2 and the computation halts. Here it is collected in the language. Thus the picture language L is generated. Note that no other correct sequence of applications of the tables of rules is possible.

6 Generation of floor designs

As an application of the array P System model considered in Sect. 4, we use a well-known technique [24] developed to generate certain interesting classes of floor designs, called “kolam patterns” [24, 26]. The idea is that with each symbol a of a rectangular picture array which is considered to occupy a unit square in the rectangular grid, a primitive picture pattern i(a) of the “kolam pattern” is associated. The picture array is then interpreted as a “kolam pattern” replacing the symbols in the picture array generated by the array P system, by the corresponding primitive picture patterns, to yield the required “kolam pattern”.

We illustrate this by considering the picture language \(L_{kolam}\) consisting of \(n \times n, n \ge 3\) picture arrays p such that \(p(1,1)=a, p(1,n) = y,\) \(p(n,1) = x, p(n,n) = e,\) \(p(1,j) = q, p(n,j) = r,\) for \(2 \le j \le n-1,\) \(p(i,1) = s, p(i,n) = t,\) for \(2 \le i \le n-1,\) \(p(i,j) = d,\) otherwise. A picture array of \(L_{kolam}\) is shown below.

$$\begin{aligned}\begin{array}{ccccc} a&{}q&{}q&{}q&{}y \\ s&{}d&{}d&{}d&{}t \\ s&{}d&{}d&{}d&{}t \\ s&{}d&{}d&{}d&{}t \\ x&{}r&{}r&{}r&{}e \end{array}\end{aligned}$$

The corresponding “kolam pattern” with the “kolam” primitives used, is shown in Fig. 2. \(L_{kolam}\) is generated by an array P system as in Definition 2 with membrane structure \([_1 \, [_2 \, ]_2 \, ]_1\), two column tables \(c_1,c_2\) in region 1 and a row table r in region 2 given by \(c_1 = \{a \rightarrow aq, d \rightarrow dd, b \rightarrow rb \},\) \(c_2 = \{a \rightarrow a, d \rightarrow d, b \rightarrow e \},\) \(r = \left\{ a \rightarrow \begin{array}{c} a\\ s \end{array}, d \rightarrow \begin{array}{c} d\\ d \end{array}, b \rightarrow \begin{array}{c} t\\ b \end{array} \right\}\) with \(c_1, c_2\) having target in and r having target out. The only initial axiom array in membrane 1, is

$$\begin{aligned}M_{0} = \begin{array}{ccc} a&{}q&{}y \\ s&{}d&{}t \\ x&{}r&{}b \end{array}. \end{aligned}$$

The primitive picture patterns associated with q, r, s, t, d are shown in Fig. 2 and \(i(a) = i(e) = i(x) = i(y) = blank.\)

Fig. 2
figure 2

A kolam pattern with its primitives

Full size image

7 Conclusions and future work

We have introduced here a new rewriting mode in pure 2D context-free grammars, called independent mode, for the generation of certain picture array languages, inspired from two-dimensional insertion systems with independent mode considered in [11]. We have shown the incomparability of the two classes of array languages, namely P2DCFL [29, 30] and IP2DCFL,  introduced here. Using P systems as a control mechanism for array rewriting, we have generated square pictures of a certain type (Example 3) using only one membrane and target agreement for rules. We also sketch an application of this formalism of P2DCFG with independent mode to the generation of certain simple floor designs, known as “kolam” patterns. It will be of interest to compare the array models considered here with other kinds of array grammars [4, 6,7,8,9] which is for future work.