Parikh Images of Matrix Ins-Del Systems

Abstract

Matrix insertion-deletion systems combine the idea of matrix control (as established in regulated rewriting) with that of insertion and deletion (as opposed to replacements). We study families of multisets that can be described as Parikh images of languages generated by this type of systems, focusing on aspects of descriptional complexity. We show that the Parikh images of matrix insertion-deletion systems having length 2 matrices and context-free insertion/deletion contain only semilinear languages and when the matrices length increased to 3, they contain non-semilinear languages. We also characterize the hierarchy of family of languages that is formed with these systems having small sizes. We also introduce a new class, namely, monotone strict context-free matrix ins-del systems and analyze the results connecting with families of context-sensitive languages and Parikh images of regular and context-free matrix languages.

1 Introduction

Classically, computations are defined on words (compare the basic definitions of finite automata or of Turing machines), leading to the description of set of words (i.e., of languages) and hence to the consideration of families of languages (for instance, as in the Chomsky hierarchy $\mathrm {REG}\subsetneq \mathrm {CF}\subsetneq \mathrm {CS}\subsetneq \mathrm {RE}$). Rather recently, the consideration of multiset languages (also known as macrosets [9]) has regained interest, where the basic entities are multisets of letters (as opposed to words), as the sequence of the letters does not matter. This renewed interest is also motivated from computational models such as membrane computing that are inspired by biology [14].

A different and supposedly older approach to multiset languages is via Parikh mappings [12]. Given an alphabet set $\varSigma =\{a_1,\ldots ,a_n\}$, the Parikh mapping of a word w can be seen as an n-dimensional vector, listing the number of occurrences of each (alphabet) symbol as it appeared in the word. This naturally leads to the Parikh image of a language L, denoted by $Ps \,L$. If $\mathcal {L}$ is some word language family, we can associate the Parikh set family $Ps \,\mathcal {L}$ to it. The following summarizes what is known about this with respect to the Chomsky hierarchy.

Proposition 1

$Ps \,\mathrm {REG}= Ps \,\mathrm {CF}\subsetneq Ps \,\mathrm {CS}\subsetneq Ps \,\mathrm {RE}.$

This paper is devoted to put Parikh images of matrix insertion-deletion systems into the context of the better known classes of macrosets. This way, we can also ascertain that several classes of matrix insertion-deletion languages are not computationally complete, rather are semilinear or non-semilinear. This is important, as the question to find matrix insertion-deletion systems of small size that are still computationally complete is one of the major research directions in that area of formal languages. As a further motivation of this study, observe that both multiset computations and insertion-deletion systems draw one of their origins in computational biology, so it is very natural to consider them together. Namely, insertions and deletions are actually a form of mutation and these operations in DNA, especially in connection with DNA computing, are discussed in [16]. In connection with RNA editing, these operations are reported in [1]. We also refer to [14] for various formalizations of DNA computing in general, including multiset computations.

Due to space constraints, several proofs in Sect. 5 have been omitted; we refer to the long version of this paper.

1.1 General Notions and Notations

Let $\mathbb {N}$ denote the set of nonnegative integers, and $[1\ldots k]=\{i\in \mathbb {N}:1\le i\le k\}$. Let $\varSigma$ be a finite set of n elements (an alphabet). $\varSigma ^*$ denotes the free monoid generated by $\varSigma$. The elements of $\varSigma ^*$ are called words or strings; $\lambda$ denotes the empty string, which is the neutral element with respect to the monoid operation on $\varSigma ^*$ called concatenation. If $f:X\rightarrow Y$ is some mapping, then this can be easily lifted to sets, i.e., $f:2^X\rightarrow 2^Y$ and $f^-:2^Y\rightarrow 2^X$ for the inverse.

We refrain from giving detailed definitions of standard terms in Formal Languages, but rather refer to any textbook from the area, in particular, to [2].

1.2 Semilinear Sets and Beyond

A Parikh mapping $\psi$ (or, more precisely, $\psi _\varSigma$) from ${\varSigma }^*$ into $\mathbb {N}^n$ is a mapping defined by first choosing an enumeration $a_1, \ldots , a_n$ of the elements of $\varSigma$ and then defining inductively $\psi (\lambda ) = (0,\ldots ,0)$, $\psi (a_i) = (\delta _{1,i},\ldots ,\delta _{n,i})$, where $\delta _{j,i} = 0$ if $i \ne j$ and $\delta _{j,i} = 1$ if $i = j$, and $\psi (au)=\psi (a)+\psi (u)$ for all $a\in \varSigma$, $u\in \varSigma ^*$. Clearly, $\psi :\varSigma ^*\rightarrow \mathbb {N}^n$ becomes thus a monoid morphism (where the operation on $\mathbb {N}^n$ is vector addition). Any two Parikh mappings from ${\varSigma }^*$ into $\mathbb {N}^n$ differ only by a permutation of the coordinates of $\mathbb {N}^n$. This is inessential when considering sets of multisets of letters, or, in other words, multiset languages. Hence, if $\mathcal {L}$ is some word language family, we can associate the Parikh set family $Ps \,\mathcal {L}$ to it. Also, we can express the commutative closure of some language $L\subseteq \varSigma ^*$ as $\psi ^-(\psi (L))$. In Proposition 1, we stated what is known about the Parikh images of the families in the Chomsky hierarchy. The equality $Ps \,\mathrm {REG}= Ps \,\mathrm {CF}$ is also known as Parikh’s Theorem, going back to [12], and the inequalities easily follow from separating examples $L_0,L_1\subsetneq \{a\}^*$ such that $L_0\in RE\setminus CS$ and $L_1\in \mathrm {CS}\setminus \mathrm {CF}$; we also refer to [9].

A subset $A \subseteq \mathbb {N}^n$ is said to be linear if there are $v, v_1, \ldots ,v_m \in \mathbb {N}^n$ such that

$$\begin{aligned} A = \{v + k_1v_1+k_2v_2+\cdots +k_mv_m \mid k_1,k_2,\ldots ,k_m \in \mathbb {N}\}. \end{aligned}$$

A subset $A \subseteq \mathbb {N}^n$ is said to be semilinear if it is a finite union of linear sets.

It is also well-known that $Ps \,\mathrm {REG}$ coincides with the family of semilinear sets.

