# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Insertion-Deletion Systems  
An _insertion-deletion system_ (_ins-del system_ for short) is a five-tuple \(ID=(V,T,A,I,D)\), consisting of two alphabets \(V\) and \(T\) with \(T\subseteq V\), a finite language \(A\) over \(V\), a set of _insertion_ rules \(I\) and a set of _deletion_ rules \(D\). Both sets of rules are formally defined as sets of triples of the form \((u,a,v)\) with \(u,v\in V^{*}\) and \(a\in V^{+}\). We call elements occurring in \(T\)_terminal_ symbols, while referring to elements of \(V\setminus T\) as _nonterminals_. Elements of \(A\) are called _axioms_. Let \(w_{1}uvw_{2}\) and \(w_{1}uavw_{2}\), with \(w_{1},u,v,w_{2}\in V^{*}\), \(a\in V^{+}\), be strings. The application of an insertion rule \((u,a,v)\in I\) (also written \((u,a,v)_{\mathrm{ins}}\)) to \(w_{1}uvw_{2}\) corresponds to inserting the string \(a\in V^{*}\) between \(u\) and \(v\), which results in the string \(w_{1}uavw_{2}\). The application of a deletion rule \((u,a,v)\in D\) (also written \((u,a,v)_{\mathrm{del}}\)) to \(w_{1}uavw_{2}\) results in the removal of a substring \(a\) from the context \((u,v)\), which results in the string \(w_{1}uvw_{2}\). The relation \(\Longrightarrow\) is defined, as follows: Let \(x,y\in V^{*}\). Afterwards, we write \(x\Longrightarrow y\) iff \(y\) is the result of applying an insertion or deletion rule to \(x\). We write \(\Longrightarrow_{\mathrm{ins}}/\Longrightarrow_{\mathrm{del}}\) if \(y\) is obtained via an insertion/ a deletion rule. We denote, by \(\Longrightarrow^{+}\) and \(\Longrightarrow^{*}\), the transitive and the reflexive and transitive closure, respectively. The language that is generated by \(ID\) is defined by \(L(ID)=\{w\in T^{*}\mid\exists\alpha\in A:\alpha\Longrightarrow^{*}w\}\). Consider \((u,a,v)_{\mathrm{ins}}\) or \((u,a,v)_{\mathrm{del}}\). We refer to \(u\) as the left context and \(v\) as the right context of \((u,a,v)_{\mathrm{ins}}/(u,a,v)_{\mathrm{del}}\). A _sentiential form_ of \(ID\) is a string over \(V\). The _size_ of \(ID\) describes its complexity and it is defined by a vector \((n,m,m^{\prime};p,q,q^{\prime})\), where \(n=\max\{|a|\mid(u,a,v)\in I\}\), \(p=\max\{|a|\mid(u,a,v)\in D\}\), \(m=\max\{|u|\mid(u,a,v)\in I\}\), \(q=\max\{|u|\mid(u,a,v)\in D\}\), \(m^{\prime}=\max\{|v|\mid(u,a,v)\in I\}\) and \(q^{\prime}=\max\{|v|\mid(u,a,v)\in D\}\). By \(\mathrm{INS}_{n}^{m,m^{\prime}}\mathrm{DEL}_{p}^{q,q^{\prime}}\), we denote the family of all insertion-deletion systems of size \((n,m,m^{\prime};p,q,q^{\prime})\)[13; 14]. Depending on the context, we also denote the family of languages that can be generated by insertion-deletion systems of size \((n,m,m^{\prime};p,q,q^{\prime})\) by \(\mathrm{INS}_{n}^{m,m^{\prime}}\mathrm{DEL}_{p}^{q,q^{\prime}}\). We first study a concrete example now to clarify the definitions and also to return to some of the general discussions of the introduction. **Example 1**. : _Consider the following ins-del system \(ID=(V,T,A,I,D)\) where \(V=T=\{a,b,c\}\), \(A=\{acb\}\), \(I=\{(a,a,c),(c,b,b)\}\), and \(D=\{(\lambda,c,\lambda)\}\). Clearly this system is of size \((1,1,1;1,0,0)\) and the generated language is \(L(ID)=a^{+}b^{+}\cup a^{+}cb^{+}\)._  
_As mentioned in the introduction, ins-del systems offer a high degree of parallelism. The system ID, for instance, exhibits this trait when considering the rules \((a,a,c)\) and \((c,b,b)\). It is easy to see that the order in which these rules are applied is insignificant and, thus, these rules do not affect each other. Hence, \((a,a,c)\) and \((c,b,b)\) are \"far enough\" from each other to be applied in parallel without affecting the computation. However, note that the deletion rule \((\lambda,c,\lambda)\) cannot be applied in parallel with any insertion rule as the order does matter in this case.