数理解析研究所講究録
第 1604 巻 2008 年 120-124

120

A remark on construction of circular codes
Noboru NAKAHATA (中畑登)Tokai University Junior College (東海大学短期大学部)
Yoshiyuki KUNIMOCHI (國持良行), Genjiro TANAKA (田中源次郎)
Shizuoka Institute of Science and Technology (静岡理工科大学)

Abstract. In this paper we treat the circular codes. We present a method of constructing circularcodcs. We first make a “large” very pure monoid by using the homomorphism from a free monoid toa semigroup. Next, by selecting subsets of its base, we can gain various circular codes.

1. 基本的諸概念
以下で使用する用語と記号について説明を行う. 説明無く使用される用語については, 例えば, J.Berstel
and D. Perrin $[1],A.H$ . Clifford and GB Prestoii[2], や G. Lallement [3] を参照されたし.
を上の語 (word) と呼び, 語の集合を言語と呼ぶ.の元の有限列を文字 (letter) の集合とする.
で表す.
から空語 1 を除い上の語 $w$ 中の文字の集合を alph $(w)$ で表す. 語の全体からなる集合を
$A$

$A$

$w$

$\mathcal{A}$$A$$\mathcal{A}^{*}$た集合を$A^{+}$で表す.

$\mathcal{A}$

上に語の並列 (concatenation) で 2 項演算を定義すると,$A^{*}$

する free monoid をなす.

$\mathcal{A}^{*}$の自明でない submonoid$\Lambda f$$\mathcal{A}*$“は空語 1 を単位元との部分半群 $M$ は単位元 1 を持つとき, submonoid と呼ばれる. free monoid
は, 唯一つの極小生成系 $C=(M-\{1\})-(M-\{1\})^{2}$ を持つ. この極小生成系を $M$ の基底と呼ぶ. $M$ の基底 $C$ が, すべての$7|,,$$m\geq 1$, とすべての$’,\cdot’,\cdot,$$\cdots,$$’\iota_{n}$,$y_{1}$, 物,$\cdot\cdot\cdot$, $?Jm\in C$に対し”を満たすとき,
$M$

$C$

$1:I,2\ldots\prime J_{n}=y_{1}y_{2}\cdots y_{?1}\Rightarrow n=m,$は code と呼ばれる.

を free monoid $A$‘の snbmonoid

このときとし,$C$$\Lambda!f$$x_{i}=yi,$ $1\leq i\leq n$.

は free submonoid と呼ばれる.

を $M$ の基底とする.

もし,$CA^{+}\cap C=\emptyset$が成り立っならば,$C$は$A..\underline{\vdash}$の prefix code

き $C$ は $A$ 上の siiffix code と呼ばれる.

$C$と呼ばれる. 右-左双対として $A^{+}C\cap C=\emptyset$ が成り立っとが prefix code かっ suffix code であるとき,$C$は bifix code であると呼ばれる. 定義により, prefix codeC においては, 任意の $w\in C$ の真の左因子は $C$ の元になることはない.
$M$を浄の submonoid とする. すべての $u,$$v\in \mathcal{A}^{*}$に対し, 誘導式 $[u, uv\in M\Rightarrow v\in M]$ が成立す

uriitary subinonoid と呼ばれる. 同様に, すべての $v\in A^{*}$ に対し, 誘導式の left unitary submonoid と呼ばれる.
もし, $M$ が$[u, vu \in i|f\Rightarrow v\in\Lambda f]$ が成立するとき, $M$ は
right unitary かつ left unitary ならば, $M$ は biunitary と呼ばれる.
を code とする.C が prefix code であるための必要十分条件 {は $C$ “ が right unitary であることである. そして, $C$ が suffix code であるための必要十分条件は $c*$ 力 s left unitary であることである.
が biunitary monoid である([1,p.46,Prop.2. 5]), 従って $C$ が bifix code であるための必要十分条件 はるとき,$M$は$A^{*}$の right$u,$$A^{*}$$|$$C\subset A^{*}$$|$

ことである.

$C^{*}$

121$\mathcal{A}^{*}$の submonoidM

以下の条件を満たすとき, very pure submonoid と呼ばれる :は,$u,$ $v\in A^{*},$ $uv,$ $vu\in M\Rightarrow u,$$v\in M$ .

very pure submoiioid の基底は circular code と呼ばれる.
定義 1.

1), $q\geq 0$ を整数とする.