Another important classical class of multiset languages is the one that can be seen as reachability sets of Petri nets. We are not going into details of the respective definitions, as there is a different perspective on this that is somehow more appropriate to us, namely matrix grammars with context-free core rules (without appearance checking); see [6]. It might be interesting to know that these macroset classes were also (independently) introduced from the viewpoint of modeling chemical-based computations; see [9, 17]. $\mathrm {MAT}(\mathrm {CF})$ ($\mathrm {MAT}(\mathrm {CF}-{\lambda })$, resp.) denotes the family of languages generated by matrix context-free grammars allowing (disallowing, resp.) erasing rules; see [2].

1.3 Insertion-Deletion Systems

We now give the basic definition of insertion-deletion systems, following [8, 14].

Definition 1

An insertion-deletion system is a construct $\gamma =(V,T,A,R)$, where V is an alphabet, $T \subseteq V$ is the terminal alphabet, A is a finite language over V, R is a finite set of triplets of the form $(u,\eta ,v)_{ins}$ or $(u,\delta ,v)_{del}$, where $(u,v) \in V^* \times V^*$, $\eta ,\delta \in V^+$.

The pair (u, v) is called the context, $\eta$ is called the insertion string, $\delta$ is called the deletion string and $x \in A$ is called an axiom. An insertion rule of the form $(u,\eta ,v)_{ins}$ means that the string $\eta$ is inserted between u and v. A deletion rule of the form $(u, \delta ,v)_{del}$ means that the string $\delta$ is deleted between u and v. Applying $(u, \eta ,v)_{ins}$ hence corresponds to the rewriting rule $uv \rightarrow u \eta v$, and $(u, \delta ,v)_{del}$ corresponds to the rewriting rule $u \delta v \rightarrow uv$. If $u=v=\lambda$ for a rule, then the corresponding insertion/deletion can be done freely anywhere in the string and is called context-free insertion/deletion and is discussed in [11]. If $|u\eta v|=1$, we speak of strict context-free insertion, and similarly of strict context-free deletion if $|u\delta v|=1$. For simplicity, we write $(\eta )_{ins}$ for context-free insertion rules $(\lambda ,\eta ,\lambda )_{ins}$, and similarly for deletion rules. Consequently, for $x,y \in V^*$ we write $x \Rightarrow y$ if y can be obtained from x by using either an insertion rule or a deletion rule.

For an ins-del system, the descriptional complexity measures are based on the size comprising of (i) the maximal length of the insertion string, denoted by n, (ii) the maximal length of the left context and right context used in insertion rules, denoted by $i'$ and $i''$, respectively, (iii) the maximal length of the deletion string, denoted by m, (iv) the maximal length of the left context and right context used in deletion rules denoted by $j'$ and $j''$, respectively. The size of an ins-del system is denoted by $(n,i',i'';m,j',j'')$. For more details, we refer to [19].

1.4 Matrix Insertion-Deletion Systems

A matrix insertion-deletion system [4, 10, 13] is a construct $\varGamma =(V, T,A, R)$ where V is an alphabet, $T \subseteq V$, A is a finite language over V, R is a finite set of matrices $\{r_1, r_2, \ldots r_l\}$, where each $r_i$, $1 \le i \le l$, is a matrix of the form

$$\begin{aligned} r_i= [(u_1, \alpha _1, v_1)_{t_1}, (u_2, \alpha _2, v_2)_{t_2}, \ldots ,(u_k,\alpha _k, v_k)_{t_k}] \end{aligned}$$

with $t_j \in \{ins,del\}$, $1\le j\le k$. For $1 \le j \le k$, the triple $(u_j, \alpha _j, v_j)_{t_j}$ is an ins-del rule. Consequently, for $x,y \in V^*$ we write $x \Longrightarrow _{r_i} y$ if y can be obtained from x by applying all the rules of a matrix $r_i,~1 \le i \le l$, in order.

By $w \Longrightarrow _{*} z$, we denote the relation $w \Longrightarrow _{r_{i_1}} w_1 \Longrightarrow _{r_{i_2}} \ldots \Longrightarrow _{r_{i_k}} z$, where for all $j,~1 \le j \le k$, we have $1 \le i_j \le l$. The language generated by $\varGamma$ is defined as $L(\varGamma )= \{w \in T^* \mid x \Longrightarrow _{*} w,~\mathrm{for~some}~x \in A \}$. If a matrix ins-del system has at most k rules in a matrix and the size of the underlying ins-del system is $(n,i',i'';m,j',j'')$, then we denote the corresponding class of languages by $\mathrm {MAT}(k;n,i',i'';m,j',j'')$. In the special case when $k=2$, the system is said to have binary matrices. In [4], it is shown that the family of languages $\mathrm {MAT}(k;n,i',i';m,j',j')$ is closed under reversal (i.e., $\mathrm {MAT}(k;n,i',i'';m,j',j'') = [\mathrm {MAT}(k;n,i'',i';m,j'',j')]^R$).

Regarding computational completeness of the systems, it is shown in [4, 5, 13] that the following matrix ins-del systems are computationally complete: $\mathrm {MAT}(3; 1,1,0;1,1,0)$, $\mathrm {MAT}(3;1,1,0;1,0,1)$, $\mathrm {MAT}(2;1,1,0;2,0,0)$, $\mathrm {MAT}(2; 2,0,0; 1,1,0)$, $\mathrm {MAT}(2;1,0,1;2,0,0)$, $\mathrm {MAT}(2;2,0,0;1,0,1)$, $\mathrm {MAT}(3;1,0,1;1,0,1)$, $\mathrm {MAT}(3; 1,0, 1; 1,1,0)$, $\mathrm {MAT}(3;1,1,1;1,0,0)$, $\mathrm {MAT}(2;1,1,1;1,0,1)$ and $\mathrm {MAT}(4;1,0,0;1,1,1)$.

In this paper, we are interested in Parikh images of these language classes, denoted as $Ps \,\mathrm {MAT}(k;n,i',i'';m,j',j'')$. We now discuss a few examples of matrix ins-del system. Later, they are used in the proofs of some theorems.

Example 1

