# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Adding Substitutions  
With substitution rules, we now introduce the central notion of this paper. We define substitution rules to be of the form \((u,a\to b,v)\); \(u,v\in V^{*}\); \(a,b\in V\). Let \(w_{1}uwv_{2}\); \(w_{1},w_{2}\in V^{*}\) be a string over \(V\). Afterwards, applying the substitution rule \((u,a\to b,v)\) allows us to substitute a single letter \(a\) with another letter \(b\) in the context of \(u\) and \(v\), which results in the string \(w_{1}uww_{2}\). Formally, we define an _insertion-deletion-substitution system_, or _ins-del-sub system_ for short, to be specified by a six-tuple \(\mathit{ID}_{\zeta}=(V,T,A,I,D,S)\), where \(V,T,A,I\), and \(D\) are defined as in the case of usual ins-del systems and \(S\) is a set of substitution rules. Let \(x=w_{1}uwv_{2}\) and \(y=w_{1}ubvw_{2}\) be the strings over \(V\). The substitution rules define a relation \(\Longrightarrow_{\text{sub}}\), as follows: \(x\Longrightarrow_{\text{sub}}y\) if there is a substitution rule \((u,a\to b,v)\). In the context of ins-del-sub systems, we write \(\Longrightarrow\) to denote any of the relations \(\Longrightarrow_{\text{ins}}\), \(\Longrightarrow_{\text{del}}\) or \(\Longrightarrow_{\text{sub}}\). We define \(\Longrightarrow^{*}\) and \(\Longrightarrow^{+}\) as usual, denoting the reflexive-transitive and transitive closure of \(\Longrightarrow\), respectively. The language that is generated by an ins-del-sub system \(\mathit{ID}_{\zeta}\) is defined as  
\[L(\mathit{ID}_{\zeta})=\left\{w\in T^{*}\mid\alpha\stackrel{{ \Longrightarrow}}{{\longrightarrow}}^{*}w,\;\alpha\in A\right\}.\]  
Figure 1: Marking corresponding to a derivation of _abac_[14; 19]. As with usual ins-del system, we measure the complexity of an ins-del-sub system \(ID_{\xi}=(V,T,A,I,D,S)\) via its _size_, which is, an eight-tuple \((n,m,m^{\prime};p,q,q^{\prime};r,r^{\prime})\), where \(n,m,m^{\prime},p,q\), and \(q^{\prime}\) are defined as in the case of usual ins-del systems and \(r\) and \(r^{\prime}\) limit the maximal length of the left and right context of a substitution rule, respectively, i.e., \(r=max\{|u|\mid(u,a\to b,v)\in S\}\), \(r^{\prime}=max\{|v|\mid(u,a\to b,v)\in S\}\). \(\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{p}^{q,q^{\prime}}\text{SUB}^{r,r^{ \prime}}\) denotes the family of all ins-del-sub systems of size \((n,m,m^{\prime};p,q,q^{\prime};r,r^{\prime})\) Note that as only one letter is replaced by any substitution rule, there is no subscript at SUB. Depending on the context, we also refer to the family of languages generated by ins-del-sub systems of size \((n,m,m^{\prime};p,q,q^{\prime};r,r^{\prime})\) by \(\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{p}^{q,q^{\prime}}\text{SUB}^{r,r^{ \prime}}\). As with ins-del systems, ins-del-sub systems can be regulated with matrix control introducing _matrix ins-del-sub systems_. A _matrix ins-del-sub system_ is a construct \(MID_{\xi}=(V,T,A,M_{\zeta})\), where \(V\), \(T\) and \(A\) are defined as in usual ins-del systems. \(M_{\zeta}=\{m_{1},\ldots,m_{t}\}\), \(t\geq 1\), is a finite set of sequences, called matrices, of the form \(m_{i}=[r_{i,1},\ldots,r_{i,k_{i}}]\), where \(k_{i}\geq 1\). \(r_{i,j}\), with \(1\leq i\leq t\), \(1\leq j\leq k_{i}\), is either an insertion, a deletion or a substitution rule. We define the relation between the strings \(w\) and \(w^{\prime}\) over \(V\)\(w\)\(\Longrightarrow\)\(m_{i}\)\(w^{\prime}\), as well as the generated language of \(MID_{\zeta}\), analogously to the case without substitution rules. We say that matrix ins-del-sub systems, which have insertion rules, deletion rules, substitution rules, and matrices of size \((n,m,m^{\prime})\),\((p,q,q^{\prime})\), \((r,r^{\prime})\), and \(k\), respectively, is of size \((k;n,m,m^{\prime};p,q,q^{\prime};r,r^{\prime})\).