code $C$ が$C$

$n_{0},$$u_{1},$が $(p, q)$ -limiled code であるならば,$J$を空でない集合とする. すべての $x,$ $y\in_{-}J$ に対し $xy=y$ と定義する.

$c*$は very pure である

じように, 左零半群は $xy=x$ で定義される.

左零半群
は直角帯 (rectangular band, [3,p.51]) と呼ばれる.
を左零半群,$u_{p+q}$について,は $(p, q)$ -limited であると呼ばれる.

$C$

命題 1.

$\cdots,$$(1\leq i\leq p+q)\Rightarrow u_{p}\in C^{*}$$u_{i-1}u_{i}\in C^{*},$

なる条件を満たすならば,の語の任意の列$A^{*}$

を右零半群とする.

([1], p.329,Proposition 2.1).と右零半群

$I$

$J$

$J$は右零半群と呼ばれる. 同の半群としての直積 $S=I\cross J$$S=I\cross J$ を半群としての直積とする.

: $A^{*}arrow S^{1}$ をの任意の部分半群とすると, $M=\varphi^{-1}(T)\cup\{1\}$ は very pure submonoid でをmorphism とする.
ある. その基底は (1, l)-limited である.
$I$

$T$

証明.
る.

明らかに,

$\Lambda$

$J$

,f ま
$|$$A^{*}$の submonoid である.

$\varphi(tl_{0}l)=(I),$ $q),$ $\varphi(u_{1})=(k, l),$$\varphi(u_{2})=(s, t)$$u_{0\}}u_{1},$例 1. $A=\{a, b\},$ $S=\{1,2\}x\{1,2\}$ とする.
$\Lambda f_{11}=\varphi^{-1}(S_{11})\cup\{1\}=\{1, a\}\cup aA^{*}a$である.

$u_{2}\in \mathcal{A}^{*}$とすると.

より $(k, t)(p, l)=(k, l)\in T$ . よって $\varphi(u_{1})\in T$ .て,$\varphi$$S$にっいて, uoui, $u_{1}u_{2}\in M$ ,と仮定す$\varphi(u0ti_{1})=(p, l)\in T,$$\varphi(u_{1}u_{2})=(k, t)\in T$とする.

$S_{11}=\{(1,1)\}$ についQED.

$\varphi(a)=(1,1),$ $\varphi(b)=(2,2)$は明らか.

$fl_{!}I_{11}$の基底 $G$, は, 命題 1 により, (1,l)-limited code

は (1,0)-limited でも $(0,1)- 1mi1_{-}ed$ でもない. なぜなら,ab $a=a\cdot ba\in C_{0^{*}}$ である$ba\inA^{*}$が, ab,であるからである. また, 語の列 ab, $a,$ $aba,$について, $aba$ , aaba, $ababa\in C_{0}^{*}$
であるから (3,0)-limited でも (0,3)-limited でもない.
しかしながら$c_{0}$$\cdot$$ba\not\in C_{0}^{*}$$C=\{a\}\cup\{ab^{m_{1}}ab^{m_{2}}\cdots ab^{m}\prime a|r\geq 1, m_{i}\geq], 1\leq i\leq r\}$とおく.
$U_{1}$$C$

が$\{$1, $a\}\cup aA^{*}a$ を生成するのは明らかである.

$=C^{-1}C-\{1\}$

っまり,
よって

