数理解析研究所講究録
第 1915 巻 2014 年 113-117

113

Regularity of Iterative Hairpin Completion of crossing words.
Kayoko Shikishima-Tsuji

Center for Liberal Arts Education and ResearchTenri University

1 Introduction
The mathematical hairpin notion introduced in [5] is a word in which some
suﬃx is theored complement of a middle factor of the word. This operation wereintroduced which are very similar in nature to it. Mirrored complementary sequences
occur frequently in DNA and are often found at functionally interesting locations suchas replication origins or operator sites. The most basic question about hairpin
completion is “given a word, can we decide whether the iterated hairpin completion ofthe word is regular?”’ The situation is very complicated. In the special case when theword is non-crossing, some results were given ([1],[3]). In section 3, we add someresults in the case when the word is crossing.
$mi_{IT}$2 Preliminaries
We assume the reader to be familiar with basic concepts as alphabet, word,
language and regular expression (for more details see [2]).
Words together with the operation of concatenation form a free monoid, whichis usually denoted by for an alphabet . Repeated concatenation of a word withitself is denoted by for nonnegative integer . The length of a finite word is thenumber of not necessarily distinct symbols it consists of and is written by $|w|.$$\Sigma^{*}$$\Sigma$$w$$w^{i}$$w$$i$

is a function, such that forbe an antimorphic involution, i.e. :, and. Then, is a
for all
for all,
pseudopalindrome if $w=\theta(w)$ . To make notation cleaner, we write forwhen is understood.
for some
Throughout this paper, let be a fixed integer. For a word $w=$ ), we define right (k)hairpin completion
ofand(with respect to ). By the notation $warrow_{r}u$ $(or w_{k}arrow_{r}u)$ , we mean thatis right$(k-)$ hairpin completion of. The left hairpin completion is defined analogously. By
the notation $warrow_{l}u$ , we mean that is left (k)hairpin completion of . The relation
Let$\theta$$\theta$$a\in\Sigma$$\theta(\theta(a))=a$$\Sigma^{*}arrow\Sigma^{*}$$\theta(uv)=\theta(v)\theta(u)$$u,$$v\in\Sigma^{+}$$(\theta-)$$w$$\theta(u)$$\overline{u}$$\theta$$k$$\alpha\in\Sigma^{k}$$\gamma,$$\alpha\sqrt{\alpha}$$\beta\in\Sigma^{*}$$\mu\sqrt{}\overline{\alpha\gamma}$$w=\mu\beta\overline{\alpha}$$u$$\alpha$

$w$

$w$

$u$

of hairpin completion$arrow$

is defined $asarrow_{r}orarrow_{l}.$ $Byarrow^{*},$

the reflexive transitive closure $ofarrow,$$arrow_{r}$and$arrow l$$arrow_{r}*andarrow_{l}^{*}$, respectively.

, we denote114
For a languageI$L\subseteq\Sigma^{+}$, we define the right $(k-)$ hairpin completion of $L$ by

and 1

and the lefl $(k-)$ hairpin
completion of by. The$(k-)$ hairpin completion ofis $H_{k}(L)=RH_{k}(L)\cup LH_{k}(L)$ . And we define the iterated$(or RH_{k}^{*}(L) or LH_{k}^{*}(L))$ of, inductively(right or left) (k)hairpin completionas follows:$H_{k}^{0}(L)=H_{k}(L)$ , $H_{k}^{n+1}(L)=H_{k}(H_{k}^{n}(L))$ and,
$RH_{k}(L)=\{\gamma\alpha\beta\overline{\alpha\gamma}$$\mu\beta\overline{\alpha}\in L,$$\gamma\in\Sigma^{+},\beta\in\Sigma^{*}$$\alpha I=k\}$$LH_{k}(L)=\{\mu\sqrt{\alpha\gamma}I)\alpha\sqrt{\alpha}\in L, \gamma\in\Sigma^{+},\beta\in\Sigma^{*}|\alpha I=k\}$

$L$

$L$

$L$

