# Outfix-Guided Insertion††thanks: This manuscript version is made available
under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-
nd/4.0/ Accepted in Theoretical Computer Science
http://dx.doi.org/10.1016/j.tcs.2017.03.040 An extended abstract of this paper
appeared in the Proceedings of the 20th International Conference Developments
in Language Theory, DLT 2016, Lect. Notes Comput. Sci. 9840, Springer-Verlag,
2016, pp. 102–113.

Da-Jung Cho Department of Computer Science, Yonsei University, 50, Yonsei-Ro,
Seodaemum-Gu, Seoul 120–749, Republic of Korea {dajungcho,
<EMAIL_ADDRESS>Yo-Sub Han† Timothy Ng School of Computing, Queen’s
University, Kingston, Ontario K7L 3N6, Canada {ng<EMAIL_ADDRESS>Ka
Salomaa‡

(February 20, 2017)

###### Abstract

Motivated by work on bio-operations on DNA strings, we consider an outfix-
guided insertion operation that can be viewed as a generalization of the
overlap assembly operation on strings studied previously. As the main result
we construct a finite language $L$ such that the outfix-guided insertion
closure of $L$ is non-regular. We consider also the closure properties of
regular and (deterministic) context-free languages under the outfix-guided
insertion operation and decision problems related to outfix-guided insertion.
Deciding whether a language recognized by a deterministic finite automaton is
closed under outfix-guided insertion can be done in polynomial time. The
complexity of the corresponding question for nondeterministic finite automata
remains open.

Keywords: language operations, closure properties, regular languages

##  1 Introduction

Gene insertion and deletion are basic operations occurring in DNA
recombination in molecular biology. Recombination creates a new DNA strand by
cutting, substituting, inserting, deleting or combining other strands.
Possible errors in this process impair the function of genes. Errors in DNA
recombination cause mutation that plays a part in normal and abnormal
biological processes such as cancer, the immune system, protein synthesis and
evolution [1]. Since mutational damage may or may not be easily identifiable,
researchers deliberately generate mutations so that the structure and
biological activity of genes can be examined in detail. _Site-directed
mutagenesis_ is one of the most important techniques in laboratory for
generating mutations on specific sites of DNA using PCR (polymerase chain
reaction) based methods [8, 12]. For a site-directed insertion mutagenesis by
PCR, the mutagenic primers are typically designed to include the desired
change, which could be base addition [18, 19]. This enzymatic reaction occurs
in the test tube with a DNA strand and predesigned primers in which the DNA
strand includes a target region, and a predesigned primer includes a
complementary region of the target region. The complementary region of primers
leads it to hybridize the target DNA region and generate a desired insertion
on a specific site as a mutation. Fig. 1 illustrates the procedure of site-
directed insertion mutagenesis by PCR.

Figure 1: An example of site-directed insertion mutagenesis by PCR. Given a
DNA sequence and four predesigned primers $a,b,c$ and $d$, two primers $a$ and
$b$ lead the DNA sequence to break and extend into two products $A$ and $B$
under enzymatic reaction (Step 1). Two primers $c$ and $d$ complementarily
bind to desired insertion region according to the overlapping region and
extend into product $C$ (Step 2). Then, the products $A,B$ and $C$ join
together to create recombinant DNA that include the desired insertion (Step
3).

In formal language theory, the insertion of a string means adding a substring
to a given string and deletion of a string means removing a substring. The
insertions occurring in DNA strands are in some sense context-sensitive and
Kari and Thierrin [16] modeled such bio-operations using contextual insertions
and deletions [9, 22]. A finite set of insertion-deletion rules, together with
a finite set of axioms, can be viewed as a language generating device.
Contextual insertion-deletion systems in the study of molecular computing have
been used e.g. by Daley et al. [4], Enaganti et al. [7], Krassovitskiy et al.
[17] and Takahara and Yokomori [24]. Further theoretical studies on the
computational power of insertion-deletion systems were done e.g. by
Margenstern et al. [20] and Pǎun et al. [21]. Enaganti et al. [7] have studied
related operations to model the action of DNA polymeraze enzymes.

We formalize site-directed insertion mutagenesis by PCR and define a new
operation _outfix-guided insertion_ that partially inserts a string $y$ into a
string $x$ when two non-empty substrings of $x$ match with an outfix of $y$,
see Fig. 2 (b). We will consider also variants where only a prefix or a suffix
of $y$ must match with a non-empty substring of $x$ at the position where the
insertion occurs. The outfix-guided insertion is an overlapping variant of the
ordinary insertion operation, analogously as the overlap assembly [2, 5, 6],
cf. Fig. 2 (a), is a variant of the ordinary string concatenation operation.
An operation equivalent to overlap assembly has been considered under the name
chop of languages by Holzer et al. [14]. Holzer and Jacobi [13] have given
tight state complexity bounds for a variant of the operation where the
overlapping string always has length one. Furthermore, Cǎrǎuşu and Pǎun [3]
have considered another related operation called short concatenation.

Figure 2: (a) If suffix $v$ of $x$ overlaps with prefix $v$ of $y$, then the
overlap assembly operation appends suffix $w$ of $y$ to $x$. (b) If the outfix
of $y$ consisting of $u$ and $v$ matches the substring $uv$ of $x$, then the
outfix-guided insertion operation inserts $w$ between $u$ and $v$ in the
string $x$.

This paper investigates the language theoretic closure properties of outfix-
guided insertion and iterated outfix-guided insertion. Note that since outfix-
guided insertion, similarly as overlap assembly, is not associative, there are
more than one way to define the iteration of the operation. We consider a
general outfix-guided insertion closure of a language which is defined
analogously as the iterated overlap assembly by Enaganti et al. [5]. Iterated
(overlap) assembly is defined by Csuhaj-Varju et al. [2] in a different way,
which we call right one-sided iteration of an operation.

It is fairly easy to see that regular languages are closed under outfix-guided
insertion. Closure of regular languages under iterated outfix-guided insertion
turns out to be less obvious. It is well known that regular languages are not
closed under the iteration of the ordinary (non-overlapping) insertion
operation [15] and it is also fairly easy to establish that iterated prefix-
guided (or suffix-guided) insertion does not preserve regularity. However, the
known counter-examples, nor their variants, do not work for iterated outfix-
guided insertion. Here using a more involved construction we show that there
exists even a finite language $L$ such that the outfix-guided insertion
closure of $L$ is non-regular. On the other hand, we show that the outfix-
guided insertion closure of a unary regular language is always regular.

It is well known that context-free languages are closed under ordinary (non-
iterated) insertion. We show that context-free languages are not closed under
outfix-guided insertion, nor under prefix-guided or suffix-guided insertion.
The outfix-guided insertion of a regular language into a context-free language
(or vice versa) is always context-free. Also we establish that a similar
closure property does not hold for the deterministic context-free and the
regular languages. Finally in section 6 we consider decision problems on
whether a language is closed under outfix-guided insertion (or og-closed). We
give a polynomial time algorithm to decide whether a language recognized by a
deterministic finite automaton (DFA) is og-closed. We show that for a given
context-free language $L$ the question of deciding whether or not $L$ is og-
closed is undecidable.

##  2 Preliminaries

We assume the reader to be familiar with the basics of formal languages, in
particular, with the classes of regular languages and (deterministic) context-
free languages [23, 25]. Here we briefly recall some definitions and in the
next section formally define the the main notion of outfix-guided insertion
and the corresponding iterated operations.

The symbol $\Sigma$ stands always for a finite alphabet, $\Sigma^{*}$
(respectively, $\Sigma^{+}$) is the set of strings (respectively, non-empty
strings) over $\Sigma$, $|w|$ is the length of a string $w\in\Sigma^{*}$,
$w^{R}$ is the reversal of $w$ and $\varepsilon$ is the empty string. For
$i\in\mathbb{N}$, $\Sigma^{\geq i}$ is the set of strings of length at least
$i$.

If $w=xy$, $x,y\in\Sigma^{*}$, we say that $x$ is a prefix of $w$ and $y$ is a
suffix of $w$. If $w=xyz$, $x,y,z\in\Sigma^{*}$, we say that $(x,z)$ is an
outfix of $w$. If additionally $x\neq\varepsilon$ and $z\neq\varepsilon$,
$(x,z)$ is a non-trivial outfix of $w$. Sometimes (in particular, when talking
about the outfix-guided insertion operation) we refer to an outfix $(x,z)$
simply as a string $xz$ (when it is known from the context what are the
components $x$ and $z$).

###### Example 2.1

Let $\Sigma=\\{a,b,c\\}$ and $w=abca$. The non-trivial outfixes of $w$ are
$(a,a)$, $(ab,a)$, $(a,ca)$, $(a,bca)$, $(ab,ca)$, and $(abc,a)$. Note that
all prefixes and suffixes of a string $u$ are outfixes of $u$ but prefixes and
suffixes are not, in general, non-trivial outfixes. A string $u$ represents
one or more non-trivial outfixes of $u$ if and only if $|u|\geq 2$.

To conclude this section we fix some basic notation on finite automata.

A nondeterministic finite automaton (NFA) is a tuple
$A=(\Sigma,Q,\delta,q_{0},F)$ where $\Sigma$ is the input alphabet, $Q$ is the
finite set of states, $\delta\colon Q\times\Sigma\rightarrow 2^{Q}$ is the
transition function, $q_{0}\in Q$ is the initial state and $F\subseteq Q$ is
the set of final states. In the usual way $\delta$ is extended as a function
$Q\times\Sigma^{*}\rightarrow 2^{Q}$ and the language accepted by $A$ is
$L(A)=\\{w\in\Sigma^{*}\mid\delta(q_{0},w)\cap F\neq\emptyset\\}$. The
automaton $A$ is a deterministic finite automaton (DFA) if $|\delta(q,a)|\leq
1$ for all $q\in Q$ and $a\in\Sigma$.

It is well known that the deterministic and nondeterministic finite automata
recognize the class of regular languages. A (nondeterministic) pushdown
automaton (PDA) is an extension of a finite automaton that reads the input
left-to-right and in addition to the finite state memory has access to a
pushdown store [23]. The nondeterministic PDAs define the class of context-
free languages (CFL). Deterministic PDAs define the class of deterministic
context-free languages (DCFL) and this is a proper subclass of CFL [23].

##  3 Definition of (Iterated) Outfix-Guided Insertion

We begin by recalling some notions associated with the non-overlapping
insertion operation.111We use the term “non-overlapping” to make the
distinction clear to outfix-guided insertion which will be the main topic of
this paper. More details on variants of the insertion operation and iterated
insertion can be found in [15].

The non-overlapping insertion of a string $y$ into a string $x$ is defined as
the set of strings $x\stackrel{{\scriptstyle\rm
nol}}{{\leftarrow}}y=\\{x_{1}yx_{2}\mid x=x_{1}x_{2}\\}$. The insertion
operation is extended in the natural way to languages by setting
$L_{1}\stackrel{{\scriptstyle\rm nol}}{{\leftarrow}}L_{2}=\bigcup_{x\in
L_{1},y\in L_{2}}x\stackrel{{\scriptstyle\rm nol}}{{\leftarrow}}y.$ Following
Kari [15] we define the left-iterated insertion  of $L_{2}$ into $L_{1}$
inductively by setting

$\mathbb{LI}^{(0)}(L_{1},L_{2})=L_{1}\mbox{ and
}\mathbb{LI}^{(i+1)}(L_{1},L_{2})=\mathbb{LI}^{(i)}(L_{1},L_{2})\stackrel{{\scriptstyle\rm
nol}}{{\leftarrow}}L_{2},\;i\geq 0.$

The left-iterated insertion closure of $L_{2}$ into $L_{1}$ is
$\mathbb{LI}^{*}(L_{1},L_{2})=\bigcup_{i=0}^{\infty}\mathbb{LI}^{(i)}(L_{1},L_{2}).$
It is well known that the iterated non-overlapping insertion operation does
not preserve regularity [15, 11].

###### Example 3.1

Let $\Sigma=\\{a,b\\}$. The left-iterated insertion closure of the string $ab$
into itself is non-regular because $\mathbb{LI}^{*}(ab,ab)\cap
a^{*}b^{*}=\\{a^{i}b^{i}\mid i\geq 0\\}$.

Next we define the main notion of this paper which can be viewed as a
generalization of the overlap assembly operation [2, 5]. An “inside part” of a
string $y$ can be outfix-guided inserted into a string $x$ if a non-trivial
outfix of $y$ overlaps with a substring of $x$ in a position where the
insertion occurs. This differs from contextual insertion (as defined in [16])
in the sense that $y$ must actually contain the outfix that is matched with a
substring of $x$ (and additionally [16] specifies a set of contexts where an
insertion can occur).

###### Definition 3.2

The outfix-guided insertion of a string $y$ into a string $x$ is defined as

$x\stackrel{{\scriptstyle\rm ogi}}{{\leftarrow}}y=\\{x_{1}uzvx_{2}\mid
x=x_{1}uvx_{2},\;y=uzv,\;u\neq\varepsilon,v\neq\varepsilon\\}.$

Using the above notations, when $w=x_{1}uzvx_{2}$ is the result of outfix-
guided inserting $y=uzv$ into $x=x_{1}uvx_{2}$ we say that the non-empty
substrings $u$ and $v$ are the matched parts. Note that the matched parts form
a non-trivial outfix of the inserted string $y$. When speaking of matched
parts we refer to specific substring occurrences in the string $x$ that are
matched with a non-empty prefix and suffix of $y$, respectively. When string
$u$ occurs as a substring $x$ after a prefix of length $i\in\mathbb{N}$, this
could be specified as a pair $(u,i+1)$ to indicate that the occurrence begins
at position $i+1$.

As variants of outfix-guided insertion we define operations where only a non-
empty prefix or a non-empty suffix of the inserted string needs to be matched
with a substring in the original string. Naturally it would be possible to
define further variants of outfix-guided insertion, e.g., by allowing the
matched outfix to be empty.

###### Definition 3.3

The prefix-guided insertion of a string $y$ into a string $x$ is defined as

$x\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}y=\\{x_{1}y_{1}y_{2}x_{2}\mid
x=x_{1}y_{1}x_{2},\;y=y_{1}y_{2},\;y_{1}\neq\varepsilon\\}.$

The suffix-guided insertion of a string $y$ into a string $x$ is defined as

$x\stackrel{{\scriptstyle\rm sgi}}{{\leftarrow}}y=\\{x_{1}y_{1}y_{2}x_{2}\mid
x=x_{1}y_{2}x_{2},\;y=y_{1}y_{2},\;y_{2}\neq\varepsilon\\}.$

The ordinary insertion, outfix-guided insertion and suffix-guided insertion
operations, respectively, are illustrated in Fig. 3.

Figure 3: (a) Non-overlapping insertion of string $y$ into string $x$. (b) If
the outfix of $y$ consisting of $u$ and $v$ matches the substring $uv$ of $x$,
then the outfix-guided insertion operation inserts $z$ between $u$ and $v$ in
the string $x$. (c) If the suffix of $y$ consisting of $v$ matches a substring
of $x$, then the suffix-guided operation inserts the prefix $z$ of $y$ before
an occurrence of $v$ in $x$.

Since we are mainly dealing with outfix-guided insertion, in the following for
notational simplicity we write just $\leftarrow$ in place of
$\stackrel{{\scriptstyle\rm ogi}}{{\leftarrow}}$. Outfix-guided insertion is
extended in the usual way for languages by setting $L_{1}\leftarrow
L_{2}=\bigcup_{w_{i}\in L_{i},i=1,2}w_{1}\leftarrow w_{2}.$ The prefix-guided
and suffix-guided insertion operations $\stackrel{{\scriptstyle\rm
pgi}}{{\leftarrow}}$ and $\stackrel{{\scriptstyle\rm sgi}}{{\leftarrow}}$ are
extended for languages in the same way.

It is known that the ordinary insertion operation is not associative and, not
surprisingly, neither are the outfix-, prefix- and suffix-guided variants.

###### Example 3.4

Outfix-guided (respectively, prefix-guided, suffix-guided) insertion operation
is not associative.

Let $\Sigma=\\{a,b,c,d\\}$. Now $abcd\in(acd\leftarrow abc)\leftarrow abcd$
but $abc\leftarrow abcd=\emptyset$.

Similarly we note that $abc\in(ab\stackrel{{\scriptstyle\rm
pgi}}{{\leftarrow}}bc)\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}abc$ but
$bc\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}abc=\emptyset$ because no
substring of $bc$ is a prefix of $abc$. By reversing all the strings we get an
example that shows that suffix-guided insertion is non-associative.