$U_{1}$

$C$

は$F$

$b$

.

$=$

$\{b^{rr\iota_{1}}$(孟 $b^{rr_{2}}$$ub^{7l\iota}\prime a|$,/$\geq$$1,$で始まる語のみからなる. よって,は ccde であり,$C=C_{0}$ である.

(1,1)-linfited である. また,.

$rn_{\gamma}$$\geq$$1.1$$\leq i\leq\uparrow\}$.

$U_{2}=C^{-1}U_{1}\cup U_{1}^{-1}C=\emptyset$

つまり,$C$. よって,は $M_{l1}$ の基底である.

$A/I_{12}=\varphi^{-1}(1,2)(i\{1\}=\{1\}\cup aA^{*}b$$a^{+}b^{+}=\{a^{\tau r\iota}b^{7\}}|\gamma\gamma\cdot l,, n\geq 1\}$

$U_{i}\cap C=\emptyset,$$i=1,2$ .

よって, 命題により $C$ はでその基底は.

である.

このような無限 limited code を作れば, それは無限 circular code である. 従って, その任意の空でない部分集合 $D$ も circular code である. 従って, 適当な部分集合 $D$ をとることにより再び $D$ が limitedcode になる可能性もある. 実際, $C$ の空でない任意の部分集合}f limii $Hed$ code である.
であるから, $C$ は $(2_{1}1)-,(1,2)$ -limited であることに注意する.

$C$

は $(1,1)- limi1_{l}ed$122$C$の任意の空でない部分集合もまた 2, $1)-,(1,2)$ -limited であることをより一般的な形で証明しておく.
$($命題 2.

$u,$

を $(J,l_{I^{j}}/ll(()\cap alpl\iota(?))=\emptyset$ であるような元とする.

$v\in\Lambda^{+}$

もし $\uparrow\iota(\Lambda^{*})^{-1}\cap(A^{*})^{-1}u=\{1, \tau\iota\}$ならば$C=u+(\uparrow\iota?l^{+})^{+}\tau\iota=\{\uparrow A\}\cup\{r\iota_{1}m_{2}\ldots l^{\gamma\gamma}\prime 1, nz_{i}\geq 1,1\leq i\leq r\cdot\}$.の空でない任意の部分集合は $(1,2)-,$ $(2,1)$ -limited code である.

証明.

$C$$(A^{*})^{-1}D$は code である. 初めに次のことに注意する.

$D$を $C$ の部分集合とする.

$\prime r,$$\in A^{*}$の元とすると $u(A^{r})^{-1}\cap(A^{*})^{-1}u=\{1, u\}$ であるから, $x=1,$ $x=u$ または, あるを $D(A^{*})^{-1}\cap$$p_{1}$,$p_{2},$$\cdots p_{s}\in$, について $x=uv^{p\iota}uv^{p\prime s}\cdots uv^{p_{r}}u$ である. つまり $D(\mathcal{A}^{*})^{-1}\cap(A^{*})^{-1}D=\{1\}\cup D\cup\{u\}$ .
“$D$ が $(1,2)-,(2,1)$ -limited であることを示す.
$u_{3}\in A$
について, $u_{i}u_{i+}i\in D$ “, $i=0,1,2$ , が成$u0,$$N,$ $s\geq 1$$u_{1},$$u_{2},$立しているとすると,$u_{0}=$

woxi, $u_{1}=y1w_{1}^{l},$ $x_{1}y\iota\in D,$$w_{0},$$w_{1}’\in D^{*}$,$u_{1}=w_{1}x_{2)}u_{2}=y2w_{2)}’x_{2}y2\in D,$ $w_{1},$ $w_{2}’\in D^{*}$ ,$u_{2}=w_{2}x_{3},$ $u_{3}=y3w_{3}^{l},$と書ける.

$x_{2}$

は $D$ の元の左因子である.

$x_{3}y3\in D,$

