Insertion-deletion systems with substitutions I

Abstract

In this paper, we discuss the addition of substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems, i.e., in addition to insertions and deletions we allow single letter replacements to occur. We investigate the effect of the addition of substitution rules on the context dependency of such systems, thereby also obtaining new characterizations of and even normal forms for context-sensitive (CS) and recursively enumerable (RE) languages and their phrase-structure grammars. More specifically, we prove that for each RE language, there is a system generating this language that only inserts and deletes strings of length two without considering the context of the insertion or deletion site, but which may change symbols (by a substitution operation) by checking a single symbol to the left of the substitution site. When we allow checking left and right single-letter context in substitutions, even context-free insertions and deletions of single letters suffice to reach computational completeness. When allowing context-free insertions only, checking left and right single-letter context in substitutions gives a new characterization of CS. This clearly shows the power of this new type of rules.

Keywords

Computational completeness context-sensitive languages insertions deletions sustitutions

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 Lila Kari [11]. In fact, insertion alone has been studied before in [8].

Originating from the field of linguistics [16,20], ins-del systems also take inspiration from the field of molecular biology. Here, the insertion and deletion operation correspond to the mismatched annealing of DNA sequences [21]. When considering ins-del systems, one key question is how context-dependent are they, i.e., how much context information is (in-)sufficient for the operation of such systems to reach computational completeness, i.e., to characterize the class of recursively enumerable languages (RE), and how long are the strings they can insert or delete.

From their very beginning, papers highlighting the potential use of ins-del systems in modelling DNA computing also discussed the replacement of single letters (possibly within some context) by other letters, an operation called substitution in [3,12]. Interestingly, all theoretical studies on grammatical mechanisms involving insertions and deletions omitted including the substitution operation in their studies or have only considered them in a specific context. For instance in [6], substitution rules are only allowed to be applied at the beginning or end of a string. With this paper, we are stepping into this gap by studying more general ins-del systems with substitutions, or ins-del-sub systems for short. In particular we investigate which effect the addition of substitution rules have on the on such systems, that is when is the addition of substitution rules sufficient for ins-del systems to reach computational completeness and how much context-dependence is necessary to achieve this goal.

In this paper, which is an extended version of [28], published at Computability in Europe 2020, we put special emphasis on extending context-free ins-del systems with substitutions. We observe quite diverse effects, depending on whether the substitutions are context-free, one-sided or two-sided. We can also characterize the context-sensitive languages by extending context-free insertion systems with substitutions, which can be seen as a new normal form for monotone Chomsky grammars.

This paper is the first in a series of three papers. The second and third parts appeared as extended abstracts in two conferences [29,30]. Apart from the mentioned characterizations, in particular of the class of recursively enumerable languages, we also see (in this paper) a number of situations where context-free ins-del systems are insufficient to simulate Turing machines, even with substitution rules. There are two potential ways out: either we allow for enhanced context checks (as worked out in [29]) or we allow additional control, say, by designing small (sequential) ‘program fragments’ that prescribe how rules of the ins-del-sub system should be applied (see [30]). As indicated, these are exactly the two research directions that we follow in parts two and three of our study on ins-del-sub systems. Most of the material of these three papers can be also found in [27].

The present paper is structured as follows: In Section 2, we formally introduce the key notions of this paper. We also summarize what has been achieved concerning computational completeness (i.e., characerizations of RE) in terms of ins-del systems in Remark 1. Section 3 constitutes the main part of this work, proving the most important results. More specifically, first we prove that adding context-free substitutions does not change the computational power of ins-del systems, so that the results listed in Remark 1 also apply in such a situation. Then, we consider one-sided substitutions. We prove that for each RE language, there is a system generating this language that only inserts and deletes strings of length two without considering the context of the insertion or deletion site, but may change symbols (by a substitution operation) by checking a single symbol to the left of the substitution site. Notice that with context-free substitutions only, computational completeness cannot be reached. When we allow checking left and right single-letter context in substitutions, even context-free insertions and deletions of single letters suffice to reach computational completeness. When allowing context-free insertions only, checking left and right single-letter context in substitutions gives a new characterization of CS. This also gives the mentioned new normal form for monotone grammars characterizing CS. In the last section, we point to several questions that are left open in the theory of ins-del-sub systems with context-free insertions and deletions and briefly discuss the broader context.

2. Basic definitions and observations

We assume the reader to be familiar with the basics of formal language theory. In particular, an alphabet is a finite non-empty set, a language is a subset of the free monoid generated by a given alphabet, and λ denotes the neutral element of any free monoid. We denote by ⧢ the binary shuffle operation, which is defined as follows: let $x, y \in V^{*}$ , then $x ⧢ y : = {x_{1} y_{1} \dots x_{n} y_{n} ∣ x = x_{1} \dots x_{n}, y = y_{1} \dots y_{n} with x_{i}, y_{i} \in V^{*}, 1 ⩽ i ⩽ n}$ .

An ins-del system is a 5-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 $a, u, v \in V^{*}$ and $a \neq λ$ . We call elements occurring in T terminal symbols, while referring to elements of $V ∖ T$ as nonterminals. Elements of A are called axioms.

Let $w_{1} u v w_{2}$ , with $w_{1}, u, v, w_{2} \in V^{*}$ , be a string. Applying the insertion rule $(u, a, v) \in I$ inserts the string $a \in V^{*}$ between u and v, which results in the string $w_{1} u a v w_{2}$ .

The application of a deletion rule $(u, a, v) \in D$ results in the removal of an substring a from the context $(u, v)$ . More formally let $w_{1} u a v w_{2} \in V^{*}$ be a string. Then, applying $(u, a, v) \in D$ results in the string $w_{1} u v w_{2}$ .

We define the relation ⟹ as follows: Let $x, y \in V^{*}$ . Then we write $x ⟹_{ins} y$ if y can be obtained by applying an insertion or deletion rule to x. We also write ${(u, a, v)}_{ins}$ or ${(u, a, v)}_{del}$ to specify whether the applied rule has been an insertion or a deletion rule. Consider ${(u, a, v)}_{ins}$ or ${(u, a, v)}_{del}$ . Then we refer to u as the left context and to v as the right context of ${(u, a, v)}_{ins}$ / ${(u, a, v)}_{del}$ . If $u = v = λ$ , we call such a rule (in analogy to classical Chomsky grammars) context-free. If all rules are context-free then the whole system is called context-free.

Let $ID = (V, T, A, I, D)$ be an ins-del system. The language generated by $ID$ is defined by $\begin{matrix} L (ID) = {w \in T^{*} ∣ α ⟹^{*} w, α \in A} . \end{matrix}$ The size of $ID$ describes its descriptional complexity and is defined by a tuple $(n, m, m^{'}; p, q, q^{'})$ , where $\begin{matrix} n = max {| a | ∣ (u, a, v) \in I}, p = max {| a | ∣ (u, a, v) \in D} \\ m = max {| u | ∣ (u, a, v) \in I}, q = max {| u | ∣ (u, a, v) \in D} \\ m^{'} = max {| v | ∣ (u, a, v) \in I}, q^{'} = max {| v | ∣ (u, a, v) \in D} . \end{matrix}$ By ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}}$ we denote the family of all ins-del systems of size $(n, m, m^{'}; p, q, q^{'})$ [2,26]. Depending on the context, we also denote the family of languages characterized by ins-del systems of size $(n, m, m^{'}; p, q, q^{'})$ by ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}}$ . We call a family ${INS}_{n}^{0, 0} {DEL}_{p}^{0, 0}$ a family of context-free ins-del systems, while we call a family ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}}$ with $m + m^{'} > 0 \land m m^{'} = 0$ or $(q + q^{'} > 0 \land q q^{'} = 0)$ a family of one-sided ins-del systems. According to [2], an ins-del system ${ID}^{'} = (V \cup {$}, T, A^{'}, I^{'}, D^{'} \cup {(λ, $, λ)})$ of size $(n, m, m^{'}; p, q, q^{'})$ is said to be in normal form if

for any $(u, a, v) \in I^{'}$ , it holds that $| a | = n$ , $| u | = m$ and $| v | = m^{'}$ , and

for any $(u, a, v) \in D^{'}$ , it holds that $| a | = p$ , $| u | = q$ and $| v | = q^{'}$ .

Alhazov et al. [2,26] have shown the following auxiliary result:

Theorem 1.
For every ins-del system $ID$ , one can construct an insertion-deletion system ${ID}^{'}$ in normal form of the same size with $L ({ID}^{'}) = L (ID)$ .
Proof.
We sketch the construction. For an ins-del system $ID = (V, T, A, I, D)$ , an equivalent insertion-deletion system ${ID}^{'} = (V \cup {$}, T, A^{'}, I^{'}, D^{'} \cup {(λ, $, λ)})$ can be constructed with $\begin{array}{l} A^{'} = & {$^{i} w $^{t} $^{j} ∣ w \in A, i = max {m, q}, j = max {m^{'}, q^{'}}, t = max {p - | w |, 0}} \\ I^{'} = & {(z_{1}, a $^{k}, z_{2}) ∣ (u, a, v) \in I, z_{1} \in u ⧢ $^{}, | z_{1} | = m, z_{2} \in v ⧢ $^{}, | z_{2} | = m^{'}, k = n - | a |} \\ \cup {(z_{1}, $^{n}, z_{2}) ∣ z_{1} \in {({$} \cup V)}^{m}, z_{2} \in {({$} \cup V)}^{m^{'}}} \\ D^{'} = & {(z_{1}, d, z_{2}) ∣ (u, a, v) \in D, z_{1} \in u ⧢ $^{}, | z_{1} | = q, z_{2} \in v ⧢ $^{}, | z_{2} | = q^{'}, d \in a ⧢ $^{}, | d | = p} . \end{array}$ The basic idea is to introduce a new symbol $ ( $$ \notin V$ ) to act as a padding symbol to increase the length of the left (respectively, right) contexts of any rule $(u, a, v)$ , which does not fit the criteria, to meet the required size. Likewise, the padding symbol $ is also used to increase the length of any string that is inserted (respectively, deleted) by an insertion (respectively, a deletion) rule, to n (respectively, p).

Filling the axioms with the padding symbol $ ensures that rules of $I^{'}$ or $D^{'}$ are applicable, as applying any rule of $I^{'}$ or $D^{'}$ to any axiom $w^{'} \in A^{'}$ requires $w^{'}$ to have a minimum size of $m + m^{'}$ , in case of an insertion, or $p + q + q^{'}$ , in case of a deletion rule. Clearly ${ID}^{'}$ is of the same size as $ID$ . □

In the following sections, we use a modified normal form for ins-del systems of size $(1, 1, 1; 1, 1, 1)$ . Given an arbitrary ins-del system of size $(1, 1, 1; 1, 1, 1)$ , the construction of this modified normal form is as follows:
Construction 1.
Let* $ID = (V, T, A, I, D)$ be an ins-del system of size $(1, 1, 1; 1, 1, 1)$ . Without loss of generality, we assume ${$, X} \cap V = \emptyset$ and $$ \neq X$ . We construct ${ID}^{″} = (V \cup {$, X}, T, A^{″}, I^{″}, D^{″})$ as follows: $\begin{array}{l} A^{″} = & {X $ α $ X ∣ α \in A} \\ I^{″} = & {(z_{1}, s, z_{2}) ∣ (r, s, t) \in I, z_{1} = r if r \neq λ and z_{1} = $ otherwise, z_{2} = t if t \neq λ and z_{2} = $ otherwise} \\ \cup {(z_{1}, $, z_{2}) ∣ z_{1}, z_{2} \in ({$} \cup V)} \\ D^{″} = & {(z_{1}, a, z_{2}) ∣ (u, a, v) \in D, z_{1} = u if u \neq λ and z_{1} = $ otherwise, \\ z_{2} = v if v \neq λ and z_{2} = $ otherwise} \cup {(z_{1}, $, z_{2}) ∣ z_{1}, z_{2} \in ({$} \cup {X} \cup V)} \cup {(λ, X, λ)} \end{array}$

