数理解析研究所講究録
第 1604 巻 2008 年 37-41

37d-primitive words and D(1)-concatenated words
Itaru KATAOKA AND Tetsuo MORIYA

School of Science and Engineering
Kokushikan University

Setagaya 4-28-1, Setagaya-ku, Tokyo 154-8515, Japan
Electric Mail: moriya@kokushikan.ac.jp
Abstract
In this paper, we study d-primitive words and D(l)-concatenated words. It is shown thatneither $D(1)$ , the set of all primitive words, nor $D(1)D(1)$ , the set of $aUD$ (l)-concatenatedwords, is regular. We also show that every d-primitive word, with the length of two ormore, is $D(1)$ -concatenated.

1

Introduction

The notion of primitivity of words plays a central role in algebraic coding theory

and combinatorial theory of words (See [3] [4], and [6]).
Recently attention has been drawn to $D(1)$ , the set of all d-primitive words,

which is a proper subset of$Q$, the set of all primitive words. ([1], [7])38
In this paper, we study languages $D(1)$ and $D(1)D(1)$ , the set of all $D(1)-$concatenated words. We consider regularity of $D(1)$ and $D(1)D(1)$ , and a relation
between $D(1)$ and $D(1)D(1)$ .
In section 2 some basic definitions and results are presented. In section 3, thefollowing results are proved. (1) Neither $D(1)$ nor $D(1)D(1)$ is regular. (2) For$w\in\Sigma^{+}$$u,$ $v,$

with $|u|=|v|,$uvw-$\in D(1)$if and only if $uv^{+}w\subseteq D(1)$ . In section 4,

we consider a relation between $D(1)$ and $D(1)D(1)$ . It is proved that for a wordin $D(1)$ , with the length of two or more,

$w$

$w$

is in $D(1)D(1)$ .

Preliminaries

2Let$\Sigma$be an alphabet.

$\Sigma^{*}$of all finite words over$\Sigma^{*},$$|w|$$\Sigma$denotes the free moniod generated by, including the empty word , and$\Sigma$, that is, the set$\Sigma^{+}=\Sigma^{*}-\epsilon$$\epsilon$

denotes the length of$w$. Any subset of

For a word $u\in\Sigma^{+}$ , if $u=vw$ for some$\Sigma^{*}$. For

is called a language over$v,$ $w\in\Sigma^{*}$$\Sigma$$w$in.

, then $v(w)$ is called aprefix (suffix) of , denoted by $v\leq_{p}u$ ( $w\leq_{s}u$ , resp.). If $v\leq_{p}u(w\leq_{S}u)$ and$u$$u\neq v(w\neq u)$ ,$v<_{p}u$then $v(w)$ is called a proper prefix (proper suffix) of( $w<_{s}u$ , resp.). For a word

prefixes (suffixes, resp.) ofA nonempty word

$u$$w$$w$. A nonempty word$u$, denoted by, let Pref $(w)(Suff(w))$ be the set of all.

is called a primitive word if $u=f^{n}$ , for some

some $n\geq 1$ always implies that $n=1$ . Let$\Sigma$$u$$Q$$f\in\Sigma^{+}$, andbe the set of all primitive words overis a non-overlapping word if $u=vx=yv$ for some $x,$$y\in\Sigma^{+}$

39
always implies that$\Sigma$$v=\epsilon$. Let $D(1)$ be the set of all non-overlapping words over

. A words in $D(1)$ is also called a d-primitive word. For$u\in\Sigma^{+}$}$u$is said to be$D(1)$ -concatenated if there exist $x,$ $y\in D(1)$ such that $xy=u$ , i.e., $u\in D(1)D(1)$.

(See [1] and [5]).

For$w\in\Sigma^{+}$

with $|w|\geq 2,$ $Hlvs(w)$ is defined as follows. If $w=xy$ for $x,$

with $|x|=|y|$ , then Hlvs $(w)=(x, y)$ . If $w=xcy$ , for $x,$$|y|$