そしてまた$x_{2}$$w_{2},$$w_{3}’\in D^{*}$,は $uoui\in D^{*}$ の右因子である.

よって次の二つの場合を考える.

Case (a).

$x_{2}$

この場合,$x_{2}$が $D$ のある元の右因子である.
は) の元の右因子であり,$\gamma$$(A^{*})^{-1}D=\{1\}\cup D\cup\{u\}$Csae (b).

$x_{2}$が$D$.

したがって,

かつ $D$ のある元の左因子である.
$u_{1},$$u_{2}\in D^{*}$

について,$y_{2}=1$.の元を右因子として含む.

命題 3.

$x_{2}$

は $u$ で終わる.

一方 $y2$ は $u_{2}u_{3}\in D^{*}$ の左因子であるから, $y2=1$ または$l/2–\tau\iota’v,$

よって,$x_{2}\in D(A^{*})^{-1}\cap$.

この場合ある $d\in D,$ $x’\in A^{r}$ について $x_{2}=x’d$ である. 従って
ついて $x_{2}=zu$ .

つまり$’(1\in A^{*}$$x_{2}\in D$$u,$ $v\in A^{+}$.

である.

$y_{2}$

1 は $u$ のある左因子 $u^{l}\neq 1$

後者の場合は $\prime r_{2y2}=zu\ddagger’v\in D$ である.

よって $u_{1)}u_{2}\in D^{*}$ .

つまりある $z\in A^{*}$ に

これは矛盾. 従って,QED.

を alph $(u)\cap alph(v)=\emptyset$ とする.

$C=(uv^{+})^{+}=(uv^{m_{1}}uv^{rn_{2}}\cdots uv^{7n}\prime u|r\geq 1,$ $m_{i}\geq 1,1\leq i\leq r\}$.の空でない任意の部分集合は $(1,2)-,$ $(2,1)$ -limited code である.

命題 2 と同様な証明による.

よって証明を略す.

以上により, 例 1 における code $C$ の空でない任意の部分集合は $(2,1)-,(1,2)$ -limited である.

分集合についての主なもののカタログは以下である;

$C$

中の部

123

