# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 4 Conclusions  
Our results complement the results that were obtained in the long versions of [6; 7]. In particular, in these papers we have shown that extending ordinary ins-del systems with substitution rules yields, in most cases, an increase in computational power. In some cases, this increase can be quite significant. To give an overview, the main characterization results for RE and for CS of [6] and [7] have been, as follows.  
\begin{tabular}{c c c c} \multicolumn{3}{c}{**Previous Result**} & \multicolumn{3}{c}{**Extended with Substitution**} \\ \hline Size & Family & Size & Family \\ \hline \((2,0,0;2,0,0)\) & \(\subset\) CF & \((2,0,0;2,0,0;1,0)\) & \(=\) RE \\ \hline \((1,0,0;1,0,0)\) & \(\subset\) REG & \((1,0,0;1,0,0;1,1)\) & \(=\) RE \\ \hline \((1,0,0;0,0,0)\) & \(\subset\) REG & \((1,0,0;0,0,0;1,1)\) & \(=\) CS \\ \hline \((1,0,1;1,0,0)\) & \(\subset\) RE & \((1,0,1;1,0,0;1,0)\) & \(=\) RE \\ \hline \end{tabular}  
The incompleteness results of systems without substitution rules can be found in [19] ([Th. 3.5] and [Th. 4.2]) and [24] [Th. 7], respectively.  
We remark that deletion rules are essential for computational completeness results, as we have shown that, even with the addition of substitution rules, systems that do not have deletion rules lack computational power beyond CS. Furthermore, we have shown that \(\text{INS}_{n}^{0,0}\text{DEL}_{m}^{0,0}=\text{INS}_{n}^{0,0}\text{DEL}_{m}^{0,0 }\text{SUB}^{0,0}\), i.e., ins-del-sub systems require some context information; otherwise, substitution rules do not offer any benefits in regards to the size complexity of those systems.  
We have shown that matrix ins-del systems do not need much context to reach computational completeness if substitution rules and appearance checking are used. For instance, we have shown that, in this setting, no context other than single symbol context for deletion rules is necessary for computational completeness. In the case of no context other than single symbol context for insertion rules, we have shown that appearance checking is a necessary and sufficient feature for ensuring computational completeness. Notice that the term \"appearance checking\" might, indeed, be a bit misleading, as it usually applies to checking the non-applicability of certain rules. Because we (always) test for the absence of single symbols, it might be better to formalize or interpret our results in the context of (forbidden) random context [25; 26; 27; 28; 29], or, more generally speaking, to semi-conditional (matrix) grammars. So-called _generalized forbidding matrix grammars_ (GFM) have been presented at ICMC 2020 (the corresponding paper will appear in the Springer LNCSvolume 12687 of CMC21) and cover the idea of associating tests for the absence of symbols (or even words) as a filter prior to applying a matrix. The mentioned paper uses (more traditional) context-free rules within the matrices. In a sense, the results of our paper could also be seen as initializing the study of generalized forbidding matrix ins-del-sub systems. Subsequently, also studies on random context with respect to ins-del systems are also interesting for comparison, see [30; 31]. Another interpretation could be in terms of ordered variants of matrix ins-del-sub systems, a topic so far explored only in connection with context-free grammars [32], because ordered grammars and forbidden context grammars mostly coincide, also see [12; 33; 34]. To provide an overview, our completeness results are collected in the following table.  
\[\