$H_{k}^{*}(L)$$H_{k}^{*}(L)= \bigcup_{n\geq 0}H_{k}^{n}(L)$$RH_{k}^{0}(L)=RH_{k}(L)$ , $RH_{k}^{n+1}(L)=RH_{k}(RH_{k}^{n}(L))$$LH_{k}^{0}(L)=LH_{k}(L)$and$RH_{k}^{*}(L)= \bigcup_{n\geq 0}RH_{k}^{n}(L)$,, $LH_{k}^{n+1}(L)=LH_{k}(LH_{k}^{n}(L))$ and $LH_{k}^{*}(L)= \bigcup_{n\geq 0}LH_{k}^{n}(L)$ ,3 Iterated hairpin completion of crossing words
is an $(m, n)-\alpha$ -word $(or$ simply $(m, n)$ -word) if the numbers of
occurrence of and in , are and respectively. We say that an $(m, n)-\alpha$ -word
is non-a -crossing if the rightmost occurrence of precedes the leftmost
occurrence of on . Otherwise, the word is -crossing.
. By one-step hairpin completion withLetand 1andrespect to and , we get two words
andRegularity of the iterative hairpin completion of is depend on those of. Our problem in this paper is for a given word , whether the iterated
hairpin completion of is regular?”’ In the rest of this paper, we may assume that theword
is in
Let be a crossing $(m, n)-\alpha$ -word. Then we have $m,n\geq 2.$
A word$w\in\Sigma^{+}$$\overline{\alpha}$$\alpha$

$w$

$m$

$n$

$w$

$\alpha$$w$$\alpha$$\alpha$$w\in oe^{*}\cap\Sigma^{*}\beta$$\alpha$$\alpha$$\beta I=k$$w”\in\alpha\Sigma^{*}\cap\Sigma^{*}\overline{\alpha}.$$w’\in f\overline{fl}^{*}\cap\Sigma^{*}\beta$$\beta$$H_{k}^{*}(w’)$$w$$H_{k}^{*}(w")$

$w$

$w$

$X^{*}\cap\Sigma^{*}\overline{\alpha}.$

$w$

$w$

The following example shows that the iterated hairpin completion of $a(3,2)-\alpha$crossing word is not always regular ([4]).

Example 1. (Kopecki) We consider a crossing word $w=$ abaaaca. Letand. Then,the iterated hairpin completion of a word is not always regular.
$R=wu^{+}v\overline{u}^{+}\overline{w}\overline{u}^{+}\overline{w}$$v=\alpha\overline{\alpha}b\overline{\alpha}$$u=\overline{b}\overline{\alpha},$$R\cap H_{i}^{*}(\{w\})=\{wu^{r}v\overline{u}^{r}\overline{wu}^{r}\overline{w} Ir\geq 1\}$. Therefore,

We have some results for the iterated hairpin completion of $a(2,2)-\alpha$ crossing

word.

Proposition 1. Let
be $(2, 2)-\alpha$ -crossing-word such that $w=xvy$
where and are $(1,1)-\alpha$ -words inandIf and are pseudopalindromes, thenis regular.
$w\in oe^{*}\cap\Sigma^{*}\overline{\alpha}$$\alpha\Sigma^{*}\overline{\alpha}$

$x$

$y$

$H_{k}^{*}(w)$$v\in\Sigma^{*}$

$x$

$y$

115Proof) Let$R=\{x(vx)^{*}(vy(\overline{v}x)^{+}(vx)^{*})^{*}vy(\overline{v}x)^{+}\}$