Since outfix-guided (prefix-guided, suffix-guided, respectively) insertion is
non-associative we define the $(i+1)$st iterated operation, analogously as was
done with iterated overlap assembly [5], by inserting to a string of the $i$th
iteration another string of the $i$th iteration.

###### Definition 3.5

For a language $L$ define inductively

$\mathbb{OGI}^{(0)}(L)=L,\;\;\mbox{ and
}\mathbb{OGI}^{(i+1)}(L)=\mathbb{OGI}^{(i)}(L)\leftarrow\mathbb{OGI}^{(i)}(L),\;\;i\geq
0.$

The outfix-guided insertion closure of $L$ is

$\mathbb{OGI}^{*}(L)=\bigcup_{i=0}^{\infty}\mathbb{OGI}^{(i)}(L).$

The prefix-guided insertion closure of $L$, $\mathbb{PGI}^{*}(L)$,
(respectively, suffix-guided insertion closure of $L$, $\mathbb{SGI}^{*}(L)$)
is defined as above by replacing $\leftarrow$ everywhere with
$\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}$ (respectively, with
$\stackrel{{\scriptstyle\rm sgi}}{{\leftarrow}}$).

Recall that the left-iterated non-overlapping insertion [15] discussed above
uses two argument languages, and the same is true for the left- and right-
iterated outfix-guided insertion introduced below in Definition 3.6. One of
the arguments can be viewed as the “target” of the insertions, and the other
as the “source” of the inserted strings. The unrestricted insertion closures
of Definition 3.5 are defined for one argument language because, roughly
speaking, the $i+1$st stage uses the $i$th stage both as the target and the
source of the insertion.

For talking about specific iterated outfix-guided insertions, we use the
notation $x\stackrel{{\scriptstyle[y]}}{{\Rightarrow}}z$ to indicate that
string $z$ is in $x\leftarrow y$, $x,y,z\in\Sigma^{+}$. A sequence of steps

$x\stackrel{{\scriptstyle[y_{1}]}}{{\Rightarrow}}z_{1}\stackrel{{\scriptstyle[y_{2}]}}{{\Rightarrow}}z_{2}\stackrel{{\scriptstyle[y_{3}]}}{{\Rightarrow}}\cdots\stackrel{{\scriptstyle[y_{m}]}}{{\Rightarrow}}z_{m},\;\;m\geq
1,$

is called a derivation of $z_{m}$ from $x$.

When we want to specify the matched substrings, they are indicated by
underlining. If $x=x_{1}uvx_{2}$ derives $z$ by inserting $uyv$ (where $u$ and
$v$ are the matched prefix and suffix, respectively,) this is denoted

$x_{1}\underline{u}\underline{v}x_{2}\stackrel{{\scriptstyle[\underline{u}y\underline{v}]}}{{\Rightarrow}}z.$

Also, sometimes underlining is done only in the inserted string if this makes
it clear what must be the matched substrings in the original string.

By a trivial derivation step we mean a derivation
$x\stackrel{{\scriptstyle[x]}}{{\Rightarrow}}x$ where $x$ is obtained from
itself by selecting the outfix to consist of the entire string $x$. Every
string of length at least two can be obtained from itself using a trivial
derivation step. This means, in particular, that for any language $L$,
$L-(\Sigma\cup\\{\varepsilon\\})\subseteq\mathbb{OGI}^{(1)}(L).$ The sets
$\mathbb{OGI}^{(i)}(L)$, $i\geq 1$, cannot contain strings of length less than
two and, consequently $\mathbb{OGI}^{(i)}(L)\subseteq\mathbb{OGI}^{(i+1)}(L)$,
for all $i\geq 1$.

Definition 3.5 iterates the outfix-guided insertion by inserting a string from
the $i$th iteration of the operation into another string in the $i$th
iteration. Since the operation is non-associative we can define iterated
insertion in more than one way. The right one-sided iterated insertion of
$L_{2}$ into $L_{1}$ inserts in an outfix-guided way a string of $L_{2}$ into
$L_{1}$ and then iteratively inserts a string obtained in the process into
$L_{1}$. The left one-sided iterated outfix-guided insertion is defined
symmetrically. In fact, when considering iterated ordinary insertion, Kari
[15] uses a definition that we call left one-sided iterated insertion (and the
operation was defined as $\mathbb{LI}^{*}(L_{1},L_{2})$ above). Csuhaj-Varju
et al. [2] define iterated overlap assembly using right one-sided iteration of
the operation.

###### Definition 3.6

Let $L_{1}$ and $L_{2}$ be languages. The right one-sided iterated insertion
of $L_{2}$ into $L_{1}$ is defined inductively by setting
$\mathbb{ROGI}^{(0)}(L_{1},L_{2})=L_{2}$ and
$\mathbb{ROGI}^{(i+1)}(L_{1},L_{2})=L_{1}\leftarrow\mathbb{ROGI}^{(i)}(L_{1},L_{2})$,
$i\geq 0$. The right one-sided insertion closure of $L_{2}$ into $L_{1}$ is
$\mathbb{ROGI}^{*}(L_{1},L_{2})=\bigcup_{i=0}^{\infty}\mathbb{ROGI}^{(i)}(L_{1},L_{2}).$