(1) $D=(abb^{*})(J$苅- し,(2)り,$(p, q)$の空でない任意の部分集合-limited ではない.
を code とする.

$X\subset A^{*}$

かつ$A^{+}XA^{+}\cap X=\emptyset$

正整数 $n$ を固定する.とする.

$D_{0}$

は,$p+q=2$ であるような任意の $P,$ $q\geq 0$ に$p+q=3$ であるような任意の $p,$ $q\geq 3$ に対し $(p, q)$ -liinited であであるとき, $X$ は coinma-free と呼ばれる.
$X$が,$|$$D=(abb^{*})^{n}a$ の空でない任意の部分集合 $D_{0}$は comma-free である.の任意の部分集合(3)の任意の部分集合とする.
(4) Do を $D=$ ab
は $(3,0)-,(0,3)$ -limited である.
(i)Card $(D_{0})=1,$ $D_{0}=\{w\},$ $w\neq a$ , ならば,$n\geq 3$$C^{(n)}=A^{n}\cap C$$D_{0}$

は cornrna-free である.

$)^{*}a$$($$D_{0}$は任意の整数 $k\geq 1$ に対し $(k, 0)-,(0, k)$ -limitcd ではない.
(ii) $Cr/,’\cdot d(D_{0})\geq 2$ ならば,を満たす $n\geq 0,$ $m\geq 2$ , が存在したら, $D0$ は 1, $1)-,$ $(0, k)-,$ $(k, 0)$ -limited ではな(iii) 次の条件
$D_{0}$$(^{*})$$($$A\backslash$,

ただし $k\geq 2$ .
$(*)$$(ab)^{n}a,$(iv) Card$(ab)^{n+m}a\in D_{0}$$(D_{0})\geq 2,$ $a\in D_{0}$$(**)$$(ab)^{n}a,$例えば,$D_{0}=${

かっある $n\leq l\leq n+m$ , であるようなであり,かつ次の条件 $(**)$ を満たすとき$(ab)^{n+m}a\in D_{0},$ $m>0,$$a,$$aba$ ,ababa}$n\geq 0\Rightarrow(ab)^{l}a\in D_{0},$$\forall l,$$l$$D_{0}$$|$

こ $r’J-$ し $(ab)^{l}a\not\in D0$.

は (1,l)-limitted である.

$n\leq l\leq n+m$ .

は $(1,1)$ -limited code である.

$M_{12}=L_{\varphi}((1, t2))=aA$ ” $b$ でその基底は$C=\{a^{\tau r\iota}b^{n}|m., n\geq 1\}$

この $C$ についての空でない部分集合 $D$ は code である.

命題 4. $u,$ $v\in A^{+}\rangle alph(u)\cap alph(v)=\emptyset$ とする.

.

以下 $D$ について基本的なものを見出す.

$u^{+}v^{+}$の任意の空でない部分集合は $(1,2)-,(2,1)-$

limited である.
証明略.

(5) $T$ を自然数全体の集合 $N,$ $0\not\in N$ , の任意の空でない部分集合とする.
する.

$D=\{a^{n}\cdot b^{\alpha(n.)}|n\in S\}$$\alpha$: $Sarrow N$ を任意の単射ととおく.

(i) もし任意の $m,$ $n\in S$ に対し, 条件 $[m<n\Rightarrow\alpha(m)<\alpha(n)]$ を満たすならば, $D$ は $p+q=2$ であるような任意の ), $q\geq 0$ に対し-limited である. また $Ccx\tau\cdot d(D)\geq 2$ ならば, $D$ は comma-free$(J^{J,(}l)$$\int$

ではない.

(ii) もし任意のである.

$rr|,,$.

$71$$\in S$に対し,

条件 $[rn$. $>\tau|-\Rightarrow c\}.(m)<\alpha(r’,)]$ を満たすならば,$D$は comma-frcc

また Card $(D)\geq 2$ ならば, 任意の $p,$ $q\geq 0,$ $p+q=2,$ こ対し $(p, q)$ -limited でない. 特に$\ovalbox{\tt\small REJECT}$$D=(a^{k}b^{\iota-k}|k=1,2,$ $\cdots,$ $n-1\},$ $n\geq 2$ ,とおくと $D$ 1 は comma-free である.

は,
(6) $n\geq 1,$ $a^{r\iota}b^{+}=\{a^{n}b^{k}|k\geq 1\}$ の空でない任意の部分集合である.
(i)
は 2, $0)$ -limited である. もし Card(Do)(ii) もし Card $(D_{0})=1$ ならば,し $(p,O)$ -limited ではない.
$D_{0}$$(0_{;}2)-,(1,1)- 1i_{I\mathfrak{l}1}ited$$D_{0}$$($$\geq\prime 2$

ならば,$p\geq 2$に対124References[1] J.Berstel and D.Perrin, Theory of Codes, Academic Press, New York, 1985.
[2] A.H.Clifford and G.B.Preston, The lgebraic Theory of Semigroups, Vol.1, American MathematicalSociety, Mathematical Surveys 7, 1961.
$Sem\dot{\uparrow,}gro?lpo,nd$ Combinatorial[3]lications. Wilcy, New York, 1979.
[4] H.J.Shyr, Free Monoid and Languages, Hon
Book Co, Taichung, Taiwan,1991.
[5] $Shyrarrow bhc^{3}n$ Yu, Languages and Codes. Tsang Hai Book $Publi_{S}$ } $iing$ Co, Taiwan, 2005.
$\mathcal{A}$$G.L_{c}\iota 11_{P.1}nent,$$\mathcal{A}pp$${\rm Min}$