The basic idea of Construction 1 is the same as in the usual normal form constructions (see Theorem 1): the symbol $ is used as a padding symbol to ensure that the left and right contexts of all rules are of the required size. We can show that Construction 1 is equivalent to the usual normal form construction.
Theorem 2.
Let ${ID}^{'} = (V \cup {$}, T, A^{'}, I^{'}, D^{'} \cup {(λ, $, λ)})$ be an ins-del system of size $(1, 1, 1; 1, 1, 1)$ in normal form and ${ID}^{″} = (V \cup {$, X}, T, A^{″}, I^{″}, D^{″})$ be defined according to Construction 1 . Then, $L ({ID}^{'}) = L ({ID}^{″})$ .
Proof.
The nonterminals X introduced by the axioms of ${ID}^{″}$ must be deleted at some point of any derivation of ${ID}^{″}$ , as otherwise the derivation cannot yield a word consisting only of terminal symbols. It is easy to see that for any derivation of ${ID}^{″}$ leading to a word $w \in T^{}$ , there is an equivalent derivation to w, in which the last two rules to be applied are both ${(λ, X, λ)}_{del}$ . It is clear that we can therefore assume that the deletion of both symbols X are the last steps of any derivation of ${ID}^{″}$ . We remark that there is no insertion rule introducing a nonterminal X. Therefore, all X occurring during the derivation have been introduced via the axiom. Due to our assumption that both nonterminals X of the axiom will not be deleted until the very end, it is easy to see that all insertions and deletions of any derivation of ${ID}^{″}$ occur between these occurrences of nonterminal X.

We remark that $\begin{matrix} D^{'} = D^{″} ∖ ({(z_{1}, $, z_{2}) ∣ z_{1} \in ($ \cup X \cup V), z_{2} \in ($ \cup V \cup X)} \cup {(λ, X, λ)}) \end{matrix}$ and $I^{'} = I^{″}$ hold. Furthermore, $$ α $ \in A^{'}$ iff $X $ α $ X \in A^{″}$ holds.

Consider the set of deletion rules ${(z_{1}, $, z_{2}) ∣ z_{1} \in ($ \cup X \cup V), z_{2} \in ($ \cup V \cup X)}$ . Clearly this set of rules is essentially equivalent to a context-free deletions rule of the form $(λ, $, λ)$ as long as $ has arbitrary left and right context. Given our assumption that all occurrences of X are not deleted until the very end, this is always the case.

Therefore, it is easy to see that $$ α $ \underset{{ID}^{'}}{⟹} w^{'}$ iff $X $ α $ X \underset{{ID}^{″}}{⟹} X w^{'} X$ holds. □

Unlike the usual normal form construction, context-free deletions can only occur at the beginning and the end of a sentential form in the case of Construction 1. This fact will prove useful below.
Remark 1.
Ins-del systems have been extensively studied regarding the question if they can describe all of the recursively enumerable languages. We summarize these results first by listing the classes of languages known to be equal to RE: $\begin{array}{l} {INS}_{1}^{1, 1} {DEL}_{1}^{1, 1} [24], {INS}_{1}^{1, 1} {DEL}_{2}^{0, 0} [21, Theorem 6.3], {INS}_{3}^{0, 0} {DEL}_{2}^{0, 0} and {INS}_{2}^{0, 0} {DEL}_{3}^{0, 0} [17], \\ {INS}_{2}^{0, 0} {DEL}_{1}^{1, 1} and {INS}_{1}^{1, 0} {DEL}_{1}^{1, 2} [13], {INS}_{2}^{0, 1} {DEL}_{2}^{0, 0} and {INS}_{1}^{1, 2} {DEL}_{1}^{1, 0} [18], as well as {INS}_{1}^{2, 0} {DEL}_{1}^{0, 2} [14] . \end{array}$ By way of contrast, the following language families are known not to be equal to RE, the first one is even a subset of CF: ${INS}_{2}^{0, 0} {DEL}_{2}^{0, 0}$ [26], ${INS}_{1}^{1, 1} {DEL}_{1}^{1, 0}$ [18], ${INS}_{1}^{1, 0} {DEL}_{1}^{1, 1}$ [13], ${INS}_{1}^{1, 0} {DEL}_{2}^{0, 0}$ and ${INS}_{2}^{0, 0} {DEL}_{1}^{1, 0}$ [15].

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} u a v w_{2}$ ; $w_{1}, w_{2} \in V^{}$ be a string over V. Then 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, resulting in the string $w_{1} u b v w_{2}$ . Formally, we define an ins-del-sub system to be a 6-tuple ${ID}_{ς} = (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. Substitution rules define a relation $⟹_{sub}$ : Let $x = w_{1} u a v w_{2}$ and $y = w_{1} u b v w_{2}$ be strings over V. We write $x ⟹_{sub} y$ iff there is a substitution rule $(u, a \to b, v)$ . In the context of ins-del-sub systems, we write $\hat{⟹}$ to denote any of the relations $⟹_{ins}$ , $⟹_{del}$ or $⟹_{sub}$ . We define the closures ${\hat{⟹}}^{}$ and ${\hat{⟹}}^{+}$ as usual. The language generated by an ins-del-sub system ${ID}_{ς}$ is defined as $L ({ID}_{ς}) = {w \in T^{} ∣ α {\hat{⟹}}^{} w, α \in A}$ .

As with usual ins-del system, we measure the complexity of an ins-del-sub system ${ID}_{ς} = (V, T, A, I, D, S)$ via its size, which is defined as a tuple $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ , where n, m, $m^{'}$ , p, q and $q^{'}$ are defined as in the case of usual ins-del systems, while r and $r^{'}$ limit the maximal length of the left and right context of a substitution rule, respectively, i.e., $r = max {| u | ∣ (u, a \to b, v) \in S}$ , $r^{'} = max {| v | ∣ (u, a \to b, v) \in S}$ . ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}}$ denotes the family of all ins-del-sub systems of size $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ . Note that, as only one letter is replaced by any substitution rule, there is no subscript below $SUB$ . Depending on the context, we also refer to the family of languages generated by ins-del-sub systems of size $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ by ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}}$ . Expanding our previous terminology, we call substitution rules of the form $(λ, a \to b, λ)$ context-free, while substitution rules of the form $(u, a \to b, λ)$ or $(λ, a \to b, v)$ with $u \neq λ \neq v$ are called one-sided. Substitution rules of the form $(u, a \to b, v)$ with $u \neq λ \neq v$ are referred to as two-sided.

Let $^{R}$ be the reversal (mirror) operator. For a language L and its mirror $L^{R}$ the following lemma holds.
Lemma 1.
$L \in {INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}}$ iff* $L^{R} \in {INS}_{n}^{m^{'}, m} {DEL}_{p}^{q^{'}, q} {SUB}^{r^{'}, r}$ . □

We will now define the term resolve. Let ${ID}_{ς} = (V, T, A, I, D, S)$ be an ins-del-sub system. We say that a nonterminal X of ${ID}_{ς}$ is resolved if X is either deleted or substituted. The language generated by ${ID}_{ς}$ only contains words consisting of terminal symbols. Therefore, it is easy to see that in any terminal derivation of ${ID}_{ς}$ all occurring nonterminals must be resolved at some point of the derivation otherwise the derivation cannot yield a word consisting only of terminal symbols. We remark that a nonterminal X may be resolved by being substituted with a nonterminal Y, which in turn must be resolved.

As in the case of ins-del systems without substitution rules, we define a normal form for ins-del-sub systems. An ins-del-sub system $\begin{matrix} {ID}_{ς} = (V \cup {$}, T, A, I, D \cup {(λ, $, λ)}, S) \end{matrix}$ of size $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ is said to be in normal form if

for any $(u, a, v) \in I$ , it holds that $| a | = n$ , $| u | = m$ and $| v | = m^{'}$ ;

for any $(u, a, v) \in D$ , it holds that $| a | = p$ , $| u | = q$ and $| v | = q^{'}$ ;

for any $(u, a \to b, v) \in S$ , it holds that $| u | = r$ and $| v | = r^{'}$ .
Theorem 3.
For every ins-del-sub system ${ID}_{ς}$ of size $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ , one can construct an ins-del-sub system ${ID}_{ς}^{'}$ of the same size in normal form, with $L ({ID}_{ς}^{'}) = L ({ID}_{ς})$ .
Proof.
Let ${ID}_{ς} = (V, T, A, I, D, S)$ be an ins-del-sub system of size $(n, m, m^{'}; p, q, q^{'}; r, r^{'})$ . The basic idea is similar to the normal form construction for ins-del systems in [2,26]. In fact, the sets of insertion and deletion rules of ${ID}_{ς}^{'} = (V \cup {$}, T, A^{'}, I^{'}, D^{'} \cup {(λ, $, λ)}, S^{'})$ are constructed as in the ins-del system normal form construction. $S^{'}$ and $A^{'}$ are defined as follows: $\begin{array}{l} S^{'} = {(z_{1}, a \to b, z_{2}) ∣ (u, a \to b, v) \in S, z_{1} \in u ⧢ $^{}, | z_{1} | = r, z_{2} \in v ⧢ $^{}, | z_{2} | = r^{'}}, \\ A^{'} = {$^{i} α $^{t} $^{j} ∣ α \in A, i = max {m, q, r}, j = max {m^{'}, q^{'}, r^{'}}, t = max {p - | w |, 0}} . \end{array}$ As in Theorem 1, $ is a new symbol, that is, $$ \notin V$ , which is introduced to be the padding symbol. We denote by h the homomorphism from $V \cup {$}$ to V defined as follows: $h (x) = x if x \in V$ and $h ($) = λ$ . By induction it can be shown that $\begin{matrix} α {\hat{\underset{{ID}_{ς}}{⟹}}}^{n} w, α \in A if and only if $^{i} α $^{t} $^{j} {\hat{\underset{{ID}_{ς}^{'}}{⟹}}}^{m} w^{'} \end{matrix}$ where $h (w^{'}) = w$ and $m ⩾ n$ . While the only-if part follows easily, consider the following for the if part. We can assume that in any derivation of ${ID}_{ς}^{'}$ the first i and the last j letters of the axiom are not deleted until the very end of derivation. Hence, insertion rules of the form $(z_{1}, $^{n}, z_{2})$ with $z_{1} \in {($ \cup V)}^{m}$ , $z_{2} \in {($ \cup V)}^{m^{'}}$ are applicable until the very end. It is clear that due to insertion rules of the form $(z_{1}, $^{n}, z_{2})$ and the deletion rule $(λ, $, λ)$ it is possible to generate an arbitrary number of $ between two letters of any sentential form of ${ID}_{ς}^{'}$ .

Let $α {\hat{\underset{{ID}_{ς}}{⟹}}}^{n} w$ . Let $w = w_{1} u a v w_{2}$ such that the substitution rule $(u, a \to b, v)$ is applicable to w. By induction $$^{i} α $^{t} $^{j} {\hat{\underset{{ID}_{ς}^{'}}{⟹}}}^{m} w^{'}$ where $h (w^{'}) = w$ and $m ⩾ n$ . Due to previous considerations it is clear that $w^{'} {\hat{\underset{{ID}_{ς}^{'}}{⟹}}}^{m} w^{″}$ such that $h (w^{″}) = w$ and $w^{″} = w_{1}^{″} z_{1} a z_{2} w_{2}^{″}$ where $z_{1} \in u ⧢ $^{}$ with $| z_{1} | = r$ and $z_{2} \in v ⧢ $^{}$ with $| z_{2} | = r^{'}$ . By definition $(z_{1}, a \to b, z_{2}) \in S^{'}$ . Hence it is easy to see that our claim holds. □

The following result will be useful in subsequent proofs; compare to Lemma 1.
Lemma 2.
Let $L$ be a family of languages that is closed under reversal. Then:
$L \subseteq {INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}}$ iff $L \subseteq {INS}_{n}^{m^{'}, m} {DEL}_{p}^{q^{'}, q} {SUB}^{r^{'}, r}$ .

${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}} \subseteq L$ iff ${INS}_{n}^{m^{'}, m} {DEL}_{p}^{q^{'}, q} {SUB}^{r^{'}, r} \subseteq L$ . □

Due to the definition of ins-del-sub systems, the following result is clear.
Lemma 3.
${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} \subseteq {INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}} {SUB}^{r, r^{'}}$ . □

Whether this inclusion is proper, is the question, that will be addressed in the following sections. We will see that while in some cases an arbitrary system of size $(n, m, m^{'}; p, q, q^{'}, r, r^{'})$ can be simulated by a system of size $(n, m, m^{'}; p, q, q^{'})$ , this is not the general case. Furthermore, we will see that families ${INS}_{n}^{m, m^{'}} {DEL}_{p}^{q, q^{'}}$ , which are not computationally complete, may reach computational completeness via an extension with substitution rules. Additionally, we will see below that families of ins-del systems which are equally powerful may no longer be after being extended with the same class of substitution rules, i.e., we have ${INS}_{n_{1}}^{m_{1}, m_{1}^{'}} {DEL}_{p_{1}}^{q_{1}, q_{1}^{'}} = {INS}_{n_{2}}^{m_{2}, m_{2}^{'}} {DEL}_{p_{2}}^{q_{2}, q_{2}^{'}}$ , but possibly ${INS}_{n_{1}}^{m_{1}, m_{1}^{'}} {DEL}_{p_{1}}^{q_{1}, q_{1}^{'}} {SUB}^{r, r^{'}} \subset {INS}_{n_{2}}^{m_{2}, m_{2}^{'}} {DEL}_{p_{2}}^{q_{2}, q_{2}^{'}} {SUB}^{r, r^{'}}$ . The reverse case might occur, as well.

Because the application of an insertion rule $(u, x, v)$ corresponds to the application of the monotone rewriting rule $u v \to u a v$ and the application of a substitution rule $(u, a \to b, v)$ corresponds to the application of the monotone rewriting rule $u a v \to u b v$ , a monotone grammar can simulate derivations of an insertion-substitution system. (More technically speaking, we have to do the replacements on the level of pseudo-terminals $N_{a}$ for each terminal a and also add rules $N_{a} \to a$ , but these are minor details.) Hence, we can conclude: Theorem 4.
For any integers $m, m^{'}, n, r, r^{'} ⩾ 0$ , ${INS}_{n}^{m, m^{'}} {DEL}_{0}^{0, 0} {SUB}^{r, r^{'}} \subseteq CS$ . □

3. Main results

We will focus on context-free ins-del systems, which are extended with substitution rules. More precisely, we will analyze the computational power of the family of systems ${INS}_{n}^{0, 0} {DEL}_{p}^{0, 0} {SUB}^{r, r^{'}}$ .

3.1. Extending ins-del systems with context-free substitutions

We are going to analyze substitution rules of the form $(λ, a \to b, λ)$ , which means that letters may be substituted regardless of any context. We will show that extending context-free ins-del systems with context-free substitution rules does not result in a more powerful system. In fact, a context-free ins-del-sub system of size $(n, 0, 0; p, 0, 0; 0, 0)$ can be simulated by an ins-del system of size $(n, 0, 0; p, 0, 0)$ .

Theorem 5.
Let ${ID}_{ς} \in {INS}_{n}^{0, 0} {DEL}_{p}^{0, 0} {SUB}^{0, 0}$ , then there exists an ins-del system $ID \in {INS}_{n}^{0, 0} {DEL}_{p}^{0, 0}$ such that $L ({ID}_{ς}) = L (ID)$ .
Proof.
We only sketch the construction of how to build in ins-del system from a given ins-del-sub system with context-free substitution rules in the following. The correctness of the construction follows similarly to the standard proof showing how to eliminate chain rules in context-free grammars, as contained in any introductory textbook on formal languages. Let ${ID}_{ς} = (V, T, A, I, D, S) \in {INS}_{n}^{0, 0} {DEL}_{p}^{0, 0} {SUB}^{0, 0}$ . It is clear that any letter a, that is to be replaced by a substitution rule $(λ, a \to b, λ)$ , has been introduced by either an insertion rule $(λ, w_{1} a w_{2}, λ)$ or as part of an axiom $w_{1}^{'} a w_{2}^{'}$ at some point before executing the substitution. As a serves no purpose other than to be replaced (i.e., it is not used as a context), the basic idea is to skip introducing a altogether and introduce b instead. More formally: instead of applying an insertion rule $(λ, w_{1} a w_{2}, λ)$ or using an axiom $w_{1}^{'} a w_{2}^{'}$ and replacing a via $(λ, a \to b, λ)$ at a later point, we introduce a new insertion rule $(λ, w_{1} b w_{2}, λ)$ or a new axiom $w_{1}^{'} b w_{2}^{'}$ , respectively, which we apply instead of $(λ, w_{1} a w_{2}, λ)$ , or $w_{1}^{'} a w_{2}^{'}$ , respectively. This idea can be cast into an algorithm to produce an ins-del system $ID = (V, T, A^{'}, I^{'}, D)$ with $L ({ID}_{ς}) = L (ID)$ . As only context-free insertion rules of maximum size $(n, 0, 0)$ are added to $I^{'}$ , it is clear that $ID \in {INS}_{n}^{0, 0} {DEL}_{p}^{0, 0}$ holds. □

Considering the question about the generative power of context-free ins-del systems with context-free substitution rules compared to usual context-free ins-del systems, Theorem 5 and Lemma 3 together yield the important fact that ins-del systems and ins-del-sub systems with context-free substitutions are equally powerful:
Corollary 1.
${INS}_{n}^{0, 0} {DEL}_{p}^{0, 0} {SUB}^{0, 0} = {INS}_{n}^{0, 0} {DEL}_{p}^{0, 0}$ .

Hence, what has been said about the power of ins-del systems in Remark 1 readily transfers to ins-del-sub systems with context-free substitutions. Although we do not focus on issues of descriptional complexity in this paper, the following examples shows that when considering the size of ins-del systems and ins-del-sub systems with context-free subsitutions, the latter ones could be exponentially more succinct. Example 1.
Let $V_{k} = {a_{1}, \dots, a_{k}}$ for $k > 1$ . Consider the ins-del-sub system $\begin{matrix} {ID}_{ς} = (V_{k}, V_{k}, {λ}, {(λ, w, λ)}, \emptyset, S), \end{matrix}$ where $w \in {a_{1}}^{m}$ , $m > 0$ , and $S = {(λ, a_{i} \to a_{i + 1}, λ) ∣ 1 ⩽ i < k}$ . Clearly, the language generated by ${ID}_{ς}$ is $L ({ID}_{ς}) = {w ∣ w \in V_{k}^{*}, | w | = m \cdot n, n \in N}$ as any application of the rule $(λ, w, λ)$ increases the length of the generated word by m and substitution rules do not affect the length. Using the construction introduced in Theorem 5 yields the ins-del system $ID = (V_{k}, V_{k}, {λ}, I, \emptyset)$ , with $I = {(λ, x_{1} x_{2} \dots x_{m}, λ) ∣ x_{1}, x_{2}, \dots, x_{m} \in V_{k}}$ . While it is clear that $L (ID) = L ({ID}_{ς})$ , we remark that this example shows that the construction method of Theorem 5 may yield an ins-del system whose number of rules is exponentially larger than the number of rules of the system with substitutions, as $| I | = | V_{k} |^{m} = k^{m}$ grows exponentially with m.

3.2. Extension with one-sided substitution

Now, we will analyze the effect of one-sided substitution rules if used to extend a context-free ins-del system. We will show that using one-sided substitution rules can greatly increase the computational power of context-free insertion and deletion rules. In some cases, we even get computationally completeness results.

We will now construct an ins-del-sub system ${ID}_{ς}^{'}$ of size $(1, 0, 0; 1, 0, 0; 1, 0)$ which simulates ${ID}_{ς}$ of size $(1, 1, 0; 1, 1, 0; 1, 0)$ . The idea behind this construction is very simple: instead of applying an insertion rule (inserting a symbol a) with some left context, we first insert some special marker (individual to this rule) in a context-free manner, and in a second step, we substitute this marker by a, watching over the left context inherited from the original insertion rule at this point. Analogously, in the case of a deletion rule that removes a symbol a in some left context, we first replace a by some some symbol that is individual to this deletion rule, observing the context of the simulated deletion rule, and then this specific introduced symbol is deleted without checking any context condition. More formally, the system ${ID}_{ς}^{'}$ is constructed in the following manner:

Construction 2.
We assume the system ${ID}_{ς} = (V, T, A, I, D, S)$ to be in normal form and any rule of ${ID}_{ς}$ to be labelled in a one-to-one manner, i.e., there is a bijection between a set of labels and the rule set. Let $ be the padding symbol used in the construction of the normal form of ${ID}_{ς}$ . The system ${ID}_{ς}^{'} = (V^{'}, T, A, I^{'}, D^{'}, S \cup S^{'})$ is constructed as follows. For each rule of ${ID}_{ς}$ , we introduce a new nonterminal $X_{i}$ and define $\begin{matrix} V^{'} = V \cup {X_{i} ∣ i is the label of a rule of {ID}_{ς}} . \end{matrix}$ The set $I^{'}$ of insertion rules of ${ID}_{ς}^{'}$ contains all $(λ, X_{i}, λ)$ , where i is the label of an insertion rule of ${ID}_{ς}$ , while the set $D^{'}$ of deletion rules as contains $(λ, $, λ)$ and all $(λ, X_{i}, λ)$ , where i is the label of a deletion rule of ${ID}_{ς}$ . Furthermore, we define the set of substitution rules $S^{'} = S_{1} \cup S_{2}$ , with $\begin{array}{l} S_{1} = {(u, X_{i} \to a, λ) ∣ i is the label of an insertion rule (u, a, λ) of {ID}_{ς}} and \\ S_{2} = {(u, a \to X_{i}, λ) ∣ i is the label of a deletion rule (u, a, λ) of {ID}_{ς}, u \neq λ} . \end{array}$

Each deletion rule $(u, a, λ) \in D$ of ${ID}_{ς}$ , where i is the label of $(u, a, λ)$ , corresponds to a deletion rule $(λ, X_{i}, λ) \in D^{'}$ and a substitution rule $(u, a \to X_{i}, λ) \in S_{2}$ of ${ID}_{ς}^{'}$ . The basic idea of the construction is to simulate a deletion rule $(u, a, λ) \in D$ by substituting the letter a with left context u via $(u, a \to X_{i}, v) \in S_{2}$ . The introduced nonterminal $X_{i}$ is then deleted at some point by the deletion rule $(λ, X_{i}, λ) \in D^{'}$ . It is clear that a derivation of the form $\begin{matrix} w_{1} u a w_{2} \hat{⟹} w_{1} u X_{i} w_{2} \hat{⟹} w_{1} u w_{2}, \end{matrix}$ in which the application of $(λ, X_{i}, λ) \in D^{'}$ succeeds an application of $(u, a \to X_{i}, λ) \in S_{2}$ immediately, is equivalent to the application of a deletion rule $(u, a, v) \in D$ . It needs much more care to prove the following converse.

We begin by proving the following statement.
Lemma 4.
Let $(u, a, λ) \in D$ be a deletion rule of ${ID}_{ς}$ and $(u, a \to X_{i}, λ) \in S_{2}$ and $(λ, X_{i}, λ) \in D^{'}$ be the corresponding rules of ${ID}_{ς}^{'}$ . Consider the derivation $\begin{matrix} u_{1} \dots u_{n - 1} u a v_{1} \dots v_{m} \hat{⟹} u_{1} \dots u_{n - 1} u X_{i} v_{1} \dots v_{m} {\hat{⟹}}^{} w \in T^{} \end{matrix}$ of ${ID}_{ς}^{'}$ , with $u \in V$ and $\begin{matrix} u_{1}, \dots, u_{n - 1}, v_{1}, \dots, v_{m} \in V \cup {X_{i} ∣ i is the label of an insertion rule (u, a, λ) of {ID}_{ς}} . \end{matrix}$ We refer to the nonterminal $X_{i}$ , introduced at this point, as ${\underline{X}}_{i}$ , to mark its specific occurrence. Then there is a derivation, leading from $u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v_{1} \dots v_{m}$ to w, in which ${\underline{X}}_{i}$ is resolved immediately.
Proof.
It is clear that the nonterminal ${\underline{X}}_{i}$ must be resolved at some point of the derivation. Given our construction, ${\underline{X}}_{i}$ can only be resolved by the context-free deletion rule $(λ, X_{i}, λ) \in D^{'}$ . Therefore, any derivation starting out from $u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v_{1} \dots v_{m}$ to produce w is of the form $\begin{matrix} u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v_{1} \dots v_{m} {\hat{⟹}}^{} w_{1} {\underline{X}}_{i} w_{2} \hat{⟹} w_{1} w_{2} {\hat{⟹}}^{} w . \end{matrix}$ Because of the construction of ${ID}_{ς}^{'}$ , $X_{i}$ is not the left context of any rule of ${ID}_{ς}^{'}$ . For this reason, $u_{1} \dots u_{n - 1} u {\hat{⟹}}^{} w_{1}$ and $v_{1} \dots v_{m} {\hat{⟹}}^{} w_{2}$ follow from the derivation $u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v_{1} \dots v_{m} {\hat{⟹}}^{} w_{1} {\underline{X}}_{i} w_{2}$ . Hence, there is the derivation $\begin{matrix} u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v_{1} \dots v_{m} \hat{⟹} u_{1} \dots u_{n - 1} u v_{1} \dots v_{m} {\hat{⟹}}^{} w_{1} w_{2} {\hat{⟹}}^{} w, \end{matrix}$ in which ${\underline{X}}_{i}$ is resolved immediately. □

Applying Lemma 4 inductively, it is easy to see that we can assume that all nonterminals $X_{i}$ , where i is the label of a deletion rule of ${ID}_{ς}$ , are resolved immediately after their introduction. We remark that this means that for any sentential form $\underline{w}$ of a derivation of ${ID}_{ς}^{'}$ $\begin{matrix} | \underline{w} |_{{X_{i} ∣ i is the label of a deletion rule of {ID}_{ς}}} ⩽ 1 \end{matrix}$ holds (without loss of generality). As in the case of deletion rules of ${ID}_{ς}$ , each insertion rule $(r, s, λ) \in I$ , where j is the label of $(r, s, λ)$ , corresponds to a context-free insertion rule $(λ, X_{j}, λ) \in I^{'}$ and a substitution rule $(r, X_{j} \to s, λ) \in S_{1}$ of ${ID}_{ς}^{'}$ . We now prove that we can assume that a substitution rule $(r, X_{j} \to s, λ) \in S_{1}$ is applied immediately after an application of a rule $(λ, X_{j}, λ) \in I^{'}$ . It is easy to see that applying $(r, X_{j} \to s, λ) \in S_{1}$ immediately after $(λ, X_{j}, λ) \in I^{'}$ achieves the same result as applying $(r, s, λ) \in I$ .
Lemma 5.
Let* $α \in V^{+}$ and $α {\hat{⟹}}^{} w \in T^{}$ be a derivation of ${ID}_{ς}^{'}$ , in which at most n insertion rules are used. Then the rules of this derivation can be reordered such that immediately after the application of a rule $(λ, X_{j}, λ) \in I^{'}$ the corresponding substitution rule $(r, X_{j} \to s, λ) \in S_{1}$ is applied.
Proof.
As stated before, we assume that nonterminals $X_{i}$ , where i is the label of a deletion rule of D, are resolved immediately after being introduced.

We prove our claims by induction on the number n of insertion rules that have been used:

$\underline{n = 1}$ : Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}^{'}$ , in which only one insertion rule is used. Let the insertion rule be $(λ, X_{j}, λ)$ and the corresponding substitution rule be $(r, X_{j} \to s, λ)$ . Then the derivation is of the form $\begin{matrix} α {\hat{⟹}}^{} w_{1} w_{2} \hat{⟹} w_{1} X_{j} w_{2} {\hat{⟹}}^{} w_{1}^{'} r X_{j} w_{2}^{'} \hat{⟹} w_{1}^{'} r s w_{2}^{'} {\hat{⟹}}^{} w \in T^{} . \end{matrix}$ Consider $w_{1} X_{j} w_{2} {\hat{⟹}}^{} w_{1}^{'} r X_{j} w_{2}^{'}$ . As $(λ, X_{j}, λ)$ is the only insertion rule ever used in the entire derivation, $w_{1} X_{j} w_{2} {\hat{⟹}}^{} w_{1}^{'} r X_{j} w_{2}^{'}$ is achieved with context-free deletion rules $(λ, X_{i}, λ)$ and the corresponding substitution rules $(u, a \to X_{i}, λ)$ . As $X_{j}$ is not the context of any of these rules, we conclude that $w_{1} {\hat{⟹}}^{} w_{1}^{'} r$ and $w_{2} {\hat{⟹}}^{} w_{2}^{'}$ hold. Therefore, we also have the derivation $\begin{matrix} α {\hat{⟹}}^{} w_{1} w_{2} {\hat{⟹}}^{} w_{1}^{'} r w_{2}^{'} \hat{⟹} w_{1}^{'} r X_{j} w_{2}^{'} \hat{⟹} w_{1}^{'} r s w_{2}^{'} {\hat{⟹}}^{} w \in T^{}, \end{matrix}$ which satisfies our claim.

$\underline{n \to n + 1}$ : Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ , in which $n + 1$ insertion rules are used. Due to our construction, all symbols that are inserted are nonterminals $X_{j}$ , where j is the label of an insertion rule of ${ID}_{ς}$ , which are eventually substituted via the corresponding rules of the form $(r, X_{j} \to s, λ)$ with $s \in V$ . Clearly, there is a nonterminal $X_{k}$ , which is the first of all inserted nonterminals to be substituted. Let $(x, X_{k} \to y, λ)$ be the substitution rule corresponding to $X_{k}$ . Then, the derivation is of the form $\begin{matrix} α {\hat{⟹}}^{} w_{1} x X_{k} w_{2} \hat{⟹} w_{1} x y w_{2} {\hat{⟹}}^{} w \in T^{}, \end{matrix}$ where for $i = 1, 2$ ; $w_{i} = w_{1}^{i} X_{1}^{i} w_{2}^{i} X_{2}^{i} w_{3}^{i} \dots w_{n_{i}}^{i} X_{n_{i}}^{i} w_{n_{i} + 1}^{i}$ with $w_{1}^{i}, \dots, w_{n_{i}}^{i} \in V^{}$ and $X_{1}^{i}, \dots, X_{n_{i}}^{i} \in V^{'} ∖ V$ .

According to Lemma 4, all nonterminals related to deletion rules of ${ID}_{ς}$ are deleted immediately after being introduced. Therefore, $\begin{matrix} X_{1}^{1}, \dots, X_{n_{1}}^{1}, X_{1}^{2}, \dots, X_{n_{2}}^{2} \in {X_{j} ∣ j is the label of an insertion rule of {ID}_{ς}} \end{matrix}$ follows. Furthermore, as $X_{k}$ is the first of all inserted nonterminal to be substituted with a letter in V, all symbols occurring in $w_{1}^{1}, \dots, w_{n_{1}}^{1}, w_{1}^{2}, \dots, w_{n_{2}}^{2}$ are either symbols belonging to the initial word α or have substituted symbols of initial word α via sequences of substitution rules in S. Therefore, it is clear that $\begin{matrix} α {\hat{⟹}}^{} w_{1}^{1} \dots w_{n_{1}}^{1} x w_{1}^{2} \dots w_{n_{2}}^{2} \end{matrix}$ holds, as $X_{1}^{1}, \dots, X_{n_{1}}^{1}, X_{1}^{2}, \dots, X_{n_{2}}^{2}$ and $X_{k}$ are introduced via context-free insertions and are not used as a context for any rule.

Also observe: Applying all rules of $D^{'}$ , S and $S_{2}$ used in the derivation $α {\hat{⟹}}^{} w_{1} x X_{k} w_{2}$ while skipping all rules of $I^{'}$ yields $\begin{matrix} α {\hat{⟹}}^{} w_{1}^{1} \dots w_{n_{1}}^{1} x w_{1}^{2} \dots w_{n_{2}}^{2} . \end{matrix}$ Therefore, consider the derivation $\begin{array}{l} α & {\hat{⟹}}^{} w_{1}^{1} \dots w_{n_{1}}^{1} x w_{1}^{2} \dots w_{n_{2}}^{2} \\ \hat{⟹} w_{1}^{1} \dots w_{n_{1}}^{1} x X_{k} w_{1}^{2} \dots w_{n_{2}}^{2} \\ (1) & \hat{⟹} w_{1}^{1} \dots w_{n_{1}}^{1} x y w_{1}^{2} \dots w_{n_{2}}^{2} \\ {\hat{⟹}}^{} w_{1}^{1} X_{1}^{i} w_{2}^{1} \dots w_{n_{1}}^{1} X_{n_{1}}^{1} w_{n_{1} + 1}^{1} x y w_{1}^{2} X_{1}^{2} w_{2}^{i} \dots w_{n_{2}}^{2} X_{n_{2}}^{2} w_{n_{2} + 1}^{2} = w_{1} x y w_{2} \\ {\hat{⟹}}^{} w \in T^{}, \end{array}$ in which the substitution rule corresponding to the nonterminal $X_{k}$ is applied immediately after the introduction of $X_{k}$ . Due to derivation (1), we can easily see that $\begin{array}{l} (2) & w_{1}^{1} \dots w_{n_{1}}^{1} x y w_{1}^{2} \dots w_{n_{2}}^{2} {\hat{⟹}}^{} w \in T^{} \end{array}$ holds. Furthermore, it is clear that in the derivation (2) at most n insertion rules are used. Using the induction hypothesis, it follows that in there is a derivation from α to w which satisfies our claim. □

Using Lemma 4 and Lemma 5, it is clear that the following proposition holds.
Proposition 1.
Let $α \in A$ . Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}^{'}$ . Then, there is an alternative derivation of ${ID}_{ς}^{'}$ , leading from α to w, in which all nonterminals $X_{i} \in V^{'} ∖ V$ are resolved immediately after being introduced.

Therefore we obtain the following result.
Theorem 6.
$L ({ID}_{ς}) = L ({ID}_{ς}^{'})$ .
Proof.
”⊆” Let ${ID}_{ς} \in {INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} {SUB}^{1, 0}$ and let ${ID}_{ς}^{'} \in {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ be constructed according to Construction 2. Consider an arbitrary derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}$ . Then there is a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}^{'}$ . Whenever an insertion rule $(r, s, λ)$ of ${ID}_{ς}$ is applied in the derivation of ${ID}_{ς}$ , we apply the corresponding rule $(λ, X_{j}, λ) \in I^{'}$ immediately followed by an application of the rule $(r, X_{j} \to s, t)$ . Whenever a deletion rule is applied, we act in an analogous manner.

”⊇” Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}^{'} \in {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ . Without loss of generality, we assume that all nonterminals $X_{i} \in V^{'} ∖ V$ are resolved by the corresponding rules immediately after being introduced. Replacing all insertion rules $(λ, X_{j}, λ)$ and all deletion rules $(u, X_{i}, λ)$ occurring in the derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}^{'}$ with the corresponding insertion and deletion rules of ${ID}_{ς}$ and removing all rules of $S^{'} = S_{1} \cup S_{2}$ yields a derivation $α ⟹^{} w \in T^{}$ of ${ID}_{ς}$ . □

This allows us to state:
Theorem 7.
${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0} = {INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} {SUB}^{1, 0}$ .

It is easy to see that a result identical to Theorem 7 can be shown analogously for the mirrors of ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ and ${INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} {SUB}^{1, 0}$ . Therefore, we find:
Corollary 2.
${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{0, 1} = {INS}_{1}^{0, 1} {DEL}_{1}^{0, 1} {SUB}^{0, 1}$ . □

Consider ins-del systems of size $(1, 0, 0; 1, 0, 0)$ extended with one-sided substitution rules; the increase in computational power is quite significant:
Proposition 2.
${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} \subset {INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} \subset {INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} {SUB}^{1, 0} = {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ .
Proof.
Both trivial inclusions are proper. For the first inclusion, observe that $b a^{+} \in {INS}_{1}^{1, 0} {DEL}_{0}^{0, 0} ∖ {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0}$ . Intuitively, it is clear that a system consisting of a single axiom $b a$ and a single insertion rule $(b, a, λ)$ yields $b a^{+}$ . On the other hand, if a system of size $(1, 0, 0; 1, 0, 0)$ can generate $b a^{m}$ , where m is arbitrary, then that system must have an insertion rule $(λ, a, λ)$ and thus $a b a^{m}$ is included in the generated language as well. For the second inclusion, note that the system of size $(1, 1, 0; 0, 0, 0; 1, 0)$ presented in Example 2 below generates ${(b a)}^{+}$ . Verlan [26, Theorem 5.3] has shown that even ins-del systems of size $(1, 1, 0; 1, 1, 1)$ cannot generate the language ${(b a)}^{+}$ . □
Example 2.
Consider the following ins-del-sub system: ${ID}_{ς} = (V, T, A, I, \emptyset, S)$ , with $V = {X_{1}, X_{2}, X_{3}, a, b}$ , $T = {a, b}$ and $A = {b a, b X_{1} X_{3}}$ . The set of insertion rules is defined as $I = {(X_{1}, X_{2}, λ), (X_{2}, X_{1}, λ)}$ , while the set of substitution rules is $S = {(b, X_{1} \to a, λ), (a, X_{2} \to b, λ), (b, X_{3} \to a, λ)}$ . The generated language is $L ({ID}_{ς}) = {(b a)}^{+}$ , as we can easily see that any generated word begins with a letter b and ends with a letter a. Furthermore, any word generated by ${ID}_{ς}$ is not of the form $w_{1} b b w_{2}$ , as the only way to introduce the terminal symbol b (except for the b introduced via the axiom) is by substituting a nonterminal $X_{2}$ with b. However, this substitution requires a left context a, which means that at some point the letter to the left of any b has been a. There are no insertion rules which can insert an additional b or $X_{2}$ between a and b. Furthermore, there are no deletion rules at all, which means that no a can be deleted. Therefore, the letter to the left of any b cannot be another b. Using the same argumentation, we can see, that any word generated by ${ID}_{ς}$ is not of the form $w_{1} a a w_{2}$ , either.

As all previous examples of languages not belonging to a specific language class of ins-del(-sub) systems are regular, the question might arise which (known) subregular language classes can be described by certain ins-del(-sub) language families, or if such subregular language classes can be even characterized by them.1
¹
This question was raised by one referee of this paper.

We are not aware of earlier studies in this direction, but we like to add one such result in the following, which possibly inspires further similar results.
Proposition 3.
The language class ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} = {INS}_{1}^{0, 0} {DEL}_{0}^{0, 0}$ can be characterized in the following way.

$L \in T^{}$ belongs to ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0}$ if and only if it can be represented as $F ⧢ X^{}$ , with $X \subseteq T$ and $F \subset T^{}$ being finite.
Proof.
First, we have to prove that ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} = {INS}_{1}^{0, 0} {DEL}_{0}^{0, 0}$ . As the inclusion ‘⊇’ is trivial, let as consider an ins-del system $I D = (V, T, A, I, D)$ with $D \neq \emptyset$ . First, observe that $I D_{f i n} = (V, T, A, \emptyset, D)$ describes a finite language $A^{'} = L (I D_{f i n})$ . Moreover, defining $I D^{'} = (V, T, A^{'}, I, D)$ , one sees that $L (I D) = L (I D^{'})$ . But now, the only purpose of deletion rules is to delete symbols (in a context-free manner) that have been introduced before (by inserting them in a context-free manner). This explains that these possible deletions are superfluous concerning the generated language, i.e., with $I D^{″} = (V, T, A^{'}, I, \emptyset)$ , we find that $L (I D) = L (I D^{″})$ .

What is the language described by a ${INS}_{1}^{0, 0} {DEL}_{0}^{0, 0}$ system $\hat{I D} = (V, T, F, I, \emptyset)$ ? I clearly determines a set of symbols X that can be freely inserted to the finite set of axioms F. As symbols cannot be deleted anymore later, we can assume that $X \subseteq T$ without loss of generality. Hence, $L (\hat{I D}) = F ⧢ X^{}$ . Conversely, any language that can be described as $F ⧢ X^{}$ , with $X \subseteq T$ and $F \subset T^{}$ being finite, can be described by some ${INS}_{1}^{0, 0} {DEL}_{0}^{0, 0}$ system $(T, T, F, I_{X}, \emptyset)$ , where $I_{X}$ allows for context-free insertions of all symbols from X. □

We now analyze the computational power of ins-del-sub systems of size $(2, 0, 0; 2, 0, 0; 0, 1)$ . While the family of ins-del systems of size $(2, 0, 0; 2, 0, 0)$ is known to be a proper subset of $CF$ , see [25,26], we will show that an extension with substitution rules of the form $(λ, A \to B, C)$ results in a significant increase in computational power. More precisely, by simulating an ins-del systems of size $(2, 0, 1; 2, 0, 0)$ , we will show that ${INS}_{2}^{0, 0} {DEL}_{2}^{0, 0} {SUB}^{0, 1} = RE$ holds.
Construction 3.
Let* $ID = (V, T, A, I, D)$ be an ins-del system of size $(2, 0, 1; 2, 0, 0)$ in normal form and all insertion rules of $ID$ be labelled in a one-to-one manner. We construct the ins-del-sub system ${ID}_{ς} = (V^{'}, T, A, I^{'}, D, S^{'})$ of size $(2, 0, 0; 2, 0, 0; 0, 1)$ , which simulates $ID$ , as follows: $\begin{array}{l} V^{'} = V \cup {N_{i, 2}, N_{i, 1} ∣ i is the label of an insertion rule (λ, a b, c) \in I} \\ I^{'} = {(λ, N_{i, 2} N_{i, 1}, λ) ∣ i is the label of an insertion rule (λ, a b, c) \in I} \\ S^{'} = {(λ, N_{i, 1} \to b, c), (λ, N_{i, 2} \to a, b) ∣ i is the label of a rule (λ, a b, c) \in I} \end{array}$

The basic idea of Construction 3 is essentially the same as in Construction 2: as context-free insertion rules cannot scan for contexts (by definition), this task is handled by the corresponding substitution rules. Consider an insertion rule $(λ, N_{i, 2} N_{i, 1}, λ)$ of ${ID}_{ς}$ where i is the label of an insertion rule $(λ, a b, c) \in I$ . Then the substitution rules, corresponding to this rule, are $(λ, N_{i, 1} \to b, c)$ and $(λ, N_{i, 2} \to a, b)$ . As in the case of Construction 2, clearly a derivation of the form $\begin{matrix} w_{1} c w_{2} \hat{⟹} w_{1} N_{i, 2} N_{i, 1} c w_{2} \hat{⟹} w_{1} N_{i, 2} b c w_{2} \hat{⟹} w_{1} a b c w_{2}, \end{matrix}$ in which all introduced nonterminals $N_{i, 2}$ , $N_{i, 1}$ are immediately resolved after being inserted, corresponds directly to the application of an insertion rule $(λ, a b, c) \in I$ . In the following paragraphs, we will show that for every derivation of ${ID}_{ς}$ , leading to a terminal string w, there is an alternative derivation leading to w, in which all nonterminals $N_{i, 2}$ , $N_{i, 1}$ are immediately resolved after being inserted as described above. We begin with the following lemma:
Lemma 6.
Let i be the label of an insertion rule $(λ, a b, c)$ of $ID$ and $w_{1}, w_{2} \in V^{' }$ . If* $w_{1} N_{i, 2} w_{2} {\hat{⟹}}^{} w \in T^{}$ holds, then $w_{1} a w_{2} {\hat{⟹}}^{} w \in T^{}$ . Furthermore, with exception of one substitution rule, all rules used in the derivation $w_{1} a w_{2} {\hat{⟹}}^{} w$ and the derivation* $w_{1} N_{i, 2} w_{2} {\hat{⟹}}^{} w$ are identical.*
Proof.
Consider the derivation $w_{1} N_{i, 2} w_{2} {\hat{⟹}}^{} w \in T^{}$ . As $N_{i, 2}$ must be resolved at some point of this derivation, it is of the form $\begin{matrix} w_{1} N_{i, 2} w_{2} {\hat{⟹}}^{} w_{1}^{'} N_{i, 2} b w_{2}^{'} \hat{⟹} w_{1}^{'} a b w_{2}^{'} {\hat{⟹}}^{} w \in T^{} . \end{matrix}$ Clearly, as $N_{i, 2}$ is not used as a context of any rule according to Construction 3, $w_{1} {\hat{⟹}}^{} w_{1}^{'}$ and $w_{2} {\hat{⟹}}^{} b w_{2}^{'}$ follow from $w_{1} N_{i, 2} w_{2} {\hat{⟹}}^{} w_{1}^{'} N_{i, 2} b w_{2}^{'}$ . Therefore, $\begin{matrix} w_{1} a w_{2} {\hat{⟹}}^{} w_{1}^{'} a b w_{2}^{'} {\hat{⟹}}^{} w \in T^{} \end{matrix}$ holds. Clearly, the second part of our claim holds as well. □

Informally, Lemma 6 means that not resolving the nonterminal $N_{i, 2}$ as early as possible does not yield computations which would otherwise be not possible. Thus, we can resolve the nonterminal $N_{i, 2}$ as early as possible.

Note that the nonterminal $N_{i, 2}$ cannot be resolved before the corresponding $N_{i, 1}$ is resolved. Consider the computation $w_{1} w_{2} \hat{⟹} w_{1} N_{i, 2} N_{i, 1} w_{2}$ , where $w_{1}, w_{2} \in V^{' }$ . Assume that $N_{i, 2}$ is resolved before its corresponding $N_{i, 1}$ , then clearly a computation $w_{1} N_{i, 2} N_{i, 1} w_{2} {\hat{⟹}}^{} w_{1} N_{i, 2} b w_{3} N_{i, 1} w_{2}$ , $w_{3} \in V^{' }$ exists. However, the set of insertion rules $I^{'}$ only contains rules of the form $(λ, N_{j, 2} N_{j, 1}, λ)$ , where j is the label of an insertion rule in I. Consider for instance the sentential form $w_{1} N_{i, 2} N_{j, 2} N_{j, 1} N_{i, 1} w_{2}$ . By construction it is clear that neither $N_{j, 2}$ nor $N_{j, 1}$ can be resolved before $N_{i, 1}$ is resolved. More generally, it is clear that given a sentential form $w_{1} w_{N} w_{2}$ , where $w_{N} \in {(V^{'} ∖ V)}^{}$ , it holds that the rightmost nonterminal of $w_{N}$ has to be resolved before any other symbol of $w_{N}$ . Thus, no computation $w_{1} N_{i, 2} N_{i, 1} w_{2} {\hat{⟹}}^{} w_{1} N_{i, 2} b w_{3} N_{i, 1} w_{2}$ exists and hence it follows that $N_{i, 2}$ cannot be resolved before the corresponding $N_{i, 1}$ .

Furthermore, by Lemma 6, it is clear that resolving $N_{i, 2}$ immediately after $N_{i, 1}$ does not affect the computation. Therefore the following lemma holds analogously to Lemma 5.
Lemma 7.
Let i be the label of an insertion rule $(λ, a b, c)$ of $ID$ . Let $α \in V^{+}$ and $α {\hat{⟹}}^{} w \in T^{}$ be a derivation of ${ID}_{ς}^{'}$ , in which at most n insertion rules are used. Then the rules of this derivation can be reordered such that immediately after the application of a rule $(λ, N_{i, 2} N_{i, 1}, λ) \in I^{'}$ the corresponding substitution rules $(λ, N_{i, 1} \to b, c) \in S^{'}$ and $(λ, N_{i, 2} \to a, b)$ applied.

Lemma 7 yields the following theorem.
Theorem 8.
${INS}_{2}^{0, 1} {DEL}_{2}^{0, 0} \subseteq {INS}_{2}^{0, 0} {DEL}_{2}^{0, 0} {SUB}^{0, 1}$ . □

As ${INS}_{2}^{0, 1} {DEL}_{2}^{0, 0} = RE$ holds according to [18, Theorem 5], we conclude:
Corollary 3.
${INS}_{2}^{0, 0} {DEL}_{2}^{0, 0} {SUB}^{0, 1} = RE$ . □

This is an interesting result, as the families of ins-del systems of size $(2, 0, 0; 2, 0, 0)$ and of size $(2, 0, 0; 0, 0, 0)$ are known to be equal [26, Theorem 4.7], yet both classes—extended with the same class of substitution rules—differ in their computational power. As $RE$ and $CS$ are closed under reversal, the next corollary follows with Lemma 2 and Theorem 4. Corollary 4.
${INS}_{2}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{1, 0} \subseteq CS$ and ${INS}_{2}^{0, 0} {DEL}_{2}^{0, 0} {SUB}^{1, 0} = RE$ . □
Remark 2.
Construction 3 can be generalized in various ways. For instance, an insertion rule $(α_{i}, u_{i}, β_{i})$ , with $u_{i} = a_{| u_{i} |} a_{| u_{i} | - 1} \dots a_{1}$ , $| u_{i} | ⩾ 2$ and $β_{i} \neq λ$ , can be simulated by a context-free insertion rule of the form $(λ, N_{i, | u_{i} |} \dots N_{i, 1}, λ)$ , together with substitution rules $(α_{i}, N_{i, | u_{i} |} \to a_{| u_{i} |}, a_{| u_{i} | - 1})$ , $(λ, N_{i, | u_{i} | - 1} \to a_{| u_{i} | - 1}, a_{| u_{i} | - 2})$ , …, $(λ, N_{i, 2} \to a_{2}, a_{1})$ , $(λ, N_{i, 1} \to a_{1}, β_{i})$ . Notice that the context size parameters of the simulated insertion rule determine the context parameters of the simulating substitution rules. We will not follow up on this here, but such generalizations could be useful in other simulations.

3.3. Extension with two-sided substitution

After analyzing the effect of context-free and one-sided substitution rules on context-free ins-del systems, we will now proceed to two-sided substitution rules, i.e., substitution rules with left and right context. Somehow surprisingly, this lifts the computational power of even the ‘weakest’ ins-del systems, that is, systems of size $(1, 0, 0; 1, 0, 0)$ , up to the level of RE. Let $ID \in {INS}_{1}^{1, 1} {DEL}_{1}^{1, 1}$ . We will show that there is a system ${ID}_{ς} \in {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1}$ capable of simulating $ID$ . The basic idea is that the context checks, necessary for simulating rules with left and right context, are performed by the substitution rules. The system ${ID}_{ς}$ is constructed in the following manner:

Construction 4.
Let $ID = (V, T, A, I, D) \in {INS}_{1}^{1, 1} {DEL}_{1}^{1, 1}$ be in normal form according to Construction 1 . For each rule of $ID$ , we have a unique label, say, i, and we introduce a new nonterminal $X_{i}$ . Define ${ID}_{ς} = (V^{'}, T, A, I^{'}, D^{'}, S)$ with $\begin{array}{l} V^{'} & = V \cup {X_{i} ∣ i is the label of a rule in I or D}, \\ I^{'} & = {(λ, X_{i}, λ) ∣ i is the label of an insertion rule (u, a, v)}, \\ D^{'} & = {(λ, X_{i}, λ) ∣ i labels a deletion rule (u, a, v) \neq (λ, X, λ)} \cup {(λ, X, λ)}, \end{array}$ where X is defined as in Construction 1 . Finally, $S = S_{1} \cup S_{2}$ with $\begin{array}{l} S_{1} & = {(u, X_{i} \to a, v) ∣ i is the label of an insertion rule (u, a, v)} and \\ S_{2} & = {(u, a \to X_{i}, v) ∣ i is the label of a deletion rule (u, a, v) \neq (λ, X, λ)} . \end{array}$

The basic idea is similar to Construction 2. Each deletion rule $(u, a, v) \in D$ of $ID$ , where i is the label of $(u, a, v)$ , corresponds to a deletion rule $(λ, X_{i}, λ) \in D^{'}$ and a substitution rule $(u, a \to X_{i}, v) \in S_{2}$ . We leave the context checks to the substitution rules. The same idea is applied to the insertion rules. With some technical effort, we can prove the following result.

The basic idea is similar to Construction 2. Each deletion rule $(u, a, v) \in D$ of $ID$ , where i is the label of $(u, a, v)$ , corresponds to a deletion rule $(λ, X_{i}, λ) \in D^{'}$ and a substitution rule $(u, a \to X_{i}, v) \in S_{2}$ . We leave the context checks to the substitution rules. More precisely, ${ID}_{ς}$ simulates a deletion rule $(u, a, v) \in D$ by substituting a in the context $(u, v)$ via $(u, a \to X_{i}, v) \in S_{2}$ . The introduced nonterminal $X_{i}$ is then deleted at some point by the deletion rule $(λ, X_{i}, λ) \in D^{'}$ .

It is clear that a derivation of the form $\begin{matrix} w_{1} u a v w_{2} \hat{⟹} w_{1} u X_{i} v w_{2} \hat{⟹} w_{1} u v w_{2}, \end{matrix}$ in which the application of $(λ, X_{i}, λ) \in D^{'}$ succeeds an application of $(u, a \to X_{i}, v) \in S_{2}$ immediately, is equivalent to the application of a deletion rule $(u, a, v) \in D$ .

The same reasoning applies to insertion rules, where an insertion rule $(u, a, v) \in I$ , where i is the label of $(u, a, v)$ , corresponds to an insertion rule $(λ, X_{i}, λ) \in I^{'}$ and a substitution rule $(u, X_{i} \to a, v) \in S_{1}$ . Applying $(u, X_{i} \to a, v) \in S_{1}$ immediately after $(λ, X_{i}, λ) \in I^{'}$ achieves the same result as applying $(u, a, v) \in I$ .

We will show that for every derivation of ${ID}_{ς}$ , leading to a word $w \in T^{}$ , there is an alternative derivation, which results in w as well and in which all rules, introducing nonterminals $X_{i} \in V^{'} ∖ V$ , are immediately followed by the corresponding rules, which resolve $X_{i}$ . We remark that any sentential form occurring in such a derivation has at most one nonterminal $X_{i} \in V^{'} ∖ V$ .
Proposition 4.
Let $α \in A$ . Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ . Then, there is an alternative derivation, leading from α to w, in which all nonterminals $X_{i} \in V^{'} ∖ V$ are resolved immediately after being introduced.
Proof.
The claim of Proposition 4 follows by inductively applying Lemma 8 and Lemma 11, as $α \in V^{}$ . □

These lemmas and further auxiliary results are described in the following.
Lemma 8.
Let $(u, a, v) \in D$ be a deletion rule of $ID$ and $(u, a \to X_{i}, v) \in S_{2}$ and $(λ, X_{i}, λ) \in D^{'}$ be the corresponding rules of ${ID}_{ς}$ . Consider the derivation $\begin{matrix} u_{1} \dots u_{n - 1} u a v v_{1} \dots v_{m} \hat{⟹} u_{1} \dots u_{n - 1} u X_{i} v v_{1} \dots v_{m} {\hat{⟹}}^{} w \in T^{} \end{matrix}$ of ${ID}_{ς}$ with $u_{1} \dots u_{n - 1} u, v v_{1} \dots v_{m} \in V^{}$ . We refer to the nonterminal* $X_{i}$ , introduced at this point, as ${\underline{X}}_{i}$ . Then there is an alternative derivation, leading from $u_{1} \dots u_{n - 1} u {\underline{X}}_{i} v v_{1} \dots v_{m}$ to w, in which ${\underline{X}}_{i}$ is resolved immediately.
Proof.
The proof is analogous to Lemma 4. □

Before we prove that there is an equivalent lemma for insertion rules, we show that the following statements holds.
Lemma 9.
Consider a sentential form $w_{1} X_{i} X_{j} w_{2}$ of ${ID}_{ς}$ , where i and j are the labels of insertion rules of $ID$ . There does not exist any word $w \in T^{}$ such that* $w_{1} X_{i} X_{j} w_{2} {\hat{⟹}}^{} w$ holds.*
Proof.
Let $(r, s, t)$ and $(f, g, h)$ be the insertion rules corresponding to the labels i and j, respectively. As $ID$ is in normal form, neither of r, t, f or h is the empty word.

Assuming that there is a $w \in T^{}$ , such that $w_{1} X_{i} X_{j} w_{2} {\hat{⟹}}^{} w$ , then $X_{i}$ and $X_{j}$ must be resolved at some point of the derivation. Given our construction of ${ID}_{ς}$ , $X_{i}$ can only be resolved by a substitution rule $(r, X_{i} \to s, t) \in S_{1}$ with $t \in V$ . Clearly, as the right context of $X_{i}$ is $X_{j} \in V^{'} ∖ V$ and all letters that can be inserted between $X_{i}$ and $X_{j}$ are nonterminals $X_{k}$ , where k is the label of an insertion rule, $X_{i}$ cannot be resolved before $X_{j}$ is resolved. (Inserting $X_{k}$ between $X_{i}$ and $X_{j}$ would result in the initial situation.)

Resolving $X_{j}$ in turn requires $X_{j}$ to have $f \in V$ as its left context, as the only rule resolving $X_{j}$ is $(f, X_{j} \to g, h) \in S_{1}$ . However, the current left context of $X_{j}$ is the nonterminal $X_{i} \notin V$ , which cannot be resolved before $X_{j}$ is resolved.

Therefore, neither $X_{i}$ nor $X_{j}$ can be resolved. □
Lemma 10.
No terminal string can be derived from sentential forms $X_{j} w^{'}$ or $w^{'} X_{j}$ with $w^{'} \in V^{' }$ and j being the label of an insertion rule* $(r, s, t)$ of $ID$ .
Proof.
We consider the case $X_{j} w^{'}$ . The case $w^{'} X_{j}$ is handled analogously. Assuming $X_{j} w^{'} {\hat{⟹}}^{} w \in T^{}$ holds, then clearly $X_{j}$ has to be resolved at some point of the derivation. The only rule resolving $X_{j}$ is $(r, X_{j} \to s, t) \in S_{1}$ . However, this rule is not applicable as $X_{j}$ has no left context and no letters can be inserted to the left of $X_{j}$ due to Lemma 9. (All insertion rules are of the form $(λ, X_{k}, λ)$ , where k is the label of an insertion rule.) □

We now prove that all nonterminals $X_{j}$ , where j is the label of an insertion rule, can be resolved immediately after being introduced.
Lemma 11.
Let $(r, s, t)$ be an insertion rule of $ID$ and $(λ, X_{j}, λ) \in I^{'}$ and $(r, X_{j} \to s, t) \in S_{1}$ be the corresponding rules of ${ID}_{ς}$ . Consider the derivation $\begin{matrix} X $ α $ X {\hat{⟹}}^{} r_{1} \dots r_{n - 1} r_{n} t_{1} t_{2} \dots t_{m} \hat{⟹} r_{1} \dots r_{n - 1} r_{n} X_{j} t_{1} t_{2} \dots t_{m} {\hat{⟹}}^{} w \in T^{} \end{matrix}$ of ${ID}_{ς}$ with* $r_{1}, \dots, r_{n}, t_{1}, \dots, t_{m} \in V$ and $X $ α $ X \in A$ .

We refer to the nonterminal $X_{j}$ , introduced at this point, as ${\underline{X}}_{j}$ . Then there is an alternative derivation, leading from $r_{1} \dots r_{n - 1} r_{n} {\underline{X}}_{j} t_{1} t_{2} \dots t_{m}$ to w, in which ${\underline{X}}_{j}$ is resolved immediately.
Proof.
We begin by analyzing $r_{n}$ and $t_{1}$ . Due to Lemma 10, $r_{1} \dots r_{n} \neq λ \neq t_{1} \dots t_{m}$ follows. We show that $r_{n} = r$ and $t_{1} = t$ . In the following, we only prove $r_{n} = r$ , as $t_{1} = t$ is shown analogously. Due to Lemma 9 and as all insertion rules are of the form $(λ, X_{k}, λ)$ , where k is the label of an insertion rule of $ID$ , it is clear that no letter can be inserted between $r_{n}$ and ${\underline{X}}_{j}$ .

As all substitution rules require a left and a right context in V and the right context of $r_{n}$ is ${\underline{X}}_{j} \notin V$ , $r_{n}$ cannot be substituted as long as ${\underline{X}}_{j}$ is not resolved.

Given our construction of ${ID}_{ς}$ , $r_{n}$ cannot be deleted, as all deleting rules only delete symbols in $V^{'} ∖ V$ and X. As $\begin{matrix} r_{1} \dots r_{n - 1} r_{n} {\underline{X}}_{j} t_{1} t_{2} \dots t_{m} {\hat{⟹}}^{} w \in T^{} \end{matrix}$ and therefore ${\underline{X}}_{j}$ is resolved via $(r, X_{j} \to s, t) \in S_{1}$ at some point, but $r_{n}$ can neither be deleted or substituted and no letter can be inserted between $r_{n}$ and ${\underline{X}}_{j}$ , $r_{n} = r$ follows.

We remark that we can assume that $r_{n} \neq X$ holds. If $r_{n} = X$ , then this X has been introduced as part of the axiom and $r_{1} \dots r_{n - 1} r_{n} = X$ follows, as due to Lemma 10, no letter is inserted to the left of the leftmost X of the axiom. Additionally, due to Lemma 10 $r_{n} = X$ cannot be deleted. Using the same argument as before, we see that $r_{n}$ cannot be substituted either and no letter can be inserted between $r_{n}$ and $X_{j}$ . Therefore, resolving ${\underline{X}}_{j}$ requires a substitution rule with left context X, which, according to Construction 4, requires an insertion rule of the form $(X, s, t)$ of $ID$ . However, there is no such insertion rule according to Construction 1.

As ${\underline{X}}_{j}$ has to be resolved at some point of the derivation, all derivations leading from $r_{1} \dots r_{n - 1} r_{n} {\underline{X}}_{j} t_{1} t_{2} \dots t_{m}$ to w are of the form $\begin{matrix} r_{1} \dots r_{n - 1} r {\underline{X}}_{j} t t_{2} \dots t_{m} {\hat{⟹}}^{} w_{1} r {\underline{X}}_{j} t w_{2} \hat{⟹} w_{1} r s t w_{2} {\hat{⟹}}^{} w . \end{matrix}$ Given our construction, there is no rule which has $X_{j}$ as either its left or right context.

Therefore, $r_{1} \dots r_{n - 1} r {\underline{X}}_{j} t t_{2} \dots t_{m} {\hat{⟹}}^{} w_{1} r {\underline{X}}_{j} t w_{2}$ implies both $r_{1} \dots r_{n - 1} r {\hat{⟹}}^{} w_{1} r$ and $t t_{2} \dots t_{m} {\hat{⟹}}^{} t w_{2}$ . Then, the derivation $\begin{matrix} r_{1} \dots r_{n - 1} r {\underline{X}}_{j} t t_{2} \dots t_{m} \hat{⟹} r_{1} \dots r_{n - 1} r s t t_{2} \dots t_{m} {\hat{⟹}}^{} w_{1} r s t w_{2} {\hat{⟹}}^{} w \end{matrix}$ results in w as well and resolves ${\underline{X}}_{j}$ immediately. □
Proposition 5.
$L (ID) = L ({ID}_{ς})$ .
Proof.
”⊆” Let $ID \in {INS}_{1}^{1, 1} {DEL}_{1}^{1, 1}$ be in normal form and let ${ID}_{ς}$ be of size $(1, 0, 0; 1, 0, 0; 1, 1)$ and be constructed according to Construction 4. Consider an arbitrary derivation $α ⟹^{} w \in T^{}$ of $ID$ . Then there is a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}$ . Whenever an insertion rule $(r, s, t)$ of $ID$ is applied in the derivation of $ID$ , we apply the corresponding rule $(λ, X_{j}, λ) \in I^{'}$ immediately followed by an application of the rule $(r, X_{j} \to s, t)$ . Whenever a deletion rule is applied, we act in an analogous manner.

”⊇” Consider a derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς} \in {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1}$ . Without loss of generality, we assume that all nonterminals $X_{i} \in V^{'} ∖ V$ are resolved by the corresponding rules immediately after being introduced. Replacing all insertion rules $(λ, X_{j}, λ)$ and all deletion rules $(u, X_{i}, v)$ occurring in the derivation $α {\hat{⟹}}^{} w \in T^{}$ of ${ID}_{ς}$ with the corresponding insertion and deletion rules of $ID$ and removing all rules of $S_{1} \cup S_{2}$ yields a derivation $α ⟹^{} w \in T^{}$ of $ID$ . □

Thus, we conclude that for any ins-del system $ID$ of size $(1, 1, 1; 1, 1, 1)$ in normal form according to Construction 4 an equivalent system ${ID}_{ς}$ of size $(1, 0, 0; 1, 0, 0; 1, 1)$ can be constructed. As ins-del system of size $(1, 1, 1; 1, 1, 1)$ are known to be computational complete, we conclude:
Corollary 5.
${INS}_{1}^{1, 1} {DEL}_{1}^{1, 1} = {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1} = RE$ . □

We now analyze the power of ins-del-sub systems of size $(1, 0, 0; 0, 0, 0; 1, 1)$ . By definition, it is clear that ${INS}_{1}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{1, 1} \subseteq {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1}$ holds. In the following, we will show that this inclusion is proper. To be more precise, we will show that ins-del-sub systems of size $(1, 0, 0; 0, 0, 0; 1, 1)$ characterize the context-sensitive languages. By Theorem 4, we are left to prove $CS \subseteq {INS}_{1}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{1, 1}$ . For every context-sensitive language L, there is a linear bounded automaton (LBA) $L B = (Q, T, Γ, q_{0}, δ, □, F)$ accepting L. We are going to construct an ins-del-sub system of size $(1, 0, 0; 0, 0, 0; 1, 1)$ to simulate $L B$ . We refrain from introducing LBA formally, but only mention that □ denotes the blank symbol and that we will use $$$ and # as two further symbols denoting the left and right endmarkers, respectively. These will be used, in particular, to describe LBA configurations. Clearly, blanks to the immediate right of $ or to the immediate left of # can be omitted or inserted without changing the configuration.

We first give a brief sketch of the basic idea behind this simulation in the following paragraph. The simulation revolves around strings of the form $\begin{matrix} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) \end{matrix}$ where $u_{1}, \dots, u_{n} \in T$ ; $q \in Q$ , $v_{1}, \dots, v_{n} \in Γ$ . The concatenation of the first component of each tuple, that is, $u_{1} \dots u_{n}$ , is the input word of the linear bounded automaton $L B$ , while the concatenation of the second component of each tuple, that is, $$ v_{1} v_{2} \dots v_{i - 1} q v_{i} v_{i + 1} \dots v_{n - 1} v_{n} #$ , represents a configuration of $L B$ running on the input word $u_{1} \dots u_{n}$ . If $(q, v_{i}) \to (q^{'}, v_{i}^{'}, R)$ is a transition rule of $L B$ such that $\begin{matrix} $ v_{1} v_{2} \dots v_{i - 1} q v_{i} v_{i + 1} \dots v_{n - 1} v_{n} # \to_{L B} $ v_{1} v_{2} \dots v_{i - 1} v_{i}^{'} q^{'} v_{i + 1} \dots v_{n - 1} v_{n} #, \end{matrix}$ then this transition is simulated by the ins-del-sub system via the derivation $\begin{array}{l} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) {\hat{⟹}}^{} \\ (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, v_{i}^{'}) (u_{i + 1}, q^{'} v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) . \end{array}$ The idea is thus as follows: first, the ins-del-sub system generates a string $\begin{matrix} (u_{1}, $ q_{0} u_{1}) (u_{2}, u_{2}) \dots (u_{n - 1}, u_{n - 1}) (u_{n}, u_{n} #), \end{matrix}$ where $$ q_{0} u_{1} u_{2} \dots u_{n - 1} u_{n} #$ is clearly the starting configuration of $L B$ on input $u_{1} \dots u_{n}$ . Starting from this string, $L B$ is simulated via the second components of the tuples. If in this simulation a string $\begin{matrix} (u_{1}, $ p_{1}) (u_{2}, p_{2}) \dots (u_{j - 1}, p_{j - 1}) (u_{j}, q_{f} p_{j}) (u_{j + 1}, p_{j + 1}) \dots (u_{n - 1}, p_{n - 1}) (u_{n}, p_{n} #) \end{matrix}$ such that $$ p_{1} p_{2} \dots p_{j - 1} q_{f} p_{j} p_{j + 1} \dots p_{n - 1} p_{n} #$ is an accepting configuration is generated, i.e., $q_{f} \in F$ , we substitute all tuples with their respective first component. For instance, a tuple $(u_{k}, p_{k})$ is substituted with $u_{k}$ . In short, this means that if (the simulation of) $L B$ running on $u_{1} \dots u_{n}$ halts in an accepting configuration, we generate the word $u_{1} \dots u_{n}$ . More details follow:
Construction 5.
Consider an arbitrary LBA $L B = (Q, T, Γ, q_{0}, δ, □, F)$ accepting $L \subseteq T^{}$ . Let* $ be the left and # be the right endmarker of $L B$ . Then, the following ins-del-sub system ${ID}_{ς} = (V \cup T, T, A, I, \emptyset, S)$ generates the language L by simulating $L B$ . The set V is defined as $V = V_{code} \cup V_{init} \cup V_{sim}$ , where $\begin{matrix} V_{code} = {(a, b), (a, $ b), (a, b #), (a, q b), (a, $ q b), (a, q $ b), (a, q b #), (a, b q #) ∣ a \in T, b \in Γ, q \in Q} . \end{matrix}$ Strings of the form $\begin{matrix} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #), \end{matrix}$ which encode the input and a configuration of $L B$ consist of symbols in $V_{code}$ , while the symbols in $V_{init}$ and $V_{sim}$ are auxiliary symbols. Symbols in $V_{init}$ are used are used in the initialization phase, that is they are used to generate strings of the form $\begin{matrix} (u_{1}, $ q_{0} u_{1}) (u_{2}, u_{2}) \dots (u_{n - 1}, u_{n - 1}) (u_{n}, u_{n} #), \end{matrix}$ where $$ q_{0} u_{1} \dots u_{n} #$ is the starting configuration of $L B$ on input $u_{1} \dots u_{n}$ and symbols in $V_{sim}$ are used during the simulation of a transition. We define $V_{init} = {X} \cup {X_{a} ∣ a \in T}$ and $V_{sim} = V_{L} \cup V_{R}$ where the symbols in $\begin{matrix} V_{L} = {L_{(a, b)}, L_{(a, q b)}, L_{(a, b #)}, L_{(a, $ q b)} ∣ a \in T, b \in Γ, q \in Q} \end{matrix}$ and $\begin{matrix} V_{R} = {R_{(a, b)}, R_{(a, q b)}, R_{(a, $ b)}, R_{(a, q b #)} ∣ a \in T, b \in Γ, q \in Q} \end{matrix}$ are used to simulate transitions with left and right movement respectively. Furthermore we define $A = {X (a, a #) ∣ a \in T} \cup {a ∣ a \in L \cap T}$ and $I = {(λ, X_{a}, λ) ∣ a \in T}$ . If $λ \in L$ , we add λ to the set of axioms. The set of substitution rules is defined as $S = Init \cup N \cup R \cup L \cup Fin$ , where the substitution rules in $Init = {(X, X_{a} \to (a, a), λ), (λ, X \to (a, $ q_{0} a), λ) ∣ a \in T}$ are used in conjunction with $V_{init}$ and I during the initialization phase. The set N consists of substitution rules used to simulate a transition of $L B$ with no movement while rules in L and R are used to simulate a transition of $L B$ with left and right movement, respectively. The sets N, L and R are constructed as follows:
if $(q, b) \to (q^{'}, c, N)$ is a transition rule of $L B$ then N contains the rules $(λ, (a, q b) \to (a, q^{'} c), λ)$ , $(λ, (a, $ q b) \to (a, $ q^{'} c), λ)$ , $(λ, (a, q b #) \to (a, q^{'} c #), λ)$ , where $a \in T$ .

if $(q, b) \to (q^{'}, c, L)$ is a transition rule of $L B$ then L contains the rules $\begin{array}{l} (λ, (d, e) \to L_{(d, q^{'} e)}, (a, q b)), (L_{(d, q^{'} e)}, (a, q b) \to L_{(a, c)}, λ), \\ (λ, L_{(d, q^{'} e)} \to, (d, q^{'} e), L_{(a, c)}), ((d, q^{'} e), L_{(a, c)} \to (a, c), λ) \end{array}$ where $a, d \in T$ and $e \in Γ$ . Note that applying these rules in this order simulates $(q, b) \to (q^{'}, c, L)$ . Additionally, L contains $\begin{array}{l} (λ, (d, e) \to L_{(d, q^{'} e)}, (a, q b #)), (L_{(d, q^{'} e)}, (a, q b #) \to L_{(a, c #)}, λ), \\ (λ, L_{(d, q^{'} e)} \to, (d, q^{'} e), L_{(a, c #)}), ((d, q^{'} e), L_{(a, c #)} \to (a, c #), λ) \end{array}$ and $\begin{array}{l} (λ, (d, $ e) \to L_{(d, $ q^{'} e)}, (a, q b)), (L_{(d, $ q^{'} e)}, (a, q b) \to L_{(a, c)}, λ), \\ (λ, L_{(d, $ q^{'} e)} \to, (d, $ q^{'} e), L_{(a, c)}), ((d, $ q^{'} e), L_{(a, c)} \to (a, c), λ) \end{array}$ and $\begin{array}{l} (λ, (d, $ e) \to L_{(d, $ q^{'} e)}, (a, q b #)), (L_{(d, $ q^{'} e)}, (a, q b #) \to L_{(a, c #)}, λ), \\ (λ, L_{(d, $ q^{'} e)} \to, (d, $ q^{'} e), L_{(a, c #)}), ((d, $ q^{'} e), L_{(a, c #)} \to (a, c #), λ) \end{array}$ which are derivatives of the previous rules and are used in the case of a left-movement next to endmarkers. Furthermore L contains the rule $(λ, (a, $ q b) \to (a, q^{'} $ c), λ)$ which covers the case of a left-movement to the left endmarker and the rule $(λ, (a, e q #) \to (a, q^{'} e #), λ)$ which covers the case $b = c = #$ , i.e. the case of a left-movement from the right endmarker.

if $(q, b) \to (q^{'}, c, R)$ is a transition rule of $L B$ then R contains the rules $\begin{array}{l} ((a, q b), (d, e) \to R_{(d, q^{'} e)}, λ), (λ, (a, q b) \to R_{(a, c)}, R_{(d, q^{'} e)}), \\ (R_{(a, c)}, R_{(d, q^{'} e)} \to (d, q^{'} e), λ), (λ, R_{(a, c)} \to (a, c), (d, q^{'} e)) \end{array}$ where $a, d \in T$ and $e \in Γ$ . Additionally, R contains $\begin{array}{l} ((a, $ q b), (d, e) \to R_{(d, q^{'} e)}, λ), (λ, (a, $ q b) \to R_{(a, $ c)}, R_{(d, q^{'} e)}), \\ (R_{(a, $ c)}, R_{(d, q^{'} e)} \to (d, q^{'} e), λ), (λ, R_{(a, $ c)} \to (a, $ c), (d, q^{'} e)) \end{array}$ and $\begin{array}{l} ((a, q b), (d, e #) \to R_{(d, q^{'} e #)}, λ), (λ, (a, q b) \to R_{(a, c)}, R_{(d, q^{'} e #)}), \\ (R_{(a, c)}, R_{(d, q^{'} e #)} \to (d, q^{'} e #), λ), (λ, R_{(a, c)} \to (a, c), (d, q^{'} e #)) \end{array}$ and $\begin{array}{l} ((a, $ q b), (d, e #) \to R_{(d, q^{'} e #)}, λ), (λ, (a, $ q b) \to R_{(a, $ c)}, R_{(d, q^{'} e #)}), \\ (R_{(a, $ c)}, R_{(d, q^{'} e #)} \to (d, q^{'} e #), λ), (λ, R_{(a, $ c)} \to (a, $ c), (d, q^{'} e #)) \end{array}$ which are derivatives of the previous rules and are used in the case of a right-movement next to endmarkers. Furthermore R contains the rule $(λ, (a, q b #) \to (a, c q^{'} #), λ)$ which covers the case of a right-movement to the right endmarker and the rule $(λ, (a, q $ e) \to (a, $ q^{'} e), λ)$ which covers the case $b = c = $$ , i.e. the case of a right-movement from the left endmarker.
The set $Fin$ consists of substitution rules which substitute symbols in $V_{code}$ with their first component. More, $Fin = F_{1} \cup F_{2}$ , where $F_{1}$ contains rules of the form $\begin{array}{l} (λ, (a, q_{f} b) \to a, λ), (λ, (a, $ q_{f} b) \to a, λ), (λ, (a, q_{f} $ b) \to a, λ), (λ, (a, q_{f} b #) \to a, λ), \\ (λ, (a, b q_{f} #) \to a, λ) \end{array}$ and $F_{2}$ contains rules of the form $\begin{matrix} (λ, (a, b) \to a, c), (c, (a, b) \to a, λ), (λ, (a, $ b) \to a, c), (c, (a, b #) \to a, λ) \end{matrix}$ with $a, c \in T$ , $b \in Γ$ , $q_{f} \in F$ .

Before proving the correctness of our construction, let us look into an example, describing a deterministic LBA accepting the language ${a^{n} b^{n} c^{n} ∣ n ⩾ 1}$ .
Example 3.
Consider the following deterministic LBA $L B = (Q, T, Γ, q_{0}, δ, □, F)$ .
$Q = {q_{0}, q_{1}, q_{2},}$

$T = {a, b, c}$ ,

$Γ = \emptyset$ ,

δ is given by the following table. R and L indicate head movements. When no target state is given, the processing stops and the input word is not accepted.

The empty columns concerning state $q_{f}$ and the endmarkers were omitted.

$F = {q_{f}}$ .

We explain the working of the LBA by considering the three smallest words as examples. We omit blanks (□) and the endmarkers at the two ends of the tape and write the state information immediately to the left of the symbol on the tape the head is scanning. $\begin{array}{l} q_{0} a b c ⊢ q_{1} b c ⊢ q_{1} ? c ⊢ q_{f} \\ q_{0} a a b b c c ⊢ q_{1} a b b c c ⊢ q_{2} b b c c ⊢ q_{2} ? b c c ⊢ q_{3} ? c c ⊢ q_{1} ? c ⊢ q_{f} \\ q_{0} a a a b b b c c c ⊢ q_{1} a a b b b c c c ⊢ q_{2} a b b b c c c ⊢ q_{3} b b b c c c ⊢ a q_{4} b b c c c ⊢ a a q_{5} b c c c ⊢ a a b q_{5} c c c \\ ⊢ a a q_{6} b b c c ⊢ a q_{6} a b b c c ⊢ q_{6} a a b b c c ⊢ q_{6} □ a a b b c c ⊢ q_{0} a a b b c c ⊢ \dots \end{array}$

In the following, we describe how the ins-del-sub system ${ID}_{ς}$ our construction yields operates when simulating the LBA described in Example 3. For instance, let ${ID}_{ς}$ simulate a computation of $L B$ on the input word $a a b b c c$ . To simulate this computation, ${ID}_{ς}$ first generates the string $\begin{matrix} (a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #) \end{matrix}$ before starting the actual simulation. To generate this string, our starting point is the axiom $X (c, c #)$ . Given our construction, the only rules of ${ID}_{ς}$ that can be applied at this point are the rules in I and $Init$ . More precisely, using the insertion rules $(λ, X_{c}, λ)$ , $(λ, X_{b}, λ)$ , $(λ, X_{a}, λ)$ and substitution rules $(λ, X_{c}, λ)$ , $(X, X_{c} \to (c, c), λ)$ , $(λ, X_{b}, λ)$ , $(X, X_{b} \to (b, b), λ)$ , $(λ, X_{a}, λ)$ , $(X, X_{a} \to (a, a), λ)$ $(λ, X \to (a, $ q_{0} a), λ)$ from $Init$ , the derivation $\begin{array}{l} X (c, c #) & {\hat{⟹}}_{ins} X X_{c} (c, c #) & {\hat{⟹}}_{sub} & X (c, c) (c, c #) \\ {\hat{⟹}}_{ins} X X_{b} (c, c) (c, c #) & {\hat{⟹}}_{sub} & X (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{ins} X X_{b} (b, b) (c, c) (c, c #) & {\hat{⟹}}_{sub} & X (b, b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{ins} X X_{a} (b, b) (b, b) (c, c) (c, c #) & {\hat{⟹}}_{sub} & X (a, a) (b, b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} (a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #) \end{array}$ is produced. We remark that none of the nonterminals $X_{a}$ , $X_{b}$ or $X_{c}$ can be inserted only to the left of X or to the right of $(c, c #)$ , as otherwise these nonterminal cannot be resolved anymore, because the only rules resolving these nonterminals are the substitution rules $(X, X_{a} \to (a, a), λ)$ , $(X, X_{b} \to (b, b), λ)$ and $(X, X_{c} \to (c, c), λ)$ . Thus, generating a string of the forms $(a, a) (a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #)$ , $(a, $ q_{0} a) (b, b) (b, b) (c, c) (c, c #) (b, b)$ etc. is not possible. Therefore, all insertions occur between X and $(c, c #)$ . Furthermore, note that any of the nonterminals $X_{a}$ , $X_{b}$ or $X_{c}$ must be resolved by the corresponding substitution rule before a new nonterminal in $V_{init}$ is inserted, as otherwise at least one symbol in $V_{init}$ cannot be resolved at all, because only the nonterminals in $V_{init}$ to the immediate right of X can be resolved. Therefore, it follows easily that, after the application of the substitution rule $(λ, X \to (a, $ q_{0} a), λ)$ , no further nonterminals can be inserted, as otherwise these nonterminals cannot be resolved anymore. Additionally, we remark that by construction, prior to the application of the substitution rule $(λ, X \to (a, $ q_{0} a), λ)$ , none of the substitution rules in $N \cup R \cup L \cup Fin$ can be applied.

Before we describe in the following how the first two transitions of $L B$ on the input $a a b b c c$ are simulated, we note that the correctness of the set R, i.e., that applying the rules in R only yields correct simulations of transition rules and nothing else, follows from “Révész’s trick” [23]. More precisely, a transition rule $(q, b) \to (q^{'}, c, R)$ of the LBA implies that a derivation $\begin{array}{l} w_{1} (a, q b) (d, e) w_{2} {\hat{⟹}}^{} w_{1} (a, c) (d, q^{'} e) w_{2} \end{array}$ exists for all $(d, e)$ where $d \in T$ and $e \in γ$ . From the grammar perspective, any derivation of this form can be obtained by a production rule of the form $(a, q b) (d, e) \to (a, c) (d, q^{'} e)$ . In [23], it is shown that this production rule is correctly simulated by the sequence of production rules of the form $\begin{matrix} (a, q b) (d, e) \to (a, q b) Z, (a, q b) Z \to W Z, W Z \to W (d, q^{'} e), W (d, q^{'} e) \to (a, c) (d, q^{'} e) \end{matrix}$ where W and Z are new symbols, i.e., replacing $(a, q b) (d, e) \to (a, c) (d, q^{'} e)$ with this sequence of production rules yields a grammar which is equivalent to the original one. It is easy to see that this sequence of production rules is essentially the same as the sequence $\begin{array}{l} ((a, q b), (d, e) \to R_{(d, q^{'} e)}, λ), (λ, (a, q b) \to R_{(a, c)}, R_{(d, q^{'} e)}), \\ (R_{(a, c)}, R_{(d, q^{'} e)} \to (d, q^{'} e), λ), (λ, R_{(a, c)} \to (a, c), (d, q^{'} e)) \end{array}$ occurring in R. Clearly, the case concerning left movements from rule set L is simply a mirror of this case.

We now describe how the first two transitions of $L B$ on the input $a a b b c c$ are simulated. Clearly, these transitions (including blank symbols and endmarkers) are $\begin{matrix} $ q_{0} a a b b c c # ⊢ $ □ q_{1} a b b c c # ⊢ $ □ □ q_{2} b b c c # . \end{matrix}$ Applying the sequence of rules $\begin{array}{l} ((a, $ q_{0} a), (a, a) \to R_{(a, q_{1} a)}, λ), (λ, (a, $ q_{0} a) \to R_{(a, $ □)}, R_{(a, q_{1} a)}) \\ (R_{(a, $ □)}, R_{(a, q_{1} a)} \to (a, q_{1} a), λ), (λ, R_{(a, $ □)} \to (a, $ □), (a, q_{1} a)) \end{array}$ from R obtained from the transition rule $(q_{0}, a) \to (q_{1}, □, R)$ to $(a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #)$ yields the derivation $\begin{array}{l} (a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #) & {\hat{⟹}}_{sub} (a, $ q_{0} a) R_{(a, q_{1} a)} (b, b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} R_{(a, $ □)} R_{(a, q_{1} a)} (b, b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} R_{(a, $ □)} (a, q_{1} a) (b, b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} (a, $ □) (a, q_{1} a) (b, b) (b, b) (c, c) (c, c #) \end{array}$ This clearly simulates the first transition. In general it holds by construction that only rules in $N \cup L \cup R$ are applicable to strings of the form $\begin{matrix} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) \end{matrix}$ generated by the ins-del-sub system constructed according to Construction 5, where $q \notin F$ . In our example in particular, note that the substitution rule $(λ, (a, $ q_{0} a) \to R_{(a, $ □), q_{0}}, λ)$ is the only rule applicable to $(a, $ q_{0} a) (a, a) (b, b) (b, b) (c, c) (c, c #)$ , aside from insertion rules whose application results in a sentential form from which no terminal string can be derived. Analogously, the sequence $\begin{array}{rcl} ((a, q_{0} a), (a, a) \to R_{(a, q_{1} a)}, λ), (λ, (a, q_{0} a) \to R_{(a, □)}, R_{(a, q_{1} a)}) \\ (R_{(a, □)}, R_{(a, q_{1} a)} \to (a, q_{1} a), λ), (λ, R_{(a, □)} \to (a, □), (a, q_{1} a)) \end{array}$ obtained from the transition rule $(q_{1}, a) \to (q_{2}, □, R)$ yields the derivation $\begin{array}{l} (a, $ □) (a, q_{1} a) (b, b) (b, b) (c, c) (c, c #) & {\hat{⟹}}_{sub} (a, $ □) (a, q_{1} a) R_{(b, q_{2} b)} (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} (a, $ □) R_{(a, □)} R_{(b, q_{2} b)} (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} (a, $ □) R_{(a, □)} (b, q_{2} b) (b, b) (c, c) (c, c #) \\ {\hat{⟹}}_{sub} (a, $ □) (a, □) (b, q_{2} b) (b, b) (c, c) (c, c #) \end{array}$ which clearly simulates $$ □ q_{1} a b b c c # ⊢ $ □ □ q_{2} b b c c #$ . Note that again only rules in $N \cup L \cup R$ are applicable to $(a, $ □) (a, q_{1} a) (b, b) (b, b) (c, c) (c, c #)$ . In particular, only the rule $(λ, (a, q_{1} a) \to R_{(a, □), q_{1}}, λ)$ is applicable to $(a, $ □) (a, q_{1} a) (b, b) (b, b) (c, c) (c, c #)$ and following the application of this rule only the remaining rule of this sequence can be applied. The remaining transition rules used in the computation of $L B$ on the input word $a a b b c c$ are simulated analogously. Thus, ${ID}_{ς}$ eventually arrives at $\begin{matrix} (a, $ □) (a, □) (b, □) (b, □) (c, q_{f} □) (c, □ #), \end{matrix}$ where $$ □ □ □ □ q_{f} □ □ # = $ q_{f} #$ is the accepting configuration of $L B$ on input $a a b b c c$ . Applying the rule $(λ, (c, q_{f} □) \to c, λ)$ from $F_{1}$ and further rules from $F_{2}$ , we arrive at the derivation $\begin{matrix} (a, $ □) (a, □) (b, □) (b, □) (c, q_{f} □) (c, □ #) {\hat{⟹}}^{} a a b b c c . \end{matrix}$ We remark that, by construction, it holds in general that only a rule from $F_{1}$ is applicable to strings of the form $\begin{matrix} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) \end{matrix}$ generated by an ins-del-sub system constructed according to Construction 5 if $$ v_{1} v_{2} \dots v_{i - 1} q v_{i} v_{i + 1} \dots v_{n - 1} v_{n} #$ is an accepting configuration. Clearly, this also holds for our example. After the application of a rule from $F_{1}$ , only the rules from $F_{2}$ are applied in a terminal derivation.

We now show that ${ID}_{ς}$ generates the language accepted by $L B$ in general.
Proposition 6.
$L (L B) = L ({ID}_{ς})$ .
Proof.
By definition it is clear that $L ({ID}_{ς}) \subseteq L (L B)$ holds, as any word generated by ${ID}_{ς}$ is accepted by $L B$ .

We now show $L (L B) \subseteq L ({ID}_{ς})$ . By definition any $w \in L (L B)$ with $| w | = 1$ is generated by ${ID}_{ς}$ as $w \in A$ . Consider a word $w \in L (L B)$ with $| w | ⩾ 2$ . Let $w = u_{1} \dots u_{n}$ with $n ⩾ 2$ . Clearly there is a derivation of the form $\begin{matrix} X (u_{n}, u_{n} #) {\hat{⟹}}^{} (u_{1}, $ q_{0} u_{1}) (u_{2}, u_{2}) \dots (u_{n - 1, u_{n - 1}}) (u_{n}, u_{n} #) . \end{matrix}$ As $w \in L (L B)$ , the simulation of $L B$ running on $u_{1} \dots u_{n}$ results in a sentential form $\begin{matrix} (u_{1}, $ v_{1}) (u_{2}, v_{2}) \dots (u_{i - 1}, v_{i - 1}) (u_{i}, q_{j} v_{i}) (u_{i + 1}, v_{i + 1}) \dots (u_{n - 1}, v_{n - 1}) (u_{n}, v_{n} #) \end{matrix}$ such that $$ v_{1} v_{2} v_{3} \dots v_{i - 1} q_{j} v_{i} v_{i + 1} \dots v_{n - 1} v_{n} #$ is an accepting configuration and therefore ${ID}_{ς}$ generates w. □

Working out details proving the correctness of this construction, one can show:
Theorem 9.
${INS}_{1}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{1, 1} = CS$ . □

Using a similar approach, one can show a characterization of the recursively enumerable languages.
Theorem 10.
${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1} = RE$ .
Proof.
The basic idea is the same as in the simulation of linear bounded automata with the addition of a phase 0 before the first derivation phase, in which the amount of space needed by the Turing machine in addition to the input word is guessed. We give a short description of the workflow and rules used in the phase 0, using the following rules: $\begin{array}{l} A = {X_{0}^{'}} \\ I = {(λ, X_{□}, λ)} \\ S = {(λ, X_{0}^{'} \to X_{0}, λ), (λ, X_{□} \to (λ, □), X_{0}^{'}), (X_{0}^{'}, X_{□} \to (λ, □), λ)} . \end{array}$ Clearly, all symbols $X_{□}$ must be inserted directly to the left or right of the axiom $X_{0}^{'}$ , otherwise these symbols cannot be resolved.

Phase 0 concludes with the application of the substitution rule $(λ, X_{0}^{'} \to X_{0}, λ)$ after which phase 1 is conducted analogously to the case of linear bounded automata. The basic idea is that after the application of $(λ, X_{0}^{'} \to X_{0}, λ)$ no further nonterminals $X_{□}$ can be inserted anymore, as they cannot be resolved otherwise. Furthermore, all $X_{□}$ introduced up to the application of $(λ, X_{0}^{'} \to X_{0}, λ)$ must have been resolved via either $(λ, X_{□} \to (λ, □), X_{0}^{'})$ or $(X_{0}^{'}, X_{□} \to (λ, □), λ)$ . The idea is that the symbols of the form $(λ, □)$ , where □ is the blank symbol of the Turing machine provide the additional space needed.

In the last phase, we finally delete all symbols of the form $(λ, x)$ where x is some symbol that occurs during the simulation of the Turing machine via a deletion rule of the forms $(a, (λ, x), λ)$ or $(λ, (λ, x), a)$ , $a \in T$ . These are the only deletion rules used in the system.

Consider Construction 5. Symbols of the form $(a, a)$ , $a \in T$ , are introduced by substituting symbols $X_{a}$ which in turn are introduced by context-free insertion rules $(λ, X_{a}, λ)$ . It can be shown that if more than one $X_{a}$ is introduced in phase 0 or if following the application of $(λ, X_{0}^{'} \to X_{0}, λ)$ the $X_{a}$ introduced in phase 0 is not positioned directly to the right of $X_{0}$ , no terminal string can be derived. □

As a consequence of Theorem 9, we can formulate the following Penttonen-style normal form theorem for context-sensitive languages.2
²
Recall that Penttonen [22] proved that for any context-sensitive language, there is a grammar that contains only one-sided rules of the forms $A \to B C$ , $A B \to A C$ , $A \to a$ for nonterminals A, B, C and terminals a.

We believe that this could be useful in particular when dealing with variations of insertion systems. In our experience, it is often more complicated to simulate context-free rules (as opposed to context-sensitive ones), and in the case of the normal form presented in the following theorem, it is obviously only necessary to implement one insertion rule (with one-sided context) instead of presenting a whole simulation of arbitrary context-free rules.
Theorem 11.
For every context-sensitive language L,* $λ \notin L$ , there is a context-sensitive grammar $G = (N, T, P, S)$ , such that $L = L (G)$ , with rules of the forms $\begin{array}{l} A \to A B \\ A B \to A C, A B \to C B \\ A \to a, with a \in T, A, B, C \in N . \end{array}$

Before we prove Theorem 11 consider the following auxilliary lemma.
Lemma 12.
Consider an ins-del-sub system ${ID}_{ς} = (V, T, A, I, \emptyset, S)$ of size $(1, 0, 0; 0, 0, 0; 1, 1)$ . Then there is an ins-del-sub system ${ID’}_{ς} = (V, T, A \cup A^{'}, I^{'}, \emptyset, S)$ of size $(1, 1, 0; 0, 0, 0; 1, 1)$ , such that $L ({ID}_{ς}) = L ({ID’}_{ς})$ and all insertion rules of ${ID’}_{ς}$ are of the form $(u, a, λ)$ , $u, a \in V^{'} \cup T$ .
Proof.
We define $A^{'} = {k α ∣ α \in A, (λ, k, λ) \in I}$ . If $λ \in A$ , we add λ to $A^{'}$ as well. For each insertion rule $(λ, a, λ)$ of ${ID}_{ς}$ and each $b \in V$ we introduce an insertion rule $(b, a, λ)$ to $I^{'}$ . Consider an arbitrary derivation of ${ID}_{ς}$ . Then at some point of this derivation a symbol c is inserted such that this c is the leftmost symbol of the sentential form and no further insertions occur left of this c (or any symbol this c is substituted with). The basic idea is that we guess this c in advance and start the derivation of ${ID’}_{ς}$ with the corresponding axiom $c α \in A^{'}$ . By induction it is clear that $α {\hat{⟹}}_{{ID}_{ς}}^{} w^{'}$ iff $c α {\hat{⟹}}_{{ID’}_{ς}}^{} c w^{'}$ where $w^{'}$ is a string over $V \cup T$ . As the derivation of ${ID}_{ς}$ is of the form $α {\hat{⟹}}_{{ID}_{ς}}^{} w^{'} {\hat{⟹}}_{{ID}_{ς}} c w^{'} {\hat{⟹}}_{{ID}_{ς}}^{} w \in T^{}$ , it is clear that $c α {\hat{⟹}}_{{ID’}_{ς}}^{} w$ . (If in a derivation of ${ID}_{ς}$ starting with the axiom $α \neq λ$ and leading to $w \in T^{}$ no symbol is inserted left of the leftmost symbol of α (or any symbol this symbol is substituted with), then clearly $α {\hat{⟹}}_{{ID}_{ς}} w$ iff $α {\hat{⟹}}_{{ID’}_{ς}} w$ .)

Clearly, $L ({ID}_{ς}) = L ({ID’}_{ς})$ . Moreover, all insertion rules of ${ID’}_{ς}$ are of the form $(u, a, λ)$ , $u, a \in V^{'} \cup T$ . □
Lemma 13.
Consider an ins-del-sub system* ${ID}_{ς} = (V, T, A, I, \emptyset, S)$ of size $(1, 1, 0; 0, 0, 0; 1, 1)$ such that all insertion rules of ${ID}_{ς}$ are of the form $(u, a, λ)$ , $u, a \in$ . Then there is an ins-del-sub system ${ID’}_{ς} = (V^{'}, T, A^{'}, I \cup I^{'}, \emptyset, S \cup S^{'})$ of the same size such that $A^{'}$ consists of a single axiom of length 1 and all insertion rules of ${ID’}_{ς}$ are of the form $(u, a, λ)$ , $u, a \in V^{'} \cup T$ which generates the same language.
Proof.
Let all axioms of ${ID}_{ς}$ be labelled in a one-to-one manner. ${ID’}_{ς} = (V^{'}, T, A^{'}, I^{'}, \emptyset, S^{'})$ is constructed as follows. Let $A^{'} = {X}$ and $\begin{matrix} V^{'} = V \cup {X} \cup {X_{i, k} ∣ i is the label of an axiom and 1 ⩽ k ⩽ γ_{i}, γ_{i} is the length of the axiom with label i} . \end{matrix}$ For each axiom $α_{1} \dots α_{n}$ labelled by i, with $n > 1$ , we add the following insertion and substitution rules to $I^{'}$ and $S^{'}$ : $\begin{array}{l} (λ, X \to X_{i, 1}, λ), (X_{i, 1}, X_{i, 2}, λ), \dots, (X_{i, n - 1}, X_{i, n}, λ), \\ (λ, X_{i, 1} \to X_{i, 1}^{'}, λ), (X_{i, 1}^{'}, X_{i, 2} \to X_{i, 2}^{'}, λ), \dots, (X_{i, n - 1}^{'}, X_{i, n} \to X_{i, n}^{'}, λ), \\ (λ, X_{i, n}^{'} \to α_{n}, λ), (λ, X_{i, n - 1}^{'} \to α_{n - 1}, α_{n}), \dots, (λ, X_{i, 1}^{'} \to α_{1}, α_{2}) . \end{array}$ If $n = 1$ , we simply add the substitution rule $(λ, X \to α_{1}, λ)$ to $S^{'}$ .

For the correctness of our construction, consider the following. Assume that a derivation of ${ID’}_{ς}$ begins with the application of $(λ, X \to X_{i, 1}, λ)$ . $X_{i, 1}$ can only be resolved by being substituted with $X_{i, 1}^{'}$ which in turn requires the application of $(λ, X_{i, n}^{'} \to α_{n}, λ)$ at some point to be resolved. (We remark that by our construction prior to the application $(λ, X_{i, n}^{'} \to α_{n}, λ)$ no symbol in V can be introduced, as all insertion rules in I are of the form $(u, a, λ)$ , $u, a \in V$ .) As the application of $(λ, X_{i, n}^{'} \to α_{n}, λ)$ requires the introduction of the symbol $X_{i, n}^{'}$ it is clear that all $X_{i, k}$ and $X_{i, k}^{'}$ , $1 ⩽ k ⩽ n$ , have been introduced at least once before $(λ, X_{i, n}^{'} \to α_{n}, λ)$ is applied. This means that all insertion rules $(X_{i, k^{'} - 1}, X_{i, k^{'}}, λ)$ , $2 ⩽ k^{'} ⩽ n$ , have been applied at least once before the application of $(λ, X_{i, n}^{'} \to α_{n}, λ)$ . As all $X_{i, k^{'}}$ are resolved by being substituted by $X_{i, k^{'}}^{'}$ via a rule of the form $(X_{i, k^{'} - 1}^{'}, X_{i, k} \to X_{i, k}^{'}, λ)$ , we can deduce that every insertion rule $(X_{i, k^{'} - 1}, X_{i, k^{'}}, λ)$ is applied exactly once. (Otherwise, some nonterminals $X_{i, k^{'}}$ cannot be resolved.)

Therefore, it is clear that $L ({ID}_{ς}) = L ({ID}_{ς}^{'})$ . □

We now prove Theorem 11.
Proof.
Let L be an arbitrary context-sensitive language. Due to Theorem 9, there is an ins-del-sub system of size $(1, 0, 0; 0, 0, 0; 1, 1)$ which generates L. Then clearly there is an ins-del-sub system ${ID}_{ς} = (V, T, A, I, \emptyset, S)$ of size $(1, 1, 0; 0, 0, 0; 1, 1)$ which generates L with the property specified in Lemma 12. By Lemma 13, let the set of axioms consist of a single symbol X. Based on ${ID}_{ς}$ we construct the context-sensitive grammar $G = (N, T, P, X)$ as follows: We define $N = {N_{a}, N_{a}^{'} ∣ a \in V}$ . For each insertion rule $(u, a, λ) \in I$ we add a production rule $N_{u} \to N_{u} N_{a}$ to P. For each substitution rule $(u, a \to b, v) \in I$ we add the production rules $N_{u} N_{a} \to N_{u} N_{b}^{'}$ and $N_{b}^{'} N_{v} \to N_{b}^{'} N_{v}$ to P. Finally, for each $a \in T$ we add a production rule $N_{a} \to a$ to P. □

Clearly, it is also possible to ‘swap the direction’ in the context-free rules of this normal form, which means that (when interpreted as insertion rules), context information ‘from the other side’ is used.
Corollary 6.
For every context-sensitive language L, $λ \notin L$ , there is a context-sensitive grammar $G = (N, T, P, S)$ , such that $L = L (G)$ , with rules of the forms $\begin{array}{l} A \to B A \\ A B \to A C, A B \to C B \\ A \to a, with a \in T, A, B, C \in N . \end{array}$

Allowing erasing productions on top, from Theorem 11 and Corollary 6 we also arrive at new characterizations of the family of recursively enumerable languages. By different methods, we could even prove that either of the two non-context-free forms suffices to achieve RE. Details can be found in the long version of [29]. Therefore, we do not make the phrase structure grammar normal forms for RE explicit in this paper.
4. Summary, open questions, and general discussions

In this paper, we have introduced substitution as an additional operation and have investigated the effect of the addition of substitution rules on context-free ins-del systems. In particular, we have shown that the addition of substitution rules to ins-del systems yields new characterizations of $RE$ and $CS$ . More precisely, we have shown the following equalities: ${INS}_{2}^{0, 0} {DEL}_{2}^{0, 0} {SUB}^{1, 0} = RE$ , ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 1} = RE$ and ${INS}_{1}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{1, 1} = CS$ . Additionally we have shown ${INS}_{1}^{1, 0} {DEL}_{1}^{1, 0} {SUB}^{1, 0} = {INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ . While in the above cases, an extension with (non-context-free) substitution rules leads to an increase in computational power, we have also shown that the addition of context-free substitution rules to context-free ins-del systems does not affect the computational power.

The main open question is if ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ is computationally complete. We conjecture this not to be the case, as with only left context rules, information can only be propagated in one direction. Yet, should ${INS}_{1}^{0, 0} {DEL}_{1}^{0, 0} {SUB}^{1, 0}$ equal $RE$ , this would provide an interesting new normal form. A minor open question is the strictness of the inclusion ${INS}_{2}^{0, 0} {DEL}_{0}^{0, 0} {SUB}^{0, 1} \subseteq CS$ .

It would be also interesting to know which subregular language classes can be described by certain ins-del(-sub) language families, or if such subregular language classes can be even characterized by them. In more general terminology, this asks about comparing ins-del(-sub) language families that are not computationally complete with the very well-known language classes from the Chomsky hierarchy.

For further results on ins-del systems extended with substitution rules, we refer to [29] and [30] in which the effect of such a type of rules on context-free ins-del systems and matrix ins-del systems, that is ins-del system with matrix control, are investigated, respectively.

4.1. Discussing the broader context

Insertion-deletion systems are one model of molecular computing, trying to use elementary operations on (DNA) strings. Admittedly, the basic operations of this study (insertions, deletions, and substitutions) are quite akin to traditional operations on strings; they are even the basic of the definition of edit distance as discussed in [31].

However, there are also other operations motivated by the structure and working of DNA that have been suggested and discussed in the literature. Prominent examples include the Watson-Crick complement and the splicing operation. For a thorough discussion of the biological background, the best source is still probably the original paper of Tom Head [9], both accessible for biologists and for computer scientists. Quite a number of further models have been suggested in (theoretical) biocomputing; for a brief survey, we point to [7], or for a more in-depth presentation, to the already mentioned monograph [21]. Many variations of these models have been shown to be computationally complete, i.e., they are capable of simulating Turing machines and hence, based on the famous Church-Turing thesis, this means that any algorithm can be implemented using these mechanisms.

However, we believe that combining these operations (as we did in the present paper) is an interesting venue also to pave the ground for further applications, going far beyond storage implementations as announced by Microsoft in https://news.microsoft.com/innovation-stories/hello-data-dna-storage/. Further applications range from solving NP-hard problems (as described in [1,10,19]) on more special-purpose machines to building universal computers (we only refer to [5] in the case of splicing systems, catching up on earlier discussions).

Another strand of interest can be deduced from the parsimony principle, also cf. [4]: How small can the resources be that have to be used to build universal computers? If several such resources are available (as length of insertion or deletion strings, or length of contexts in the grammatical mechanisms that we study), we often find trade-off results that are also interesting from the perspective of possibly trading some resources for others. This can be quite important for the sketched applications, also because (due to new technologies) it could happen that resources earlier considered to be cheap later become expensive, or vice versa.

Footnotes

Acknowledgements

We are grateful to the referees of this paper, whose comments helped improve the presentation of this manuscript and also inspired to add several further examples and results.

References

L.M.

Adleman, Molecular computation of solutions to combinatorial problems, Science 266(11) (1994), 1021–1024. doi:10.1126/science.7973651.

Alhazov,

Krassovitskiy,

Rogozhin and

Verlan, Small size insertion and deletion systems, in: Applications of Language Methods,

Martin-Vide, ed., Imperial College Press, 2010, pp. 459–515.

Beaver, Computing with DNA, Journal of Computational Biology 2(1) (1995), 1–7. doi:10.1089/cmb.1995.2.1.

Fernau, Parsimonious computational completeness, in: Developments in Language Theory – 25th International Conference, DLT,

Moreira and

Reis, eds, LNCS, Vol. 12811, Springer, 2021, pp. 12–26. doi:10.1007/978-3-030-81508-0_2.

Freund,

Kari and

Păun, DNA computing based on splicing: The existence of universal computers, Theory of Computing Systems 32(1) (1999), 69–112. doi:10.1007/s002240000112.

Freund,

Rogozhin and

Verlan, Generating and accepting P systems with minimal left and right insertion and deletion, Natural Computing 13(2) (2014), 257–268. doi:10.1007/s11047-013-9396-3.

Gheorge and

Mitrana, A formal language-based approach in biology, Comparative and Functional Genomics 5 (2004), 91–94. doi:10.1002/cfg.364.

Haussler, Insertion languages, Information Sciences 31(1) (1983), 77–89. doi:10.1016/0020-0255(83)90023-3.

Head, Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biology 49(6) (1987), 737–759. doi:10.1016/S0092-8240(87)90018-8.

10.

Head,

Rozenberg,

R.S.

Bladergroen,

C.K.D.

Breek,

P.H.M.

Lommerse and

H.P.

Spaink, Computing with DNA by operating on plasmids, Biosystems 57(2) (2000), 87–93. doi:10.1016/S0303-2647(00)00091-5.

11.

Kari, On insertions and deletions in formal languages, PhD thesis, University of Turku, Finland, 1991.

12.

Kari, DNA computing: Arrival of biological mathematics, The Mathematical Intelligencer 19(2) (1997), 9–22. doi:10.1007/BF03024425.

13.

Krassovitskiy,

Rogozhin and

Verlan, in: Further Results on Insertion-Deletion Systems with One-Sided Contexts, in: Language and Automata Theory and Applications, Second International Conference, LATA, 2008, pp. 333–344.

14.

Krassovitskiy,

Rogozhin and

Verlan, One-sided insertion and deletion: Traditional and P systems case, in: International Workshop on Computing with Biomolecules,

Csuhaj-Varjú,

Freund,

Oswald and

Salomaa, eds, Vol. 244, Österreichische Computer Gesellschaft OCG, 2008, pp. 53–64, https://hal.archives-ouvertes.fr/hal-01352396 .

15.

Krassovitskiy,

Rogozhin and

Verlan, Computational power of insertion-deletion (P) systems with rules of size two, Natural Computing 10(2) (2011), 835–852. doi:10.1007/s11047-010-9208-y.

16.

Marcus, in: Contextual Grammars, in: Third International Conference on Computational Linguistics, COLING, 1969. doi:10.3115/990403.990451.

17.

Margenstern,

Păun,

Rogozhin and

Verlan, Context-free insertion-deletion systems, Theoretical Computer Science 330(2) (2005), 339–348. doi:10.1016/j.tcs.2004.06.031.

18.

Matveevici,

Rogozhin and

Verlan, Insertion-deletion systems with one-sided contexts, in: Machines, Computations, and Universality, 5th International Conference, MCU,

J.O.

Durand-Lose and

Margenstern, eds, Lecture Notes in Computer Science, Vol. 4664, Springer, 2007, pp. 205–217. doi:10.1007/978-3-540-74593-8_18.

19.

Ouyang,

P.D.

Kaplan,

Liu and

Libchaber, DNA solution of the maximal clique problem, Science 278(5337) (1997), 446–449. doi:10.1126/science.278.5337.446.

20.

Păun, Marcus contextual grammars, Bulletin of the EATCS 52 (1994), 263–273.

21.

Păun,

Rozenberg and

Salomaa, DNA Computing: New Computing, Paradigms (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag, Berlin, Heidelberg, 2006. ISBN 3540641963.

22.

Penttonen, One-sided and two-sided context in formal grammars, Information and Control 25 (1974), 371–392. doi:10.1016/S0019-9958(74)91049-3.

23.

G.E.

Révész, Comment on the paper “Error detection in formal languages”, Journal of Computer and System Sciences 8(2) (1974), 238–242. doi:10.1016/S0022-0000(74)80057-7.

24.

Takahara and

Yokomori, On the computational power of insertion-deletion systems, Natural Computing 2(4) (2003), 321–336. doi:10.1023/B:NACO.0000006769.27984.23.

25.

Verlan, On minimal context-free insertion-deletion systems, Journal of Automata, Languages and Combinatorics 12(1–2) (2007), 317–328.

26.

Verlan, Recent developments on insertion-deletion systems, The Computer Science Journal of Moldova 18(2) (2010), 210–245.

27.

Vu, On Insertion-Deletion Systems with Substitution Rules, Master’s thesis, Informatikwissenschaften, Universität Trier, Germany, 2019.

28.

Vu and

Fernau, Insertion-deletion systems with substitutions I, in: Beyond the Horizon of Computability – 16th Conference on Computability in Europe, CiE,

Anselmo,

G.D.

Vedova,

Manea and

Pauly, eds, Lecture Notes in Computer Science, Vol. 12098, Springer, 2020, pp. 366–378.

29.

Vu and

Fernau, Insertion-deletion with substitutions II, in: Descriptional Complexity of Formal Systems – 22nd International Conference, DCFS,

Jirásková and

Pighizzini, eds, Lecture Notes in Computer Science, Vol. 12442, Springer, 2020, pp. 231–243. doi:10.1007/978-3-030-62536-8_19.

30.

Vu and

Fernau, Adding matrix control: Insertion-deletion systems with substitutions III, in: SOFSEM 2021: Theory and Practice of Computer Science – 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM,

Bures,

Dondi,

Gamper,

Guerrini,

Jurdzinski,

Pahl,

Sikora and

P.W.H.

Wong, eds, Lecture Notes in Computer Science, Vol. 12607, Springer, 2021, pp. 577–592. doi:10.1007/978-3-030-67731-2_42.

31.

R.A.

Wagner and

M.J.

Fischer, The string-to-string correction problem, Journal of the ACM 21(1) (1974), 168–173. doi:10.1145/321796.321811.