The language $L_{1}=\{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$ can be generated by a matrix Ins-del system of size (2; 1, 0, 0; 0, 0, 0) as follows. $\varGamma _1=(\{a,b\},\{a,b\},\{ \lambda \}, \{[(a)_{ins},(b)_{ins}]\} )$. It is easy to see that $L(\varGamma _1)=L_1$. Note that $L_1$ is a non-regular language and cannot be generated by (matrix) ins-del system of size (1; 1, 0, 0; 1, 0, 0). It can be argued that any matrix ins-del system $\varGamma$ of size (1; 1, 0, 0; 1, 0, 0) must contain an insertion-only matrix, and this can be applied to some axiom $\omega \in L_1$ of $\varGamma$ to produce a word that is not in $L_1$.

The commutative closure of $L_1$ equals $L_1$ itself. In other words, $\psi ^-(\psi (L_1))=L_1$. However, if we modify $\varGamma _1$ a bit by changing the axiom set to $\{ab\}$, then this new system $\varGamma _1'$ describes a strict subset of $L_1$ whose commutative closure equals $L_1\setminus \{\lambda \}$, with $ba\in (L_1\setminus \{\lambda \})\setminus L(\varGamma '_1)$.   $\square$

Remark 1

$L_1=\{w \in \{a,b\}^* \mid |w|_a = |w|_b \} \notin \mathrm {MAT}(1;1,0,0;1,0,0)$.

Proof

For the sake of contradiction, let us assume that $\varGamma '_1$ is a matrix ins-del system of size (1; 1, 0, 0; 1, 0, 0) such that $L(\varGamma '_1)=L_1$. Consider a word $w\in L_1$ that is longer than any axiom of $\varGamma '_1$. Hence, at some point of the derivation of w, either a terminal symbol a (or a terminal symbol b, resp.) was inserted by using a matrix $[(a)_{ins}]$ (or $[(b)_{ins}]$, resp.). If we skip this mentioned insertion, say, by applying $[(a)_{ins}]$, in the derivation, but keep all other derivation steps, then the finally derived string will have an unequal number of occurrences of a and b, a contradiction to $L(\varGamma '_1)=L_1$. More precisely, the derivation of w from an axiom $\omega$ can be described by a sequence of matrices $m_1,\dots ,m_\ell$, such that

$$\begin{aligned} \omega \Rightarrow _{m_1}w_1\Rightarrow _{m_2}w_2\Rightarrow \dots \Rightarrow _{m_\ell }w_\ell =w\,. \end{aligned}$$

Now assume that $m_i=[(a)_{ins}]$ was causing the last insertion of an a in this sequence. Then,

$$\begin{aligned} \omega \Rightarrow _{m_1}w_1\Rightarrow _{m_2}w_2\Rightarrow \dots \Rightarrow _{m_{i-1}}w_{i-1}\Rightarrow _{m_{i+1}}w_{i+1}'\Rightarrow \dots \Rightarrow _{m_\ell } w_\ell ' \end{aligned}$$

is also a valid derivation according to $\varGamma _1'$ where, for all $j>i$, $w_j=u_jav_j$ but $w_j'=u_jv_j$. In particular, $w_\ell '$ satisfies $\#_a w_\ell '=\#_aw_\ell -1$ and $\#_b w_\ell '=\#_b w_\ell$; hence $\#_a w_\ell '<\#_b w_\ell '=\#_b w=\#_aw$.    $\square$

Example 2

Hopcroft and Pansiot [7] described a so-called vector addition system with states that generates the non-semilinear language $L_2=\{w\in T^*\mid |w|_b+|w|_c\le 2^{|w|_a}\}$. Only a little scrutiny is needed to translate this mechanism into some MAT(3; 1, 0, 0; 1, 0, 0) system $\varGamma _2$. The axiom of $\varGamma _2$ is Ac. We take the following rules into $\varGamma _2$: $[(A)_{del},(c)_{del},(A')_{ins}]$, $[(A')_{del},(b)_{ins},(A)_{ins}]$, $[(A)_{del},(B)_{ins}]$, $[(B)_{del},(b)_{del},(B')_{ins}]$, $[(B')_{del},(c)_{ins},(B'')_{ins}]$, $[(B'')_{del},(c)_{ins}, (B)_{ins})$, $[(B)_{del},(a)_{ins},(A)_{ins}]$, $[(A)_{del}]$. Lemma 2.8 in [7] shows that, with terminal alphabet $T=\{a,b,c\}$, this system generates $L_2$.    $\square$

2 Preparatory Results

From earlier findings [4] on $\mathrm {MAT}(k;n,i',i'';m,j',j'')$ and its mirror image, we can immediately conclude the following, as the Parikh image of the mirror image of a language L equals the Parikh image of L.

Theorem 1

For all non-negative integers $k,n,i',i'',m,j,j''$, we have that

$$\begin{aligned} Ps \,\mathrm {MAT}(k;n,i',i'';m,j',j'') = Ps \,\mathrm {MAT}(k;n,i'',i';m,j'',j') \,. \end{aligned}$$

This allows us to summarize the known computational completeness results of matrix ins-del systems of small weights [4, 13] as follows:

Theorem 2

(i) $Ps \,\mathrm {RE}= Ps \,\mathrm {MAT}(3;1,1,1;1,0,0)= Ps \,\mathrm {MAT}(4;1,0,0;1,1,1)$.

(ii) Let $i'+i''\ge 1$ and $j'+j''\ge 1$. Then, $Ps \,\mathrm {RE}= Ps \,\mathrm {MAT}(3;1,i',i'';1,j',j'')$.

(iii) Let $n+m\ge 3$, $\min (n,m)\ge 1$, $n+i'+i''\ge 2$, $m+j'+j''\ge 2$, as well as $i'+i''+j'+j''\ge 1$. Then, $Ps \,\mathrm {RE}= Ps \,\mathrm {MAT}(2;n,i',i'';m,j',j'')$.

Recall that $Ps \,\mathcal {L}$ is a class of macrosets if $\mathcal {L}$ is a class of languages, as a language $L\in \mathcal {L}$ is mapped to a set of vectors $\psi (L)$. Clearly, one can also reverse this process and consider the language $\psi ^-(\psi (L))\supseteq L$. Accordingly, we can form the language class $Ps ^-( Ps \,\mathcal {L})$. In general, the relation between $\mathcal {L}$ and $Ps ^-( Ps \,\mathcal {L})$ is unclear. However, for matrix ins-del systems, we can show the following.

Theorem 3

Let $k\ge 2$, $n\ge 1$, $i',i''\ge 0$, $m\ge 1$, $j',j''\ge 0$. Then,