The left one-sided iterated insertion of $L_{2}$ into $L_{1}$ is defined
inductively by setting $\mathbb{LOGI}^{(0)}(L_{1},L_{2})=L_{1}$ and
$\mathbb{LOGI}^{(i+1)}(L_{1},L_{2})=\mathbb{LOGI}^{(i)}(L_{1},L_{2})\leftarrow
L_{2}$, $i\geq 0$. The left one-sided insertion closure of $L_{2}$ into
$L_{1}$ is
$\mathbb{LOGI}^{*}(L_{1},L_{2})=\bigcup_{i=0}^{\infty}\mathbb{LOGI}^{(i)}(L_{1},L_{2}).$

Note that for any language $L$,
$\mathbb{OGI}^{(1)}(L)=\mathbb{LOGI}^{(1)}(L,L)=\mathbb{ROGI}^{(1)}(L,L)=L\leftarrow
L.$

The iterated version of unrestricted outfix-guided insertion is considerably
more general than the one-sided variants. For any language $L$,
$\mathbb{ROGI}^{*}(L,L)$ and $\mathbb{LOGI}^{*}(L,L)$ are always included in
$\mathbb{OGI}^{*}(L)$ and, in general, the inclusions can be strict.

###### Example 3.7

Let $\Sigma=\\{a,b,c\\}$ and $L_{1}=\\{aacc\\}$, $L_{2}=\\{abc\\}$. Now
$\mathbb{ROGI}^{*}(L_{1},L_{2})=a^{+}bc^{+}.$ For example, by inserting $abc$
into $aacc$ derives $aabcc$:

$a\underline{ac}c\stackrel{{\scriptstyle[\underline{a}b\underline{c}]}}{{\Rightarrow}}aabcc.$
(1)

A right one-sided iterated insertion of $L_{2}$ into $L_{1}$ could then be
continued, for example, as
$a\underline{acc}\stackrel{{\scriptstyle[\underline{a}ab\underline{cc}]}}{{\Rightarrow}}aaabcc$.
In this way right one-sided derivations can generate all strings of
$a^{+}bc^{+}$. Since all inserted strings must contain the symbol $b$, the
first matched part must always belong to $a^{+}$ and the second matched part
must belong to $c^{+}$. This means that
$\mathbb{ROGI}^{*}(L_{1},L_{2})\subseteq a^{+}bc^{+}$.

On the other hand, $\mathbb{LOGI}^{*}(L_{1},L_{2})=\\{aabcc,aacc\\}.$ In a
left one-sided iterated insertion of $L_{2}$ into $L_{1}$, the only non-
trivial derivation step is (1).

By denoting $L_{3}=L_{1}\cup L_{2}$, it can be verified that

$\mathbb{OGI}^{*}(L_{3})=\mathbb{ROGI}^{*}(L_{3},L_{3})=\mathbb{LOGI}^{*}(L_{3},L_{3})=a^{+}bc^{+}\cup
a^{2}a^{*}c^{2}c^{*}.$

The next example illustrates that unrestricted outfix-guided insertion closure
of a language $L^{\prime}$ can be larger than
$\mathbb{LOGI}^{*}(L^{\prime},L^{\prime})$. The language $L$ used in the proof
of Theorem 4.6 in the next section gives an example where the unrestricted
insertion closure is larger than $\mathbb{ROGI}^{*}(L,L)$ (as explained before
Proposition 4.13).

###### Example 3.8

Let $\Sigma=\\{a,b,c,d,e,f\\}$ and $L^{\prime}=\\{abce,bcde,acdef\\}$. We note
that
$a\underline{bce}\stackrel{{\scriptstyle[\underline{bc}d\underline{e}]}}{{\Rightarrow}}abcde$.
Furthermore, it is easy to verify that by outfix-guided inserting strings of
$L^{\prime}$ into $L^{\prime}\cup\\{abcde\\}$ one cannot produce more strings
and, thus,
$\mathbb{LOGI}^{*}(L^{\prime},L^{\prime})=L^{\prime}\cup\\{abcde\\}$. On the
other hand, we have

$\underline{acde}f\stackrel{{\scriptstyle[\underline{a}b\underline{cde}]}}{{\Rightarrow}}abcdef\in\mathbb{OGI}^{(2)}(L^{\prime}).$

##  4 Outfix-Guided Insertion and Regular Languages

As can be expected, the family of regular languages is closed under the
outfix-guided (prefix-guided, suffix-guided, respectively) insertion
operation. On the other hand, the answer to the question whether regular
languages are closed under iterated outfix-guided insertion seems less clear.
From Kari [15] we recall that it is easy to construct examples that establish
the non-closure of regular languages under iterated non-overlapping insertion.
Using variants of such examples we see that the prefix-guided (or suffix-
guided) insertion closure of a singleton language may be non-regular.

On the other hand, analogous straightforward counter-examples do not work for
the unrestricted outfix-guided insertion closure. Using a more involved
construction we establish that the outfix-guided insertion closure of a finite
language need not be regular. The non-closure of regular languages under right
one-sided insertion closure is established by a more straightforward
construction (Proposition 4.13).

We begin by showing that regular languages are closed under non-iterated
outfix-guided insertion. The proof is not surprising but we give an explicit
construction because, essentially, the same construction will be used to show
in Theorem 5.3 that the outfix-guided insertion of a regular (respectively,
context-free) language into a context-free (respectively, regular) language is
always context-free, and for the polynomial time algorithm to decide whether
the language recognized by a DFA is closed under outfix-guided insertion in
section 6.

###### Lemma 4.1

If $L_{1}$ and $L_{2}$ are regular, then so is $L_{1}\leftarrow L_{2}$.

Proof.  Let $L_{1}$ be recognized by an NFA $A=(\Sigma,Q,\delta,q_{0},F_{A})$
and $L_{2}$ be recognized by an NFA $B=(\Sigma,P,\gamma,p_{0},F_{B})$. Denote
$\overline{Q}=\\{\overline{q}\mid q\in Q\\}$ and
$\overline{P}=\\{\overline{p}\mid p\in P\\}$. Here $Q\cup P$ is disjoint with
$\overline{Q}\cup\overline{P}$ and $\clubsuit$, $\heartsuit$ are new symbols
not occurring in any of the sets.

For the language $L_{1}\leftarrow L_{2}$ we construct an NFA
$C=(\Sigma,R,\omega,r_{0},F_{C})$ where

$R=Q\times(P\cup\overline{P}\cup\\{\clubsuit,\heartsuit\\})\cup\overline{Q}\times
P,$ $F_{C}=\\{(q,\overline{p})\mid q\in F_{A},p\in
F_{B}\\}\cup\\{(q,\heartsuit)\mid q\in F_{A}\\},$

$r_{0}=(q_{0},\clubsuit)$, and for defining the transitions of $\omega$ let
$b$ be an arbitrary symbol of $\Sigma$. We set

  1. (i)

for $q\in Q$: $\omega((q,\clubsuit),b)=\\{(q^{\prime},\clubsuit)\mid
q^{\prime}\in\delta(q,b)\\}\cup\\{(q^{\prime},p^{\prime})\mid
q^{\prime}\in\delta(q,b),p^{\prime}\in\gamma(p_{0},b)\\}$,

  2. (ii)

for $q\in Q$, $p\in P$: $\omega((q,p),b)=\\{(q^{\prime},p^{\prime})\mid
q^{\prime}\in\delta(q,b),p^{\prime}\in\gamma(p,b)\\}\cup\\{(\overline{q},p^{\prime})\mid
p^{\prime}\in\gamma(p,b)\\}\cup\\{(q^{\prime},\overline{p^{\prime}})\mid
q^{\prime}\in\delta(q,b),p^{\prime}\in\gamma(p,b)\\}$,

  3. (iii)

for $q\in Q$, $p\in P$:
$\omega((\overline{q},p),b)=\\{\overline{q},p^{\prime})\mid
p^{\prime}\in\gamma(p,b)\\}\cup\\{(q^{\prime},\overline{p^{\prime}})\mid
q^{\prime}\in\delta(q,b),p^{\prime}\in\gamma(p,b)\\}$,

  4. (iv)

for $q\in Q$, $p\in P$:
$\omega((q,\overline{p}),b)=\\{(q^{\prime},\overline{p^{\prime}})\mid
q^{\prime}\in\delta(q,b),p^{\prime}\in\gamma(p,b)\\}\cup Z_{p}$, where

$Z_{p}=\begin{cases}\\{(q^{\prime},\heartsuit)\mid
q^{\prime}\in\delta(q,b)\\}&\text{ if }p\in F_{B},\\\ \emptyset&\text{ if
}p\not\in F_{B},\end{cases}$

  5. (v)

for $q\in Q$: $\omega((q,\heartsuit),b)=\\{(q^{\prime},\heartsuit)\mid
q^{\prime}\in\delta(q,b)\\}$.

All transitions not listed above are undefined.

We begin by verifying that $L(A)\leftarrow L(B)\subseteq L(C)$. Consider a
string $w=x_{1}uzvx_{2}$ where $x_{1}uvx_{2}\in L(A)$ and $uzv\in L(B)$,
$u,v\neq\varepsilon$. Roughly speaking, $C$ uses the states of
$Q\times\\{\clubsuit\\}$ to process the prefix $x_{1}$, the states of $Q\times
P$ to process the following substring $u$, the states of $\overline{Q}\times
P$ to process the substring $z$, the states of $Q\times\overline{P}$ to
process the substring $v$, and the states of $Q\times\\{\heartsuit\\}$ to
process the suffix $x_{2}$. Note that according to rules (ii), on states of
$Q\times P$ the NFA simulates $A$ in the first component and $B$ in the second
component of the states. According to rules (iii), on states of
$\overline{Q}\times P$, the NFA $C$ simulates only $B$ in the second
component, and according to rules (iv), on states of $Q\times\overline{P}$ the
NFA $C$ simulates again both $A$ and $B$ (in the first and second component of
the state of $C$, respectively).

In more detail, consider an accepting computation ${\rm
comp_{A}}(x_{1}uvx_{2})$ of $A$ on $x_{1}uvx_{2}$ that reaches state
$q_{x_{1}}$ (respectively, $q_{u}$, $q_{v}$, $q_{x_{2}}$) after reading the
prefix $x_{1}$ (respectively, $x_{1}u$, $x_{1}uv$, $x_{1}uvx_{2}$). An
accepting computation of $C$ first reads $x_{1}$ using rules (i) and
simulating the computation ${\rm comp}_{A}(x_{1}uvx_{2})$ of $A$ on the prefix
$x_{1}$, thus ending in state $(q_{x_{1}},\clubsuit)$.

