# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Combining Ideas: Matrix Insertion-Deletion Systems  
The idea of regulating ins-del systems with matrix control goes back to [10; 15]. A _matrix ins-del system_[10] is a construct \(MID=(V,T,A,M)\) where \(V\), \(T\) and \(A\) are defined as in usual ins-del systems. \(M=\{m_{1},\ldots,m_{t}\}\), \(t\geq 1\), is a finite set of sequences, called matrices, of the form \(m_{i}=[r_{i,1},\ldots,r_{i,k_{i}}]\), where \(k_{i}\geq 1\). \(r_{i,j}\), with \(1\leq i\leq t\), \(1\leq j\leq k_{i}\), is either an insertion or a deletion rule. A sentential form of \(MID\) is a string \(w\in V^{*}\). Consider a matrix \(m_{i}=[r_{i,1},\ldots,r_{i,k_{i}}]\). A transition \(w\Longrightarrow_{m_{i}}w^{\prime}\) is performed if there exist strings \(w_{1},\ldots,w_{k_{i}+1}\in V^{*}\) such that \(w_{j}\Longrightarrow_{r_{i,j}}w_{j+1}\) with \(w_{1}=w\) and \(w_{k_{i}+1}=w^{\prime}\). Let \(\Longrightarrow:=\bigcup_{m\in M}\Longrightarrow_{m}\). The language that is generated by \(MID\) is defined as  
\[L(MID)=\left\{w\in T^{*}\mid\exists\alpha\in A:\alpha\Longrightarrow^{*}w \right\}.\]  
We say that \(MID\) has _matrices of size \(k\)_ if \(k=\max_{1\leq i\leq l}k_{i}\). If \(MID\) is an ins-del system of size \((n,m,m^{\prime};p,q,q^{\prime})\) with matrices of size \(k\), we also say that \(MID\) is of size \((k;n,m,m^{\prime};p,q,q^{\prime})\). We denote by \(\text{MAT}_{k}\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{p}^{q,q^{\prime}}\) either the family of languages that are generated by ins-del systems of size \((k;n,m,m^{\prime};p,q,q^{\prime})\) or the family of ins-del systems of size \((k;n,m,m^{\prime};p,q,q^{\prime})\), depending on the context. Denote, by \(\text{MAT}_{*}\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{p}^{q,q^{\prime}}\text{ SUB}^{r,q^{\prime}}\), the family of matrix ins-del-sub systems with matrices of arbitrary size and insertion rules and deletion rules, of size \((n,m,m^{\prime})\) and \((p,q,q^{\prime})\), respectively. The following matrix ins-del systems are known to describe RE:  
* \(\text{MAT}_{3}\text{INS}_{1}^{1,1}\text{DEL}_{1}^{0,0}\) and \(\text{MAT}_{3}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{1,1}\)[16]
* \(\text{MAT}_{3}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{2,0}\), \(\text{MAT}_{3}\text{INS}_{2}^{0,0}\text{DEL}_{1}^{0,0}\) and \(\text{MAT}_{2}\text{INS}_{1}^{1,0}\text{DEL}_{1}^{1,0}\)[17]
* \(\text{MAT}_{3}\text{INS}_{1}^{1,0}\text{DEL}_{1}^{0,1}\), \(\text{MAT}_{2}\text{INS}_{1}^{1,0}\text{DEL}_{2}^{0,0}\) and \(\text{MAT}_{2}\text{INS}_{2}^{0,0}\text{DEL}_{1}^{1,0}\)[10]. The incompleteness results for matrix ins-del sub systems includeMAT\({}_{*}\text{INS}_{2}^{0,0}\text{DEL}_{2}^{0,0}\), for instance. More precisely, the following theorem holds. Theorem 1.: \(REG\setminus\text{MAT}_{*}\text{INS}_{2}^{0,0}\text{DEL}_{2}^{0,0}\
eq\emptyset\)_, testified by \(a^{*}b\)._  
This result follows from [18], as stated as in [10]. For reasons of completeness, we give a formal proof of this result in the following. Proof. : Before we begin with our proof, we introduce'markings' [14; 19] in the following paragraph. We explain the details of the marking approach with the following example. Consider the derivation  
\[\lambda \Longrightarrow_{\text{ins}}aA\Longrightarrow_{\text{ins}}aAaA \Longrightarrow_{\text{ins}}abCAaA\Longrightarrow_{\text{ins}}abDECAaA\] \[\Longrightarrow_{\text{del}}abDAaA\Longrightarrow_{\text{del}} abA\Longrightarrow_{\text{ins}}abaAbc\Longrightarrow_{\text{del}}abac\]  
of an ins-del system of size \((2,0,0,2,0,0)\). Then we introduce'markings', as follows: Two symbols that have been introduced together are joined with an overline, while two symbols that are deleted together are joined with an underline. The overlines and underlines mark the insertion pairs and the deletion pairs, respectively.