$$\begin{aligned} Ps ^-( Ps \,\mathrm {MAT}(k;n,i',i'';m,j',j''))\subsetneq \mathrm {MAT}(k;n,i',i'';m,j',j''). \end{aligned}$$

In other words, we claim that nearly all the language families that are considered in this paper are closed under commutative closure. It would be interesting to get a complete picture about for which values of $n,i',i'',m,j',j''$ the language families $\mathrm {MAT}(1;n,i',i'';m,j',j'')$ are closed under commutative closure and for which not. The following proof only works for $k\ge 2$.

Proof

Let $\varGamma =(V,T,A,R)$ be some matrix ins-del system of size $(k;n,i',i''; m,j',j'')$. Let $V'=\{a'\mid a\in V\}$ be the set of primed versions of symbols from V. Consider $\varGamma '=(V\cup V',T,A,R\cup R')$, where $R'=\{[(a)_{del},(a')_{ins}], [(a')_{del},(a)_{ins}]\}$. Then, $L(\varGamma ')=\psi _T^-(\psi _T(L(\varGamma )))$. Hence, there is a matrix ins-del system of the required size to describe the commutative closure of $L(\varGamma )$. The claimed strictness of the inclusion follows with Example 1.    $\square$

3 Languages in $Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)$ are semilinear

Consider some matrix ins-del system $\varGamma$ containing binary matrices only, with context-free insertion rules and context-free deletion rules.

First, we claim that we can assume that, without loss of generality, a derivation of some word $w\in L(\varGamma )$ can be decomposed into three phases that work in the following order:

• 1. matrices containing two insertion rules are used;

• 2. matrices containing one insertion and one deletion rule (mixed type) are used;

• 3. only deletion rules are used.

Namely, a derivation of some $w\in L(\varGamma )$ that does not obey this order can be re-ordered by first moving the insertion-only matrices to the beginning (their applicability does not depend on the prior application of any other matrix) and then moving all deletion-only matrices to the end, leaving in particular the relative order of the matrices containing one insertion and one deletion rule.

Based on this observation, we are proving a normal form lemma that is useful to show the main result of this section.

Lemma 1

Let $L\in \mathrm {MAT}(2;1,0,0;1,0,0)$. Then, there is a matrix ins-del system $\varGamma '$ of size (2; 1, 0, 0; 1, 0, 0) with $L(\varGamma ')=L$ satisfying the following properties.

• 1. $\varGamma '$ contains no matrices of mixed type.

• 2. $[(a)_{ins},(b)_{ins}]$ is a matrix of $\varGamma '$ if and only if $[(b)_{ins},(a)_{ins}]$ is a matrix of $\varGamma '$.

• 3. $[(a)_{del},(b)_{del}]$ is a matrix of $\varGamma '$ if and only if $[(b)_{del},(a)_{del}]$ is a matrix of $\varGamma '$.

• 4. $\varGamma '$ contains no matrices of the form $[(a)_{del}]$.

• 5. If $w\in L$ can be obtained in $\varGamma '$ by exclusively using deletion-only matrices, then w is an axiom of $\varGamma '$.

Proof

Let a matrix ins-del system $\varGamma =(V,T,A,R)$ of size (2; 1, 0, 0; 1, 0, 0) with $L(\varGamma )=L$ be given. We are describing how to transform $\varGamma$ in order to satisfy the claimed normal form.