When reading the first symbol $b_{1}$ of $u$, again using a rule (i) the
computation of $C$ goes to a state $(q^{\prime},p^{\prime})$ where
$q^{\prime}\in\delta(q_{x_{1}},b_{1})$ and the second component begins to
simulate an accepting computation of $B$ on $uzv$ in a state
$p^{\prime}\in\gamma(p_{0},b_{1})$. The computation nondeterministically
guesses when it sees the first symbol of $z$, and using rules (ii) enters a
state $(\overline{q_{u}},p^{\prime})$ where $p^{\prime}$ is the state of $B$
in an accepting computation on $uzv$ after reading the first symbol of $z$. If
$z=\varepsilon$, the computation guesses when it sees the first symbol $b_{2}$
of $v$ and using the “third option” in the rules (ii), $C$ goes to a state
$(q^{\prime},p^{\prime})$ where $q^{\prime}\in\delta(q_{u},b_{2})$ and
$p^{\prime}$ is a state that can be reached by $B$ after reading $ub_{2}$.

The computation processes the substring $z$ in a state of
$\\{\overline{q_{u}}\\}\times P$ using rules (iii) and simulating the
computation of $B$ in the second component. When the computation guesses that
it sees the first symbol $b_{2}$ of $v$, using the “second part” of the rules
(iii) the NFA $C$ goes to a state $(q^{\prime},p^{\prime})$ where
$q^{\prime}\in\delta(q_{u},b_{2})$ and $p^{\prime}$ is a state that can be
reached by $B$ after reading the prefix $uzb_{2}$. Then, according to rules
(iv), $C$ simulates the computation ${\rm comp}_{A}(x_{1}uvx_{2})$ in the
first component of the state and $B$ in the second component of the state.
Always when the second component is an element of $F_{B}$, according to rules
(iv), the computation may enter a state of the form $(q^{\prime},\heartsuit)$
that indicates that it has finished reading the substring $uzv$.

The remaining computation, using rules (v), simulates the computation ${\rm
comp}_{A}(x_{1}uvx_{2})$ of $A$ on the first component of the states. The
choice of the final states then guarantees that $C$ accepts in the state
$(q_{x_{2}},\heartsuit)$. If $x_{2}=\varepsilon$, then the computation of $C$
ends in an accepting state $(q_{v},p_{f})$ where $p_{f}\in F_{B}$ is the state
at the end of the simulated computation of $B$ on $uzv$.

For the converse inclusion we note that the definition of the transitions of
$\omega$ guarantees that any computation of $C$ ending in an accepting state,
must have five parts $P_{1}$, $P_{2}$, $P_{3}$, $P_{4}$ and $P_{5}$, where
$P_{1}$ uses states of $Q\times\\{\clubsuit\\}$, $P_{2}$ uses states of
$Q\times P$, $P_{3}$ uses states of $\overline{Q}\times P$, $P_{4}$ uses
states of $Q\times\overline{P}$ and $P_{5}$ uses states of
$Q\times\\{\heartsuit\\}$. The part $P_{3}$ may be empty if, according to
rules (ii), the computation jumps directly from a state of $P_{2}$ to a state
of $P_{4}$ and the part $P_{5}$ may be empty if the computation $P_{4}$ ends
in an accepting state of the form $(q,\overline{p})$ ($q\in F_{A}$, $p\in
F_{B}$).

Since states of $P_{1}$ and $P_{5}$ simulate only a computation of $A$, states
of $P_{3}$ simulate only a computation of $B$ and states of $P_{2}$ and
$P_{4}$ simulate both a computation of $A$ and a computation of $B$, it is
easy to verify that $C$ can have accepting computations only on strings of
$L(A)\leftarrow L(B)$.

The result of Lemma 4.1 extends easily using induction:

###### Proposition 4.2

Suppose $L_{1}$ and $L_{2}$ are regular languages. Then, for all $i\geq 0$,
$\mathbb{OGI}^{(i)}(L_{1})$, $\mathbb{ROGI}^{(i)}(L_{1},L_{2})$ and
$\mathbb{LOGI}^{(i)}(L_{1},L_{2})$ are regular.

A simplified variant of the proof of Lemma 4.1 allows us to show that the
prefix-guided (or suffix-guided) insertion of a regular language into a
regular language is regular. We leave the proof as an exercise.

###### Proposition 4.3

If $L_{1}$ and $L_{2}$ are regular languages, then so are
$L_{1}\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}L_{2}$ and
$L_{1}\stackrel{{\scriptstyle\rm sgi}}{{\leftarrow}}L_{2}$.

Iterated prefix-guided or suffix-guided insertion does not preserve
regularity.

###### Proposition 4.4

There exist singleton languages $L_{1}$ and $L_{2}$ such that
$\mathbb{PGI}^{*}(L_{1})$ and $\mathbb{SGI}^{*}(L_{2})$ are non-regular.

Proof.  Choose $L_{1}=aab$. We claim that

$\mathbb{PGI}^{*}(aab)\cap a^{*}b^{*}=\\{a^{i}b^{j}\mid 2\leq i\leq j+1\\}.$
(2)

To establish the inclusion from right to left we note that, for all $i\geq 2$,
$a^{i+1}b^{i+2}\in a^{i}b^{i+1}\stackrel{{\scriptstyle\rm
pgi}}{{\leftarrow}}aab$. Furthermore, into strings of the form $a^{i}b^{j}$
($i\geq 2$) one can always add exactly one $b$ by inserting $aab$ where prefix
$aa$ is matched with the last $a$’s of $a^{i}b^{j}$.

Second we verify the inclusion from left to right in (2). Denote
$Z=\\{a^{i}b^{j}\mid 2\leq i\leq j+1\\}$. We note that derivations of strings
in $\mathbb{PGI}^{*}(aab)$ belonging to $a^{*}b^{*}$ can use only strings in
$a^{*}b^{*}$ because if $w_{1}\not\in a^{*}b^{*}$ or $w_{2}\not\in a^{*}b^{*}$
then any string in $w_{1}\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}w_{2}$
has an occurrence of $b$ preceding an occurence of $a$. It is clear that for
$u_{1},u_{2}\in Z$, all strings in $(u_{1}\stackrel{{\scriptstyle\rm
pgi}}{{\leftarrow}}u_{2})\cap a^{*}b^{*}$ must be in $Z$. Note that the
matched prefix of $u_{2}$ must contain at least one $a$ and thus the insertion
adds to $u_{1}$ at least as many $b$’s as $a$’s.

Since the language $Z$ is non-regular, (2) implies that
$\mathbb{PGI}^{*}(aab)$ is non-regular.

A completely symmetric argument establishes that $\mathbb{SGI}^{*}(abb)$ is
non-regular.

It seems difficult to extend the proof of Lemma 4.1 for outfix-guided
insertion closure because on strings with iterated insertions, the
computations on corresponding prefix-suffix pairs can, in general, depend on
each other and when processing a part inserted in between, an NFA would need
to keep track of such pairs, as opposed to simply keep track of a set of
states. On the other hand, constructions as in the proof of Proposition 4.4
rely on the property that the matched substrings are all either prefixes or
all suffixes of the inserted strings and this type of straightforward
constructions do not yield a regular language whose outfix-guided insertion
closure is non-regular.

Next we show that regular languages, indeed, are not closed under iterated
outfix-guided insertion. For the construction we use the following technical
lemma.

###### Lemma 4.5

Let $\Sigma=\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\\}$ and define

$L_{1}=\\{a_{3}a_{1}a_{2}b_{1},\;\;a_{2}b_{2}b_{1}b_{3},\;\;a_{1}a_{2}a_{3}b_{2},\;\;a_{3}b_{3}b_{2}b_{1},\;\;a_{2}a_{3}a_{1}b_{3},\;\;a_{1}b_{1}b_{3}b_{2}\\}.$

Then $L_{1}\leftarrow L_{1}=L_{1}$.

Proof.  The inclusion from right to left follows from the observation that any
string $w$ of length at least two is a non-trivial outfix of itself and,
consequently $w$ can be inserted into itself to produce $w$ as a result.

For the converse inclusion we verify that for all $x,y\in L_{1}$, if $y\neq
x$, then $y$ cannot be outfix-guided inserted into $x$ and $x$ can be outfix-
guided inserted into itself only in the trivial way of using as matching parts
a non-empty prefix $x_{1}$ and a non-empty suffix $x_{2}$ such that
$x_{1}x_{2}=x$. The second claim is obvious because each string of $L_{1}$
consists of 4 different symbols.

Consider now $x,y\in L_{1}$, $x\neq y$. For the sake of contradiction suppose
that $w\in x\leftarrow y$ and that $w$ is obtained by matching substrings $u$
and $v$ of $x$ with a prefix and a suffix of $y$, respectively. The substrings
$u$ and $v$ cannot both consist of symbols $a_{i}$, $1\leq i\leq 3$, because
if $x$ and $y$ both contain more than one symbol $a_{i}$, they must end with
symbols $b_{j_{1}}$ and $b_{j_{2}}$, $j_{1}\neq j_{2}$. Using a symmetric
argument we observe that $u$ and $v$ cannot both consist of symbols $b_{i}$,
$1\leq i\leq 3$.

The remaining possibility is that the first matched part $u$ consists of (one
or more) symbols $a_{i}$ and the second matched part $v$ consists of (one or
more) symbol $b_{j}$. For simplicity in the following discussion we assume
that $v$ begins with $b_{1}$. The definition of $L_{1}$ is symmetric, and an
analogous argument works when the first symbol of $v$ is $b_{2}$ or $b_{3}$.

Now $uv$ must be a substring of $x$. This means that the last symbol of $u$
can be $a_{2}$ if $x=a_{3}a_{1}a_{2}b_{1}$ or $a_{1}$ if
$x=a_{1}b_{1}b_{3}b_{2}$. Besides the string $a_{3}a_{1}a_{2}b_{1}$ the only
other string of $L_{1}$ where $a_{2}$ occurs before $b_{1}$ is
$a_{2}b_{2}b_{1}b_{3}$. The string $a_{2}b_{2}b_{1}b_{3}$ cannot be inserted
into $x=a_{3}a_{1}a_{2}b_{1}$ because the last symbol $b_{3}$ would be
“outside” of $x$.

As the remaining case consider then the possibility $x=a_{1}b_{1}b_{3}b_{2}$.
The only string of $L_{1}-\\{x\\}$ where $a_{1}$ occurs before $b_{1}$ is
$a_{3}a_{1}a_{2}b_{1}$ and again this cannot be inserted into $x$ because the
first symbol $a_{3}$ would be outside of $x$.

###### Theorem 4.6

There exists a finite language $L$ such that $\mathbb{OGI}^{*}(L)$ is non-
regular.

Proof.  Let $\Sigma=\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\\}$ and define
$L\subseteq(\Sigma\cup\\{\$\\})^{*}$ as

