# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### One-Sided Context Dependence
#### 3.2.2 Computational Incompleteness
By construction, it is clear that only (the rightmost letter of) root labels contribute letters to the final word, i.e., each tree contributes, at most, one letter to the final word. Furthermore, it is clear that there is no interaction between letters of two different trees, i.e., a letter belonging to certain tree is not a context for some operation on a letter of another tree. Before explaining the weaknesses of matrix ins-del-sub systems with their size limited to \((*;1,0,0;1,1,0;0,0)\), we illustrate their power by presenting a concrete example. **Example 3**. : _Consider a matrix ins-del-sub system MID\({}_{\xi}\) of size \((*;1,0,0;1,1,0;0,0)\), which has the axiom \(X_{1}X_{2}\). Let_  
\[m_{1} =[(\lambda,b,\lambda)_{\text{ins}},(b,X_{1},\lambda)_{\text{dd}}, (\lambda,X_{3},\lambda)_{\text{ins}}]\] \[m_{2} =[(\lambda,b,\lambda)_{\text{ins}},(b,X_{2},\lambda)_{\text{dd}}, (\lambda,X_{a},\lambda)_{\text{ins}}]\] \[m_{3} =[(\lambda,X_{a}\to a,\lambda),(\lambda,a,\lambda)_{\text{ins}},(a,X_{3},\lambda)_{\text{dd}}]\]  
_be matrices of MID\({}_{\xi}\). Clearly \(X_{1}X_{2}\stackrel{{\rightharpoonup}}{{\Longrightarrow}}_{m_{1}m _{2}m_{3}}\) bab holds and the corresponding group of trees is_  
\[ \begin{array}{cccc}b&X_{a}a&b\\,&\cdot&\cdot&\cdot\\ X_{1}&X_{3}&X_{2}.\end{array} \]  
_Note that all of the letters corresponding to the eventual a-tree originate from context-free insertions. Furthermore, because there is no interaction between letters of two different trees, inserting all letters of the eventual a-tree (in the order specified by the a-tree) left or right of all letters belonging to eventual b-trees does not affect the b-trees. Thus, \(X_{1}X_{2}\stackrel{{\rightharpoonup}}{{\Longrightarrow}}_{m_{1}m _{2}m_{3}}\)abb and \(X_{1}X_{2}\stackrel{{\rightharpoonup}}{{\Longrightarrow}}_{m_{1}m _{2}m_{3}}\) bba also hold._  
**Theorem 5**. : \(REG\setminus MAT_{*}INS_{1}^{0,0}DEL_{1}^{1,0}SUB^{0,0}\
eq\emptyset\)_._  
Proof. : We show that there is no matrix ins-del-sub system of size \((1,0,0;1,1,0;0,0)\) generating the regular language \(a^{+}b^{+}\). Assume to the contrary that \(MID_{\xi}=(V,T,A,M_{\xi})\) generates \(a^{+}b^{+}\). Subsequently, \(MID_{\xi}\) generates the word \(a^{\pi}b^{\pi}\), \(n>\gamma\), as well, where \(\gamma\) is the length of the longest axiom of \(MID_{\xi}\). Consider the group of trees corresponding to a derivation of \(a^{\pi}b^{\pi}\) starting from the axiom \(\alpha\). Because \(n>\gamma\), there exists a tree \(t\) with the following properties: (1) the tree contributes a letter \(a\) to \(a^{\pi}b^{\pi}\) and (2) all nodes of the tree originate from the application of some insertion rule. Consider the derivation from  
Figure 4: The tree group following the application of \((a,X,\lambda)_{\text{del}}\). Figure 5: The tree group following the application of \((\lambda,Y\to b,\lambda)\). \(\alpha\) to \(a^{n}b^{n}\). Subsequently, \(MID_{\zeta}\) also generates \(a^{n-1}b^{n}a\). The string \(a^{n-1}b^{n}a\) is generated by applying the same matrices used in the derivation from \(\alpha\) to \(a^{n}b^{n}\) in the same order. All of the insertion rules corresponding to nodes of the tree \(t\) that are specified above are applied right of all letters belonging to (eventual) \(b\)-trees. Because there is no interaction between letters of two different trees, none of the letters that correspond to nodes of \(t\) are used as context to delete symbols not affiliated with nodes of \(t\). Thus, inserting these letters right of all letters belonging to (eventual) \(b\)-trees changes nothing for the other trees. Note that the tree \(t\) specifies the position of the inserted letters in relation to each other as well as how the rest of the rules concerning symbols of \(t\) are applied.