Let $R_{mixed}$ collect all matrices of R that are of mixed type. Let $V'=\{a'\mid a\in V\}$ be a collection of new symbols, primed variants of the original alphabet. W.l.o.g., matrices in $R_{mixed}$ contain first a deletion rule and then an insertion rule. Notice that the only case when $[(b)_{ins},(a)_{del}]$ is applicable but not $[(a)_{del},(b)_{ins}]$ is when $a=b$ and there is no symbol a in the current sentential form. However, as the matrix $[(b)_{ins},(a)_{del}]$ has no effect if $a=b$ and there is no symbol a in the current sentential form, we can neglect this in the following. Matrices in $R_{mixed}$ of the form $[(a)_{del},(b)_{ins}]$ are replaced by the two matrices $(i)~[(a')_{ins},(b)_{ins}]$ (insertion-only matrix) and $(ii)~[(a)_{del},(a')_{del}]$ (deletion-only matrix). We collect all these matrices in $R_{mixed}'$. Let $V_1=V\cup V'$, $A_1=A$, $R_1=(R\setminus R_{mixed})\cup R_{mixed}'$ and $\varGamma _1=(V_1,T,A_1,R_1)$. $\varGamma _1$ contains no matrices of mixed type by construction. We will now argue that $L=L(\varGamma _1)$. (i) ‘$\subseteq$’: We only have to bother about the simulation of matrices of mixed type. Now, an application of $[(a)_{del},(b)_{ins}]$ can clearly be simulated by first applying $[(a')_{ins},(b)_{ins}]$ and then applying $[(a)_{del},(a')_{del}]$.

(ii) ‘$\supseteq$’: As argued above, we can assume that the derivation of some word $w\in L(\varGamma _1)$ first applies insertion-only matrices and then deletion-only matrices. Clearly, the sequence of insertion-only matrices that are applied and also the sequence of deletion-only matrices that are applied can be in any order without affecting the fact that w can be generated this way. Let us therefore take the following ordering. First, we apply insertion-only matrices from $R\setminus R_{mixed}$ (in any order). Secondly, we apply insertion-only matrices from $R_{mixed}'$ (in an order that we describe below). Thirdly, we apply deletion-only matrices from $R_{mixed}'$ (in an order that we describe below). Finally, we apply deletion-only matrices from $R\setminus R_{mixed}$ (in any order). Trivially, with $\varGamma$ we can simulate all matrices from $R\setminus R_{mixed}$. So, we only discuss matrices from $R_{mixed}'$ in the following. Now, observe in order to finally generate $w\in T^*$, for each insertion-only matrix from $R_{mixed}'$ that introduces some symbol $a'$, there must be one deletion-only matrix from $R_{mixed}'$ that deletes such an occurrence of $a'$ again. Let us fix an arbitrary ordering < on $V_1$. This can be used to define an ordering $<_R$ on $R_{mixed}'$ as follows. First, all insertion-only matrices are situated; these are ordered according to $[(a')_{ins},(b)_{ins}]<_R [(c')_{ins},(d)_{ins}]$ if $a'<c'$ or $a'=c'$ and $b<d$. Then, all deletion-only matrices are situated; these are ordered according to $[(a)_{del},(a')_{del}]<_R [(c)_{del},(c')_{del}]$ if $c'<a'$. Now observe that this implies that right in the middle, an application of some matrix $[(a')_{ins},(b)_{ins}]$ is immediately followed by an application of $[(a)_{del},(a')_{del}]$. These two matrix applications could be easily simulated by the matrix $[(a)_{del},(b)_{ins}]$ contained in $R_{mixed}$. Now consider the insertion-only matrix $[(c')_{ins},(d)_{ins}]$ that was applied before $[(a')_{ins},(b)_{ins}]$ (if there is no such matrix, our inductive argument is complete). If $a\ne d$, then we could clearly simulate the sequence of matrix applications of $[(c')_{ins},(d)_{ins}]$, $[(a')_{ins},(b)_{ins}]$, $[(a)_{del},(a')_{del}]$ and $[(c)_{del},(c')_{del}]$ by first applying $[(a)_{del},(b)_{ins}]$ and then $[(c)_{del},(d)_{ins}]$. If $a= d$, the simulation should be carried out by first applying $[(c)_{del},(a)_{ins}]$ and then $[(a)_{del},(b)_{ins}]$. By induction, we can see by this argument that we can simulate the whole sequence of matrix applications from $R_{mixed}'$ by using matrices from $R_{mixed}$. This shows that $w\in L(\varGamma )$.

Let $V_2=V_1$, $A_2=A_1$. $R_2=R_1\cup \{[(a)_{ins},(b)_{ins}] \mid [(b)_{ins},(a)_{ins}]\in R_1\}$. Let $\varGamma _2=(V_2,T,A_2,R_2)$. $\varGamma _2$ satisfies the first two properties. It can be easily seen that $L(\varGamma _1)=L(\varGamma _2)$.

Let $V_3=V_1$, $A_3=A_1$. $R_3=R_2\cup \{[(a)_{del},(b)_{del}] \mid [(b)_{del},(a)_{del}]\in R_1\}$. Let $\varGamma _3=(V_3,T,A_3,R_3)$. $\varGamma _3$ satisfies the first three properties. It can be easily seen that $L(\varGamma _2)=L(\varGamma _3)$.

Let $R_{del}=\{[(a)_{del}]\mid a\in V_1\}\cap R_3$. Let $\varGamma _{del}=(V_3,V_3,A_3,R_{del})$. Let $A_4=L(\varGamma _{del})$. Notice that $A_4$ is a finite language, with $A_4\subseteq L(\varGamma _3)$. Let $R_{del}'=\{[(b)_{ins}]\mid [(a)_{del}]\in R_{del}\wedge [(a)_{ins},(b)_{ins}]\in R_3\}$. Let $R_4=(R_3\setminus R_{del})\cup R_{del}'$. Let $V_4=V_1$ and $\varGamma _4=(V_4,T,A_4,R_4)$. $\varGamma _4$ satisfies the first four properties. We now show that $L(\varGamma _4)=L(\varGamma _3)$. Let $w\in L(\varGamma _4)$. This is certified by some derivation, starting from some axiom $\omega \in A_4$. If $\omega \notin A_3$, then we can obtain $\omega$ from $A_3$ by using rules from $R_{del}\subseteq R_3$. By construction, rules $[(b)_{ins}]$ from $R_{del}'$ can be simulated by first applying a matrix $[(a)_{ins},(b)_{ins}]\in R_3$ and then applying the matrix $[(a)_{del}]\in R_{del}$. As other matrices can be directly carried out within $\varGamma _3$, $w\in L(\varGamma _3)$ follows. Conversely, if $w\in L(\varGamma _3)$, then we can assume that all matrices from $R_{del}$ are executed at the end, except those applications that delete symbols from the axiom $\omega \in A_3$; these are carried out first. So, we could simulate the derivation of w in $\varGamma _4$ by starting from an axiom $\omega '$ that is obtained from $\omega$ by rules from $R_{del}$. The remaining applications of matrices $[(a)_{del}]$ from $R_{del}$ are obviously applied to symbols that have been introduced by insertion-only matrices, say, $[(a)_{ins},(b)_{ins}]$ followed by $[(a)_{del}]$. This can be simulated by a rule $[(b)_{ins}]$ from $R_{del}'$. Hence, $w\in L(\varGamma _4)$.

Finally, let $R_{del2}$ collect all deletion-only matrices of $R_4$ and define $A'=L((V_4,V_4,A_4,R_{del2}))$. Again, $A'$ is a finite subset of $L(\varGamma _4)$. Moreover, with $V'=V_4$, $R'=R_4$, one can see that $\varGamma '=(V',T,A',R')$ satisfies all claims of this lemma.    $\square$

We are going to use this normal form lemma in the proof of the following main theorem of this section.

Theorem 4

$Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)\subseteq Ps \,\mathrm {REG}$.

Proof

Let $\varGamma =(V,T,A,R)$ be a matrix ins-del system of size (2; 1, 0, 0; 1, 0, 0) that satisfies the previous normal form lemma. Notice that we can further assume that $|A|=1$, because it is known that $Ps \,\mathrm {REG}$ is closed under (finite) union. So, let $A=\{\omega \}$. We are going to define a right-linear grammar $G=(N,T,S,P)$ such that $\psi _T(L(G))=\psi _T(L(\varGamma ))$.

We define

$$\begin{aligned} N=\{S\}\cup \{S\langle v\rangle \mid v\in V^{\le \max (|\omega |,2)} \}\,. \end{aligned}$$

The idea is to memorize in the nonterminal $S\langle v\rangle$ those symbols that still have to be inserted, as we already started deletion-only matrices in our simulating derivation, stopping half-way in their simulation.

The axiom $\omega$ is dealt with using the rules

$$\begin{aligned} P_{axiom}=\{S\rightarrow wS\langle v\rangle \mid w\in T^*\wedge \exists u\in V^{\le |\omega |}:\psi _V(uw)=\psi _V(\omega )\wedge uv\Longrightarrow _*^{del}\lambda \}\,. \end{aligned}$$

Here, we use $\Longrightarrow _*^{del}$ to denote the application of deletion-only matrices from $\varGamma$ (but no insertion-only matrices are applied). In other words, upon executing $S\rightarrow wS\langle v\rangle$, we guessed that some symbols (namely those listed in u) have been already deleted from $\omega$ by applying |u| many deletion-only matrices half-way. The not yet applied rules are memorized in the string v. These symbols have yet to be generated by insertion-only matrices. Recall that due to our normal form, we can assume that no deletion-only matrix is applied to $\omega$ alone.

