# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Adding Appearance Checking
Replacing all the deletion rules of the form \((\lambda,ab,\lambda)\) in the matrices of the system constructed in Theorem 9 with deletion rules of the form \((a,b,\lambda)\) yields our claim. This result shows that appearance checking is indeed powerful, as we have previously seen that \(\text{MAT}_{*}\text{INS}_{1}^{0,0}\text{DELL}_{1}^{1,0}\text{SUB}^{0,0}\) does not even include all regular languages. Furthermore, we can conclude the following from this result. Theorem 11.: \(\text{MAT}_{*}^{ac}\text{INS}_{2}^{0,0}\text{DELL}_{2}^{0,0}=RE\)_._  
Proof. : All of the substitution rules occurring in matrices of the construction in Theorem 9 can be replaced, as specified in the proof of Theorem 6. Additionally, the following can be derived from [22], based on ideas on P systems. This is interesting, as P systems (also known as membrane systems, introduced in [23]) are another formalization of a bio-computing device, when considering a cell (abstractly viewed as a membrane structure) as a computing mechanism. An insertion-deletion P system is a construct \(\Pi=(O,T,\mu,M_{1},\ldots,M_{n},\)\(R_{1},\ldots,R_{n})\) where  
* \(O\) is a finite alphabet,
* \(T\subseteq O\) is the terminal alphabet,
* \(\mu\) is the tree structure of the system which has \(n\) nodes,
* \(M_{i},\)\(1\leq i\leq n,\) is a finite language associated to the membrane \(i\), and
* \(R_{i}\), \(1\leq i\leq n,\) is a set of insertion and deletion rules with target indicators of the node \(i\). The rules are of the form: \((u,x,v;\text{tar})\), where \((u,x,v)\) is an insertion rule or a deletion rule, and \(\text{tar}\in\{\text{here},\text{in}_{j},\text{out}\mid 1\leq j\leq n\}\). A configuration of \(\Pi\) is an \(n\)-tuple \((N_{1},\ldots,N_{n})\) of finite languages over \(O\). The transition between two configurations consists of applying rules in parallel to all possible strings, non-deterministically with respect to the target indications associated with the rules. A sequence of transitions between configurations of a given insertion-deletion P system \(\Pi\) starting from the initial configuration is called a computation with respect to \(\Pi\). The result of \(\Pi\)'s computations is collected in the language \(L(\Pi)\) that consists of all strings over \(T\) that are sent out of the root node during its computations. An insertion-deletion P system has the priority of deletion rules over insertion rules if a rule \((u_{1},x_{1},v_{1};\text{tar}_{1})\), where \((u_{1},x_{1},v_{1})\) is an insertion rule, is only allowed to be applied if no rule \((u_{2},x_{2},v_{2};\text{tar}_{2})\), where \((u_{2},x_{2},v_{2})\) is a deletion rule, is applicable. Theorem 12.: \(\text{MAT}_{*}^{ac}\text{INS}_{1}^{0,1}\text{DELL}_{1}^{0,0}=RE\)_._  
Proof. : Consider an insertion-deletion P system with the priority of deletion rules over insertion rules. It is known that such systems with insertion rules of size \((1,0,1)\) and deletion rules of size \((1,0,0)\) are computationally complete, see [22]. We now show that such an insertion-deletion P system with a priority of deletion rules over insertion rules can be simulated by an matrix ins-del system with the appearance checking of size \((*;1,0,1;1,0,0)\). Let \(\Pi=(O,T,\mu,M_{1},\ldots,M_{n},R_{1},\ldots,R_{n})\) be such a system. An equivalent matrix ins-del system with appearance checking \(\text{MID}_{\xi}=(O\cup\{1,\ldots,n\}\cup\{X\},T,A,M_{\zeta},F)\), where \(X\) is a trap symbol, is constructed, as follows. We define \(A=\{wi\mid w\in M_{i}\}\). For every deletion rule \((\lambda,x,\lambda;\text{tar})\in R_{i}\), we add a matrix \([(\lambda,i,\lambda)_{\text{del}},(\lambda,x,\lambda),(\lambda,k,\lambda)_{ \text{ins}}]\) to \(M_{\zeta}\), where \(k=i\) if \(\text{tar}=\text{here}\), \(k=j\) if \(\text{tar}=\text{in}_{j}\) and \(k=i^{\prime}\) if \(\text{tar}=\text{out}\) and \(i^{\prime}\) is the parent node of \(i\).