and$L=\{(y\overline{v})^{+}xv((yv)^{*}(y\overline{v})^{+}xv)^{*}(yv)^{*}y\}.$Since these languages are regular and, we show
$H_{k}^{*}(w)=R\cup
L\cup\{w\}$that. First, we prove that (xvyvx) $=R.$
We show that. Let
for every
nonnegative integer . Then it is obvious that
. We show that(xvyvx) by induction on. It is clear thatthe following:$H_{k}^{*}(w)=H_{k}^{*}(xvy\overline{v}x)\cup H_{k}^{*}(y\overline{v}xvy)\cup\{w\}$$H_{k}^{*}$$H_{k}^{*}(xvy\overline{v}x)\supset R$$R_{n}=x(vx)^{*}(vy(\overline{v}x)^{+}(vx)^{*})^{n}(vy)(\overline{v}x)^{+}$$n$$R= \bigcup_{n\geq 0}R_{n}$$n\geq 0$$R_{n}\subset H_{k}^{*}$$R_{0}=x(vx)^{*}vy(\overline{v}x)^{+}\subset H_{k}^{*}(xvy\overline{v}x)by$$xvy\overline{v}xarrow^{i},x(vx)^{i}vy(\overline{v}x)arrow_{r}^{j}x(vx)^{i}vy(\overline{v}x)^{j+1}$

Suppose that
nonnegative integer . Every word

is contained in (xvyvx) for someinis written by the form, and
where
is in

$R_{n}=x(vx)^{*}(vy(\overline{v}x)^{+}(vx)^{*})^{n}(vy)(\overline{v}x)^{+}$$w$$n$$H_{k}^{*}$$R_{n+1}$$x(vx)^{r}vy(vx)^{m_{1}}(vx)^{t_{1}}\cdots vy(\overline{v}x)^{m_{\iota+1}\prime}(vx)^{t_{n+1}}vy(\overline{v}x)^{s}$$r,s\geq 0$. We show that the word

$H_{k}^{*}(xvy\overline{v}x)$$t_{1},\cdots,t_{n+1}\geq 0$$w_{1}=x\nu y(vx)^{m_{1}}(vx)^{t_{1}}\cdots vy(\overline{v}x)^{m_{n+1}}(vx)^{t_{n+1}}vy(\overline{v}x)$.

When(1)$m_{1},\cdots,m_{n+1}>0,$$m_{1}>t_{n+1}$, let$w’=xvy(\overline{v}x)^{m_{1}}(vx)^{t_{1}}\cdots vy(\overline{v}x)^{m_{n}}(vx)^{t_{n}}vy(\overline{v}x)$. We have$w’=xvy(\overline{v}x)^{m_{1}}(vx)^{t_{l}}\cdots vy(\overline{v}x)^{m_{n}}(vx)^{t,\prime}vy(\overline{v}x)arrow_{r}^{m_{n+J}-1}xvy(\overline{v}x)^{m_{J}}(vx)^{t_{1}}\cdots Vy(\overline{v}x)^{m_{n}}(vx)^{t_{n}}vy(\overline{v}x)^{m_{n+1}}$$=xvy\overline{v}(x\overline{v})^{t_{n+1}}\cdot x(\overline{v}x)^{m_{1}-t_{n+1}-1}(vx)^{t_{1}}\cdots vy(\overline{v}x)^{m_{n}}(vx)^{t_{n}}vy(\overline{v}x)^{m_{n+1}}$$arrow_{r}xvy\overline{v}(x\overline{v})^{t_{n+1}}\cdot x(\overline{v}x)^{m_{1}-t_{n+1}-1}(vx)^{t_{1}}\cdots vy(\overline{v}x)^{m_{n}}(vx)^{t_{n}}vy(\overline{v}x)^{m_{n+1}}\cdot(vx)^{t_{n+1}}vy\overline{v}x=w_{1}$Since

is in R., it is contained in(2)
, let
When
We have$w^{ノ}$$m_{1}\leq t_{n+1}$$H_{k}^{*}(xvy\overline{v}x)$. Then the word

$w_{1}$is also in$w”=x\nu y(\overline{v}x)^{m_{2}}(vx)^{t_{2}}\cdots vy(\overline{v}x)^{m_{n+1}}(vx)^{t_{n+1}}vy(\overline{v}x)$$H_{k}^{*}(xvy\overline{v}x)$.

.