Then, we enter a phase to simulate the insertion-only matrices.

The simulation of an insertion-only matrix works in a way similar to the construction of the axiom word $\omega$. All the simulation rules are collected in $P_{simul}$. Let us first consider the simpler case when $[(a)_{ins}]$ has to be simulated. To capture the case that a is not again deleted, which is only possible if $a\in T$, we introduce the rules $S\langle v\rangle \rightarrow aS\langle v\rangle$ for all v. If a is going to be deleted by applying some $[(a)_{del},(b)_{del}]\in R$, we capture this by two types of rules. If b occurs in v, say, $v=xby$, then $S\langle v\rangle \rightarrow S\langle xy\rangle$ is added to $P_{simul}$. If b does not occur in v and if $|v|<\max (|\omega |,2)$, then $S\langle v\rangle \rightarrow S\langle vb\rangle$ is added to $P_{simul}$.

The simulation of $m=[(a)_{ins},(a')_{ins}]$ is more complicated yet similar. We have three cases to consider (as also $m'=[(a')_{ins},(a)_{ins}]\in R$: (i) none of a and $a'$ are later deleted, (ii) only a is later deleted, or (iii) both a and $a'$ are later deleted. Let us consider these cases in details in the following.

In case (i), we know that $aa'\in T^*$. Hence, we can add the rules $S\langle v\rangle \rightarrow aa'S\langle v\rangle$ for all v.

In case (ii), $a'\in T$ is known. Assume that a is going to be deleted by applying some $[(a)_{del},(b)_{del}]\in R$. We have two subcases. If b occurs in v, say, $v=xby$, then $S\langle v\rangle \rightarrow a'S\langle xy\rangle$ is added to $P_{simul}$. If b does not occur in v and if $|v|<\max (|\omega |,2)$, then $S\langle v\rangle \rightarrow a'S\langle vb\rangle$ is added to $P_{simul}$.

In case (iii), we assume that a is going to be deleted by applying some $[(a)_{del},(b)_{del}]\in R$ and that $a'$ is going to be deleted by applying some matrix $[(a')_{del},(b')_{del}]\in R$. We have four subcases. (iii.a) If b and $b'$ occur in v, say, $v=xbyb'z$, then $S\langle v\rangle \rightarrow S\langle xyz\rangle$ is added to $P_{simul}$. (iii.b) If b occurs in v, but $b'$ does not occur in v, say, $v=xby$, then $S\langle v\rangle \rightarrow S\langle xyb'\rangle$ is added to $P_{simul}$. (iii.c) If $b'$ occurs in v, but b does not occur in v, this can be treated symmetrically. (iii.d) If neither b nor $b'$ occur in v and if $|v|+1<\max (|\omega |,2)$, then $S\langle v\rangle \rightarrow S\langle vbb'\rangle$ is added to $P_{simul}$.

The termination is only accomplished via the rule $S\langle \lambda \rangle \rightarrow \lambda$. So, in total $P=P_{axiom}\cup P_{simul}\cup \{S\langle \lambda \rangle \rightarrow \lambda \}$.

The main point to understand the simulation is that whenever we apply an insertion-only matrix that generates a symbol that will be finally deleted, we can afford storing the possibly existing second symbol that is going to be deleted by the mentioned deletion-only matrix, because we can assume (w.l.o.g.) that the next insertion-only matrix that is applied provides exactly the symbol that has to be deleted next. So, the amount of information that needs to be stored in nonterminals is finite.    $\square$

However, the reverse inclusion of the previous result seems not clear and remains as an open problem.

4 Beyond Semilinearity

In this section, we first define a notation which is often used in stating results in the remainder of this paper.

$$\begin{aligned} Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)=\bigcup _{k\ge 1} Ps \,\mathrm {MAT}(k;1,0,0;1,0,0)\,.\end{aligned}$$

Together with Theorem 4, we can conclude the following hierarchy result.

Corollary 1

For any $k\ge 3$, we find the following hierarchy of strictly context-free matrix ins-del systems:

$$\begin{aligned} Ps \,\mathrm {MAT}(1;1,0,0;1,0,0)&\subsetneq Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)\\&\subsetneq Ps \,\mathrm {MAT}(3;1,0,0;1,0,0)\\&= Ps \,\mathrm {MAT}(k;1,0,0;1,0,0) \end{aligned}$$

Proof

The first strict inclusion follows from Example 1, as $\mathrm {MAT}(1;1,0,0;1,0,0)$ can be viewed as ins-del systems of size (1, 0, 0; 1, 0, 0) without any matrix control (see also Remark 1). The second strict inclusion is due to the fact that there are non-semilinear context-free matrix languages, also refer Example 2.    $\square$

Theorem 5

$Ps \,\mathrm {MAT}(3;1,0,0;1,0,0)= Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)$ and

$Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)= Ps \,\mathrm {MAT}(\mathrm {CF})$.

Proof

First, we are going to simulate a context-free matrix grammar $G=(N,T,S,M)$ in binary normal form, potentially with erasing rules; see [2]. This means that the nonterminal alphabet N is partitioned into $N_1\cup N_2\cup \{S\}$, and all matrices $m\in M$ are of the form $m=[p\rightarrow q,X\rightarrow w]$, where $p\in N_1$, $q\in N_1\cup \{\lambda \}$, $X\in N_2$, $w\in (N_2\cup T)^*$, except the start rules, which take the form $S\rightarrow pX$ for some $p\in N_1$ and $X\in N_2$, collected in a singleton matrix. Moreover, we can assume that $[p\rightarrow \lambda ,X\rightarrow w]$ only occurs when $w=\lambda$. We put all pX with matrices $[S\rightarrow pX]\in M$ into the set of axioms A of the matrix ins-del system $\varGamma =(V,T,A,R)$ that we are going to describe. The alphabet V will contain $T\cup N_1\cup N_2$ plus several auxiliary new nonterminals whose sole purpose is to guide the application sequence of the matrices. Our description will make clear that $\psi _T(L(G))=\psi _T(L(\varGamma ))$ as required.

For the simulation itself, we consider several cases of matrices $m\in M$.