$L=\\{\$a_{3}a_{1}b_{1}b_{3}\$,\;a_{3}a_{1}a_{2}b_{1},\;a_{2}b_{2}b_{1}b_{3},\;a_{1}a_{2}a_{3}b_{2},\;a_{3}b_{3}b_{2}b_{1},\;a_{2}a_{3}a_{1}b_{3},\;a_{1}b_{1}b_{3}b_{2}\\}.$

Note that $L-\\{\$a_{3}a_{1}b_{1}b_{3}\$\\}$ is equal to the language $L_{1}$
from Lemma 4.5. Our construction is based on an idea that the only way to
produce new strings in $\mathbb{OGI}^{*}(L)$ is to insert into strings
obtained from $\$a_{3}a_{1}b_{1}b_{3}\$$ cyclically copies of the strings of
$L_{1}$. For ease of discussion we introduce names for the strings of $L_{1}$:

$\displaystyle
y_{1}=a_{3}a_{1}a_{2}b_{1},\;\;y_{2}=a_{2}b_{2}b_{1}b_{3},\;\;y_{3}=a_{1}a_{2}a_{3}b_{2},\;\;y_{4}=a_{3}b_{3}b_{2}b_{1},$
$\displaystyle y_{5}=a_{2}a_{3}a_{1}b_{3},\;\;y_{6}=a_{1}b_{1}b_{3}b_{2}.$

For specifying the language $\mathbb{OGI}^{*}(L)$ we define the finite set

$S_{\rm
middle}=\\{a_{1}b_{1},\,a_{1}a_{2}b_{1},a_{1}a_{2}b_{2}b_{1},\,a_{1}a_{2}a_{3}b_{2}b_{1},\,a_{1}a_{2}a_{3}b_{3}b_{2}b_{1},\,a_{1}a_{2}a_{3}a_{1}b_{3}b_{2}b_{1}\\}.$

We claim that

$\mathbb{OGI}^{*}(L)=\\{\$a_{3}(a_{1}a_{2}a_{3})^{i}z(b_{3}b_{2}b_{1})^{i}b_{3}\$\mid
i\geq 0,\;z\in S_{\rm middle}\\}.$ (3)

To establish the inclusion from right to left, we note that

$\displaystyle\$a_{3}a_{1}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{1}]}}{{\Rightarrow}}\$a_{3}a_{1}a_{2}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{2}]}}{{\Rightarrow}}\$a_{3}a_{1}a_{2}b_{2}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{3}]}}{{\Rightarrow}}\$a_{3}a_{1}a_{2}a_{3}b_{2}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{4}]}}{{\Rightarrow}}$
$\displaystyle\$a_{3}a_{1}a_{2}a_{3}b_{3}b_{2}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{5}]}}{{\Rightarrow}}\$a_{3}a_{1}a_{2}a_{3}a_{1}b_{3}b_{2}b_{1}b_{3}\$\stackrel{{\scriptstyle[y_{6}]}}{{\Rightarrow}}\$a_{3}a_{1}a_{2}a_{3}a_{1}b_{1}b_{3}b_{2}b_{1}b_{3}\$=w_{1}.$

The first five insertions generate the strings $\$a_{3}zb_{3}\$$, $z\in S_{\rm
middle}$, and the last string $w_{1}$ again has “middle part”
$a_{3}a_{1}b_{1}b_{3}$. By cyclically outfix-guided inserting the strings
$y_{1},\ldots,y_{6}$ into $w_{1}$ we get all strings
$\$a_{3}(a_{1}a_{2}a_{3})z(b_{3}b_{2}b_{1})b_{3}\$$, $z\in S_{\rm middle}$,
and the string
$\$a_{3}(a_{1}a_{2}a_{3})^{2}a_{1}b_{1}(b_{3}b_{2}b_{1})^{2}b_{3}\$$. By
simple induction it follows that $\mathbb{OGI}^{*}(L)$ contains the right side
of (3).

To establish the converse inclusion, we verify that all strings obtained by
iterated outfix-guided insertion from strings of $L$ must be obtained as
above, that is, all non-trivial derivations producing new strings must be as
above.

Since $\$a_{3}a_{1}b_{1}b_{3}\$$ is the only string in $L$ containing symbols
$ and they occur as the first and the last symbol, it is clear that all
strings in $\mathbb{OGI}^{*}(L)$ containing symbols $ must be in
$\$\Sigma^{*}\$$. A string of $\$\Sigma^{*}\$$ cannot be outfix-guided
inserted to any string not containing symbols $ and a string of
$\$\Sigma^{*}\$$ can be outfix-guided inserted into another string of
$\$\Sigma^{*}\$$ only using a trivial derivation step.

By Lemma 4.5 we know that strings of $L_{1}$ cannot be outfix-guided inserted
into other strings of $L_{1}$.

We have verified that the set

$L_{\rm gen}=\\{\$a_{3}(a_{1}a_{2}a_{3})^{i}z(b_{3}b_{2}b_{1})^{i}b_{3}\$\mid
i\geq 0,\;z\in S_{\rm middle}\\}$

is included in $\mathbb{OGI}^{*}(L)$ and strings of $L_{\rm gen}$ can be
inserted into strings of $L_{\rm gen}$ only in a trivial way. To complete the
proof it remains to verify that inserting strings of $L_{1}$ into $L_{\rm
gen}$ does not produce additional strings, that is, $L_{\rm gen}\leftarrow
L_{1}\subseteq L_{\rm gen}$.

It is impossible to insert $a_{3}a_{1}a_{2}b_{1}$ into a string of $L_{\rm
gen}$ using an outfix obtained from $a_{3}$ and $a_{2}b_{1}$ because in
strings of $L_{\rm gen}$ the symbols $a_{3}$ and $a_{2}$ do not occur
consecutively. The same applies to the other five strings
$y_{2},\ldots,y_{6}\in L_{1}$: we cannot insert $y_{j}$ into $L_{\rm gen}$
using an outfix where the prefix ends and the suffix begins with a symbol of
$\\{a_{1},a_{2},a_{3}\\}$ (respectively, with a symbol of
$\\{b_{1},b_{2},b_{3}\\}$).

The other non-trivial possibilities are that we insert $a_{3}a_{1}a_{2}b_{1}$
into a string of $L_{\rm gen}$ using an outfix $uv$ where $u$ is either
$a_{3}$ or $a_{3}a_{1}$ and $v=b_{1}$. The choice $u=a_{3}$, $v=b_{1}$ is not
possible because $a_{3}b_{1}$ is not a substring of a string in $L_{\rm gen}$.
The insertion using outfix $a_{3}a_{1}b_{1}$ can be done only to a string of
the from $\$a_{3}(a_{1}a_{2}a_{3})^{i}a_{1}b_{1}(b_{3}b_{2}b_{1})^{i}b_{3}\$$,
$i\geq 0$ and it produces
$\$a_{3}(a_{1}a_{2}a_{3})^{i}a_{1}a_{2}b_{1}(b_{3}b_{2}b_{1})^{i}b_{3}\$\in
L_{\rm gen}$. Using symmetry of the definition of $L_{1}$, the argument for
the other five strings of $L_{1}$ is completely analogous.

This establishes (3) and the non-regularity of $\mathbb{OGI}^{*}(L)$.

We conjecture that the iterated outfix-guided insertion closure of a regular
language need not be even context-free. However, a construction of such a
language would seem to be considerably more complicated than the construction
used in the proof of Theorem 4.6.

###### Open problem 4.7

Find a regular (or a finite) language $L$ such that $\mathbb{OGI}^{*}(L)$ is
not context-free.

Contrasting the result of Theorem 4.6 we show that unary regular languages are
closed under iterated outfix-guided insertion. The construction is based on a
technical lemma which shows that, for unary languages, outfix-guided insertion
closure can be represented as a variant of the iterated overlap assembly [2,
5].

###### Definition 4.8

Let $x,y\in\Sigma^{*}$. The 2-overlap catenation of $x$ and $y$,
$x\overline{\odot}^{2}y$, is defined as

$x\overline{\odot}^{2}y=\\{z\in\Sigma^{+}\mid(\exists
u,w\in\Sigma^{*})(\exists v\in\Sigma^{\geq 2})\;x=uv,y=vw,z=uvw\\}.$

2-overlap catenation is extended in the natural to an operation on languages.
For $L\subseteq\Sigma^{*}$, we define inductively $2\mathbb{OC}^{(0)}(L)=L$
and $2\mathbb{OC}^{(i+1)}(L)=$
$2\mathbb{OC}^{(i)}(L)\overline{\odot}^{2}2\mathbb{OC}^{(i)}(L)$, $i\geq 0$.
The 2-overlap catenation closure of $L$ is
$2\mathbb{OC}^{*}(L)=\bigcup_{i=0}^{\infty}2\mathbb{OC}^{(i)}(L).$

Due to commutativity of unary languages we get the following property which
will be crucial for establishing closure of unary regular languages under
outfix-guided insertion closure.

###### Lemma 4.9

If $x,y\in a^{*}$ are unary strings, then $x\leftarrow
y=x\overline{\odot}^{2}y.$

Proof.  Consider $w\in(x\leftarrow y)$, that is, we can write
$w=x_{1}uzvx_{2}$, where $x=x_{1}uvx_{2}$, $y=uzv$ and $u,v\neq\varepsilon$.
Since concatenation of unary strings is commutative, we have

$w=x_{1}x_{2}uvz,\mbox{ where }x=x_{1}x_{2}uv,\;\;y=uvz.$

This establishes that $w\in x\overline{\odot}^{2}y$.

Conversely, consider $z\in x\overline{\odot}^{2}y$, that is, $z=uvw$ where
$x=uv$, $y=vw$ and $|v|\geq 2$. Write $v=v_{1}v_{2}$ where
$v_{1},v_{2}\in\Sigma^{+}$. Now, again relying just on commutativity of unary
concatenation, $z=uv_{1}wv_{2}\in x\leftarrow y$.

###### Corollary 4.10

If $L$ is a unary language then $\mathbb{OGI}^{*}(L)=2\mathbb{OC}^{*}(L)$.

The 2-overlap closure of a regular language is always regular. The
construction does not depend on a language being unary, so we state the result
for regular languages over an arbitrary alphabet. Csuhaj-Varju et al. [2] have
shown that iterated overlap assembly preserves regularity. The proof of Lemma
4.11 is inspired by Theorem 4 of [2] but does not follow from it because [2]
defines iteration of operations as right one-sided iteration and, furthermore,
2-overlap catenation has an additional length restriction on the overlapping
strings.

###### Lemma 4.11

The 2-overlap catenation closure of a regular language is regular.

Proof.  Consider a regular language $L$ recognized by an NFA
$A=(\Sigma,Q,\delta,q_{0},F)$. We construct for the language
$2\mathbb{OC}^{*}(L)$ an NFA
$B=(\Sigma,2^{Q},\gamma,\\{q_{0}\\},2^{F}-\\{\emptyset\\})$ where the
transitions of $\gamma$ are defined below.