$w”=xvy(\overline{v}x)^{m_{2}}(vx)^{t_{2}}\cdots vy(\overline{v}x)^{m_{n+1}}(vx)^{t_{n+1}}vy(\overline{v}x)$$arrow_{r}^{t_{1}}x(vx)^{t_{1}}vy(\overline{v}x)^{m_{2}}(vx)^{t_{2}}\cdots vy(\overline{v}x)^{\prime n_{n+1}}(vx)^{t_{n+1}}vy(\overline{v}x)$$=x(vx)^{l_{1}}vy(\overline{v}x)^{m_{2}}(vx)^{l_{2}}\cdots vy(\overline{v}x)^{m_{n+1}}(vx)^{t_{n+1}-m_{1}+1}\cdot(vx)^{m_{1}-1}vy(\overline{v}x)$$arrow_{r}xvy\overline{v}(x\overline{v})^{m_{1}-1}\cdot x(vx)^{t_{1}}\cdot vy(\overline{v}x)^{m_{2}}(vx)^{t_{2}}\cdots vy(\overline{v}x)^{m_{n+1}}(vx)^{t_{n+1}-m_{1}+1}\cdot(vx)^{m_{1}-1}vy(\overline{v}x)=w_{1}$Since $w”$ is in , it is contained in
It is clear that(. Then the word is also in(xvyvx)). We proved that

$H_{k}^{*}(xvy\overline{v}x)$$R_{n}$$w\in H_{k}^{*}(w_{1})\subset H_{k}^{*}$$H_{k}^{*}(xvy\overline{v}x)$$w_{1}$$H_{k}^{*}$$=H_{k}^{*}(xvy\overline{v}x)$$H_{k}^{*}(xvy\overline{v}x)\supset R.$

To prove that
. Then we haveAs the proof of$H_{k}^{*}(xvy\overline{v}x)\subset R$$H_{k}^{n}(xvy\overline{v}x)\subset R$

is easy. For a nonnegative integer$n$, suppose that

$H_{k}^{n+1}(xvy\overline{v}x)=H_{k}^{1}(H_{k}^{n}(xvy\overline{v}x))\subset H_{k}^{1}(R)\subset R.$$H_{k}^{*}(y\overline{v}xvy)=L$

is similar, we omit it.

$\square$

The following example is that the iterated hairpin completion of $a(2,2)-\alpha$crossing word which is not satisfies the condition of Proposition 1, that is $w=xvy$, is not always regular.
such that$w$$y\neq\overline{y}$.

116
Example 2 We consider $a(2,2)-\alpha$ -crossing word $w=$ abacada where $a,b,c,d\in\Sigma,$
and $\alpha=aa$ . For integers $i,j>0$ , suppose a word
. Since $w=xcy$
where $x=abaandy=\alpha d\overline{\alpha}$ is in$a\neq\overline{a},b=\overline{b},c\neq\overline{c},d\neq\overline{d}$$H_{k}^{*}(w)$$w_{i.j}=xcy(\overline{c}\overline{x})^{j}(cx)^{j}c\overline{y}\overline{c}x$appears only one time as a factor of$w_{i,j}$, we have $w_{i,j}\in RH_{k}^{*}(w)$ .

We have $w=$ abacada
where $m>0andm\geq s>0$ . Leteasy to see that$=xcyarrow_{r}^{m}\alpha b\overline{\alpha}c\alpha d\overline{\alpha}\cdot(\overline{c}\alpha\overline{b}\overline{\alpha})^{m}=xcy\cdot(\overline{c}x)^{m}arrow_{r}^{1}xcy\cdot(\overline{c}x)^{m+1}$$xcy(\overline{c}x)^{m}\cdot(cx)^{s}c\overline{y}\overline{c}x$$S=xcy(\overline{c}x)^{*}(cx)^{*}c\overline{y}\overline{c}x$$H_{k}^{*}(w)\cap S=RH_{k}^{*}(w)\cap S=\{xcy(\overline{c}x)^{i}(cx)^{j}c\overline{y}\overline{c}x|i\geq j\geq 0\}$is regular and$H_{k}^{*}(w)\cap S$

is not regular,$H_{k}^{*}(w)$or. It is. Since$S$

is not regular.