• If $m=[p\rightarrow \lambda ,X\rightarrow \lambda ]$, then we can simply interpret m as a matrix $m' =[(p)_{del},(X)_{del}]$ containing two deletion rules and put $m'$ into R.

• If $m=[p\rightarrow q, X\rightarrow \lambda ]$ with $p,q\in N_1$, we can simulate this with the following ins-del matrix $m'=[(p)_{del},(q)_{ins},(X)_{del}]$: Again, we adjoin $m'$ to R.

• If $m=[p\rightarrow q, X\rightarrow w]$ with $p,q\in N_1$ and $|w|\ge 1$, say, $w=a_1\cdots a_n$, $n=|w|$, $a_i\in (N_2\cup T)$, we can simulate this with the following ins-del matrices m[x], where x is a prefix of w:

  $$\begin{aligned} m[w]= & {} [(p)_{del},~(q[w])_{ins},~(X)_{del}]\\ m[x]= & {} [(q[xa])_{del},~(q[x])_{ins},~(a)_{ins}] \end{aligned}$$

  if xa is a prefix of w; we identify $q[\lambda ]$ and q. Now, we adjoin all these matrices m[x] to R.

• No other matrices belong to R.

Notice that whenever we can transform a string x to y using some matrix m, then the suggested matrices $m'$ (or m[x]) can be used to obtain a string $y'$ from x such that $\psi _{V}(y)=\psi _V(y')$. By induction, the claim follows from these observations.

The converse direction is detailed in the long version. The basic idea is to introduce a new nonterminal Z and also to work with pseudo-terminals (i.e., nonterminals $a'$ for each terminal a). A deletion rule can be directly interpreted as an erasing rule, while an insertion rule is simulated by a rule of the form $Z\rightarrow ZX'$.    $\square$

As the reachability problem for Petri nets (without inhibitor arcs) is decidable, the membership problem is decidable for $Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)$. This also implies that the inclusion $Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)\subsetneq Ps \,\mathrm {RE}$ is strict. Recall the many computationally complete matrix ins-del systems that we listed in Theorem 2.

We are now discussing the simulation of context-free matrix via matrix ins-del systems explained above. If we allow the insertion of two symbols at once, we can in fact (easily) reduce the lengths of the matrices by one except for the matrix that simulates an erasing rule. Namely, instead of inserting two symbols one after the other, we can do this now with just one rule. If we add on matrices like $[(X)_{del},~(X)_{ins}]$ for any symbol X, we can also make sure that, whenever two symbols are to be deleted in some matrix of length three, then this can be simulated by deleting two symbols next to each other with one rule. This observation allows us to state:

Corollary 2

$Ps \,\mathrm {MAT}(\mathrm {CF})\subseteq Ps \,\mathrm {MAT}(2;2,0,0;2,0,0)$.

Whether or not the converse inclusion is true is open. The problem is that we would have to check whether two symbols in intermediate sentential forms sit next to each other; this seems to be impossible with context-free matrix grammars without appearance checking.

The previous corollary also shows the strictness of one of the following two inclusions; it is however unclear which is strict.

$$\begin{aligned} Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)\subseteq & {} Ps \,\mathrm {MAT}(2;2,0,0;1,0,0)\\ {}\subseteq & {} Ps \,\mathrm {MAT}(2;2,0,0;2,0,0) \end{aligned}$$

A similar situation arises with:

$$\begin{aligned} Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)\subseteq & {} Ps \,\mathrm {MAT}(2;1,0,0;2,0,0)\\ {}\subseteq & {} Ps \,\mathrm {MAT}(2;2,0,0;2,0,0) \end{aligned}$$

It is known that ins-del systems of size (2, 0, 0; 2, 0, 0) strictly contain context-free languages only [18]. So, $Ps \, \mathrm {MAT}(1,2,0,0;2,0,0) \subseteq Ps \, \mathrm {CF}$. Thus, we see:

Corollary 3

$Ps \,\mathrm {MAT}(1;2,0,0;2,0,0) \subsetneq Ps \,\mathrm {MAT}(3;1,0,0;1,0,0)$.

The following result strengthens the previous argument.

Theorem 6

$\bigcup _{k\ge 1,n\ge 1} Ps \,\mathrm {MAT}(k;n,0,0;1,0,0)= Ps \,\mathrm {MAT}(\mathrm {CF})\,.$

Proof

The inclusion $\supseteq$ follows with Theorem 5. Conversely, notice that we can always replace an insertion rule $(x)_{ins}$, with $x=a_1\cdots a_\nu$ being a word of length $1<\nu \le n$, by the following sequence of insertions (considered as a sub-matrix of the matrix originally containing r): $[(a_1)_{ins},\dots ,(a_\nu )_{ins}].$ This does not change the Parikh image of the generated language, as deletions are performed only on single symbols. Doing this repeatedly, we can transform any matrix ins-del system $\varGamma$ of size $(*;n,0,0;1,0,0)$ (with terminal alphabet T) into a matrix ins-del system $\varGamma '$ of size $(*;*,0,0;1,0,0)$ such that $\psi _T(\varGamma )=\psi _T(\varGamma ')$. This shows that $Ps \,\mathrm {MAT}(*;n,0,0;1,0,0)\subseteq Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)$. Applying Theorem 5 once more proves the claim.    $\square$

Focusing on binary matrices, it is however unclear if the inclusion

$$\begin{aligned} \bigcup _{n\ge 1} Ps \,\mathrm {MAT}(2;n,0,0;1,0,0)\subseteq Ps \,\mathrm {MAT}(\mathrm {CF}) \end{aligned}$$

is strict or not. Similar open problems arise with the following chain of inclusions:

$$\begin{aligned} Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)\subseteq & {} Ps \,\mathrm {MAT}(2;1,1,0;1,0,0)\\ {}= & {} Ps \,\mathrm {MAT}(2;1,0,1;1,0,0)\\ {}\subseteq & {} Ps \,\mathrm {MAT}(2;1,1,1;1,0,0)\\ {}\subseteq & {} Ps \,\mathrm {MAT}(2;1,1,1;1,0,1) \end{aligned}$$

As $Ps \,\mathrm {MAT}(2;1,1,1;1,0,1)= Ps \,\mathrm {RE}$ (see [5] for $\mathrm {RE}=\mathrm {MAT}(2;1,1,1;1,0,1)$), one of these inclusions must be strict. For the equality, we use Theorem 1.

Similarly, we can reason about systems with bigger deletion complexity.

Theorem 7

