# Contextual Array Grammars with Matrix and Regular Control

Henning Fernau, Rudolf Freund, Rani Siromoney, K. G. Subramanian

► To cite this version:

Henning Fernau, Rudolf Freund, Rani Siromoney, K. G. Subramanian. Contextual Array Grammars with Matrix and Regular Control. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.98-110, 10.1007/978-3-319-41114-9_8. hal-01633942

HAL Id: hal-01633942

https://inria.hal.science/hal-01633942

Submitted on 13 Nov 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Contextual Array Grammars with
Matrix and Regular Control

Henning Fernau <fnref n="1" />, Rudolf Freund <fnref n="2" />,
Rani Siromoney <fnref n="3" />, and K.G. Subramanian <fnref n="4" />

**Abstract.** We investigate the computational power of *d*-dimensional contextual array grammars with matrix control and regular control languages. For *d* ≥ 2, *d*-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. Yet in the 1-dimensional case, for a one-letter alphabet, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages coincides with the family of regular 1-dimensional array languages, whereas for alphabets with more than one letter, we obtain the array images of the linear languages.

# 1 Introduction

Contextual string grammars were introduced by Solomon Marcus [14] with motivations arising from descriptive linguistics. A contextual string grammar consists of a finite set of strings (*axioms*) and a finite set of productions, which are pairs (*s*, *c*) where *s* is a string, the *selector*, and *c* is the *context*, i. e., a pair of strings, *c* = (*u*, *v*), over the alphabet under consideration. Starting from an axiom, contexts iteratively are added as is indicated by the productions, which yields new strings. In contrast to usual sequential string grammars in the Chomsky hierarchy (e. g., see [20]), these contextual string grammars are pure grammars where new strings are not obtained by rewriting, but by adjoining strings. Several classes of contextual grammars have been introduced and investigated, e. g., see [3] and [17] for surveys on the area.

The idea of contextual productions then was also introduced for multi-
dimensional array grammars, for instance, to carry over ideas from formal lan-
guages to the processing of digital images. In the area of two-dimensional picture

<footnote n="1">¹ Universität Trier, FB 4 – Abteilung Informatikwissenschaften,
D-54296 Trier, Germany; E-mail: fernau@uni-trier.de</footnote>

<footnote n="2">² Technische Universität Wien, Institut für Computersprachen,
A-1040 Wien, Austria; E-mail: rudi@emcc.at</footnote>

<footnote n="3">³ Chennai Mathematical Institute,
Kelambakkam 603103, India; E-mail: siromoney@cmi.ac.in</footnote>

<footnote n="4">⁴ Department of Mathematics and Computer Science, Faculty of Science,
Liverpool Hope University Liverpool, L16 9JD UK
E-mail: kgsmani1948@yahoo.com</footnote>
languages, e.g., see [12, 16, 18, 19], different kinds of array grammars, both iso-
metric and non-isometric ones, have been proposed, motivated by many applica-
tions such as character recognition (also confer [4]), cluster analysis of patterns,
and so on. Isometric contextual array grammars were introduced in [11].

Regulated rewriting with different control mechanisms has been studied ex-
tensively especially for string grammars (e.g., see [2]), for example, grammars
with control languages and matrix grammars, but then also for array grammars,
e.g., see [9]. Non-isometric contextual array grammars (with regulation) were
considered in [8, 7, 13].

In this paper we consider matrix contextual array grammars and contextual
array grammars with regular control and examine their generative power. In
the 1-dimensional case, we obtain special results: the family of 1-dimensional
array languages generated by contextual array grammars with regular control
languages coincides with the family of regular 1-dimensional array languages over
unary alphabets and with array images of the linear languages over alphabets
with more than one letter; already for binary alphabets, regular control is strictly
more powerful than matrix control, a phenomenon rarely observed in regulated
rewriting (confer [10]).

## 2 Definitions

For notions and notations as well as results related to formal language theory we
refer to books like [2]. The families of $\lambda$-free ($\lambda$ denotes the empty string) regular
string languages (over a $k$-letter alphabet) is denoted by $\mathcal{L}(\mathbf{REG}) (\mathcal{L}(\mathbf{REG}^k))$.
For the definitions and notations for arrays and sequential array grammars we
refer to [9, 18, 22].