, then Hlvs $(w)=(x, y)$ . For $x,$$y\in\Sigma^{+}$$y\in\Sigma_{f}^{*}c\in\Sigma$$y\in\Sigma^{*}$,, with $|x|=$, if Pre $f(x)-\{\epsilon\})\cap(Suff(y)-\{\epsilon\})=\phi$ ,$($then $(x, y)$ is said to be a non-overlapping pair (n-o. pair).
Lemma 1 $(f2])$ Let$u\in\Sigma^{+}$. Then $u\not\in D(1)$ iff there exists a unique word $v\in D(1)$with $|v|\leq(1/2)|u|$ such that $u=vwv$ for someRemark 1 Let$u,$$v\in\Sigma^{+}$$w\in\Sigma^{*}$.

. Obviously $uv\in D(l)$ implies that $(u, v)$ is a n-o. pair.

The converse does not hold; for $u=$ abbbba, and $v=bb,$ $(u, v)$ is a n-o. pair but$uv$

is not in $D(l)$ . However, in the next Proposition, we show the above two areequivalent on the condition thatProposition 2 For$u\in\Sigma^{+}$$u$and$v$

are in $D(l)$ .

, the following two are equivalent.

(1) $u,$ $v,$ $uv$ , and vu are in $D(l)$ .
(2) $u,$$v$

are in $D(l)$ , and $(u, v),$ $(v, u)$ are n-o. pairs.

The next lemma is immediate by Lemma 1

Lemma 3 (1) For a n-o. pair $(x, y)$ and$c\in\Sigma$, with $|x|=|y|$ , both $xy$ and $xcy$ arein $D(1)$ . (2) Let $w\in D(1)$ . For every $x\in Pref(w)-\{\epsilon\}$ and $y\in Suff(w)-\{\epsilon\}$ ,$(x, y)$is a n-o. pair.

40

3Regularity of $D(1)$ and $D$ (l)-concatenated words
Proposition 4 $D(1)$ is n\‘ot regular.

Proposition 5 $D(1)D(1)$ is not regular.
Proposition 6 Let $|u|=|w|$ for$uv^{+}w\subseteq D(1)$$u,$ $v,$$w\in\Sigma^{+}$. Then $uvw\in D(1)$ if and only if.

Remark 2 Unfortunately, the previous proposition does not hold without the con-dition $|u|=|w|$ .

For example, let $u=$ babaa, $v=ba_{f}$ and $w=a$ .

uvw

D(l), but $uv^{2}w=(babaa)^{2}\not\in D(1)$ .

4$=$bavaabaa

$\in$

Then

d-primitive words and $D$ (l)-concatenated words

In this section we consider a relation between primitive words and$D$(l)-concatenatedwords.
Lemma 7 Let zxyx be in $D(1)$ for. If$z$

is in $D(1)$ , then $zx$ is. If $w\in D(1)$ , then$w$

is a $D(l)$ -concatenated$z,$ $x\in\Sigma^{+},$$y\in\Sigma^{*}$also in $D(1)$ .
Proposition 8 Let $|w|\geq 2$ for$w\in\Sigma^{+}$

word. In other words, for a word
in $D(1)D(1)$ .

$w$

in $D(1)_{z}$ with the length of two or more,$w$is41

References[1] Chen-Ming Fan, H.J.Shyr, S.S.Yu, d-words and d-languages, Acta Informatica,$vol35,$ $pp709- 727$ , 1998.

[2] Hsu, S.C., Ito, M., Shyr, H.J., “ Some properties of overlapping order and relatedlanguages” Soochow Journal of Mathematics 15, 29-45 (1989).
[3] Lothaire, M., “ Combinatorics on words”, Addison-Wesley, Reading MA, 1983.
[4] R. C. Lyndon and M. P. Shutzenberger, “The equation $a^{M}=b^{N}c^{P}$ in a freegroup”, Michigan Math. J. vol.9, pp.289-298, 1962.
[5] Shyr, H.J., “Free Monoids and Languages”, Hon${\rm Min}$Book, 2001.

[6] Shyr, H. J. , “ Disjunctive languages and codes”, in Proc. FCT77, Lecture Notes

in Computer Science, vol.56, pp.171-176, Springer, Berlin, 1977.
[7] Zheng-Zhu Li, Y. S. Tsai,)Three-element codes with one d-primitive word”,Acta Informatica, $41(2- 3)$ , 2004;