We have the following corollaries by the proof of Proposition 1.
be $(3, 3)-\alpha$ -crossing-word such that
If and are pseudowhere and are $(1,1)-\alpha$ -words in $oe^{*}a$ andof is regular andpalindromes, then the iterated hairpin completion

Corollary 1. Let$w\in\alpha\Sigma^{*}\cap\Sigma^{*}\overline{\alpha}$$w=xvyV\overline{x}$$v\in\Sigma^{*}$

$x$

$y$

$H_{k}^{*}(w)$

$x$

$y$

$w$

$H_{k}^{*}(w)=$$x(vx)^{*}(vy(\overline{v}x)^{+}(vx)^{*})^{*}vy(\overline{v}x)^{+}$

be $(2, 2)-\alpha$ -crossing-word such that $w=xvy$ where
Corollary 2. Let
If $x,y$ and are pseudo-palindromes,
andand are $(1,1)-\alpha$ -words inis regular and $H_{k}^{*}(w)=\{w\}\cup$then the iterative hairpin completion$w\in\alpha\Sigma^{*}\cap\Sigma^{*}\overline{\alpha}$$v\in\Sigma^{*}$$\alpha\Sigma^{*}a$

$x$

$v$

$y$

$H_{k}^{*}(w)$$x(vx)^{*}(vy(vx)^{+})^{*}vy(vx)^{+}\cup(yv)^{+}xv((yv)^{+}xv)^{*}(yv).y.$

The following theorem is proved by the similar way of Proposition 1.

where andTheorem 1. Let be $(2, 2)-\alpha$ -crossing-word such thatis. If and are pseudo-palindromes, thenare $(1,1)-\alpha$ -words inregular.
$w=x\Sigma^{+}\cap\Sigma^{+}y$$w$$X^{*}\cap\Sigma^{*}\overline{\alpha}$Proof) If $|w|\geq|\sqrt{}+$

$x$

$x$

$H_{k}^{l}(w)$$y$, then we already proved in Proposition 1. If $|\iota\sqrt{}\leq|x|+|M-2|\alpha|,$then is non-crossing. We may assume that $|x|+|M-2|\alpha|<|w|<|x|+|M$ . Sinceof such that $\alpha=vu,$
overlaps with , there exist factors
and $w=vx_{0}vy_{0}v$ where$y=vy_{0}v,$. SinceandLet, to prove the theorem we show that.
and$\overline{\alpha}$$w$$u,v\in\Sigma^{+}$$\alpha$$\alpha$$\overline{\alpha}\alpha=\overline{u}vu=\overline{u}\overline{v}u$$x_{0},y_{0}\in\Sigma^{*}$$x=vx_{0^{\mathcal{V}}},$$R=(vx_{0})^{+}(vy_{0}(vx_{0})^{+})^{*}vy_{0}(vx_{0})^{+}v$$H_{k}(w)=H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)\cup H_{k}^{*}(vy_{0}vx_{0}vy_{0}v)\cup\{w\}$$R=H_{k}^{*}(vx_{\mathfrak{o}}vy_{0}vx_{0}\nu)$$y$$L=H_{k}^{*}(vy_{0}vx_{0}\nu y_{0}v)$$L=v(y_{0}v)^{+}x_{0}v((y_{0}v)^{+}x_{0}v)^{*}(y_{0}v)^{+}$

117
First, we prove that

. Letforevery nonnegative integer . Then it is obvious that
We show thatby induction on. It is clear that. Suppose thatiscontained infor some nonnegative integer . Every word inis written by the form
whereand $r,s>0$ . We show that the wordis in$R=H_{k}^{*}(vx_{0}vy_{0}vx_{0})$$R_{n}=(vx_{0})^{+}(vy_{0}(vx_{0})^{+})^{n}vy_{0}(vx_{0})^{+}v$

$n$

$R.$

$R= \bigcup_{n\geq 0}R_{n}.$$n\geq 0$$\subset H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$$R_{0}=(vx_{0})^{+}vy_{0}(vx_{0})^{+}v\subset H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$$R_{n}=(vx_{0})^{+}(vy_{0}(vx_{0})^{+})^{n}vy_{0}(vx_{0})^{+}v$$R_{n}\subset H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$

