数理解析研究所講究録1093 巻 1999 年 105-110

105

Extended Reversible

語とその正例からの$\overline{\equiv}-$

多項式時間帰納推論(
佐藤 優子 (
Uemura)Sato)*
大阪府立大学総合科学研究科
大阪府立大学総合科学部
植村

仁

$*$

$**$

$\mathrm{J}\mathrm{i}\mathrm{n}$$\mathrm{M}\mathrm{a}\mathrm{S}\mathrm{a}\mathrm{k}\mathrm{o}$

**

概要:

本稿では、 Angluin によって導入された-reversible オートマトンを拡張し、simple prefix free (SPF) と呼ばれる語の有限集合上で遷移する $(l, k)$ -extended reversible$k$

オートマトンを定義する。 このオートマトンで受理される言語の特徴付け及びそれらの言語族の間の関係等について論じる。
また、 $(l, k)$ -extended reversible 言語の族は正例から多項式時間で推論可能となることを

示す。

1

序

推論可能である。 また, 線形文法に対する Szilard 言語
は「極限における同定」 という枠

や, この言語を simple prefix free (SPF)と呼ばれる語の有限集合上へ拡張した strictly regular

組みで帰納推論の数学的モデルを提案し, 形式言語と言語 (Tanida&Yokomori[10], Yokomori [13]), 同じ

帰納的関数の帰納推論に理論的基盤を与えた。

SPF 上で定義された -simple regular 言語 (Sato&
Sato [8], Watanabe&Sato [11], [12] 等も正訓から多$(\mathrm{M}\mathrm{a}\mathrm{k}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{n}[7])$1967 年,$\mathrm{G}\mathrm{o}\mathrm{l}\mathrm{d}[5]$推論アルゴリズムは, 入力要求$\Rightarrow$

計算$\Rightarrow$$k$$\text{く}$出力という過程の繰り返しである。 本稿で扱う正例からの言語の帰納推論では, 入力として正の事例, すなわち, 目
標言語に含まれる語だけが与えられる。 出力は, 目標

言語を記述するオートマトンや文法等の表現である。
推論可能な言語の族の特徴付け定理が Angluin [2] によって証明されている。 本稿で扱う言語は, Chomsky
階層の最下位にある正則 (regular) 語であるが, この族は, 正例から推論可能ではないことが示されている$\overline{\equiv}-$([5])。これまで, 正距から推論可能となる正則言語の部分族が提案されてきた。 例えば, 語上の正則表現に連接和. Kleene の 演算を高々回施して得られ$)$

項式時間推論可能である。
本稿では Angluin によって導入されたアルファベット$\Sigma$

上の k-reversible オートマトンを拡張し, SPF 集