Let $\mathbb{Z}$ be the set of integers and $\mathbb{N}$ be the set of positive integers. Let $d \in \mathbb{N}$.
A $d$-dimensional array $\mathcal{A}$ over the alphabet $V$ is a mapping $\mathcal{A}: \mathbb{Z}^d \to V \cup \{\#\}$
where $\text{shape}(\mathcal{A}) = \{v \in \mathbb{Z}^d | \mathcal{A}(v) \neq \#\}$ is finite and $\# \notin V$ is called the *blank
symbol*. We usually write $\mathcal{A} = \{(v, \mathcal{A}(v)) | v \in \text{shape}(\mathcal{A})\}$. The set of all $d$-di-
mensional arrays over $V$ is denoted by $V^{*d}$. The *empty array* $\Lambda_d$ in $V^{*d}$ satisfies
$\text{shape}(\Lambda_d) = \emptyset$. Moreover, we define $V^{+d} = V^{*d} \setminus \{\Lambda_d\}$.

Let $v \in \mathbb{Z}^d$. Then the (linear) translation $\tau_v : \mathbb{Z}^d \to \mathbb{Z}^d$ is defined by
$\tau_v(w) = w + v$ for all $w \in \mathbb{Z}^d$, and for any array $\mathcal{A} \in V^{*d}$ we define $\tau_v(\mathcal{A})$, the
corresponding $d$-dimensional array translated by $v$, by $(\tau_v(\mathcal{A}))(w) = \mathcal{A}(w - v)$
for all $w \in \mathbb{Z}^d$. The vector $(0, ..., 0) \in \mathbb{Z}^d$ is denoted by $\Omega_d$.

Usually (see [18]) arrays are regarded as equivalence classes of arrays with
respect to linear translations. The equivalence class $[\mathcal{A}]$ of an array $\mathcal{A} \in V^{*d}$
satisfies $[\mathcal{A}] = \{\mathcal{B} \in V^{*d} | \mathcal{B} = \tau_v(\mathcal{A}) \text{ for some } v \in \mathbb{Z}^d\}$. The set of all equiva-
lence classes of $d$-dimensional arrays over $V$ with respect to linear translations
is denoted by $[V^{*d}]$, and this bracket notation carries over to classes of array
languages, as well.

As many results for $d$-dimensional arrays for a specific $d$ can be taken over
immediately for higher dimensions, we introduce special notions:
Let $n, m \in \mathbb{N}$ with $n \le m$. For $n < m$, the natural embedding $i_{n,m}: \mathbb{Z}^n \to \mathbb{Z}^m$ is defined by $i_{n,m}(v) = (v, \Omega_{m-n})$ for all $v \in \mathbb{Z}^n$; for $n = m$ we define $i_{n,n}: \mathbb{Z}^n \to \mathbb{Z}^n$ by $i_{n,n}(v) = v$ for all $v \in \mathbb{Z}^n$. To an $n$-dimensional array $\mathcal{A} \in V^{+n}$ with $\mathcal{A} = \{(v, \mathcal{A}(v)) \mid v \in \text{shape}(\mathcal{A})\}$ we assign the $m$-dimensional array $i_{n,m}(\mathcal{A}) = \{(i_{n,m}(v), \mathcal{A}(v)) \mid v \in \text{shape}(\mathcal{A})\}$.

We can use the well-known graph-theoretic notion of a connected graph to define connected arrays. Let $W$ be a non-empty finite subset of $\mathbb{Z}^d$. We associate a graph $g(W)$ to $W$ with vertex set $W$ and an edge between $v, w \in W$ if and only if $\|v - w\| = 1$, where the norm $\|u\|$ of a vector $u \in \mathbb{Z}^d$, $u = (u(1), \dots, u(d))$, is defined by $\|u\| = \max\{|u(i)| \mid 1 \le i \le d\}$. Then $W$ is said to be connected if $g(W)$ is connected. There is a natural bijection between the (equivalence classes of) 1-dimensional connected arrays and strings: for any equivalence class of 1-dimensional arrays $\mathcal{A} = [((i-1), a_i) \mid 1 \le i \le n]$ we define its string image as $\text{str}(\mathcal{A}) = a_1 \dots a_n$; the string $w = a_1 \dots a_n$ can be interpreted as the array $\text{arr}(w) = [((i-1), a_i) \mid 1 \le i \le n]$. In the standard way, these notions are extended from strings and arrays to sets of strings and arrays.

**Example 1.** Consider the language $L_1$ of connected 2-dimensional arrays

$$L_1 = \left\{ \left( \left( (0, i), a \right) \mid 0 \le i \le n \right) \cup \left( \left( (j, 0), a \right) \mid 1 \le j \le m \right) \mid n, m \in \mathbb{N} \right\}.$$

a An example of these L-shaped arrays (for $n=3$ and

a $m=4$) from $[L_1]$ can be depicted as shown on the left.

a Observe that both arms of these arrays can have arbitrary lengths.

a a a a a □

**Definition 1.** A regular $d$-dimensional array grammar is specified as $G = (d, N, T, \# , P, \{(v_S, S)\})$ where $N$ is the alphabet of non-terminal symbols, $T$ is the alphabet of terminal symbols, $N \cap T = \emptyset$, $\# \notin N \cup T$; $P$ is a finite non-empty set of regular $d$-dimensional array productions over $N \cup T$, as well as $v_S \in \mathbb{Z}^d$ and $S \in N$ is the start symbol. A regular $d$-dimensional array production either is of the form $A \to b$, $A \in N$, $b \in T$, or $Av \to bC$, $A, C \in N$, $b \in T$, $v \in \mathbb{Z}^d$ with $\|v\| = 1$. The application of $A \to b$ means replacing $A$ by $b$ in a given array. $Av \to bC$ can be applied if in the underlying array we find a position $u$ occupied by $A$ and a blank symbol at position $u + v$; $A$ then is replaced by $b$, and $\#$ by $C$. The array language generated by $G$ is the set of all $d$-dimensional arrays derivable from the initial array $\{(v_S, S)\}$. The family of $\Lambda$-free $d$-dimensional array languages (of equivalence classes) of arrays over a $k$-letter alphabet generated by regular $d$-dimensional array grammars is denoted by $\mathcal{L}(d-REGA^k)$ ($\mathcal{L}(d-REGA^k)$). For arbitrary alphabets, we omit the superscript $k$.

The following results for 1-dimensional array languages are folklore:

**Theorem 1.** For all $k \ge 1$, $[\mathcal{L}(1-REGA^k)] = [\text{arr}(\mathcal{L}(REG^k))]$ and $\text{str}([\mathcal{L}(1-REGA^k)]) = \mathcal{L}(REG^k)$.

Let us mention the close similarities of the work of 1-dimensional regular array grammars and Lindenmayer systems with apical growth [21]. Another similar development can be found within Watson-Crick systems [15].
## 3 Contextual Array Grammars

We now turn our attention to the main variants of contextual array grammars considered in this paper.

**Definition 2.** A $d$-dimensional contextual array grammar ($d \in \mathbb{N}$) is a construct $G = (d, V, \# , P, A)$ where $V$ is an alphabet not containing the blank symbol $\#$, $A$ is a finite set of axioms, i. e., of $d$-dimensional arrays in $V^{+d}$, and $P$ is a finite set of rules of the form $(U_\alpha, \alpha, U_\beta, \beta)$ where

(i) $U_\alpha, U_\beta \subseteq \mathbb{Z}^d$, $U_\alpha \cap U_\beta = \emptyset$, and $U_\alpha, U_\beta$ are finite and non-empty;

(ii) $\alpha : U_\alpha \to V$ and $\beta : U_\beta \to V$.

$(U_\alpha, \alpha)$ corresponds with the selector and $(U_\beta, \beta)$ with the context of the production $(U_\alpha, \alpha, U_\beta, \beta)$; $U_\alpha$ is called the selector area, and $U_\beta$ is the context area. As the sets $U_\alpha$ and $U_\beta$ are uniquely determined by $\alpha$ and $\beta$, we will also represent $(U_\alpha, \alpha, U_\beta, \beta)$ by $(\alpha, \beta)$ only.

For $C_1, C_2 \in V^{+d}$ we say that $C_2$ is directly derivable from $C_1$ by the contextual array production $p \in P$, $p = (U_\alpha, \alpha, U_\beta, \beta)$ (we write $C_1 \implies_p C_2$), if there exists a vector $v \in \mathbb{Z}^d$ such that

- $C_1(w) = C_2(w) = \alpha(\tau_{-v}(w))$ for all $w \in \tau_v(U_\alpha)$,

- $C_1(w) = \#$ for all $w \in \tau_v(U_\beta)$,

- $C_2(w) = \beta(\tau_{-v}(w))$ for all $w \in \tau_v(U_\beta)$,

- $C_1(w) = C_2(w)$ for all $w \in \mathbb{Z}^d \setminus \tau_v(U_\alpha \cup U_\beta)$.

Hence, if in $C_1$ we find a subpattern that corresponds with the selector $\alpha$ and only blank symbols at the places corresponding with $\beta$, we can add the context $\beta$ thus obtaining $C_2$. For every $B_1, B_2 \in [V^{+d}]$ we say that $B_2$ is directly derivable from $B_1$ by the contextual array production $p \in P$, $p = (U_\alpha, \alpha, U_\beta, \beta)$, denoted $B_1 \implies_p B_2$, if and only if $C_1 \implies_p C_2$ for some $C_1 \in B_1$ and $C_2 \in B_2$. $C_1 \implies_G C_2$ ($B_1 \implies_G B_2$) means that $C_1 \implies_p C_2$ ($B_1 \implies_p B_2$) for some $p \in P$.

The array language generated by $G$ is defined as

$$L(G) = \{C \in V^{+d} \mid A \implies_G^* C \text{ for some } A \in A\}.$$

The special type of $d$-dimensional contextual array grammars where axioms are connected and rule applications preserve connectedness is denoted by $d$-Cont$A$, the corresponding family of $d$-dimensional array languages by $\mathcal{L}$ ($d$-Cont$A$); by $\mathcal{L}$ ($d$-Cont$A^k$) we denote the corresponding family of $d$-dimensional array languages over a $k$-letter alphabet.

**Remark 1.** As we mostly are interested in (families of) equivalence classes of arrays, a $d$-dimensional contextual array grammar $[G]$ for generating $[L]$ for $L \in \mathcal{L}$ ($d$-Cont$A$) being generated by a $d$-dimensional contextual array grammar $G = (d, V, \# , P, A)$ with $A = \{A_i \mid 1 \le i \le n\}$ will be specified by writing $[G] = (d, V, \# , P, A')$ where $A' = \{A'_i \mid 1 \le i \le n\}$ such that $A'_i \in [A_i]$, $1 \le i \le n$, which means specifying an axiom $A_i$ by one array from $[A_i]$.
**Example 2.** Any finite $d$-dimensional array language of connected arrays $L \subset T^{+d}$ is in $\mathcal{L}(d-\text{Cont}A)$ as $L = L(G_L)$ where $G_L = (d, T, \# , \emptyset, L)$. $\square$

**Example 3.** We now show how the language $L_1$ from Example 1 can be generated by the contextual array grammar $G_1$, i.e., $L_1 \in \mathcal{L}(2-\text{Cont}A^1)$: $G_1 = (2, \{a\}, \# , P_1, \{A_1\})$ where $A_1 = \{(0,0), a\), ((0,1),a), ((1,0),a)\}$ is the only axiom and $P_1$ consists of the two productions $p_u$ and $p_r$:

$$p_u = (\{(0,0), (0,1)\}, \{(0,0), a\}, ((0,1), a)\}, \{(0,2)\}, \{( (0,2), a)\}),$$

$$p_r = (\{(0,0), (1,0)\}, \{(0,0), a\}, ((1,0), a)\}, \{(2,0)\}, \{( (2,0), a)\}).$$

As the selector area $U_\alpha$ and the context area $U_\beta$ in a contextual array production of the form $(U_\alpha, \alpha, U_\beta, \beta)$ are disjoint, both $\alpha$ and $\beta$ can be represented within only one pattern, i.e., $p_u$ and $p_r$ can be represented in a more depictive way by the patterns shown on the right (the symbols of the selector are enclosed in boxes).

$$p_u = \frac{a}{\boxed{a}}, \quad p_r = \frac{a}{\boxed{a}} \text{ a.}$$

The example of the L-shaped array for $n = 3$ and $m = 4$ then is generated by twice applying rule $p_u$ and three times applying rule $p_r$, in any order. We also observe that every intermediate array obtained by applying these rules is in $L_1$, too. Obviously, by the definition of equivalence classes of arrays, we also have $[L(G_1)] = [L_1] \in [\mathcal{L}(2-\text{Cont}A^1)]$. $\square$

$[A_1]$ can be described in a more depictive way by $\frac{a}{a a}$, i.e., the contextual array grammar $[G_1]$ for $[L(G_1)]$ can also be written as $[G_1] = (2, \{a\}, \# , P_1, \{\frac{a}{a a}\})$ (see Remark 1). In the following, the axiom(s) often will just be given in such a pictorial variant. $\square$

**Example 4.** For the singleton language $L_\perp = \{\frac{a}{a a a a a}\} \subset [\{a\}^{+2}]$, we have $L_\perp \in [\mathcal{L}(2-\text{Cont}A)] \setminus [\mathcal{L}(2-\text{REGA})]$. As we can take $L_\perp$ (as any finite language) as a set of axioms, containment in $[\mathcal{L}(2-\text{Cont}A)]$ is clear. Conversely, any regular array grammar has to scan the non-blank symbols of the array $A$, which is impossible, as the underlying graph $g(\text{shape}(A))$ is not Hamiltonian. $\square$

**Theorem 2.** $[\mathcal{L}(1-\text{REGA}^1)] \subseteq [\mathcal{L}(1-\text{Cont}A^1)]$. $\square$

*Proof.* Due to the results from Theorem 1, it only remains to show that $[\text{arr}(\mathcal{L}(\text{REG}^1))] \subseteq [\mathcal{L}(1-\text{Cont}A^1)]$. $\square$

From [1, Theorem 4.4], we deduce that any infinite language $L \subseteq \{a\}^+$ in $\mathcal{L}(\text{REG}^1)$ can be written in the form $L = \{a^{s_1}, a^{s_2}, \dots, a^{s_t}\} \cup \bigcup_{i=1}^m \{a^{k \cdot n + d_i} | n \ge 0\}$ for some numbers $k, k \le d_1 < d_2 < \dots < d_m < 2k, 0 \le s_1 < s_2 < \dots < s_t < k$. The 1-dimensional contextual array grammar now is constructed using a context of length $k$ and putting the words $a^{s_j}, 1 \le j \le t$, and $a^{d_i}, 1 \le i \le m$, into the set of axioms, i.e., we define the 1-dimensional contextual array grammar $G(L) = (1, \{a\}, \# , P, A)$ with $A = \{\text{arr}(a^{s_j}) | 1 \le j \le t\} \cup \{\text{arr}(a^{d_i}) | 1 \le i \le m\}$ and
$P = \{\overline{[a]^k a^k}\}$. Obviously, $[L(G(L))] = [\text{arr}(L)]$. The 1-dimensional contextual array grammar $[G(L)]$ for $[L(G(L))]$ can also be written as $[G(L)] = (1, \{a\}, \#P, A')$ with $A' = \{a^{s_j} \mid 1 \le j \le t\} \cup \{a^{d_i} \mid 1 \le i \le m\}$ (compare with Remark 1).

For the sake of completeness we mention that every finite array language $A = \{\text{arr}(a^{s_j}) \mid 1 \le j \le t\}$ is generated by the 1-dimensional contextual array grammar $G(L) = (1, \{a\}, \#P, A)$ with $P = \emptyset$. $\square$

**Remark 2.** Following the definition already given in [11], our $d$-dimensional extension of (external) contextual grammars only appends at one location, while external contextual string grammars as originally defined by Solomon Marcus, see [14], append to both ends of a string at the same time. This design decision has two main reasons. First, it is not quite clear what the $d$-dimensional counterpart of external contextual grammars would really mean: for instance, for $d=2$, should we allow appending on both ends of a row or column at the same time, as we did in [8] for the case of non-isometric contextual array grammars? Or, should we rather append on ‘all ends’? Obviously, this situation becomes even more intricate for higher dimensions. Yet second and even more important, appending at both sides of a string, i.e., a 1-dimensional array, in parallel can easily be simulated sequentially by a matrix with two components. It is therefore easy to see that in the 1-dimensional case, the string images of the arrays generated by contextual array grammars with matrix control exactly correspond with the string languages generated by external contextual string grammars. This means that for the regulated variants discussed in the following, any variant that can be conceivably defined for the $d$-dimensional analogue of external contextual grammars, in the 1-dimensional case should lead to the same results as the original variant of contextual array grammars defined in [11] and taken as the basis in this paper, too.

## 3.1 Matrix Contextual Array Grammars

**Definition 3.** A $d$-dimensional matrix contextual array grammar is a pair $G_M = (G, M)$ where $G = (d, V, \#P, A)$ is a $d$-dimensional contextual array grammar and $M$ is a finite set of sequences, called matrices, of rules from $P$, i.e., each element of $M$ is of the form $\langle p_1, \cdots, p_n \rangle$, $n \ge 1$, where $p_i \in P$ for $1 \le i \le n$. Derivations in a matrix contextual array grammar are defined as in a contextual array grammar except that a single derivation step now consists of the sequential application of the rules of one of the matrices in $M$, in the order in which the rules are given in the matrix. The array language generated by $G_M$ is the set of all $d$-dimensional arrays which can be derived from any of the axioms in $A$. The family of $d$-dimensional array languages of arrays generated by $d$-dimensional matrix contextual array grammars (over a $k$-letter alphabet) is denoted by $\mathcal{L}(d-MContA)$ ($\mathcal{L}(d-MContA^k)$).

**Example 5.** Consider the language $L_2$ of connected arrays given by

$$L_2 = \left\{ \left\{ ((0,0), a) \right\} \cup \left\{ ((0,i), a), ((i,0), a) \mid 1 \le i \le n \right\} \mid n \in \mathbb{N} \right\},$$
which contains L-shaped arrays as $L_1$ from Example 1, but now with both arms having the same length. $L_2 \in \mathcal{L}(2-MContA^1)$, as it can be generated by the 2-dimensional matrix contextual array grammar $G_M = (G_1, M)$ where $G_1$ is the 2-dimensional contextual array grammar from Example 3 and $M = \{\langle p_u, p_r \rangle\}$. The only derivations possible in $G'_M$ for $[L_2] \in [\mathcal{L}(2-MContA^1)]$ (see Remark 1) are:

$$ \begin{array}{ccccc} a & \Rightarrow_{G'_M} & a & \Rightarrow_{G'_M} & a \\ a & \Rightarrow_{G'_M} & a & \Rightarrow_{G'_M} & a \\ a & \Rightarrow_{G'_M} & a & \Rightarrow_{G'_M} & a \\ a & \Rightarrow_{G'_M} & a & \Rightarrow_{G'_M} & a \\ a & \Rightarrow_{G'_M} & a & \Rightarrow_{G'_M} & a \end{array} $$

The single matrix $\langle p_u, p_r \rangle$, $p_u = \frac{a}{\frac{a}{a}}$, $p_r = \frac{a}{\frac{a}{a}}$, guarantees that both arms of the array grow in a synchronized way. □

**Theorem 3.** For any $d \ge 2$ and any $k \ge 1$, we have $\mathcal{L}(d-ContA^k) \subsetneq \mathcal{L}(d-MContA^k)$ and $[\mathcal{L}(d-ContA^k)] \subsetneq [\mathcal{L}(d-MContA^k)]$.

*Proof.* The inclusion $\mathcal{L}(d-ContA^k) \subseteq \mathcal{L}(d-MContA^k)$ and therefore also $[\mathcal{L}(d-ContA^k)] \subseteq [\mathcal{L}(d-MContA^k)]$ is obvious from general results for grammars working on various kinds of objects and with specific regulating mechanisms, see [10].

For showing the strictness of the inclusion, we prove that the array language $L_2$ from Example 5 cannot be generated by a 2-dimensional contextual array grammar; for dimensions $d > 2$, we just take $[i_{2,d}(L_2)]$.

Now assume we could find a 2-dimensional contextual array grammar $[G = (2, \{a\}, \#P, A)]$ that generates $[L_2]$. As contextual grammars are pure grammars, $[A]$ is a finite subset of $[L(G)]$. As $[L(G)]$ is infinite, we would need an infinite number of rules to get $[L_2]$ which resembles the case of external contextual string grammars; in fact, as soon as the arms get long enough, we have to apply a rule which only grows the arm going up or only grows the arm going to the right, resulting in an array which contradicts the definition of $[L_2]$. It is obvious that we also have $[i_{2,d}(L_2)] \in [\mathcal{L}(d-MContA^k)] \setminus [\mathcal{L}(d-ContA^k)];$ this observation completes the proof. □

In the 1-dimensional case, the situation is different: as we shall prove later, see Theorem 6, $[\mathcal{L}(1-ContA^1)] = [\mathcal{L}(1-MContA^1)]$, but for $k \ge 2$, we still have $[\mathcal{L}(1-ContA^k)] \subsetneq [\mathcal{L}(1-MContA^k)]$, as the following example shows.

*Example 6.* Consider the non-regular language $L_n = \{a^nba^n | n \ge 1\}$. By Theorem 1, there cannot exist an array grammar $G$ of type 1-REGA$^2$ such that $[L(G)] = [\text{arr}(L_n)]$. Even more, there is no 1-dimensional contextual array grammar for $L_n$. Namely, if this would be the case, then first observe that there must be rules that append something to the right, as well as to the left of the array, and this should be possible infinitely often. Otherwise, the sequence of context additions would happen (finally) only on one side, which means that this behavior can again be simulated by some regular array grammar, contradicting our previous reasoning. Hence, there must be a rule that contains a sequence of
a's as its selector, say, $\mathit{arr}(a^{r_s})$, and also a sequence of a's, say, $\mathit{arr}(a^{r_c})$ as its context in order to append $a^{r_c}$ to the right of the current array, and likewise, there must be a rule that contains a sequence of a's as its selector, say, $\mathit{arr}(a^{l_s})$, and also a sequence of a's, say, $\mathit{arr}(a^{l_c})$ as its context in order to append $a^{l_c}$ to the left of the current array. For sufficiently long arrays $\mathit{arr}(a^nba^n)$, both rules can be applied, and arrays like $\mathit{arr}(a^nba^{n+r_c})$ can generated that do not belong to $L_n$. Hence, $L_n \notin \mathcal{L}(1-\mathit{ContA})$.

Yet for the 1-dimensional matrix contextual array grammar $[G_M] = (G_n, M_n)$ with $[G_n] = (1, \{a, b\}, \#P, \{aba\})$ where $p_l = a[a], p_r = [a]a$, and $M_n = \{\langle p_l, p_r \rangle\}$, we have $[L(G_n)] = [\mathit{arr}(L_n)]$. The single matrix $\langle p_l, p_r \rangle$ guarantees that the number of symbols $a$ grows to the left and to the right in a synchronized way. $\square$

In addition, the following example even yields that for any $k \ge 2$, $[\mathcal{L}(1-\mathit{MContA}^k)]$ is incomparable with $[\mathcal{L}(1-\mathit{REGA}^k)]$.

**Example 7.** Consider the regular string language $L_r = \{ba^nb | n \ge 1\}$. Due to Theorem 1, there exists an array grammar of type 1-REGA² $G_r$ such that $[L(G_r)] = [\mathit{arr}(L_r)]$. Yet on the other hand, there cannot exist an array grammar of type 1-\textit{MContA}² $[G]$ such that $L([G]) = [\mathit{arr}(L_r)]$, which can be proved by a simple pumping argument: The number of symbols $a$ between the two symbols $b$ can become arbitrarily large, but we only have a finite set of axioms $A$; as $[G]$ is a pure grammar, $[A] \subset [L]$; yet $[G]$ can only grow these arrays in an external way, i.e., by adding symbols on the left or on the right, but in this way we are not able to grow the number of symbols $a$ in the middle. $\square$

## 3.2 Contextual Array Grammars with Regular Control

**Definition 4.** A d-dimensional contextual array grammar with regular control is a pair $G_C = (G, L)$ where $G = (d, V, \#P, A)$ is a d-dimensional contextual array grammar and $L$ is a regular string language over $P$. Derivations in a d-dimensional contextual array grammar with regular control are defined as in the contextual array grammar $G$ except that in a successful derivation the sequence of applied rules has to be a word from $L$. The array language generated by $G_C$ is the set of all d-dimensional arrays which can be derived from any of the axioms in $A$ following a control word from $L$. The family of d-dimensional array languages of arrays generated by d-dimensional contextual array grammars over a k-letter alphabet with regular control is denoted by $\mathcal{L}((d-\mathit{ContA}, \mathit{REG}))$. The corresponding family of array languages of equivalence classes of arrays is denoted by using brackets in the notations.

As a general result (following [10]) we can state:

**Theorem 4.** For any $d \ge 1$ and any $k \ge 1$,

$$[\mathcal{L}(d-\mathit{ContA}^k)] \subseteq [\mathcal{L}(d-\mathit{MContA}^k)] \subseteq [\mathcal{L}((d-\mathit{ContA}^k, \mathit{REG}))].$$
Example 8. Consider the regular string language $L_r = \{ba^nb | n \ge 1\}$ from Example 7. We have shown that $[\text{arr}(L_r)] \in [\mathcal{L}(1-\text{REGA}^2)] \setminus [\mathcal{L}(1-M\text{Cont}A^2)]$. Moreover, $[\text{arr}(L_r)] \in [\mathcal{L}((1-\text{Cont}A^1, \text{REG}))] \setminus [\mathcal{L}(1-M\text{Cont}A^2)]$: Consider $G'_r = (G_r, C_r)$ with $G_r = (1, \{a, b\}, \#P, \{\text{arr}(ba)\})$ and $P = \{p_{aa}, p_{ab}\}$ with $p_{aa} = [a]a$, and $p_{ab} = [a]b$, as well as $C_r = \{p_{aa}\}^* \{p_{ab}\}$. It is easy to see that $[L(G'_r)] = [\text{arr}(L_r)]$. $\square$

**Theorem 5.** For any $d \ge 1$ and any $k \ge 2$, we have:

$$[\mathcal{L}(d-\text{Cont}A^k)] \subsetneq [\mathcal{L}(d-M\text{Cont}A^k)] \subsetneq [\mathcal{L}((d-\text{Cont}A^k, \text{REG}))].$$

*Proof.* The inclusions directly follow from Theorem 4. The strictness of the first inclusion follows from Example 6 by taking the non-regular string language $L_n = \{a^nba^n | n \ge 1\}$. Then $[i_{1,d}(\text{arr}(L_n))] \in [\mathcal{L}(d-M\text{Cont}A^2)] \setminus [\mathcal{L}(d-\text{Cont}A^k)]$. The strictness of the second inclusion follows from Example 8 by taking $[i_{1,d}(\text{arr}(L_r))]$. $\square$

On the other hand, in the 1-dimensional case, the following theorem says that even with the regulating mechanisms of matrix control or regular control languages, with 1-dimensional contextual array grammars over a one-letter alphabet we cannot go beyond regularity, i.e., beyond $[\mathcal{L}(1-\text{REGA}^1)]$.

**Theorem 6.** $[\mathcal{L}(1-\text{REGA}^1)] = [\mathcal{L}(1-\text{Cont}A^1, \text{REG})] = [\mathcal{L}(1-M\text{Cont}A^1)] = [\mathcal{L}(1-\text{Cont}A^1)]$.

*Proof.* (Sketch) According to Theorems 4 and 2, we only have to show that $[\mathcal{L}(1-\text{REGA}^1)] \supseteq [\mathcal{L}((1-\text{Cont}A^1, \text{REG}))]$. The main ideas of the corresponding technically non-trivial proof can be described as follows:

- Without loss of generality, right-hand sides of rules have the form $[a]^m a^n$.

- Context information is irrelevant for the unary 1-dimensional case, assuming that the set of axioms collects all arrays of sufficient size.

- The state information of the regular control is then encoded in the nonterminals of the regular array grammar. $\square$

Allowing for more than one symbol, 1-dimensional contextual array grammars can generate exactly the array images of linear languages. The proof is based on the following normal form:

**Lemma 1.** For any 1-dimensional contextual array grammar with regular control $G_C = (G, L)$, where $G = (1, V, \#P, A)$, $L \subseteq P^*$, we can construct an equivalent 1-dimensional contextual array grammar with regular control $G'_C = (G', L')$ with $G' = (1, V, \#P, A')$, $L' \subseteq P'^*$, such that for $P'$ we have:

- All rules in $P'$ are of the form $[a]b$ or $b[a]$ for some $a, b \in V$, i.e., we only have the minimal non-empty size of selectors and minimal contexts of size 1.

- If there is a rule of the form $[a]b$ / $b[a]$ in $P'$, then also all rules of the form $[c]b$ or $b[c]$ are in $P'$, for any $c \in V$, i.e., the selector contents is irrelevant, only direction of growth of the array is important.
The rules in this normal form nicely correspond with the operations of left and
right insertions for strings, which operations together with regular control lan-
guages also characterize the family of linear languages.

**Theorem 7.** $[\mathcal{L}(1-\text{ContA}, \text{REG})] = \text{arr}(\mathcal{L}(\text{LIN}))$.

*Proof.* (Sketch) The main ideas of the proof can be described as follows:

- Adding strings in a controlled way “on both ends” corresponds to applying linear rules, but in reverse order.

- The information about the finitely many selectors possible can be stored in the nonterminal; on the other hand, the nonterminal can be stored in the state of the finite automaton of the control language. $\square$

For $d \ge 2$, i.e., in the case of at least two symbols, we can prove the in-
comparability of the families of array languages generated by contextual array
grammars and those equipped with control mechanisms:

**Theorem 8.** For any $d \ge 2$ and any $k \ge 1$, all the three families

$[\mathcal{L}(d-\text{ContA}^k)]$, $[\mathcal{L}(d-M\text{ContA}^k)]$, and $[\mathcal{L}((d-\text{ContA}^k, \text{REG}))]$ are incomparable with $[\mathcal{L}(d-\text{REGA}^k)]$.

*Proof.* For the singleton language $L_\perp$ from Example 4, we have $i_{2,d}(L_\perp) \in ([\mathcal{L}(d-\text{ContA}^1)] \cap [\mathcal{L}(d-M\text{ContA}^1)] \cap [\mathcal{L}((d-\text{ContA}^1, \text{REG}))]) \setminus [\mathcal{L}(d-\text{REGA}^1)]$. On the other hand, for $L_r$ from Example 7 we have $i_{2,d}([\text{arr}(L_r)]) \in [\mathcal{L}(1-\text{REGA}^2)] \setminus ([\mathcal{L}(d-\text{ContA}^1)] \cup [\mathcal{L}(d-M\text{ContA}^1)] \cup [\mathcal{L}((d-\text{ContA}^1, \text{REG}))])$. Yet even for the case of one-letter alphabets we can find an array language of 2-dimensional arrays in $[\mathcal{L}(2-\text{REGA}^1)] \setminus [\mathcal{L}((2-\text{ContA}^1, \text{REG}))]$ : we consider $\lfloor\rfloor$-shaped arrays with the left vertical line having a length being a multiple of 3 and the right vertical line having a length being a multiple of 5. These arrays can easily be generated by a regular array grammar by first generating the left vertical line from up to down, followed by the horizontal line, finally generating the right vertical line upwards. On the other hand, this set of 2-dimensional arrays cannot be generated by a contextual array grammar even when using regular control: as soon as the vertical lines have become long enough, we cannot distinguish any more between the left and the right one, so either the lengths will not necessarily fulfill the constraints of being a multiple of 3 and 5, respectively, any more, or even worse, the lines might even be prolonged below the horizontal line yielding arrays of the shape of an H. $\square$

# 4 Decidability Questions

As the size of the arrays generated by contextual array grammars (even with any control mechanism) increases with every derivation step, the generated array languages are computable (i.e., recursive).

As an immediate consequence of Theorem 7, we obtain:

**Corollary 1.** *Emptiness is decidable for* $\mathcal{L}(1-\text{ContA}, \text{REG})$.
Yet for higher dimensions, we obtain a completely different situation:

**Theorem 9.** *Emptiness is not decidable for $\mathcal{L}$ (d-Cont$A^k$, REG) for $d \ge 2$, even for $k = 1$.*

*Proof.* (Sketch) As, for example, described in [5], the derivation carpet of a Turing machine can be described using 2-dimensional contextual array productions in the t-mode of derivation, i.e., a derivation only stops if no rule can be applied any more. The goal of only halting with specific conditions being fulfilled can also be obtained using suitable regular control languages, as we can require specific final rules to be applied. Hence, we will obtain a non-empty array language if and only if there is a derivation simulating the acceptance of a string by the given Turing machine. The proof given in [5] does not bound the number of symbols used. Yet $m$ symbols can be encoded by $2 \times m$ rectangles with the $k$-th of these $m$ symbols being encoded by leaving the $k$-th position in the second vertical line free, which then can be checked by the selector in the contextual array productions. Hence, simulating successful computations of the given Turing machine will result in the generation of $2k \times mn$ rectangles for accepting computations. $\square$

# 5 Picture Generation

Another interesting topic is to consider the generation of geometric objects such as solid rectangles and squares, which has been used to exhibit the generative power of various array grammar variants. Both of them, i.e., the 2-dimensional array language $L_{rect}$ of all solid rectangles of size $m \times n$, $m, n \ge 2$, made of a single symbol $a$ and the 2-dimensional array language $L_{square}$ of all solid squares of side length $n$, $n \ge 2$, made of a single symbol $a$ are well-known to be in $\mathcal{L}(2-REGA^1)$, see [23], but as we are able to show they can also be generated by 2-dimensional contextual array grammars with regular control, i.e., $\{L_{rect}, L_{square}\} \subset \mathcal{L}((2-ContA^1, REG))$. We now only exhibit the contextual array grammar with regular control for the squares.

*Example 9.* $L_{square}$ is generated by the 2-dimensional contextual array grammar with regular control $G_{squareRC} = (G_{square}, C_{square})$ with $G_{square} = (\{a\}, P_{square}, A_{square})$, where $A_{square}$ collects the $2 \times 2$ and $3 \times 3$ squares,

$$P_{square} = \{s_{ul}, s_{dr}, s_{ur}, s_{dl}, r_{ul}, r_{uu}, r_{dr}, r_{dd}\}, \text{ and} \\ C_{square} = (\{s_{ul}s_{dr}\} \{r_{ul}r_{dr}\}^* \{r_{uu}r_{dd}\}^* \{s_{ur}s_{dl}\})^+.$$

The rules are listed in the following:

$$s_{ul} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, s_{dr} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, s_{ur} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, s_{dl} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, \\ r_{ul} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, r_{uu} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, r_{dr} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}, r_{dd} = \begin{array}{c} a \\ | \\ a \end{array} \begin{array}{c} a \\ | \\ a \end{array}.$$
8. Fernau, H., Freund, R., Siromoney, R., Subramanian, K.G.: Non-isometric contextual array grammars with regular control and local selectors. In: Durand-Lose, J., Nagy, B. (eds.) Machines, Computations, and Universality, MCU. Lecture Notes in Computer Science, vol. 9288, pp. 61–78. Springer (2015)

9. Freund, R., Kogler, M., Oswald, M.: Control mechanisms on #-context-free array grammars. In: Păun, Gh. (ed.) Mathematical Aspects of Natural and Formal Languages, pp. 97–136. World Scientific Publ., Singapore (1994)

10. Freund, R., Kogler, M., Oswald, M.: A general framework for regulated rewriting based on the applicability of rules. In: Kelemen, J., Kelemenovà, A. (eds.) Computation, Cooperation, and Life, Lecture Notes in Computer Science, vol. 6610, pp. 35–53. Springer (2011)

11. Freund, R., Păun, Gh., Rozenberg, G.: Contextual array grammars. In: Subramanian, K., Rangarajan, K., Mukund, M. (eds.) Formal Models, Languages and Applications, Series in Machine Perception and Artificial Intelligence, vol. 66, chap. 8, pp. 112–136. World Scientific (2007)

12. Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer (1997)

13. Krithivasan, K., Balan, M., Rama, R.: Array contextual grammars. In: Martín-Vide, C., Păun, Gh. (eds.) Recent Topics in Mathematical and Computational Linguistics, pp. 154–168. Editura Academiei Române, Bucureşti (2000)

14. Marcus, S.: Contextual grammars. Revue Roumaine de Mathématiques Pures et Appliquées 14, 1525–1534 (1969)

15. Nagy, B.: On a hierarchy of $5' \to 3'$ sensing Watson-Crick finite automata languages. Journal of Logic and Computation 23(4), 855–872 (2013)

16. Pradella, M., Cherubini, A., Crespi-Reghizzi, S.: A unifying approach to picture grammars. Information and Computation 209, 1246–1267 (2011)

17. Păun, Gh.: Marcus contextual grammars, Studies in Linguistics and Philosophy, vol. 67. Springer, Dordrecht (1997)

18. Rosenfeld, A.: Picture Languages. Academic Press, Reading, MA (1979)

19. Rosenfeld, A., Siromoney, R.: Picture languages – a survey. Languages of Design 1(3), 229–245 (1993)

20. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 1-3. Springer (1997)

21. Subramanian, K.G.: A note on regular controlled apical growth filamentous systems. International Journal of Computer and Information Sciences 14, 235–242 (1985)

22. Wang, P.S.-P.: Some new results on isotonic array grammars. Information Processing Letters 10, 129–131 (1980)

23. Yamamoto, Y., Morita, K., Sugata, K.: Context-sensitivity of two-dimensional regular array grammars. International Journal of Pattern Recognition and Artificial Intelligence 3, 295–319 (1989)