$\bigcup _{k\ge 1,m\ge 1} Ps \,\mathrm {MAT}(k;1,0,0;m,0,0)= Ps \,\mathrm {MAT}(\mathrm {CF})\,.$

Proof

The inclusion $\supseteq$ follows with Theorem 5. Conversely, notice that we can always replace a deletion rule $(x)_{del}$, with $x=a_1\cdots a_\mu$, $\mu \le m$, being a word of length $\mu >1$, by the following sequence of deletions (considered as a sub-matrix of the matrix originally containing r): $[(a_1)_{del},\dots ,(a_\mu )_{del}].$ This does not change the Parikh image of the generated language, as insertions are performed only on single symbols. Doing this repeatedly, we can transform any matrix ins-del system $\varGamma$ of size $(*;1,0,0;m,0,0)$ (with terminal alphabet T) into a matrix ins-del system $\varGamma '$ of size $(*;1,0,0;1,0,0)$ such that $\psi _T(\varGamma )=\psi _T(\varGamma ')$. This shows that $Ps \,\mathrm {MAT}(*;1,0,0;m,0,0)\subseteq Ps \,\mathrm {MAT}(*;1,0,0;1,0,0)$. Applying Theorem 5 once more proves the claim.    $\square$

5 Monotonicity Conditions

With matrix ins-del systems, it is at least possible to define a condition that ensures some kind of monotonicity. For simplicity, we define this concept for strict context-free matrix ins-del systems only. So, such a system is called monotone if no axiom equals the empty word (this prevents the system from generating the empty word at all, but according to usual convention in formal languages, this does not matter) and each matrix $[(x_1)_{\mu _1},\dots ,(x_r)_{\mu _r}]$ obeys:

$$\begin{aligned} \sum _{i=1}^r |x_i|\cdot [\mu _i=ins] \ge \sum _{i=1}^r |x_i|\cdot [\mu _i=del] \end{aligned}$$

where [cond] is the usual interpretation of a logical condition cond to yield 1 if it is true and 0 otherwise. We indicate this by adding $mon$ as a subscript.

Theorem 8

$\mathrm {CS}=\mathrm {MAT}_{mon}(2;3,0,0;3,0,0)$.

Note that possible corollaries for $\mathrm {RE}$ are superseded by results from [11].

For the proof of the next characterization theorem, the following normal form comes in handy. A strict context-free matrix ins-del system $\varGamma$ is said to be in deletion first normal form if in every matrix, all deletion rules precede all insertion rules. (This covers, of course, the extreme cases when a matrix contains only deletion rules or only insertion rules, as well.)

Lemma 2

To every strict context-free matrix ins-del system $\varGamma$, there exists a strict context-free matrix ins-del system $\varGamma '$ in deletion first normal form such that $L(\varGamma )=L(\varGamma ')$.

Theorem 9

$Ps \,\mathrm {MAT}(\mathrm {CF}-\lambda )$ can be characterized by monotone systems. Hence, $Ps \,\mathrm {MAT}(\mathrm {CF}-\lambda )= Ps \,\mathrm {MAT}_{mon}(*;1,0,0;1,0,0)= Ps \,\mathrm {MAT}_{mon}(4;1,0,0;1,0,0)$.

Let us indicate our simulations in the following. A rule $A\rightarrow w$, with $w=a_1\cdots a_j$, in a context-free matrix grammar $G=(N,T,S,P)$ can be simulated by the sequence $(A)_{del},(a_1)_{ins},\dots ,(a_j)_{ins}$ of deletion and insertion rules, which is monotone. This idea can be combined with that from Theorem 5 to show the complete simulation. For the reverse direction, we simulate a strict context-free monotone matrix ins-del system $\varGamma =(V,T,A,R)$ in deletion first normal form.

Remark 2

It is sufficient that either all insertion or all deletion rules are strict context-free. The other rules could be just context-free ; compare Theorems 6 and 7 for the non-monotone case.

Corollary 4

The class of Parikh images of languages generated by monotone strict context-free matrix ins-del systems is a strict subclass of the class of Parikh images of languages generated by monotone context-free matrix ins-del systems.

Theorem 10

$Ps \,\mathrm {MAT}_{mon}(1;1,0,0;0,0,0)= Ps \,\mathrm {MAT}_{mon}(1;1,0,0;1,0,0)\subsetneq Ps \,\mathrm {MAT}_{mon}(2;1,0,0;1,0,0)\subsetneq Ps \,\mathrm {MAT}_{mon}(3;1,0,0;1,0,0)= Ps \, \mathrm {REG}$ .

6 Conclusions

In this paper, we have considered results associated with Parikh images of languages generated by matrix ins-del systems, especially, of small sizes. We show that $Ps \,\mathrm {MAT}(2;1,0,0;1,0,0)$ contains only semilinear languages. Besides, $Ps \,\mathrm {MAT}(3;1,0,0;1,0,0)$ contains non-semilinear languages and we have shown that this family of languages and the family of languages $Ps \,\mathrm {MAT}(\mathrm {CF})$ are the same. We often dealt with binary matrices (matrices of length at most two) with context-free insertion and deletion rules. We have analyzed the characterization of the hierarchy of family of languages that is formed with these small sizes. For many classes of languages, proving the strict inclusion is left open. To the best of our knowledge, the question whether or not the inclusion $Ps \,\mathrm {MAT}(\mathrm {CF}-\lambda )\subseteq Ps \,\mathrm {MAT}(\mathrm {CF})$ is strict is also an (old) open problem, see [2], that obviously relates to the systems that we investigated.

Apart from ins-del systems where no deletions take place at all (as in Example 1), it is unclear if we get somehow context-sensitive languages only. In the context of our paper, we want to finally recall that $\mathrm {MAT}(1;2,2,2;0,0,0)$ contains non-semilinear languages, see [14, Theorem 6.5].

Let us point out once more the many open problems that we listed throughout the paper, concerning whether or not some inclusions between language classes are strict. Notice that in some of these cases, the upper bounds on the inclusion chains were mostly given by computational completeness results for the corresponding classes of word languages. It might well be that a more genuine approach to multiset languages could yield better upper bounds. For the related area of graph-controlled insertion-deletion systems, such an attempt has been undertaken in [3]. It might be also an idea to try to simulate Petri nets with inhibitor arcs in order to prove the strictness of some of the inclusions. The limits of such an approach are discussed in [15].