# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### One-Sided Substitutions  
We now consider matrix ins-del systems with one-sided substitution rules. In particular, the families of systems that are discussed in detail now are \(\text{MAT}_{2}\text{INS}^{0,0}_{1}\text{DEL}^{0,0}_{1}\text{SUB}^{1,0}\) and \(\text{MAT}_{2}\text{INS}^{0,0}_{1}\text{DEL}^{0,0}_{0}\text{SUB}^{1,0}\). Theorem 7: \(MAT_{*}\text{INS}^{1,0}_{1}\text{DEL}^{1,0}_{1}\subseteq MAT_{*}\text{INS}^{0,0 }_{1}\text{DEL}^{1,0}_{1}\text{SUB}^{1,0}_{1}\)_._Proof. : Let \(MID=(V,T,A,M)\in\text{MAT}_{*}\text{INS}_{1}^{1,0}\text{DEL}_{1}^{1,0}\). Subsequently, \(MID_{\xi}=(V^{\prime},T,A,M^{\prime})\) is defined as follows: Let \(V^{\prime}:=V\cup\{X\}\). Without a loss of generality, we assume \(V\cap\{X\}=\emptyset\). The following procedure is applied to all matrices of \(MID\). Consider an arbitrary matrix \(m\) of \(MID\). We replace every occurrence of an insertion rule of the form \((a,b,\lambda)\) with an insertion rule \((\lambda,X,\lambda)\) and a substitution rule \((a,X\to b,\lambda)\). Additionally, any deletion rule of the form \((a,b,\lambda)\) is replaced with a substitution rule \((a,b\to X,\lambda)\) and a deletion rule \((\lambda,X,\lambda)\). The matrix that is obtained by these replacements is added to \(M^{\prime}\). Clearly, \(MID_{\xi}\in\text{MAT}_{*}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{0,0}\text{ SUB}^{1,0}\). The basic idea of this proof is that the nonterminal \(X\) is immediately resolved after being introduced. It is easy to see that applying the substitution rule \((a,b\to X,\lambda)\) immediately after the insertion rule \((\lambda,X,\lambda)\) is essentially the same as applying a rule of the form \((a,b,\lambda)\). Likewise, applying the deletion rule \((\lambda,X,\lambda)\) immediately after the substitution rule \((a,b\to X,\lambda)\) is basically the same as applying the deletion rule \((a,b,\lambda)\). Therefore, clearly \(L(MID)=L(MID_{\xi})\). It has been shown in [10] that \(\text{MAT}_{3}\text{INS}_{1}^{1,0}\text{DEL}_{1}^{1,0}=\text{RE}\) holds. Therefore, \(\text{RE}=\text{MAT}_{*}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{0,0}\text{ SUB}^{1,0}\). We can improve this result by using the result that is presented in Theorem 3.2. Together with Lemma 1, the next corollary follows. Corollary 5.: \(RE=\text{MAT}_{2}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{0,0}\text{SUB}^{1,0}= \text{MAT}_{2}\text{INS}_{1}^{0,0}\text{DEL}_{1}^{0,0}\text{SUB}^{0,1}\)_._  
We now show that omitting deletion rules in the systems mentioned above yields a characterization of context-sensitive languages, which is quite rare with ins-del systems. Lemma 5.: \(\text{MAT}_{2}\text{INS}_{1}^{0,0}\text{DEL}_{0}^{0,0}\text{SUB}^{0,1}\subseteq CS\)__  
Proof. : Let \(MID=(V,T,A,M_{\zeta})\in\text{MAT}_{*}\text{INS}_{1}^{0,0}\text{DEL}_{0}^{0,0} \text{SUB}^{0,1}\) be constructed according to Theorem 3.2. The basic idea is the same as in Lemma 3. We define the matrix grammar \(G=(N,T,P,M)\) with \(N=\{N_{a}\mid a\in V\}\), as in Lemma 3.2 with the following addition: For every matrix of the form \([\lambda,b\to b^{\prime},a),(\lambda,c\to d,\lambda)]\) in \(M_{\zeta}\) we add a matrix of the form \([N_{b}N_{a}\to N_{b^{\prime}}N_{a},N_{c}\to N_{d}]\) to \(M\) (we remark that the second component of every matrix of \(MID\) is a context-free substitution rule). Clearly, \(G\) is a matrix grammar with context-sensitive production rules. In ([12] [Theorem 1.2.1]), it is shown that \(\mathcal{L}(\text{M},\text{CS})=L(\text{CS})\) holds. Therefore, our claim holds. We now prove the converse. Lemma 6.: \(CS\subseteq\text{MAT}_{2}\text{INS}_{1}^{0,0}\text{DEL}_{0}^{0,0}\text{ SUB}^{0,1}\)__  
Proof. : Let \(G=(V,T,S,P)\) be a context-sensitive grammar in Penttonen normal form [21]. Subsequently, we construct the following matrix ins-del-sub systems to simulate \(G\):  
\[MID_{\xi}=(V^{\prime},T,A,M_{\zeta})\]  
with \(V^{\prime}=V\cup\{X_{1},X_{2}\}\) and \(A=\{S\}\). Without a loss of generality, we assume \(V\cap\{X_{1},X_{2}\}=\emptyset\).