合上で遷移する $(l, k)$ -extended reversibleと略記) オートマトンを定義する。
マトンで受理される言語を$((l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$言語と呼ぶ。

Angluin の k-reversible 言語は, SPF 集合が場合の$(0, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

言語に対応する。

オート$\Sigma$である$(0, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$言語

は, reversible 言語であるが, $l\geq 1$ ならば, reversible

最近, Head 等 [6] は, 本稿で扱う reversible 言語族と,言語が存在する。本稿では,
言語の特徴付け定理を与え, これらの言語族の間の包含関係を調べる。 本稿の後半は, ( , k)-言語の族が上例から多項式時間で推論可能となることを示す。

strictly locally testable な言語の族を統–的に記述できると呼ばれる言語族を導入し, 正則言語の族
が,言語族を用いて, 正例から近似的に推論可

2

$*$

$n$

る正則言語の族は正例から推論可能である ([9])。また,

ではない$(\iota, k)-$$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$l$$k- \mathrm{D}\mathrm{B}_{n}$$\mathrm{k}-\mathrm{D}\mathrm{B}_{n}$能であることを示した。

正則言語の推論に関しては, 効率的な推論という観点から様々な正則言語が導入されてきた。 Angluin [3]が導入した -reversible 言語は, 正例から多項式時間で$k$

Extended Reversible –\equiv -r---吾$\Sigma$$\lambda$

上の文字列を語と呼び, 語の集合をを除く語の集合を言語という。 言語$\Sigma^{+}$$L_{1},$ $L_{2}$で表す。

$\Sigma^{*}$, 空語の部分集合をに対して連接$\{w_{1}.w_{2}|w_{1}\in L_{1},w_{2}\in L_{2}\}$$\Sigma^{*}$$L_{1}$.

$L_{2}=$

を定義する。 言語 $L$ を

106

$n$

回連接したものを$L^{*}=L^{+}\cup\{\lambda\}$数を$\# S$とし、 さらに$L^{n}$$L^{+}= \bigcup_{n=1}^{\infty}L^{n}$,とする。 また, 有限集合 $S$ の要素の個$T_{L}(w)=\{u\in\Sigma^{*}|wu\in L\}$とする。

語 $w\in\Sigma^{+}$ の長さを $|w|$ とかく。 語

prefix であるとは $w=uv$ となる語$u$が語 $w$ の$v\in\Sigma^{*}$が存在することである。

2.1

また, 語 $w$ に対する $L$ の tail 集合をとする。
言語 $L$ が正則であるための必要十分条件は, $\{T_{L}(w)|$が有限であり, また, 正則言語を受理する最小オートマトン (状態数が最小) は, tail 集合を用いる
定義できることが知られている [1]。同様の方法で, 与えられた $W$ 上の正則言語を受理する最小オートマト$w\in\Sigma^{*}\}$

Extended 有限オートマトン

まず, 文字単位ではなく, 語単位で遷移するオートマ
トンを定義する。
定義 21. 語の集合

$W$が simple$\Sigma^{+}$$\subseteq$と略す) であるとは, 任意の異なる
free($W$ の最初の文字が互いに異なることをいう。
$\mathrm{S}\mathrm{P}\mathrm{F}$prefix$u_{1},$$u_{2}\in$

ンを導入する。
定義 23. 言語 $L\neq$
る。

語 $L$ が $L\subseteq W^{*}$ を満たすとき, $W$ 上の言語という。
以下 $W,$ $W’$ が SPF であることを仮定する。

をいう。

は語の有限集(1)
は状態の有限集合, (2)は受は初期状態の集合, (4)合, (3)
遷移の有限集合。
理状態の集合, (5)$\Delta\subseteq Q\mathrm{x}W\cross Q$$\delta(T_{L}(w), u)=T_{L}(wu),$

かつ任意の $q\in Q,$ $u\in W$ に対して,$\#\{(q, u,p)\in\Delta|P\in Q\}\leq 1$という。

のとき, $M$ は決定性の代わりに遷移部分関数を用いることもある。

$\delta$に対し$\delta^{*}$:$\delta$$u\in W$

トマトン $M_{0}^{W}(L)$ は $L$ を受理する $W$ 上の最小オー

定義 2.5. SPF $W,$ $W’$ に対して, 次の順序関係を導入する。
$W\preceq W’\Leftrightarrow W\subseteq W^{l}+$定義 26. SPF $W$ が言語 $L$ の SPF 生成集合であると:$Q,$ $u\in W,$ $w\in W^{*})$$Q\mathrm{x}W^{*}arrow 2^{Q}$と定義する。 このことがある。 また,$\{q\}$の元からなるとき$q$$L\subseteq W^{*}$

かつ, 任意の $W’\subset\neq W\text{に対して},L\not\subset W^{r_{*}}$であることをいう。 $L$ の SPF 生成集合全体を$\mathrm{W}^{L}$

で

あらわす。

$Q\cross Warrow 2^{Q}$を帰納的に $\delta^{*}(q, \lambda)=q,$ $\delta^{*}(q,wu)=\delta(\delta^{*}(q, w),$ $u)(q\in$$*$は省略される

以下の結果が得られている。

補助定理 27. (Watanabe [11]) 任意の言語 $L$ に対して,w\fallingdotseq は有限束である。

のように状態の集合がただ 1 つ$\mathrm{W}^{L}$と略記する。

extended 有限オートマトン $M$ で受理される言語を$L(M)$ で表す。 明らかに, $L(M)$ は $W$ 上の言語で正則である。上記の extended 有限オートマトンを $W$ 上の

オートマトン, もしくはただ単にオートマトンと呼ぶ。
$W$$w,wu\in \mathrm{P}\mathrm{r}^{W}(L),$定理 24. $W$ 上の正則言語 $L$ に対して, canonical オーは,$\Delta$$F=\{T_{L(w})|w\in L\}$$F\subseteq Q$$Q_{0}\subseteq Q$$\# Q\mathrm{o}\leq 1$

を次のように定義する。

$q_{0}=\tau_{L}(\lambda, ),$$W\subseteq\Sigma^{+}$

$Q$

$=$

トマトンである。

上の extended 有限 X 一トマトンとは, 次の条件を満たす 5 つ組 $M=(Q, W, \Delta, Qo, p)$$M_{0}^{W}(L)$$Q=\{T_{L}(w)|w\in \mathrm{P}\mathrm{r}^{W}(L)\}$なわち, $w=uv,$ $u\in W^{*}$ ならば, $v\in W^{*}$ である。 言$\Sigma$

を $W$ 上の正則言語とす

上の canonical オートマトン$(Q, W, \delta, q_{0}, F)$

上記の定義から, SPF 集合 $W$ は有限集合であり, 任
意の語 $w\in W^{*}$ は, $W$ の語で–意的に分解される。 す定義 22.

$W$$\emptyset$

上の言語 $L$ に対して,$\mathrm{P}\mathrm{r}^{W}(L)$の最大元及び最小元をそれぞれ,書く。 明らかに,$W_{\sup}^{L}$$W_{\sup}^{L},$ $W_{\inf}^{L}$

は $L$ の語に出現する$\Sigma$との文字の集合である。

補助定理 28. (Watanabe [11])と,L$\subseteq L’$

ならば$L,$ $L’$

を言語とする$W_{\inf}^{L}\preceq W_{\inf}^{L’}$を以下のように

補助定理 29. $L$ を正則言語とする。任意の定義する。

$W\in \mathrm{W}^{L}$に対して, $L$ を受理する $W$ 上の canonical オートマ$\mathrm{P}\mathrm{r}^{W}(L)=\{u\in W^{*}|\exists v\in W^{*}s.t.

uv\in L\}$

トンが存在する。

107

上記の結果から, 任意の正則言語
受理する

トマトンが存在する。
受理する

$L$

上のオートマトン及び$W_{\inf}^{L}$と$W_{\inf}^{L}$$M_{\inf}^{L}$$W_{\sup}^{L}$と$M_{\sup}^{L}$に対して,$W_{\sup}^{L}$

$L$

を

上のオー

をそれぞれ,$L$を

上の canonical オートマトンとする。

定理 24, 補助定理 29 から, 次の定理が得られる。
定理 210. (1)$M_{\inf}^{L}$

は, $L$ を受理する SPF 集合上のオートマトンの中で最小の状態数をもつ。 (2)は,通常のアルファベット
上の最小オートマトンである。
$M_{\sup}^{L}$$\Sigma$$W$

上の正則言語 $L$ に対して, 次の集合を定義する。
$=\{w\in \mathrm{P}\mathrm{r}^{W}(L)||w|^{W}=l\}$$\mathrm{p}_{\mathrm{r}_{l}^{W}}(L)$味する。 すなわち, $w=u_{1}u_{2}\cdots u_{n}(u=i\in W)$ に対して, $|w|^{W}=n$ とする。 また, $W$ のオートマトンが与えられているとき, 上記の, と表す。

$\mathrm{P}\mathrm{r}_{l}^{W}(L(M))$

を単に$\mathrm{p}_{\mathrm{r}_{l}^{W}}(M)$$M=(Q, W, \delta, q0, F)$$\delta^{*}(q, v)=q$

態

$q$

$l$

ical オートマトンと呼ぶ。
定義 214. $M=(Q, W, \Delta, q_{0}, F)$ ,$M’=(Q’, Wl, \Delta’, q_{\mathit{0}}, F),$$M’$

が $M$ の $W’$ による

$W,$

$u$

refined であるとは,のとき,かつ $(p, u_{1}, q_{1}),$ (であることと $p,$$q_{1},$$\cdots,$ $q_{n-1},$

$u$

$\in$

$p,$ $q$$\in$$q’\in Q’$$u_{2,q)}2,$ $\cdots,$ $(q_{n-1}, u_{n}, q)\in\Delta’$$q_{1},$となることが同値となることである。
明らかに, $L(M)=L(M’)$ となる。

$W$

Extended Zero Reversible語$\overline{\equiv}-$

上のオートマトン $M=(Q, W, \delta, Q_{0}, F)$ の rever-sal オートマトンとは, $M^{r}=(Q, W, \delta^{r}, F, Qo)$ である。
ただし, $\delta^{r}(p, u)=\{q|p\in\delta(q, u)\},$ $(p\in Q, u\in W)$とする。

$M^{r}$

は, $M$ の遷移の矢印を逆向きにした遷移図をもつ。

を決定性オートマトンとする。

となる語 $v\in W^{+}$ が存在しないとき, 状は loop-free という。

定義 215. $W$ 上のオートマトン $M=(Q, W, \delta, Q0, F)$が extended zero reversible(

定義 211. $M=(Q, W, \delta, q_{0}, F)$ を $W$ 上の決定性
オートマトンとする。 $\delta(q_{0}, v)\in Q$ となる $v\in W^{*}$

に対して, 次のような $M$ の部分オートマトン $M_{v}=$を定義する。

(1) $Q_{v}=\{q\in Q|\exists w\in W^{*}s.t. \delta^{*}(q_{v}, w)\in Q\}$
(2) $W_{v}=\{u\in W|\exists q\in Q_{v}s.t. \delta(q, u)\in Q_{v}\}$(3) $\delta_{v}(q, u)=q’$$\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{Z}\mathrm{R}$と略す) オートマト

ンであるとは,となることである。
$M$$(Q_{v}, W_{v}, \delta_{v}, q_{v’ v}F)$とする。

$W\preceq W’$$=u_{1}u_{2}\cdots u_{n}(uj \in W’)$

$Q,$ $(p, u, q)\in\Delta$

22

ここで, $|w|^{W}$ は語 $w\in W^{*}$ の $W$ における長さを意$M$

上記の定理で述べた $M’$ を言語 $L$ の -tree 型 canon-と $M^{r}$ がともに決定性オートマトン

定義 216. 言語 $L$ が extended zero reversible (extZRと略す) 言語であるとは,

$L$

を受理する

$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$オートマ

トン $M$ が存在することである。 $M$ が $W$ 上のオートマトンのとき, $L$ を $W$ 上の言語の族を$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\Re$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$

言語という。

$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$とする。

-tree 型オートマトンといオー
上記の定義で, $W=\Sigma$ とすると, 上のトマトンは Angluin [3] が導入した zero reversible
トマトン (
オートマトンと略す) となる。
言語の族を乞 N とする。 明らかに,言語は上の言語でもある。 しかし, 逆は成り立たない。

に対しうのは, 任意の $i<l$ と任意の語が状態
roop-free であることをいう。
て,言
例えば, $\Sigma=\{a, b\}$ 上の言語 $L=$ { , ab} は
言語ではない。 従って, 次の定理が成語であるが,$\Sigma$$\Leftrightarrow\delta(q, u)=q’,$$(q, q’\in Q_{v}, u\in W_{v})$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$$\text{オ}-$(4) $F_{v}=Q_{v}\cap F$$\mathrm{Z}\mathrm{R}$

定義 212. $l\geq 1$ とする。 $W$ 上の決定性オートマト
ン $M=(Q, W, \delta, q_{0}, F)$ が$l$$v\in \mathrm{P}\mathrm{r}_{i}^{W}(M)$$\delta(q_{0}, v)$

定理 213. $l\geq 1$ とする。 正則言語 $L$ の canonical
オートマトン $M=M_{\inf}(L)$ に対して, 次の条件を満たす$W_{\inf}^{L}$

任意の
ン $M_{v}’$

上の

$l$

$\mathrm{Z}\mathrm{R}$$\Sigma$$\mathrm{Z}\mathrm{R}$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$$b$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$$\mathrm{Z}\mathrm{R}$り立つ。
定理 2.17.

$\mathrm{Z}\mathrm{J}l\underline{\subset}eXt\mathrm{z}\Re$-tree 型オートマトン $M’$ が存在する。

に対して, $M’$ の部分オートマト
は $M$ の部分オートマトンと状態の名前$v\in \mathrm{p}_{\mathrm{r}_{l}^{W}}(L)$23

Extended Reversible語$\overline{\equiv}-$$M_{v}$の状態の集合は交わりがない。
を除いて等しく, 各
ただし, $W=W_{\inf}^{L}$ とする。
$M_{v}’$

まず, Angluin による -reversible オートマトンを
SPF 集合上のオートマトンに拡張する。
$k$

108

を $W$ 上のオートマトンとし,$M=(Q, W, \delta, q_{0}, F)$

を非負整数とする。 語 $w\in W^{*}$ が状態 $q\in Q$ の

$k$

$k$

-leader というのは,であることを$\delta^{r}(w_{W}^{r}, q)\neq\emptyset$

いう。 ただし, $w=u_{1}u_{2}\cdots u_{n}(ui\in W)$ に対して,とする。

$w_{W}^{r}=u_{n}\cdots u_{2}u_{1}$定理 223. (1) 任意の$(0, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$言語である。 (2) 任意の$k$

言語は, reversible-reversible 言語は, $(0, k)-$語である。 逆は成り立たない。

$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}\overline{\equiv}-$

定理 224. $l\geq 1,$ $k\geq 0$ とする。 reversible ではない言語が存在する o$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

定義 218. $W$ 上のオートマトン $M=(Q, W, \delta, q_{0}, F)$-extended reversible(k-extR と略記) オートマト
ンというのは, 異なる 2 つの状態 $p,.q\in Q$ が伺じ kが共には受理状態でなくか
leader をもつならば,
が

$k$

3

語の正例からの極限同定$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}\overline{\equiv}-$$p,$ $q$

つ, $\delta(p, u)\neq\delta(q, u)(u\in W)$ となることをいう。

定義 219.

$W$

らの効率的な帰納アルゴリズムについて考察する。

上のオートマトン $M=(Q, W, \delta, q_{0}, F)$

が $(l, k)$ -extended reversible オートマトン$((l, k)-\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

オートマトンと略す) であるとは, 任意のの状態の集合が互いに対して, 各部分オートマトン$v\in \mathrm{p}_{\mathrm{r}_{l}^{W}}(M)$$M_{v}$に素となる k-extZR オートマトンとなることである。

オートマトンに受理される言語を$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$extended reversible 言語$(l, k)-\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$((l, k)-\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$とする。

$\bigcup_{l,k}\geq 0(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\Re$tended reversible 言語 ($\mathrm{e}\mathrm{x}\mathrm{t}\Re$$\mathrm{e}\mathrm{x}\mathrm{t}R$に含まれる言語を ex-

言語族の間には次の包含関係が成り立つ。

$(l+1, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$(l, k+1)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

言語を表す。 しかし,

言語か$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$言$l,$ $k\cdot\geq 0$に対して, 以下の包含関係が成り立つ。
$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\Re\subset,$$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\Re\subset\neq(l, k+1)- \mathrm{e}\mathrm{x}\mathrm{t}\Re$$l$

言語の正の事例, すなわち,
本節では,
を受理する
に含まれる語の例だけから効率的にオートマトンを推論学習する問題を考える。 この問題を正元からの帰納推論 ([5]) の枠組みに$L$$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

$L$

$L$

基づいて定式化する。「入力要求$\Rightarrow$

計算$\Rightarrow$という。 推論アルゴリズムの出力は, 推測或いは仮説とも呼ばれる。 本稿では, 推論アルゴリズムに入力と言語の正して提示されるのは, 未知である$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

オートマトンである。
提示であり, 出力は,の正提示とは, 語の無限列
一般に, 言語
で $L=\{w_{n}|n\geq 1\}$ を満たすものをいう。 $(l, k)$ 言語に対して, その初期断片の正提示 $\sigma=w_{1},$$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$w_{1},$ $w_{2},$$L$$w_{2},$

測をとする。入力$M_{n}$がある 1 つの言語に対して, ある
前節の定理 213 より,が存在して -tree 型 canonical オートマトンが存在
$L$

$l$

出力」 と

いう過程を繰り返すアルゴリズムを推論アルゴリズム$\sigma[n]=w1,$ $w_{2},$ $\cdots,$ $w_{n}$,,$(l+1, k)- \mathrm{e}\mathrm{x}\mathrm{t}\Re$$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$

正例からの多項式時間帰納推論$L$語ではないことに注意する。

定理 220.

3.1$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$言語) と呼ぶ。

言語と略記) と呼ぶ。

ここで, 正則表現 $a^{l+k+1}a^{*}$ は,つ$(\iota, k)-$言語の全体を $(l, k)$ -extlR で表し, extiR $=$$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

本節では、 $(l, k)$ -extended reversible 言語の正例か$\cdots$に対するアルゴリズム$\sigma$に対する推測の列$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$$\mathrm{J}A$の推$M_{1},$ $M_{2},$定理 221. 正則言語 $L$ が$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$言語であるため$L(M)=L$ ならば, その推論アルゴリズムク A は, 目標
言語 $L$ の正提示$\sigma$から $L$ を極限同定するという。 $L$

$L$

トンが

オートマトンとなることである。

$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$の$l$$\mathrm{J}A$

は目標言語を正例から極限同定するという。 また, ア
言語を正例からルゴリズム
が, 任意の$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$\mathrm{J}\mathcal{A}$-tree 型 canonical オートマの必要十分条件は,$\cdots$

オートマトン $M$ に収束し,の任意の正提示に対して, $L$ を極限同定するとき,する。

$\cdots$

言語の族は, 推論アル
極限同定するとき,によって正例から推論可能であるという。
ゴリズム$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$$\mathrm{J}A$

定理 222.
$L$$((l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$を正則言語,W$=W_{\inf}^{L}$とする。 $L$ が$(l, k)-\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$であるための必要十分条件は, 任意の $w,$
$W^{*}$

また,言語の特徴付け定理)$u_{1},$ $u_{2},$言語$w’,$ $v\in$$|w|^{W}=l,$ $|w’|^{W}=k,$ $wu_{1}w’v,wu2w^{l}v\in L$’$T_{L}(wu_{1}w’)=TL(wu_{2}w)$$n$におけるアルゴリズムの出力$M_{n}$

がそれまでに入力された事例 (語) を受理するオートマトン

ならば,

に対して

$\Rightarrow$

. 各時点
.

$\mathrm{J}A$は無矛盾という。

$w_{n}\in L(M_{n-1})$

保守的という。

.

ならば, $M_{n}=M_{n-1}$ のとき, J みは109を出力するまでのを受け取ってから, 推測
計算時間がそれまでに入力された語の長さの総和に関に対して, 次々と推測を生成し出力する推論アルゴリ

する多項式のオーダーで抑えられるとき,ズムを与える。

$M_{n}$$w_{n}$$\mathrm{J}A$

は多項式

時間推論アルゴリズムという。
$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

言語の族は, 無矛盾, 保守的かっ多項式時

以下, ある$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$Algorithm IA
入力 : 語の無限列,

間推論アルゴリズムによって正例から推論可能である

出力 :とき, 正例から多項式時間推論可能という。

begin
initialize $i:=0$ ;

次の概念は, Angluin [3] で導入された。 効率的な推論アルゴリズムの構築に重要な役割を果たす概念である。

言語の語の無限列$w_{1},$ $w_{2},$$S\subseteq\Sigma^{*}$$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{z}\mathrm{R}$が $L$ の言語とする。 有限集合$((l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\Re$

tic sample であるとは,(1)語 $L’$ に対して,

における) characteris-$S\subseteq L,$(2) 任意の言$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{Z}\mathrm{R}$ならば $L\subseteq L’$ となること$S\subseteq L’$$\cdots$;$Q_{0}:=\{q_{0}\};W_{0}:=\emptyset;\Delta_{0}:=\emptyset$;

repeat$i:=i+1$ ;let $M_{i-1}=(Q_{i-1}, W_{i-1}, \Delta i-1, q0, F_{i-}1)$ be the current conjecture ;read the next data ;if $w_{i}\in L(M_{i-1})$ then $M_{i}:=M_{i-1}$
else
begin
if
begin
;
;
;
end
;
;
end ;
outputas the i-th conjecture
foreverend$w_{i}$である。

32$\cdots$

オートマトンの無限列$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$M_{0}:=(Q_{0}, W0, \Delta 0, q0, \emptyset)$

定義 31. $L$ を$w_{1},$ $w_{2},$$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

言語の推論アルゴリズム$w_{i}\not\in W_{\dot{f}}^{*}=1$

先ず,

語 $L$ の$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}\overline{\equiv}-$$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{z}\Re$におけるcharacteristic sample を与える。
$M=(Q, W, \delta, q_{0}, F)$を$\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$$W_{i}:=\mathrm{U}\mathrm{P}\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{E}(W_{i-1}, w_{i})$オートマトンとする。

任意の状態 $q\in Q$ に対して次のような集合を定義する。
$\mathrm{p}_{\mathrm{r}\mathrm{e}}(q)$は, 初期状態$q_{0}$から$q$へ最短の遷移回数で遷移する語の集合である。

Post $(q)$ は, 状態$q$から最終状態 $q_{f}\in F$ へ最短の遷$(l, k)- \mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$言語とする。 $L$ の -tree 型$l$canonical オートマトンを $M=(Q, W, \delta, q_{0}, F)$ とする。 ただし, $W=W_{\inf}^{L}$ とする。 この $M$ を用いて,$L$の有限部分集合

し,W$=W_{\inf}^{L}$$S_{L}$$M_{i-1}:=\mathrm{B}\mathrm{I}\mathrm{N}\mathrm{D}(M_{i}-1)$$M_{i}:=\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{S}\mathrm{E}(Wi, M_{i-1}, wi)$

$M_{i}:=\mathrm{C}\mathrm{O}\mathrm{N}\mathrm{s}\mathrm{T}\mathrm{R}\mathrm{U}\mathrm{C}\mathrm{T}(M_{i}, w_{i})$移回数で遷移する語の集合の $q_{f}\in F$ についての和。
定義 32. $L$ を$M_{i-1}:=\mathrm{R}\mathrm{E}\mathrm{F}\mathrm{I}\mathrm{N}\mathrm{E}(W_{i}, Mi-1)$を次のように定義する。 ただとする。

$M_{i}$

ただし,(1) UPDATE$(W_{irightarrow 1}, w_{i})$: 入力$w_{i}$

を生成するため, 現在の SPF $W_{i-1}$ を更新し, 新しい SPF $W_{i}=$$W_{\inf}^{W_{-1}\cup \mathrm{t}\}}w\dot$を出力する。

(2) REFINE $(W_{i}, Mi-1):W_{i-1}\text{上}\sigma)$ k-extR $A^{--}$
トマトン $M_{i-1}$ を$S_{L}= \bigcup_{q\in Q,u\in W\cup\{\lambda\}}\mathrm{P}\mathrm{r}\mathrm{e}(q)\cdot u\cdot \mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}(\delta(q,u)))$$W_{i}$

上の refined オートマトンに変換する。 この操作の前後で $M_{i-1}$ の受理する言語は変補助定理 33. 任意の$W_{\inf}^{L}=W_{\inf}S_{\iota}$$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

言語 $L$ に対して,化しない。

(3) BINDが成り立つ。

よって, 高さ
定理 34. $L$ をは$(l, k)-\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$ある。

$(l, k)- \mathrm{e}\mathrm{x}\mathrm{t}\mathrm{R}$言語とする。 有限集合

$S_{L}$

言語族における characteristic sample で$(M_{i}$

$l$

-1

$)$

:新しい SPF$W_{i}$と REFINE にの tree 構造が変化する。 $|v|^{W}=l$ に対して $(M_{i-1})_{v}$ が k-extR となるようまで合併を繰り返す。

(4) PARSE $(Wi, Mi-1,wi)$ : (2) では, $W_{i-1}$ 上の110

オートマトンをのオートマトンヘ変換した。 ここ$W_{i}$

上のオートマトンが入力 $w_{i}(W_{i}$では, 変換された上の語である) を受理するように, 必要な状態, 受理状$W_{i}$

態及び遷移を追加する。

(5) CONSTRUCT $(Mi,w_{i}):|w_{i}|^{W}\cdot\geq l$ のとき,
$v(\in W_{i}^{+})$ をの prefix $\text{であり},|v|^{W:}=l$ とする。 (4)$w_{i}$

で得られた$W_{i}$

オートマトン

上のオートマトンの$(M_{i})_{v}$$v$に対する部分

は必ずしも k-extR オートマトンとは限らない。 ここでは, そのオートマトンを$k_{- \mathrm{e}\mathrm{X}}\mathrm{t}\mathrm{R}$

オートマトンへと変換する。 $|w_{i}|^{W}\cdot<l$ のとき,M, を出力する。

(1),(2) $,(4)$ の手続きは, Tanida &Yokomori [10],Yokomori [13] によって多項式時間で計算する効率的なアルゴリズムが与えられている。また, (2),(4) に関しては, Angluin [3] による -reversible 言語の推論アルゴリズムを SPF 上のアルゴリズムに変更すればよい。
$k$

入力
力を

$w_{1},$ $w_{2},$ $\cdots w_{n}$$M_{n}$

に対する推論アルゴリズムの出とすると次の結果が成り立つ。

補助定理 35. $L(M_{n})\subseteq L(M_{n+1})$ ,補助定理 36. IA$\{w_{1}, \cdots, w_{n}\}$

る

$l$

の

$n$

$(n\in N)$

番目の出力は,$S_{n}$$=$[4] M. D. Davis, R. Siegal&E. J. Weyuker. Computability, Complexity, and Languages”, Aca“

demic Press., 1994.
[5] E. M. Gold. “Language Identification in the
Limif’, Information and Control., vol. 10, pp.
447-474, 1967.
[6] T. Head, S. Kobayashi &T. Yokomori. ‘(Locally, reversibility, and beyond: Learning languages from from positive data”, in Proceedingsof the 9th International Conference on Algorithmic Learning Theory., Lecture Notes in Artificial
Intelligence., vol. 1501, pp. 191-204, 1998.

[7] E. Makinen. “ The grammatical inference problem for the Szilard languages of linear grammars”, Inpormation Processing Letters., Vol. 36,

pp.203-206, 1990.
[8] K. Sato&M. Sato. “正データからの Simple Regular 言語の多項式時間帰納推論”, 数理解析研究. $290_{-}227,1995$ .
所講究録., Vol. 906,$\mathrm{p}\mathrm{p}$を含む最小の$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

言語を受理す-tree 型 canonical オートマトンである。

[9] M. Sato. “Inductive Inference of Formal Lan. Cybern., Vol. 27-1, pp. 85-106,
guage”, Bull.
$\mathrm{I}\mathrm{n}\mathrm{f}$定理 37. 手続き$\mathrm{I}\mathrm{A}(S)$の計算時間は, $O(nm)$ である。 ただし, $m=\# S,$ $n= \max\{|w||w\in S\}$ とする。

これらの結果から, 次の主定理が示される :定理 38.

$(l, k)-\mathrm{e}\mathrm{X}\mathrm{t}\mathrm{R}$

言語の族は, 正論から多項式時間推論可能である。

参考文献. “ The, Hopcroft, J.E., &Ullman,[1] Aho,Design and Analysis of Computer Algorithms.”,
Addison-Wesley, Reading, Mass., 1974.

1995.
[10] N. Tanida & T. Yokomori. “Polynomial-time
identification of strictly regular languages in thelimif’, IEICE Tkansactions on Information and
Systems., Vol. E75-D, pp. 125-132, 1992.

[11] N. Watanabe&M. Sato. “完全データからの Sim$ple$ Regular 言語の多項式時間帰納推論”, 数理解
析研究所講究録., Vol. 906, pp. 228-235, 1995.

$\mathrm{J}.\mathrm{D}$$\mathrm{a}.\mathrm{v}.$[2] D. Angluin. “Inductive Inference of Formal Languages form Positive Data”, Information andContoral., vol. 45. 117-135, 1980.
[3] D. Angluin. “Inference of Reversible Language”,
Journal of the Association for Computing
Machinary., vol. 29, No.3, pp. 741-765, July

1982.

[12] N. Watanabe&M. Sato. “k-Simple Regular 言語の多項式時間帰納推論”, 情報基礎論ワークショッ
プ., pp. 97-102, 1995.
[13] T. Yokomori. “ On Polynomial-time learnability
in the limit of strictly deterministic automata”,
Machine Learning., Vol. 19, pp. 153-179, 1995.