$w$

$n$

$(vx_{0})^{r}vy_{0}(vx_{0})^{m_{1}}\cdots vy_{0}(vx_{0})^{m_{n+1}}vy_{0}(vx_{0})^{s}v$$R_{n+1}$$m_{1},\cdots,m_{n+1}>0$$w_{1}=vx_{0}vy_{0}(vx_{0})^{m_{1}}\cdots vy_{0}(vx_{0})^{m_{n+1}}vy_{0}(vx_{0})v$$H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$

Let.

$w’=vx_{0}vy_{0}(vx_{0})^{m_{1}}\cdots vy_{0}(vx_{0})^{\prime n_{n}}vy_{0}(vx_{0})v$. We have$w’=vx_{0}vy_{0}(vx_{0})^{m_{1}}\cdots vy_{0}(vx_{0})^{m_{n}}vy_{0}(vx_{0})vkarrow^{m_{n+1}-1}rvx_{0}vy_{0}(vx_{0})^{m_{1}}\cdots vy_{0}(vx_{0})^{m_{n}}vy_{0}(vx_{0})^{m_{n+1}}v$$=vx_{0}vy_{0}\cdot(vx_{0})(vx_{0})^{m_{1}-m_{n+1}}\cdots vy_{0}(vx_{0})^{m_{n}}vy_{0}(vx_{0})^{m_{n+1}}v$$arrow_{r}vx_{0}vy_{0}\cdot(vx_{0})^{m} tvy_{0}(vx_{0})^{m_{n}}vy_{0}(vx_{0})^{m_{n+1}}vy_{0}vx_{0}v=w_{1}$

Since

$w’$

is in

$R_{n}$, it is contained in$H_{k}^{*}(vx_{0}\nu y_{0}vx_{0}v)$. Then the word

and then.
On the other hand, for a nonnegative integer , suppose that

$H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$, then we haveis also in$R\subset H_{k}^{*}(vx_{0}vy_{0}vx_{0}v)$$n$$\subset R$$w_{1}$$H_{k}^{n}(vx_{0}vy_{0}vx_{0}v)$$H_{k}^{1}(H_{k}^{n}(vx_{0}vy_{0}vx_{0}v))=H_{k}^{1}(H_{k}^{n}(vx_{0}vy_{0}vx_{0}v))\subset H_{k}^{1}(R)\subset R.$

As the proof of$H_{k}^{*}(vy_{0}vx_{0}vy_{0}v)=L$is similar, we omit it.

$\square$

References.
[1] V. Diekert, S. Kopecki, and V. Mitrana. On the hairpin completion of regular

languages. In ICTAC, vol. 5684 of Lect. Notes Comput. Sci., 170-184, 2009.
[2] M. A. Hamson. Introduction to Formal Language Theory. Addison-Wesley,Reading, Massachusetts, 1978.
[3] Lila Kari, Steﬀen Kopecki, Shinnosuke Seki: Iterated Hairpin Completions ofNon-crossing Words. SOFSEM 2012: 337-348[4] S. Kopecki, On the iterated hairpin completion, Theoretical Computer Science 412(2011) 3629.
[5] G. Paun, G. Rozenberg, and T. Yokomori. Hairpin languages. Int. J. Found.

Comput. Sci., pages 837-847, 2001.

Center for Liberal Arts Education and ResearchTenri University

1050 Somanouchi, Tenri,
Nara 632-8510, Japan-mail address: tsuji @sta.tenri-u.ac.jp$E$$*\ovalbox{\tt\small REJECT}*\not\cong\cdot K\epsilon_{\backslash \Pi}^{\backslash A}\ovalbox{\tt\small REJECT} F\Re_{J}^{\ovalbox{\tt\small REJECT}_{\iota}}*\sqrt[\backslash ]{}$

タ$-\grave{7}\backslash \pm f\not\leqq ft\mp$