# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Appearance Checking: An Additional Feature  
It is known that matrix grammars with context-free production are not computationally complete, but they can reach computational completeness if used with _appearance checking_. Transferring this idea to matrix ins-del-sub systems, we introduce matrix ins-del-sub systems with appearance checking and show that, similar to the matrix grammar case, formerly computationally incomplete matrix ins-del-sub systems can reach computational completeness if they are used in conjunction with appearance checking. We begin by defining matrix ins-del-sub systems and appearance checking. A matrix ins-del-sub systems and appearance checking is a tuple \(MID_{\zeta,ac}=(V,T,A,M_{\zeta},F)\), where \(V\), \(T\), \(A\), and \(M_{\zeta}\) are defined as in usual matrix ins-del-sub systems. \(F\) is a subset of all rules occurring in \(M_{\zeta}\). Let \(w_{1},w_{2}\in V^{*}\) and \(z\) be an arbitrary rule occurring in \(M_{\zeta}\). We define the relation \(\Longrightarrow\)\({}_{z}^{ac}\), as follows: \(w_{1}\)\(\Longrightarrow\)\({}_{z}^{ac}\) for one of the following conditions hold: (a) the rule \(z\) is applicable to \(w_{1}\), such that \(w_{1}\)\(\Longrightarrow\)\({}_{z}\)\(w_{2}\) or (b) the rule \(z\) is not applicable to \(w_{1}\), \(z\in F\) and \(w_{1}=w_{2}\). Basically, this means that, if some rule in \(F\) is not applicable, we can skip that rule. Let \(m=[r_{1},\ldots,r_{n}]\in M_{\zeta}\) and \(x,y\in V^{*}\). Then \(x\)\(\Longrightarrow\)\({}_{m}^{ac}\)\(y\) iff  
**Theorem 2**. : _For every \(\mathit{MID}_{\xi}\in\mathit{MAT}_{k}\mathit{INS}_{n}^{m,m^{\prime}}\mathit{DEL}_{p}^ {\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{ \mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{ \mathit{d}^{\mathit{d}}}}}}}}}}}}}}\mathit{\mathit{SUB}^{r,r^{\prime}}}\), \(p>0\), there is a system \(\mathit{MID}_{\xi}^{\prime}\in\mathit{MAT}_{2}\mathit{INS}_{n}^{m,m^{\prime}} \mathit{DEL}_{p}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d} ^{\mathit{d}^{\mathit{d}^{\mathit{d}^{\mathit{d}}}}}}}}}\mathit{SUB}^{r,r^{ \prime}}}\), such that \(L(\mathit{MID}_{\xi})=L(\mathit{MID}_{\zeta}^{\prime})\)._  
Proof. : Let \(\mathit{MID}_{\xi}=(V,T,A,M_{\zeta})\) and all matrices of \(\mathit{MID}_{\xi}\) be labelled in a one-to-one manner, i.e., a bijection from \(M_{\zeta}\) to a set of labels exists. Subsequently, we define \(\mathit{MID}_{\zeta}^{\prime}=(V^{\prime},T,A^{\prime},M_{\zeta}^{\prime})\), where \(V^{\prime}=V\cup\{(i,j)\mid i\) is the label of a matrix of \(\mathit{MID}_{\xi}\) and \(j\leq k\}\) and \(A^{\prime}=\{\alpha(i,1)\mid\alpha\in A\) and \(i\) is the label of a matrix of \(\mathit{MID}_{\xi}\}\cup\{\alpha\mid\alpha\in A\cap T^{*}\}\). Without a loss of generality we assume \(V\cap\{(i,j)\mid\quad i\) is the labelof a matrix of \(\mathit{MID}_{\xi}\) and \(j\leq k\}=\emptyset\). For every matrix \(m=[r_{1},r_{2},\ldots,r_{n}]\) of \(\mathit{MID}_{\xi}\), where \(r_{j}\), with \(j=1,\ldots,n\), is some insertion, deletion, or substitution rule and \(i\) is the label of \(m\), we add the following matrices  
\[[r_{1},(\lambda,(i,1)\to(i,2),\lambda)],\] \[[r_{2},(\lambda,(i,2)\to(i,3),\lambda)],\] \[\ldots,\] \[[r_{n-1},(\lambda,(i,n-1)\to(i,n),\lambda)]\text{ and }\] \[[r_{n},(\lambda,(i,n),\lambda)_{\text{del}}]\]  
to \(\mathit{MID}_{\xi}^{\prime}\). For every label \(i^{\prime}\) of some matrix of \(\mathit{MID}_{\xi}\) and every matrix \(m=[r_{1},r_{2},\ldots,r_{n}]\) of \(\mathit{MID}_{\xi}\), we add a matrix \([r_{n},(\lambda,(i,n)\to(i^{\prime},1),\lambda)]\) to \(\mathit{MID}_{\xi}^{\prime}\). By definition, the second component of every matrix of \(\mathit{MID}_{\xi}^{\prime}\) is either a context-free deletion rule of the form \((\lambda,(i,j),\lambda)_{\text{del}}\) or a context-free substitution rule of the form \((\lambda,(i,j)\to(i^{\prime},j^{\prime}),\lambda)\), where \(i\) and \(i^{\prime}\) are the labels of some matrices of \(\mathit{MID}_{\xi}\) and \(j,j^{\prime}\leq k\).