19
$\begingroup$

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.

Klaus Draeger 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, then $\hat{L} = L^+$ (and hence is regular).

If $L = {ab}$, then $\hat{L}$ is the 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. 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).

Improve this question
$\endgroup$
8
  • $\begingroup$ Can you give some illustrating examples? $\endgroup$ – phs Jun 18 '15 at 5:41
  • 2
    $\begingroup$ 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). $\endgroup$ – Klaus Draeger Jun 19 '15 at 9:16
  • $\begingroup$ @phs I have modified the question with (much) more detail. $\endgroup$ – John Machacek Jun 19 '15 at 16:50
  • 1
    $\begingroup$ One more relatively straightforward result is that if $L$ is context-free, then so is $\hat{L}$. $\endgroup$ – Klaus Draeger Jun 19 '15 at 17:19
  • 1
    $\begingroup$ 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. $\endgroup$ – phs Jun 20 '15 at 8:21
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

As J.-E. Pin 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 and Part II of the thesis.

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.