For $\emptyset\neq P\subseteq Q$ and $b\in\Sigma$ define

$\displaystyle\gamma(P,b)$ $\displaystyle=\\{$
$\displaystyle\;(\delta(P,b)-X_{\rm rem})\cup Y_{\rm add}\;\mid\;X_{\rm
rem}\subseteq F,\;\delta(P,b)-X_{\rm rem}\neq\emptyset,$ $\displaystyle Y_{\rm
add}\subseteq\delta(q_{0},b)\;\;\\}.$

States of $B$ are subsets of $Q$ and the transition relation is
nondeterministic: $\gamma(P,b)$ is a collection of subsets of $Q$.

The computation of $B$ simulates multiple computations of $A$. When reading a
symbol $b\in\Sigma$, the NFA $B$ can guess that this occurrence of $b$ begins
(one or more) 2-overlap-catenated strings, and adds to the simulated
computations the corresponding states of $\delta(q_{0},b)$. Always when a
simulated computation reaches a state of $F$, the NFA $B$ can
nondeterministically guess that $b$ ends a string that is 2-overlap
concatenated with another string. This is done by the choice of the set
$X_{\rm rem}\subseteq F$ in the definition of $\gamma$. Note that the
condition $\delta(P,b)-X_{\rm rem}\neq\emptyset$ guarantees that at least one
of the simulated computations that were originated before reading $b$ must
remain alive: this enforces that the overlap with the new computations indeed
will be at least two.

It is clear that, by always choosing the sets $X_{\rm rem}$ and $Y_{\rm add}$
correctly, $B$ has a computation on an arbitrary string in $w\in
2\mathbb{OC}^{*}(L(A))$ that ends in a state $P\subseteq F$, $P\neq\emptyset$.
The set $P$ consists of final states of $A$ that appear in an accepting
computation in all strings that in the representation of $w$ as a 2-overlap
catenation of strings of $L(A)$ are a suffix of $w$. Note that the
construction works also if $w$ has length one: in this case $w$ must be an
element of $L(A)$.

To verify the converse inclusion $L(B)\subseteq 2\mathbb{OC}^{*}(L(A))$, we
note that, in general, some parts of computations of $B$ need not simulate any
iterated 2-overlap concatenation of a set of strings of $L(A)$. For example,
if $A$ accepts both $xyz$ and $y$ where $|y|\geq 2$, on the string $xyz$ the
NFA $B$ can begin a second computation $C_{2}$ when reading the first symbol
of $y$ and this computation then may end in a final state at the end of the
substring $y$. However, the existence of the superfluous computation $C_{2}$
cannot lead to new illegal computations because the transitions of $\gamma$
add new computations depending only on the input symbol and not on the current
state. (In the transitions of $\gamma$, the sets $Y_{\rm add}$ depend only on
the input symbol and the initial state of $A$.) Thus, the added superfluous
computations cannot cause $B$ to accept strings not in
$2\mathbb{OC}^{*}(L(A))$.

By Corollary 4.10 and Lemma 4.11 we have shown that unary regular languages
are closed under outfix-guided insertion closure, constrasting the result of
Theorem 4.6 for general regular languages.

###### Theorem 4.12

The outfix-guided insertion closure of a unary regular language is always
regular.

###  4.1 One-sided iterated outfix-guided insertion

The left and right one-sided insertion closures are restricted variants of the
general outfix-guided insertion closure, so Theorem 4.6 does not directly
imply the existence of regular languages $L_{1}$ and $L_{2}$ such that
$\mathbb{LOGI}^{*}(L_{1},L_{2})$ or $\mathbb{ROGI}^{*}(L_{1},L_{2})$ are non-
regular. Here we show that the one-sided outfix-guided insertion closures are
not, in general, regularity preserving. For the left-one one-sided outfix-
guided insertion closure the construction is similar to that used in the proof
of Theorem 4.6. However, this construction does not work for right one-sided
closure because if $L$ is the language used in the proof of Theorem 4.6, then
$\mathbb{ROGI}^{*}(L,L)$ is the finite language
$L\cup\\{\$a_{3}a_{1}a_{2}b_{1}b_{3}\$\\}$.

###### Proposition 4.13

There exist finite languages $L_{1}$, $L_{2}$, $L_{3}$ and $L_{4}$ such that
$\mathbb{ROGI}^{*}(L_{1},L_{2})$ and $\mathbb{LOGI}^{*}(L_{3},L_{4})$ are non-
regular.

Proof.  We consider first the right one-sided outfix-guided insertion closure.
Let $\Sigma=\\{\$,a,b,c,d\\}$ and choose $L_{2}=\\{a\$b\\}$,
$L_{1}=\\{acdb,cabd\\}$. Then

$\mathbb{ROGI}^{*}(L_{1},L_{2})=\\{(ca)^{i}\$(bd)^{i}\mid i\geq
0\\}\cup\\{a(ca)^{i}\$(bd)^{i}b\mid i\geq 0\\},$

which is non-regular. Inserting $a\$b$ into $cabd$ derives $ca\$bd$ and next,
in a right one-sided derivation, inserting the latter string into $acdb$
derives $aca\$bdb$. Continuing in this way we get a right one-sided derivation
for all strings in the set appearing on the right side of the equation.

The fact that $\mathbb{ROGI}^{*}(L_{1},L_{2})$ does not contain any additional
strings follows from the property of right one-sided iterated insertions: all
strings that are inserted into $L_{1}$ will have the marker $ and strings of
$L_{1}$ cannot be inserted into strings of $L_{1}$. We leave to the reader the
details of verifying that the inclusion holds from left to right.

The construction of the languages $L_{3}$ and $L_{4}$ for the left one-sided
outfix-guided insertion closure is obtained by modifying the language in the
proof of Theorem 4.6. Let $\Sigma=\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\\}$
and define $L_{3}=\\{\$a_{3}a_{1}b_{1}b_{3}\$\\}$ and

$L_{4}=\\{a_{3}a_{1}a_{2}b_{1},\;\;a_{2}b_{2}b_{1}b_{3},\;\;a_{1}a_{2}a_{3}b_{2},\;\;a_{3}b_{3}b_{2}b_{1},\;\;a_{2}a_{3}a_{1}b_{3},\;\;a_{1}b_{1}b_{3}b_{2}\\}.$

Denote

$L_{5}=\\{\$a_{3}(a_{1}a_{2}a_{3})^{i}z(b_{3}b_{2}b_{1})^{i}b_{3}\$\mid i\geq
0,\;z\in S_{\rm middle}\\},$

where $S_{\rm
middle}=\\{a_{1}b_{1},\;a_{1}a_{2}b_{1},\;a_{1}a_{2}b_{2}b_{1},\;a_{1}a_{2}a_{3}b_{2}b_{1},\;a_{1}a_{2}a_{3}b_{3}b_{2}b_{1},\;a_{1}a_{2}a_{3}a_{1}b_{3}b_{2}b_{1}\\}$.

From the proof of Theorem 4.6 it follows that

$\mathbb{LOGI}^{*}(L_{3},L_{4})=L_{5}.$

Note that the first part of the proof of Theorem 4.6 establishes that all
strings of $L_{5}$ are obtained by left one-sided iterated insertion of
$L_{4}$ into $\$a_{3}a_{1}b_{1}b_{3}\$$. Thus,
$L_{5}\subseteq\mathbb{LOGI}^{*}(L_{3},L_{4})$. The proof of Theorem 4.6 also
establishes that $\mathbb{OGI}^{*}(L_{3}\cup L_{4})=L_{5}$ and directly by the
definition of the iterated operations,
$\mathbb{LOGI}^{*}(L_{3},L_{4})\subseteq\mathbb{OGI}^{*}(L_{3}\cup L_{4})$.

##  5 Outfix-Guided Insertion and Context-Free Languages

It is well known that the family of context-free languages is closed under
ordinary insertion. We show that context-free languages are not closed under
outfix-guided (or prefix-guided, suffix-guided, respectively) insertion. This
contrasts also the corresponding result for regular languages from Lemma 4.1.

###### Theorem 5.1

There exists a context-free language $L$ such that $L\leftarrow L$ is not
context-free.

Proof.  Let $\Sigma=\\{\$,a,b,c\\}$. By choosing

$L=\\{\$a^{n}\$\$c^{n}\mid n\geq 1\\}\cup\\{\$a^{n}\$b^{n}\$\mid n\geq 1\\}$

we note that

$(L\leftarrow L)\cap\$a^{+}\$b^{+}\$c^{+}=\\{\$a^{n}\$b^{n}\$c^{n}\mid n\geq
1\\}.$

The claim follows since the intersection of a context-free language and a
regular language is always context-free [23].

The same language $L$ as in the proof of Theorem 5.1 can be used to establish
that context-free languages are not closed under prefix-guided insertion and
the reversal of $L$ can be used to establish non-closure under suffix-guided
insertion.

###### Corollary 5.2

There exist context-free languages $L_{1}$ and $L_{2}$ such that
$L_{1}\stackrel{{\scriptstyle\rm pgi}}{{\leftarrow}}L_{1}$ and
$L_{2}\stackrel{{\scriptstyle\rm sgi}}{{\leftarrow}}L_{2}$ are not context-
free.

On the other hand, the outfix-guided insertion of a regular (respectively,
context-free) language into a context-free (respectively, regular) language is
always context-free.

###### Theorem 5.3

If $L_{1}$ is context-free and $L_{2}$ is regular, then $L_{1}\leftarrow
L_{2}$ and $L_{2}\leftarrow L_{1}$ are context-free.

Proof.  Suppose $L_{1}$ is recognized by a nondeterministic PDA $M$ and
$L_{2}$ is recognized by an NFA $A$. By combining the finite state transitions
of $M$ and $A$ as in the proof of Lemma 4.1, and simultaneously simulating the
pushdown stack of $M$ we can construct a PDA $M_{1}$ for $L_{1}\leftarrow
L_{2}$. Always when $M_{1}$ makes a transition simulating a transition of $M$,
it makes a corresponding stack operation. On the other hand, transitions of
$M_{1}$ simulating only transitions of $A$ do not touch the stack. A PDA for
$L_{2}\leftarrow L_{1}$ is obtained by interchanging in the construction of
Lemma 4.1 the roles of $M$ and $A$.

The analogy of Theorem 5.3 does not hold for deterministic context-free
languages. Techniques for proving that a language is not deterministic
context-free are known already from [10].

###### Theorem 5.4

If $L_{1}$ is deterministic context-free and $L_{2}$ is regular, the languages
$L_{1}\leftarrow L_{2}$ or $L_{2}\leftarrow L_{1}$ need not be deterministic
context-free.

