<p>As J.-E. Pin pointed out my question deals with <em>insertion</em>. I have found another source which I will post here for anyone interested.</p>

<p>L.Kari. On Insertion and Deletion in Formal Languages. Ph.D. Thesis, University of Turku, 1991.</p>

<p>Here is <a href="http://www.csd.uwo.ca/~lila/pdfs/THESIS1.pdf" rel="nofollow">Part I</a> and <a href="http://www.csd.uwo.ca/~lila/pdfs/THESIS2.pdf" rel="nofollow">Part II</a> of the thesis.</p>

<p>From what I can tell this is the original source for the study of insertion.</p>

CC BY-SA 3.0
2015-09-17T00:18:26.863Z
2015-09-17T00:47:53.037Z
2015-09-17T00:47:53.037Z
John Machacek
<p>This question is related to the so called <em>insertion systems</em>.</p>

<p>An <em>insertion system</em> is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$. Let us write $u \rightarrow_R v$ if $u = u'u''$ and $v = u'ru''$ for some $r \in R$. Let us denote by $\buildrel{*}\over\rightarrow_R$ the reflexive transitive closure of the relation $\rightarrow_R$. The closure of a language $L$ of $A^*$ under $\buildrel{*}\over\rightarrow_R$ is the language
$$  
[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}
$$
Recall that a <em>well quasi-order</em> on a set $E$ is a reflexive and
transitive relation $\leqslant$ such that for any infinite sequence $x_0,
x_1, \ldots$ of elements of $E$, there are two integers $i &lt; j$ such
that $x_i \leqslant x_j$. The following theorem is proved in [1]:</p>

<blockquote>
  <p>If $H$ is a finite set of words such that the language $A^* \setminus
A^*HA^*$ is finite, then the relation $\buildrel{*}\over\rightarrow_R$ is a well quasi-order on $A^*$ and $[L]_{\buildrel{*}\over\rightarrow_R}$ is regular.</p>
</blockquote>

<p>[1] W. Bucher, A. Ehrenfeucht and D. Haussler, On total regulators generated by derivation relations, <em>Theor. Comput. Sci.</em> <strong>40</strong>, 2-3 (1985), 131– 148.</p>

CC BY-SA 3.0
2015-06-20T22:32:03.043Z
2015-06-20T22:32:03.043Z
J.-E. Pin
<p><strong>Main/General Question</strong></p>

<p>Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and 
$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we repeatedly "embed" $L$ into itself to obtain $\hat{L}$.</p>

<p>Has $\hat{L}$ been studied? Does it have a name?</p>

<p><strong>Examples/Motivation</strong></p>

<p>As requested in the comments by here are some examples to better illustrate what $\hat{L}$ is. Then since no one (so far) seems to have seen this notion I will discuss my motivation for looking at it.</p>

<p>Klaus Draeger beat me to adding examples. I'll put those examples from the comments here for increased visibility since they are good examples.</p>

<p>If $L$ is a <a href="https://en.wikipedia.org/wiki/Unary_language">unary language</a>, then $\hat{L} = L^+$ (and hence is regular).</p>

<p>If $L = {ab}$, then $\hat{L}$ is the <a href="https://en.wikipedia.org/wiki/Dyck_language">Dyck language</a>.</p>

<p>Here is a alternative way to think of $\hat{L}$. Given a language $L$ over an alphabet $A$ we play the following game. We take any $w \in A^*$ the try to reduce $w$ to the empty string $\epsilon$ by repeatedly removing subwords that are in $L$. (Here we need to by a little careful how we treat the empty string itself to make sure that this is equivalent to the definition above, but this is morally correct.)</p>

<p>Originally I came the define $\hat{L}$ by considering deleting powers in words. Take $L = \{w^3 : w \in A^*\}$ to be the language of cubes over the binary alphabet $A = \{a,b\}$. Then $aaabaabaabbabab \in \hat{L}$ and we can consider the following "$L$-deletion"</p>

<p>$$a(aabaabaab)babab \to ababab \to \epsilon.$$</p>

<p>Observe not all deletions will work</p>

<p>$$(aaa)baabaabbabab \to baabaabbabab$$</p>

<p>and we are stuck with a cube-free word. So, there is another notation of "strongly $L$-deletable" which in general does not coincide with $\hat{L}$.</p>

