# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 1 Introduction  
Insertion-deletion systems, or ins-del systems for short, are well-established as computational devices and as a research topic within Formal Languages throughout the past nearly 30 years, starting off with the PhD thesis of [PERSON] [1]. Corresponding to the mismatched annealing of DNA sequences, both the insertion and deletion operations have a strong biological background, which led to their study in the molecular computing framework (cf. [2]). Insertion rules add a substring to a string, given a specified left and right context, while deletion rules remove a substring from a string, again taking a specified left and right context into consideration. The replacement of single letters (possibly within some context) by other letters by an operation, called _substitution_, is discussed in [3, 4], again from a bio-computing background.Interestingly, all of the theoretical studies on grammatical mechanisms involving insertions and deletions (except [5]) omitted, including the substitution operation in their studies. In [6, 7, 8], we started out a project to formally and systematically study insertion-deletion systems with substitutions as an additional operation, leading to ins-del-sub systems (for short). It can be argued that the potentially most error-prone part of a bio-computing implementation of ins-del-sub systems are context checks concerning the site where the operation (be it an insertion, a deletion or a substitution operation) may be applied. Therefore, it is interesting to study how much context dependency is necessary for achieving computational completeness, given the ability to add a substring of length \(n\) and to delete a substring of length \(p\). Conversely, assuming that one can prove that ins-del-sub systems with limited context checks exist that can simulate arbitrary Turing machines (or phrase structure grammars, or any arbitrary computational mechanism that can be used to define terms like _computability_), then this means that there is some hope that some day one could build computers that are no longer silicon-based, but that compute with RNA, DNA, or protein structures. It should be noted that all of our computational completeness proofs are constructive, which means that algorithms exist that will finally turn any program written in some high-level programming language of your choice into an ins-del-sub system that executes this program based on insertion, deletion, or substitution operations. As the following definitions will show, the 'derivation relation', although formally defined as a sequential series of insertion, deletion, or substitution operations, can be easily seen to allow an inherent parallelism, as all operations that are 'far enough' from each other can be executed in parallel. Because the potentially high degree of parallelism in bio-computing is argued as one of the main attractive features of this form of computation, this gives another reason as to why one should strive for operations that are as context-independent as possible, as context dependencies could be seen as semaphore-like synchronization points. Namely, on the level of bio-computing, checking certain strings means building up some structures (mostly proteins) that read and check'matching structures' by forming chemical links between molecules. This means that 'checking from one side' prevents and, hence, rules out 'checking from the other side' in parallel. Ins-del systems can be extended with some form of control to further reduce their context dependency. Matrix insertion-deletion systems, or matrix ins-del systems for short, were introduced in [9; 10]. These systems group insertion and deletion rules in sequences, called _matrices_; either the whole sequence of operations is applied consecutively, or no rule is applied at all, thus resembling traditional _matrix grammars_, originally introduced with a linguistic motivation [11].