Proof.  First we show that there exist a DCFL $L_{1}$ and a regular language
$L_{2}$ such that $L_{1}\leftarrow L_{2}$ is not deterministic context-free.

Let $L_{1}=\\{cda^{i}b^{i}a^{j}\mid i,j\geq 1\\}\cup\\{ca^{i}b^{j}a^{j}\mid
i,j\geq 1\\}$ and $L_{2}=\\{cda\\}$. We can outfix-guided insert $cda$ in a
non-trivial way only into words of the form $ca^{i}b^{j}a^{j}$, which gives us

$L_{1}\leftarrow L_{2}=cd\cdot(\\{a^{i}b^{i}a^{j}\mid i,j\geq
1\\}\cup\\{a^{i}b^{j}a^{j}\mid i,j\geq 1\\}).$

From [10], we have that $L\subseteq(\Sigma-c)^{*}$ is a DCFL if and only if
$cL$ is a DCFL and that the language $(\\{a^{i}b^{i}a^{j}\mid i,j\geq
1\\}\cup\\{a^{i}b^{j}a^{j}\mid i,j\geq 1\\})$ is not deterministic. Thus,
$L_{1}\leftarrow L_{2}$ is not a DCFL.

Second, we show that there exist a regular language $L_{3}$ and a DCFL $L_{4}$
such that $L_{3}\leftarrow L_{4}$ is not deterministic context-free.

Let $L_{3}=(a^{*}bac)+(aba^{*})$ and $L_{4}=\\{b^{j}a^{j}c\mid j\geq
1\\}\cup\\{a^{i}b^{i}a^{2}\mid i\geq 1\\}$. We can insert words of the form
$b^{j}a^{j}c$ in a non-trivial way only into words of the form $a^{i}bac$.
This gives us the set $\\{a^{i}b^{j}a^{j}c\mid i,j\geq 1\\}$. Similarly, we
can only insert words of the form $a^{i}b^{i}a^{2}$ into words of the form
$aba^{2}a^{j}$, resulting in the set $\\{a^{i}b^{i}a^{j}\mid i\geq 1,j\geq
2\\}$. Thus,

$L_{3}\leftarrow L_{4}=\\{a^{i}b^{j}a^{j}c\mid i,j\geq
1\\}\cup\\{a^{i}b^{i}a^{j}\mid i\geq 1,j\geq 2\\},$

which is not deterministic context-free.

Theorem 5.1 raises the question how complex languages can be obtained from
context-free languages using iterated outfix-guided insertion. Note that if
$L_{1}$ and $L_{2}$ are context-free, it is easy to verify that
$L_{1}\leftarrow L_{2}$ is deterministic context-sensitive. Next we consider
the corresponding question for the insertion closures.

###### Proposition 5.5

If $L_{1}$ and $L_{2}$ are context-free then $\mathbb{ROGI}^{*}(L_{1},L_{2})$
and
$\mathbb{LOGI}^{*}(L_{1},L_{2})$ are context-sensitive.

Proof.  We consider only the right one-sided insertion closure – the proof for
left one-sided insertion closure is similar.

Below by a substring occurrence of $w$ we mean a unique substring beginning at
a specified position in $w$. From the definition of right one-sided iterated
insertion it follows that $w\in\mathbb{ROGI}^{*}(L_{1},L_{2})$ if and only if
there exists $k\geq 1$ and a sequence of substring occurrences of $w$:
$s_{1},s_{2},\ldots,s_{k}$ where $s_{k}=w$ and $s_{i}$ is always inside the
substring occurrence $s_{i+1}$, $i=1,\ldots,k-1$, and:

  * •

We can write $s_{1}=x_{1}uzvx_{2}$, where $x_{1}uvx_{2}\in L_{1}$, $uzv\in
L_{2}$.

  * •

We can write
$s_{2}=x_{1}^{\prime}u^{\prime}z^{\prime}v^{\prime}x_{2}^{\prime}$, where
$x_{1}^{\prime}u^{\prime}v^{\prime}x_{2}^{\prime}\in L_{1}$,
$u^{\prime}z^{\prime}v^{\prime}=s_{1}$,

  * •

…

  * •

We can write
$s_{k}=x_{1}^{\prime\prime}u^{\prime\prime}z^{\prime\prime}v^{\prime\prime}x_{2}^{\prime\prime}$,
where
$x_{1}^{\prime\prime}u^{\prime\prime}v^{\prime\prime}x_{2}^{\prime\prime}\in
L_{1}$, $u^{\prime\prime}z^{\prime\prime}v^{\prime\prime}=s_{k-1}$.

Furthermore, we can assume that $|s_{i}|<|s_{i+1}|$, $i=1,\ldots,k-1$, because
if this is not the case, in the chain we can simply omit $s_{i+1}$. Now, on
input $w$, a nondeterministic linear space Turing machine $M$ can begin by
guessing $s_{1}$ and verifying that it has the required decomposition. In the
$(i+1)$st stage $M$ always “remembers” (by markers on the tape) the previous
string $s_{i}$, then guesses the substring $s_{i+1}$ (where $s_{i}$ is a
substring of $s_{i+1}$) and verifies that the conditions hold for $s_{i+1}$.
At the end $M$ accepts if $s_{k}=w$. Since the values $|s_{i}|$ form a
strictly increasing sequence, the process can be ended after at most $|w|$
stages.

In the proof of Proposition 5.5 it is sufficient to know that the languages
$L_{1}$ and $L_{2}$ are context-sensitive, and as a consequence it follows
that context-sensitive languages are closed under one-sided outfix-guided
insertion closure.

We conjecture that, for any context-free language $L$, $\mathbb{OGI}^{*}(L)$
must be context-sensitive. Constructing a linear bounded automaton for
$\mathbb{OGI}^{*}(L)$ is more difficult than in the case of the right or left
one-sided insertion closures, because a direct simulation of a derivation of
$w\in\mathbb{OGI}^{*}(L)$ (i.e., simulation of the iterated outfix-guided
insertion steps producing $w$) would need to remember, at a given time, an
unbounded number of substrings of the input.

Also we do not know how to make the procedure in the proof of Proposition 5.5
deterministic and it remains open whether the one-sided outfix-guided
insertion closures of context-free languages are always deterministic context-
sensitive.

##  6 Deciding Closure under Outfix-Guided Insertion

In this section we consider the question whether a given language is closed
under outfix-guided insertion and show that this question is undecidable for
context-free languages.

We say that a language $L$ is closed under outfix-guided insertion, or og-
closed for short, if outfix-guided inserting strings of $L$ into $L$ does not
produce strings outside of $L$, that is, $(L\leftarrow L)\subseteq L$.

A natural algorithmic problem is then to decide for a given language $L$
whether or not $L$ is og-closed. If $L$ is regular, by Lemma 4.1, we can
decide whether or not $L$ is og-closed. For a given DFA $A$, Lemma 4.1 yields
only an NFA for the language $L(A)\leftarrow L(A)$. In general, the NFA
equivalence or inclusion problem is PSPACE complete [25]. However, inclusion
of an NFA language in the language $L(A)$ can be tested efficiently when $A$
is deterministic.

###### Theorem 6.1

There is a polynomial time algorithm to decide whether for a given DFA $A$ the
language $L(A)$ is og-closed.

Proof.  As in the proof of Lemma 4.1 we construct an NFA $B$ for the language
$L(A)\leftarrow L(A)$. The number of states of $B$ is quadratic in the number
of states of $A$. Let $A^{\prime}$ be the DFA obtained from $A$ by
interchanging the final states and the non-final states. Now $L(B)\subseteq
L(A)$ if and only if $L(B)\cap L(A^{\prime})=\emptyset$ and intersection
emptiness for NFAs can be tested in polynomial time.

The method used in Theorem 6.1 does not yield an efficient algorithm if the
regular language $L$ is specified by an NFA. The complexity of deciding og-
closure of a language accepted by an NFA remains open. On the other hand,
using a reduction from the Post Correspondence Problem it follows that the
question whether or not a context-free language is og-closed in undecidable.

###### Theorem 6.2

For a context-free language $L$, specified e.g. by a context-free grammar, the
question whether or not $L$ is og-closed is undecidable.

Proof.  Recall that an instance of the Post Correspondence Problem (PCP) [23]
consists of two lists of strings
$((u_{1},\ldots,u_{n}),(v_{1},\ldots,v_{n}))$, $u_{i},v_{i}\in\Sigma^{*}$,
$1\leq i\leq n$, and a solution of this instance is a sequence of integers
$(i_{1},\ldots,i_{k})$, $i_{j}\in\\{1,\ldots,n\\}$, $j=1,\ldots,k$, such that
$u_{i_{1}}\cdots u_{i_{k}}=v_{i_{1}}\cdots v_{i_{k}}$. It is well known that
deciding whether or not a PCP instance has a solution is undecidable [23].