<p>One final example, if $L$ in the language of squares over the binary alphabet $A = \{a,b\}$, then $\hat{L}$ is the strings with both an even number of $a$'s and an even number of $b$'s. Clearly this condition is necessary. One way to see it is sufficient is to consider deleting squares and recall every binary word of length 4 or great has a square. Here $\hat{L}$ is regular.</p>

<p>For larger alphabets this type of argument fails since there are <a href="https://en.wikipedia.org/wiki/Square-free_word">arbitrarily long square-free words</a>. With alphabets of size $k \geq 3$ I can show $\hat{L}$ is not regular using Myhill-Nerode and the fact there are arbitrarily long square-free words, but I have not been able to say much more. I was hoping looking at it in this more abstract way could shed some light on the situation (and this more abstract definition seems interesting in its own right).</p>

CC BY-SA 3.0
2015-06-18T05:41:24.797Z
Can you give some illustrating examples?
phs
CC BY-SA 3.0
2015-06-19T09:16:49.477Z
Some examples: if $L$ is the singleton language $\{()\}$, then $\hat{L}$ is the Dyck language of balanced strings of parentheses; for a language $L=\{a^i|i\in I\}$ over a singleton alphabet we get $\hat{L}=L^+$ (so it is always regular in this case).
Klaus Draeger
CC BY-SA 3.0
2015-06-19T16:50:16.267Z
@phs I have modified the question with (much) more detail.
John Machacek
CC BY-SA 3.0
2015-06-19T16:50:59.520Z
@KlausDraeger thank you for the examples. I had not yet thought of the Dyck language is this light, but that is a great example.
John Machacek
CC BY-SA 3.0
2015-06-19T17:19:52.213Z
One more relatively straightforward result is that if $L$ is context-free, then so is $\hat{L}$.
Klaus Draeger
CC BY-SA 3.0
2015-06-19T22:13:43.430Z
Yes. If $L$ is $X$, then $\hat{L}$ is $X$ holds in many cases I think. Not for $X = REG$, but for many other grammars.
John Machacek
CC BY-SA 3.0
2015-06-19T22:15:35.700Z
Also if $L$ in P, then $\hat{L}$ in NP.
John Machacek
CC BY-SA 3.0
2015-06-20T08:21:41.873Z
Thanks for the examples and motivation. It is now much easier to remember your problem and pass it around. Keep updating your original question if you have new developments.
phs
<reference-request><fl.formal-languages>
"Embedding" a language in itself
John Machacek
# "Embedding" a language in itself

(Asked by: username_0 on 2015-06-17)

**Main/General Question**