Let $I_{\rm PCP}=((u_{1},\ldots,u_{n}),(v_{1},\ldots,v_{n}))$,
$u_{i},v_{i}\in\\{a,b\\}^{*}$, $1\leq i\leq n$ be an arbitrary instance of
PCP. Choose $\Sigma=\\{a,b,f,\cent,\$,\\#\\}$ and define

$\displaystyle L_{1}$ $\displaystyle=\\{\;$
$\displaystyle\cent\$i_{1}i_{2}\cdots
i_{r}\\#u_{i_{r}}^{R}u_{i_{r-1}}^{R}\cdots
u_{i_{1}}^{R}\\#\\#v_{j_{1}}v_{j_{2}}\cdots v_{j_{s}}\\#j_{s}j_{s-1}\cdots
j_{1}\$\cent\;\mid\;$ $\displaystyle r,s\geq 1,1\leq i_{x},j_{y}\leq n,1\leq
x\leq r,1\leq y\leq s\;\\},\;\mbox{ and, }$ $\displaystyle L_{2}$
$\displaystyle=\\{\;$ $\displaystyle\$i_{1}i_{2}\cdots
i_{r}\\#w\\#f\\#w^{R}\\#i_{r}i_{r-1}\cdots i_{1}\$\;\mid\;$ $\displaystyle
w\in\\{a,b\\}^{*},r\geq 1,1\leq i_{x}\leq n,1\leq x\leq r\;\\}.$

The languages $L_{1}$ and $L_{2}$ are context-free. (The language $L_{2}$ can
be generated by a linear context-free grammar and $L_{1}$ is the concatenation
of two linear context-free languages.)

We define $L=L_{1}\cup L_{2}$ and claim that the instance $I_{\rm PCP}$ has a
solution if and only if $L$ is not og-closed. Below we prove both implications
of the claim.

$\bullet$ “$I_{\rm PCP}$ has a solution implies $L$ is not closed”:

Suppose that $(i_{1},\ldots,i_{k})$ is a solution for $I_{\rm PCP}$. Now

$w_{1}=\cent\$i_{1}i_{2}\cdots i_{k}\\#u_{i_{k}}^{R}u_{i_{k-1}}^{R}\cdots
u_{i_{1}}^{R}\\#\\#v_{i_{1}}v_{i_{2}}\cdots v_{i_{k}}\\#i_{k}i_{k-1}\cdots
i_{1}\$\cent\in L_{1}\;(\subseteq L).$

Also since $(i_{1},\ldots,i_{k})$ is solution we note that

$w_{2}=\$i_{1}i_{2}\cdots i_{k}\\#u_{i_{k}}^{R}u_{i_{k-1}}^{R}\cdots
u_{i_{1}}^{R}\\#f\\#v_{i_{1}}v_{i_{2}}\cdots v_{i_{k}}\\#i_{k}i_{k-1}\cdots
i_{1}\$\in L_{2}\;(\subseteq L).$

As illustrated in Fig. 4, the string $w_{2}$ can be (in a unique way) outfix-
guided inserted into the string $w_{1}$ and the resulting string is not in $L$
because no string of $L$ contains both symbols $\cent$ and $f$.

Figure 4: Only possible outfix-guided insertion of $w_{2}$ into $w_{1}$.

$\bullet$ “$I_{\rm PCP}$ has no solution implies $L$ is closed”:

Recall that by a trivial outfix-guided derivation step we mean a derivation
step $w\stackrel{{\scriptstyle[w]}}{{\Rightarrow}}w$ where $w$ is obtained
from itself by selecting the outfix to consist of a prefix and suffix of $w$
whose concatenation is equal to $w$.

Using the assumption that the instance $I_{\rm PCP}$ does not have a solution
we show that strings of $L$ can be inserted into strings of $L$ using only
trivial derivation steps which naturally then implies $(L\leftarrow
L)\subseteq L$.

Strings of $L_{1}$ begin and end with the symbol $\cent$ and this symbol
occurs exactly two times in strings of $L_{1}$. Thus, strings of $L_{1}$ can
be outfix-guided inserted into strings of $L_{1}$ only using a trivial
derivation step. For the same reason (by replacing $\cent$ with $) strings of
$L_{2}$ can be inserted into strings of $L_{2}$ only using a trivial
derivation step.

Strings of $L_{1}$ cannot be outfix-guided inserted into strings of $L_{2}$
because the former begin and end with the symbol $\cent$ and the latter do not
contain any occurrences of $\cent$. The remaining possibility we need to
consider is under what conditions strings of $L_{2}$ can be outfix-guided
inserted into strings of $L_{1}$.

Consider

$w_{1}=\cent\$i_{1}i_{2}\cdots i_{r}\\#u_{i_{r}}^{R}u_{i_{r-1}}^{R}\cdots
u_{i_{1}}^{R}\\#\\#v_{j_{1}}v_{j_{2}}\cdots v_{j_{s}}\\#j_{s}j_{s-1}\cdots
j_{1}\$\cent\in L_{1},$ $\mbox{ and, }w_{2}=\$i_{1}i_{2}\cdots
i_{r}\\#w\\#f\\#w^{R}\\#i_{r}i_{r-1}\cdots i_{1}\$\in L_{2},$

and suppose we can write $w_{1}=x_{1}uvx_{2}$, $w_{2}=uzv$,
$u,v\neq\varepsilon$. Since $w_{1}$ does not contain occurrences of the symbol
$f$, in the decomposition of $w_{2}$ the symbol $f$ must be in the substring
$z$. The string $w_{2}$ begins and ends with $\$$ which are then the first and
last symbol of $u$ and $v$, respectively (and consequently
$x_{1}=x_{2}=\cent$). Since the concatenation of $u$ and $v$ must contain all
four occurrences of # in $w_{1}$, it follows that

$u=\$i_{1}i_{2}\cdots i_{r}\\#u_{i_{r}}^{R}u_{i_{r-1}}^{R}\cdots
u_{i_{1}}^{R}\\#\;\mbox{ and }\;v=\\#v_{j_{1}}v_{j_{2}}\cdots
v_{j_{s}}\\#j_{s}j_{s-1}\cdots j_{1}\$.$

Now in the decomposition of $w_{2}$ the only possibility is that $z=f$, and
the strings $w_{1}$ and $w_{2}$ must be as illustrated in Fig. 5. From the
definition of the language $L_{2}$ it follows that $r=s$, $i_{x}=j_{x}$,
$x=1,\ldots,r$. and
$(u_{i_{r}}^{R}u_{i_{r-1}}^{R}u_{i_{1}}^{R})^{R}=v_{i_{1}}v_{i_{2}}\cdots
v_{i_{r}}$. Together these conditions mean that $(i_{1},\ldots,i_{r})$ is a
solution for the instance $I_{\rm PCP}$, which contradicts our assumption that
the instance did not have a solution.

Figure 5: Decompositions of $w_{1}\in L_{1}$ and $w_{2}\in L_{2}$.

Note that in the proof of Theorem 6.2 the language $L_{1}$ is not
deterministic context-free. It remains open whether og-closure can be decided
for deterministic context-free languages.

##  7 Conclusion

Analogously with the recent overlap assembly operation [2, 5], we have
introduced an overlapping insertion operation on strings and have studied
closure and decision properties of the outfix-guided insertion operation.
While closure properties of non-iterated outfix-guided insertion are
straightforward to establish, the questions become more involved for the
outfix-guided insertion closure. As the main result we have shown that the
outfix-guided insertion closure of a finite language need not be regular.

Much work remains to be done on outfix-guided insertion. One of the main open
questions is to determine upper bounds for the complexity of the outfix-guided
insertion closures of regular languages. Does there exist regular languages
$L$ such that the outfix-guided insertion closure of $L$ is non-context-free?

## Acknowledgments

We thank the referees for many useful suggestions that have improved the
presentation of the paper. Cho and Han were supported by the Basic Science
Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei
University Future-leading Research Initiative of 2016 and the IITP grant
funded by the Korea government (MSIP) (R0124-16-0002). Ng and Salomaa were
supported by Natural Sciences and Engineering Research Council of Canada Grant
OGP0147224.

## References

  * [1] John S Bertram.  The molecular biology of cancer.  Molecular Aspects of Medicine, 21(6):167–223, 2000.
  * [2] E. Csuhaj-Varju, I. Petre, and G. Vaszil.  Self-assembly of strings and languages.  Theoretical Computer Science, 374:74–81, 2007.
  * [3] A. Cǎrǎuşu and G. Pǎun.  String intersection and short concatenation.  Revue Roumaine de Mathématiques et Appliquées, 26:713–726, 1981\.
  * [4] Mark Daley, Lila Kari, Greg Gloor, and Rani Siromoney.  Circular contextual insertions/deletions with applications to biomolecular computation.  In String Processing and Information Retrieval Symposium, pages 47–54, 1999.
  * [5] Srujan Enaganti, Oscar Ibarra, Lila Kari, and Steffen Kopecki.  On the overlap assembly of strings and languages.  Natural Computing, 16:175–185, 2017.
  * [6] Srujan Kumar Enaganti, Oscar H Ibarra, Lila Kari, and Steffen Kopecki.  Further remarks on DNA overlap assembly.  Manuscript, 2016.
  * [7] Srujan Kumar Enaganti, Lila Kari, and Steffen Kopecki.  A formal language model of dna polymerase enzymatic activity.  Fundamenta Informaticae, 138:179–192, 2015.
  * [8] RA Flavell, DL Sabo, EF Bandle, and Ch Weissmann.  Site-directed mutagenesis: effect of an extracistronic mutation on the in vitro propagation of bacteriophage qbeta RNA.  Proceedings of the National Academy of Sciences, 72(1):367–371, 1975.
  * [9] B.S. Galiukschov.  Semicontextual grammars (in russian).  Mat. Logica i Mat. Lingvistika, pages 38–50, 1981.
  * [10] S. Ginsburg and S. Greibach.  Deterministic context free languages.  Information and Control, 9:620–648, 1966.
  * [11] D. Haussler.  Insertion languages.  Information Sciences, 31:77–89, 1983.
  * [12] Anne Hemsley, Norman Arnheim, Michael Dennis Toney, Gino Cortopassi, and David J Galas.  A simple method for site-directed mutagenesis using the polymerase chain reaction.  Nucleic Acids Research, 17(16):6545–6551, 1989.
  * [13] Markus Holzer and Sebastian Jacobi.  Chop operations and expressions: Descriptional complexity considerations.  In G. Mauri and A. Leporati, editors, Proceedings of the 15th International Conference Developments in Language Theory, pages 264–275. LNCS 6795, Springer, 2011.
  * [14] Markus Holzer, Sebastian Jacobi, and Martin Kutrib.  The chop of languages.  In P. Dömösi and S. Iván, editors, Proceedings of the 13th International Confenrece Automata and Formal Languages, pages 197–210, 2011\.
  * [15] Lila Kari.  On insertion and deletion in formal languages.  PhD thesis, University of Turku, 1991.
  * [16] Lila Kari and Gabriel Thierrin.  Contextual insertions/deletions and computability.  Information and Computation, 131(1):47–61, 1996.
  * [17] Alexander Krassovitskiy, Yurii Rogozhin, and Sergey Verlan.  Computational power of insertion–deletion (P) systems with rules of size two.  Natural Computing, 10:835–852, 2011.
  * [18] Jehan Lee, Myeong-Kyun Shin, Dong-Kyun Ryu, Seahee Kim, and Wang-Shick Ryu.  Insertion and deletion mutagenesis by overlap extension PCR.  In Vitro Mutagenesis Protocols: Third Edition, pages 137–146, 2010\.
  * [19] Huanting Liu and James H Naismith.  An efficient one-step site-directed deletion, insertion, single and multiple-site plasmid mutagenesis protocol.  BMC Biotechnology, 8(1):91–101, 2008.
  * [20] Maurice Margenstern, Gheorghe Păun, Yurii Rogozhin, and Sergey Verlan.  Context-free insertion–deletion systems.  Theoretical Computer Science, 330(2):339–348, 2005.
  * [21] Gheorghe Păun, Mario J Pérez-Jiménez, and Takashi Yokomori.  Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems.  International Journal of Foundations of Computer Science, 19(4):859–871, 2008.
  * [22] Gheorghe Pǎun.  On semicontextual grammars.  Bulletin Mathematique de la Societe des Sciences Mathematiques de Roumanie, 28:63–68, 1984.
  * [23] Jeffrey Shallit.  A second course in formal languages and automata theory.  Cambridge University Press Cambridge, 2009.
  * [24] Akihiro Takahara and Takashi Yokomori.  On the computational power of insertion-deletion systems.  Natural Computing, 2:321–336, 2003.
  * [25] Sheng Yu.  Regular languages.  In Arto Salomaa and Grzegorz Rozenberg, editors, Handbook of Formal Languages, vol. I, pages 41–110. Springer, 1997.