Let $L$ be a language. Define the languages $L\_i$ with $L\_0 = L$ and
$$L\_i = \{xwy : xy \in L\_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L\_i$. So, we repeatedly "embed" $L$ into itself to obtain $\hat{L}$.

Has $\hat{L}$ been studied? Does it have a name?

**Examples/Motivation**

As requested in the comments by here are some examples to better illustrate what $\hat{L}$ is. Then since no one (so far) seems to have seen this notion I will discuss my motivation for looking at it.

username_2 beat me to adding examples. I'll put those examples from the comments here for increased visibility since they are good examples.

If $L$ is a [unary language](https://en.wikipedia.org/wiki/Unary_language), then $\hat{L} = L^+$ (and hence is regular).

If $L = {ab}$, then $\hat{L}$ is the [Dyck language](https://en.wikipedia.org/wiki/Dyck_language).

Here is a alternative way to think of $\hat{L}$. Given a language $L$ over an alphabet $A$ we play the following game. We take any $w \in A^\*$ the try to reduce $w$ to the empty string $\epsilon$ by repeatedly removing subwords that are in $L$. (Here we need to by a little careful how we treat the empty string itself to make sure that this is equivalent to the definition above, but this is morally correct.)

Originally I came the define $\hat{L}$ by considering deleting powers in words. Take $L = \{w^3 : w \in A^\*\}$ to be the language of cubes over the binary alphabet $A = \{a,b\}$. Then $aaabaabaabbabab \in \hat{L}$ and we can consider the following "$L$-deletion"

$$a(aabaabaab)babab \to ababab \to \epsilon.$$

Observe not all deletions will work

$$(aaa)baabaabbabab \to baabaabbabab$$

and we are stuck with a cube-free word. So, there is another notation of "strongly $L$-deletable" which in general does not coincide with $\hat{L}$.

One final example, if $L$ in the language of squares over the binary alphabet $A = \{a,b\}$, then $\hat{L}$ is the strings with both an even number of $a$'s and an even number of $b$'s. Clearly this condition is necessary. One way to see it is sufficient is to consider deleting squares and recall every binary word of length 4 or great has a square. Here $\hat{L}$ is regular.

For larger alphabets this type of argument fails since there are [arbitrarily long square-free words](https://en.wikipedia.org/wiki/Square-free_word). With alphabets of size $k \geq 3$ I can show $\hat{L}$ is not regular using Myhill-Nerode and the fact there are arbitrarily long square-free words, but I have not been able to say much more. I was hoping looking at it in this more abstract way could shed some light on the situation (and this more abstract definition seems interesting in its own right).

**Tags:** reference-request, fl.formal-languages

> **Comments:**
> **username_1**: Can you give some illustrating examples?  
> **username_2**: Some examples: if $L$ is the singleton language $\{()\}$, then $\hat{L}$ is the Dyck language of balanced strings of parentheses; for a language $L=\{a^i|i\in I\}$ over a singleton alphabet we get $\hat{L}=L^+$ (so it is always regular in this case).  
> **username_0**: @username_1 I have modified the question with (much) more detail.  
> **username_0**: @KlausDraeger thank you for the examples. I had not yet thought of the Dyck language is this light, but that is a great example.  
> **username_2**: One more relatively straightforward result is that if $L$ is context-free, then so is $\hat{L}$.  
> **username_0**: Yes. If $L$ is $X$, then $\hat{L}$ is $X$ holds in many cases I think. Not for $X = REG$, but for many other grammars.  
> **username_0**: Also if $L$ in P, then $\hat{L}$ in NP.  
> **username_1**: Thanks for the examples and motivation. It is now much easier to remember your problem and pass it around. Keep updating your original question if you have new developments.  

---

## 2 answers

### Answer by username_3 on 2015-06-20. Score: 13 | Accepted answer

This question is related to the so called *insertion systems*.

An *insertion system* is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$. Let us write $u \rightarrow\_R v$ if $u = u'u''$ and $v = u'ru''$ for some $r \in R$. Let us denote by $\buildrel{\*}\over\rightarrow\_R$ the reflexive transitive closure of the relation $\rightarrow\_R$. The closure of a language $L$ of $A^\*$ under $\buildrel{\*}\over\rightarrow\_R$ is the language
$$
[L]\_{\buildrel{\*}\over\rightarrow\_R} = \{ v \in A^\* \mid \text{ there exists $u \in L$ such that $u \buildrel{\*}\over\rightarrow\_R v$} \}
$$
Recall that a *well quasi-order* on a set $E$ is a reflexive and
transitive relation $\leqslant$ such that for any infinite sequence $x\_0,
x\_1, \ldots$ of elements of $E$, there are two integers $i < j$ such
that $x\_i \leqslant x\_j$. The following theorem is proved in [1]:

> If $H$ is a finite set of words such that the language $A^\* \setminus
> A^\*HA^\*$ is finite, then the relation $\buildrel{\*}\over\rightarrow\_R$ is a well quasi-order on $A^\*$ and $[L]\_{\buildrel{\*}\over\rightarrow\_R}$ is regular.

[1] W. Bucher, A. Ehrenfeucht and D. Haussler, On total regulators generated by derivation relations, *Theor. Comput. Sci.* **40**, 2-3 (1985), 131– 148.


---

### Answer by username_0 on 2015-09-17. Score: 2

As username_3 pointed out my question deals with *insertion*. I have found another source which I will post here for anyone interested.

L.Kari. On Insertion and Deletion in Formal Languages. Ph.D. Thesis, University of Turku, 1991.

Here is [Part I](http://www.csd.uwo.ca/~lila/pdfs/THESIS1.pdf) and [Part II](http://www.csd.uwo.ca/~lila/pdfs/THESIS2.pdf) of the thesis.

From what I can tell this is the original source for the study of insertion.


---

