数理解析研究所講究録 1325 巻 2003 年 116-121

116

2 つの節をもつ正規基本形式体系の正例からの学習
大阪府立大学大学院理学系研究科 * 植村 仁 (Jin Uemura), 道正田 昌 (Masashi Dosyouda)
大阪府立大学総合科学部数理・情報科学科 * * 佐藤 優子 (Masako Sato)

Graduate School of Science, Osaka Prefecture University
Department of Mathematics and Information Sciences
Colledge of Integrated Arts and Sciences, Osaka Prefecture University
*

**

1

序
パターンとは, 定数及び変数からなる有限文字列あり, パターン言語は, 各変数へ定数文字列を代入して得られる文字列からなる. 空列 代入を許す場合, erasing パターン言語といい, 許さ
ない場合, nonerasing パターン言語という. non$\epsilon$

ミングのように機能し, 形式言語を定義する機構として用いることができる. EFS は, 公理 (確定推論による演鐸体系であり,節) の有限集合と従来の EFS では, 項 (パターン) に含まれる変数への空列代入は, 許されていなかった. 本稿では,変数への空列代人を許し, さらに正規 EFS と呼$\mathrm{M}\mathrm{P}$

ばれる節の構文に制限を課した EFS を扱う. 正規

erasing パターン言語の族は, Gold[6] の枠組みで

EFS は, Chomsky 階層における文脈自由言語の正例から推論可能な言語族として,よって導入された. 一方, nonerasing パターン言語の族は, Shinohara[ll] により extended パター
ン言語の名前で導入された. この言語族の推論可能性の問題は, 今日まで未解決である. 昨年, Reidenbach [5] によって, 定数記号が 2 個の場合にこの問題を否定的に解決した. 一方, パターンに含まれる変数が異なる場合, 正規パターンと呼ばれる. Shinohara[11] は, erasing, nonerasing の双方に対して, 正例から多項式時間で推論可能であることを示した. また, Arimura[4] は, 高々個のパターン言語の和の族に関して, 言語の包含関係とパターン集合の構文的包摂関係の等価性を与える Compactness の概念を導入し, Compactness を有する言語和の族を効率的に学習するアルゴリズムを 般的な枠組みで構築した. そして,
著者等は, Compactness が成立する必要十分条件
を nonerasing(Sat0[10]) と erasing(Uemura andSato[15] の双方に対して与えた.

族を記述する能力がある (Arikawa et al. [3]). 空

Angluin[2] に

$k$

–

$)$

本稿では, 2 つの節をもつ正規基本形式体系 (以下, EFS) の正例からの学習問題を扱う. 基本形式

体系は, Smullyan[14] によって, 帰納的関数の理論を再構築するために考案され, その後, Arikawa

et a1.[3] によって, 帰納推論のための統一的な枠踏みとして発展された. EFS は, 論理プログラ

列代人を許す場合も同じ結果が成り立つ.

2 つの節が共に本体 (body) を含まない場合, 正
規 EFS から定義される言語は, 2 つの erasing パ

ターン言語の和で表され, 正規言語である. 一方,

1 つの節が本体を含む場合は, 定義される言語は
必ずしも正規ではないが,正規パターン
er と言語の無限和として表すことができる.
$\mathrm{a}\mathrm{s}\mathrm{s}[] \mathrm{n}\mathrm{g}$

本稿では, 2 つの節からなる正規 EFS を正例から効率的に学習するアルゴリズムの構築のため,

erasing 正規 EFS 言語の性質, 特に包含問題について考察する. 正例から推論可能となる十分条件
として, Wright[16], [8] は, 有限の弾力性の概念を導入した. Shinohara[12] による長さ限定 EFS
言語の族をはじめ, これまでに推論可能となる具体的な言語族は, 殆どこの性質を有する. 残念ながら, 本稿で扱う erasing 正規 EFS 言語の族は,この性質を持たないことが示される. しかし, 言語族が M-有限の厚さと呼ばれる族の性質を持ち,各言語の有限証拠集合の存在が成り立つならぼ,
正例から推論可能である ([7], [9]). 本稿では, M有限の厚さを示し, さらに, 各 erasing 正規 EFS
言語の有限証拠集合を具体的に提示し, 正例からの推論可能性を示している.

117 117

2erasing 正規 EFS 可 Q=-吾
ここでは, 正規基本形式体系 (EFS) 及び erasing

語を導入する. 構文に制約がない–
般的な EFS の定式化及び Chomsky 階層との対応に関しては, Arikawa[3] に詳しい.
は, 兇鮓澆い妨鬚錣蕕覆ね 限集合とする.
通常のアルファベットである.
兇陵彖任禄匕豕
号 (predicate symbol) とよばれ, それぞれの述語
記号には引数 (arity) とよばれる自然数が対応付
けられている. ここでは, 引数が 1 である述語記号のみを扱う. さらに,, 兇噺鬚錣蕕覆げ鳥嗣
$X$
$X$
限集合
を仮定する.
の要素を変数と呼ぶ.
$X$ の要素は $x,$ $y,$
およびそれらに添字をつけたで表すことにする.
の要素を項 (term) またはパターン(pattern) とよび,で表す. 空列
もパターンであることに注意する. パターンに含まれる変数が異なっているとき, 正規
パターンという. 正規パターンの全体集合を正規 EFS(こ対して,$p\in\Pi$

節

と定義し,

$p(\pi)\theta=p(\pi\theta)$$(p(\pi) \- q_{1}(x_{1}), \cdots, q_{n}(x_{m}))\theta=p(\pi)\thetaarrow$$q_{1}(x_{1})\theta,$, q。

と定義する.

$(x_{m})\theta$$\cdots$$\overline{=}-\square$$\Sigma$$\Sigma$

定義 2.3. 節の有限集合
および自然数と集合 $\{p(u\dagger)|u’\in$$\Sigma^{*}\}(p\in\Pi)$に対して, 関係
$p(w)$ を次のように帰納的に定義する.

1.

$\Gamma$$\Gamma$$k$$\Gamma\vdash_{k}$中の base step p(\pi )\leftarrow と任意の代入対して, w=\pi \mbox{\boldmath $\theta$}\in \Sigma ゝならぼ,

2. $p(\pi)arrow- q_{1}(x_{1}),$
代入$\cdots,$(こ対して,$\theta$に$\Gamma\vdash_{1}p(w)$と任意の$q_{n}(x_{n})\in\Gamma$$\Gamma\vdash_{k_{1}}$$\theta$$x_{i}\theta(=w_{i})(i=$$\Sigma$$1,$$\cdots,$

かつ $w=\pi\theta$ ならば,$n)$$\Gamma\vdash_{k}p(u’)$

かつ $k=k_{1}+\cdots+k_{n}+1$$z$$x_{1},$ $y_{1},$ $z_{1},$ $x_{2},$$\cdots$$(\Sigma\cup X)^{*}$$\pi,$$\tau,$$\pi_{1},$$\tau_{1},$$\cdots$$\pi_{2},$$\epsilon$が成り立つとき, $p(u|)$ はから高々なる
steps で証明可能であるといい,が存在するとき, 単にと表し, $p(w)$はから証明可能であるという.

$\Gamma\vdash_{k}p(w)$$\Gamma$$k$$\Gamma\vdash_{k}p(w)$$k$$\Gamma\vdash p(w)$$\Gamma$$\pi$$\mathcal{R}\mathcal{P}$で表す. パターン$\pi$に含まれる変数の集合を定義 24. EFS$S=(\Sigma, \Pi, \Gamma),$$p\in\Pi l_{\sim}^{}$

対して,$V_{\pi}$$L(S,p)=\{u|\in\Sigma^{*}|\Gamma\vdash p(u|)\}$

で表す.
$p,$ $q_{1},$ $\cdots,$ $q_{n}\in$兇$\pi\in \mathcal{R}P$に対して, 次のような式を確定節 (節) という.
$(i)p(\pi)arrow(ii)p(\pi)\succ q_{1}(x_{1}),$

ただし, (ii) では,とする. $p(\pi)$$V_{\pi}$$\cdots,$$=$$q_{n}(x_{n}),$$n\geq 0$$\{x_{1}, x_{2}, \cdots, x_{n}\}$を頭部(head),
を本体 (body) という. また, (i) の式を base step といい, (ii) の式で $n\geq 1$ のとき,
step という. (ii)において, $\pi=x$ となる場合は考えない.
$q_{1}(x_{1}),$ $q_{2}(x_{2}),$と定義する.

$L(S,p)$ は$L(S,p)$ なる

EFS

$S$

$\Sigma$上の言語である.

と述語

$p$

$L=$

が存在するとき,によって定
言語 L\Sigma ゝは etsing 正規 EFS
義可能である, あるいは emsing 正規 EFS 言語という.

$\cdots,$ $q_{n}(x_{n})$$\mathrm{i}_{11}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$個の節をもつ正規 EFS の全体集合を表し,$k$$\mathcal{R}\mathcal{E}^{k}$で$\mathcal{R}\mathcal{E}\mathcal{L}^{k}=\{L(S,p)|S\in \mathcal{R}\mathcal{E}^{k}\}$定義 2.1. 正規基本形式体系 (EFS) は三項組によって定義される.
は確定節の有限集合であり, 公理とよばれる.
$(\Sigma, \Pi,\Gamma)$$\Gamma$

定義 22. 互いに異なる
意のパターン$\tau_{i}\in \mathcal{R}P$$x_{i}(1\leq i\leq n)$

に対し,

と任

$\theta=\{x_{1}:=$の形をした有限集合 (空でもとして, 空列も可能である. 従って, 空列代入を許さない通常の基本形式
体系とは異なり, 代入された後の項が元の項より長さが短くなるという可能性を考えなけれぼなら$\tau_{1},$$\cdots,$パターン

定理 2.1. 言語$L\subseteq\Sigma^{*}$

が文脈自由言語であるた$\tau_{i}$ない.

めの必要十分条件は $L=L(S,p)$ を満たす正規
EFS $S=(\Sigma, \Pi, \Gamma)$ が存在することである.
例 2.1. 正規 EFS $S=(\{a, b\}, \{p\}, \Gamma)$ を次のように定義する.
$\pi$と代入 $\theta=\{x_{1}:=\tau_{1},$$\cdots,$$x_{n}:=$に対して,lこ中に現れるすべての変数. を代入して得られるパターンをで表す.

$\tau_{1}$示される.

$x_{n}:=\tau_{\mathrm{r}\iota}\}$よい) を代入とよぶ.

$\tau_{n}\}$Arikawa et a1.[3] は, 通常の正規 EFS 言語族が
文脈自由言語族に対応することを示した. 本稿で導入した erasing 正規 EFS 言語族でも同じ結果が$\pi$$p(\epsilon)\mathrm{g}-$,$p(axb)arrow p(x)$$x_{i}$$\pi\theta$

このとき,$L(S,p)=\{a^{n}b^{n}|n\geq 0\}$

である.

118

本稿では, 2 つの節をもつ正規 EFS の族を扱う. 節が 2 つしか含まない erasingEFS 言語
では, 言語を定義する述語記号 だけで十分であと表すと, induction step を一度以上使って得らである. 故に,れる定数列の最短の長さは,$|w| \geq\min\{|c(\pi)|, |c(\tau_{\pi})|\}$ 或$w\in L(\Gamma)$ ならば,り, 他の述語記号を含む節は, 冗長な節であることが容易に示される. 従って以下, 正規 EFS を単り立つ.

$\mathcal{R}\mathcal{E}^{2}$$p$$|c(\tau_{\pi})|$に対して,
定義 25. EFS
は, 任意 0)のとき, 既 (reduced) という.
$\Gamma’\subset\Gamma$$\Gamma$を用いる. さらに,で表し, 述語記号はとで定義される erasing 正規言語を単に,は次のいずれが固定されているので,表す.
に,$\Gamma$$p$$L(\Gamma)$$\Gamma$$L(\Gamma)\underline{\subset}L(\Gamma)$$\#\backslash \mathfrak{h}\backslash$$\Gamma$$p$かの形で表すことができる.

(i)
(ii)

3

$\Gamma$$=\{p(\pi)arrow, p(\tau)arrow\}$$\Gamma$$=\{p(\pi)arrow$,$p(\tau)arrow\pi(x_{1}),$ $\cdots$,\pi (xn 垣とかぎ, (ii) の場合は, 順
序対 $\Gamma=(\pi, \tau)$ で表す. (i) の場合,

(i) の場合,$\Gamma=\{\pi, \tau\}$

正例からの帰納推論の正提示
が言語
文字列の無限列であるとは, $\{w_{n}|n\geq 1\}=L$ が成り立つことの番である. 文字列の無限列 $\sigma=u_{1}|,$で表す.
目までの初期部分列を$w_{1},$ $u_{2}|,$$w_{2},$する.

w = \pi\theta\}$とは正規パターン言語と呼ばれ,$L(\pi)$Shinohara[ll] によって, 導入された.
を $\pi=w_{1}X_{1}w_{2}X_{2}\cdots$ wmXmwm 刊とおく. ただ
パターン

し,

$w_{1},$ $w_{m+1}$

は空列も可であるが,$w_{2},$ $\cdots,$’$u_{m}$

は, 長さが 1 以上の変数列では空列ではない.
代入が許ある. erasing 正規パターン言語では,されているので, 次の結果が示されている ([11]):$X_{i}$$\epsilon$$\pi’=w_{1}x_{1}w_{2}x_{2}\cdots w_{m}x_{m}w_{m+1}$,$\cdots$を代入
を標準形と呼ぶ. すべての変数にした定数列を $c(\pi)$ で表すと, $c(\pi)(=c(\pi’))=$$L(\pi)$ の最短の$c(\pi)$ は,$w_{1}w_{2}\cdots w_{m+1}$ である.
定数列である. (i) の場合, $w\in L(\Gamma)$ ならば,$\epsilon$が成り立つ. ただし,$|\pi|$の長さを表す.
一方, (ii) の induction step を含む EFS では,
次の例で示されるように に対して, 標準形を適
は,

$\pi$

$\tau$

用することができない.
仔 22.
$||$

$=$

$\Gamma$$i$$w\not\in L_{i}$$\sigma$$\sigma$

$L$

$L$

$i$

$L\in \mathcal{L}$$\mathcal{L}$$(aa, bx_{1}x_{2}b)$, すなわち,$\Gamma$$=$$\mathcal{L}$を考える. induction step 使って得られる最短の文字列の標準形
は, $b(aa)(aa)b$ である. しかし,
$bxb$ [こ対して, $\Gamma’=(aa, bxb)$ とすると, $b(aa)b$が得られる. 従って, $L(\Gamma)\neq L(\Gamma’)$ である.
$\{p(aa)arrow, p(bx_{1}x_{2}a)arrow p(x_{1}),p(x_{2})\}$$bx_{1}x_{2}b$

な時間がそれまでの入力の長さの和のある多項式
で押えられる時, その推論機械 $M$ は言語族$\Gamma=(\pi, \tau)$

$\pi$

において,

$\tau$のすべての変数に,を代入して得られる正規パターンをパ$\tau_{\pi}$$\mathcal{L}$を正例から多項式時間 (の更新) で推論するという.
また, 言語族を正例から多項式時間 (の更新)で推論する推論機械が存在する時, その言語族は,
正例から多項式時間 (の更新) で推論可能であると$\mathcal{L}$ターン$N\mathrm{x}\Sigma^{*}arrow$$\sigma[n]$$L(\pi)=L(\pi’)$$\pi’$$|w| \geq\min\{|c(\pi)|, |c(\tau)|\}$$n$が帰納的言語の添字付
き族 (indexed family of recursive languages) であるとは, 次のような計算可能関数 :$\{0,1\}$ が存在することをいう: $f(i, w)=1$ , if $w\in$$L_{i};0$ , if
. ここでの添字 は言語を定義す
るオートマトンや形式文法等を意味すると考えられるが, 本稿では前節で扱った正規 EFS 等を意
味する.
推論機械 $M$ とは, 次々に入力を要求し, 次々に出力を生或する実行的な手続きのことであり, $M$が生或する出力を推測と呼ぶ. 文字列の無限列が人力された後, $M$に対して, その有限列$M(\sigma[n])$で表す. 推論機械 $M$
が生或する推測をに対して, 添字 $g\in N$ に収束する
が入力の列とは, ある $m\in N$ が存在し, 任意の $n\geq m$ に対して, $M(\sigma[n])=g$ となることをいう. 推論機械
$M$ が言語を正例から極限同定 (identfficationin the limit) する (または, 単 [こ推論する) とは,の任意の正提示に対して, $M$ が $L_{i}=L$ とな
る添字 l こ収束することをいう. また, 任意の言を正例から極限同定する推論機械 $M$ が語は正例から推論可能で存在するとき, 言語族
あるという.
を正例から推論し, 各
推論機械 $M$ が言語族
入力を受け取ってから推測を出力するまでに必要$\mathcal{L}=L_{1},$ $L_{2},$$f$$\{w \in \Sigma^{*} | \exists\theta s.t.

$\cdots$$\sigma[n]$言語族$L(\Gamma)=L(\pi)\cup L(\tau)$$L$$\cdots$

118 119いう.

Angluin[2] は, 正例からの推論可能性の特徴づけ定理を証明し, 更に, 有限の厚さ等推論可能性の十分条件を提示した. 一方, Wright[16], [8] は, 有限の厚さを一般化した有限の弾力性の概念を導入した. 言語族が有限の弾力性を持つとは, 次の集合的性質を満たす定数列の無限列, 及びの言語の無限列が存在しないことをいう. 任意の $k\geq 1$ に対して,である.
L化$\mathcal{L}$$w_{0},$ $w_{1},$$L_{1},$ $L_{2},$$\mathcal{L}$42 つの節からなる正則基本形式の学習
本節では, 1 つの basic step 及び 1 つの石 duc-tion step からなる正規 EFS
特に$\cdots$$\cdots$$\{w_{0}, w_{1}, \cdots, u_{k}’\}\subseteq$$w_{k+1}\not\in L_{k}$有限の弾力性は, (i) 正例からの推論町能である
ための十分条件であり, (ii) 言語族の和 ([16]) . 積.
連接等 ([7], [9]) の演算に関して閉じている等, 極
めて良い性質を有している. Shinohara[12] による長さ限定 EFS を始めこれまでに正例から推論
可能な具体的な言語族は, 殆どこの性質を有している.

$\Gamma=(\pi, \tau)$について,’ 考える.
をに含まれる変数とし,$\pi\not\in\Sigma$$V_{\pi},$$V_{\tau}$$\pi,$$V_{\tau}$$\tau$とする.

$\{x_{1}, x_{2}, \cdots, x_{n}\}$注意する. パターン$\tau$のすべての変数に$\pi$$\mathcal{R}\mathcal{E}\mathcal{L}^{2}$は有限の弾力性をもたない.

一方, Moriyama&Sato[7] は, M-有限の厚さという有限の厚さを一般化した概念を導入した. 空
でない有限集合に対して,$S\subseteq\Sigma^{*}$

を代入したパターンをで表し,を導入する. ただし,は, 次のように帰納的に定義する :
さらに$\tau_{\pi}$$\Gamma_{\tau}=\bigcup_{t=1}^{\infty}\Gamma_{t}$$\Gamma_{t}$$\Gamma_{1}=\{\tau_{\pi}\}$, where $\tau_{\pi}=\tau\{X::=\pi(i=1, \cdots, n)\}$ ,$\Gamma_{t}=\Gamma_{t-1}\cup\{\tau\{x_{1}:=\xi_{1}, x_{2}:=\xi_{2}, \cdots, x_{n}:=\xi_{n}\}$$|\xi_{i}\in\Gamma_{t-1}\cup\{\pi\}(i=1,2, \cdots, n)\}(t\geq 2)$

ただし, 代入される変数名は, すべて異なるものとする. 明らかに, 任意のに対して,$\xi\preceq\tau$$\xi\in\Gamma_{\tau}$

定理 31. erasing 正規言語族$=$

であること}こ$V_{\tau}\neq\phi$である.

補題 41. EFS $=(\pi, \tau),$ $V_{\tau}=\{x_{1}, \cdots, x_{n}\}$ とをパターンとする.
し,$\xi_{1},$$\xi_{2},$$L(\xi_{i})\subseteq$$\xi_{n}$$\cdots,$

であならば,
ただし, $\theta=\{x_{1}:=\xi_{1}, \cdots, x_{n}:=\xi_{n}\}$ と$L(\Gamma)(i=1, \cdots, n)$る.

$L(\tau\theta)\subseteq L(\Gamma)$

する,

MIN(S, )$\mathcal{L}$$=${$L\in \mathcal{L}|L$

定義 3.1. 言語族

は $S$ の極小言語}

が次の条件を満たすとき, M有限の厚さをもつという. 任意の有限集合に対して, (i), (ii)
#MIN
$L,$
となる
ならば,
が存在することである.

定理 41. EFS$=(\pi, \tau)$に対して,$L(\Gamma)=L(\pi)\cup L(\Gamma_{\tau})$$\mathcal{L}$.

$S\subseteq\Sigma^{*}$$S\subseteq$$(\mathrm{S}, \mathcal{L})<\infty$$L’\subseteq L$$L\in \mathcal{L}$$L’\in \mathrm{M}\mathrm{I}\mathrm{N}(\mathrm{S}, \mathcal{L})$-有限の厚さは, 正例から推論可能であるための十分条件ではないが, 有限の弾力性と同様, 様々な族演算に関して閉じている $([7],[9])$ . 更に, M有限の厚さをもつ族では, 正例からの推論可能性
が「各言語が, 有限証拠集合 (finite tell-tale) をも

上記の補題より, induction step を含む EFS
言語は, パターン言語の和をして表現できることがわかる. しかし, この和は, 無限個の和である.
さらに, 次のパターンを定義する.

$M$つこと」 という集合論的な性質に帰着できる ([9]).

ここで, 言語は,との有限証拠集合を満たす有限集合をいう ([2]).

$L\in \mathcal{L}$$L\in \mathrm{M}\mathrm{I}\mathrm{N}(\mathrm{S}, \mathcal{L})$定理 32. 言語族$\xi$

次の結果は,
補題 42.
(1) 任意の$\Gamma$$\overline{\tau}_{\pi},$$=$$\xi\in\Gamma_{\tau}$$\Gamma_{\tau}$の定義から導ける.

$(\pi, \tau)$

とする.

に対して,

$\xi\preceq\overline{\tau}_{\pi},$

このとき,
(2)

$L(\Gamma_{\tau})\subseteq$$L(\overline{\tau}_{\pi})$$S\subseteq\Sigma^{*}$$\mathcal{L}=L(\Gamma_{1}),$ $L(\Gamma_{2}),$限の「 さをもち, 各言語$\overline{\tau}_{\pi}=\tau\{y:=x\pi x’, y\in V_{\tau}\}(=\tau_{x\pi x’})$$L(\Gamma)\in \mathcal{L}$$\cdots$が M-有の有限証拠集合が存在するならば, 正例から推論可能である.

パターン言語 (の和) の包含問題では, パターンがどのような文字で始まり, どのような文字で終わっているかの情報が重要な key である. パターン($\epsilon$の接頭語で最長の定数列をで表す.
も可能) といい,$\pi$$A_{\pi}$

$\pi$

$\pi$

の接頭定数列の接尾定数列120で表す. $\pi=u’(x\pi’x’)w’$ なも同様に定義し,らぼ, $A_{\pi}=w,$ $B_{\pi}=u’$ である. また, 定数列が変数ならば, $A_{\pi}=B_{\pi}=\pi$ であり,も可) とを含むならば, $\pi=A_{\pi}(x\pi’x’)B_{\pi}$ (表すことが出来る.
を次のように定義する :’ 上の関係がの接頭語であるとき,がの接尾語の場合,で表す. また,
は共に, 半順序関係でで表す. 明らかに,$B_{\pi}$’$\pi\in\Sigma^{*}$$\pi$$\pi’=\epsilon$$\Sigma$$\preceq_{\mathrm{P}},$$\preceq_{s}$$w\in\Sigma^{*}$$v\in\Sigma^{*}$$\mathrm{t}^{1}\preceq_{p}w$

$w$

$v$

$\mathrm{t}$$\preceq_{p},$)$\preceq_{S}u|$$\preceq_{S}$ある.

$(i)\exists i_{0}\geq 1s.t$$\Leftrightarrow\forall \mathrm{i}\geq 0,$.

$\Leftrightarrow$$u|\preceq_{\mathrm{P}}1’w\iota_{0}$$w\preceq_{\mathrm{P}}\mathrm{z}^{1}*$$w\preceq_{p}\mathrm{t}^{i}’ w$$(ii)\exists j\mathrm{o}\geq 1s.t$$v^{*}\Leftrightarrow\forall j\geq 0,$.

$u’\preceq_{S}wv^{\overline{J}0}$$\Leftrightarrow$$u’\preceq_{\mathrm{S}}$$w\preceq_{S}u’ v^{g}$

定理 42. EFS$\Gamma$

$=$

に対して,

$(\pi, \tau)$の命題は等価である.
(1)
または,
(2)
(3) $L(\Gamma_{\tau})\cap L(\pi)=\phi$$A_{\pi}\not\leq_{\mathrm{P}}A:(A_{\tau}\neq\epsilon)$

次は既約である.

$\Gamma$$B_{\pi}\not\leq_{s}B_{\tau}^{*}(B_{\tau}\neq\epsilon)$

上記の定理より, 次の結果が得られる.

補題 43.
とき,$\mathrm{E}\mathrm{F}\mathrm{S}\Gamma=(\pi, \tau),$$A_{\xi}=A_{\tau^{\mathrm{O}}}^{i}A_{\pi}$$i_{0},j\mathrm{o}\geq 1$

,

とする.

$\xi\in\Gamma_{\tau}$$B_{\xi}=B_{\pi}B_{\tau}^{j_{0}}$

この

を満たす

が存在する.

文字列の対 $(u|, v)$ は,または,であるとき, pref $ix$ の関係があるといい, $(w, \tau.’)\in$に対して定Pref で表す. 同様に, Suff も関係
義する.
$v\preceq_{p}u1$$w\preceq_{p}v$

系 4.1. 与えられた EFS

かの決定問題は,
ある.
系 42.

EFS

$\pi$

と

$\tau$

が既約か否の時間で計算可能で$\Gamma=(\pi, \tau)$$O(|\pi|+|\tau|)$のいずれかが v-v パターンならば,は既約ではない.

$\Gamma=(\pi, \tau)$$\preceq_{S}$

補題 44. 変数を含むパターン
に対して, 次が成り立つ. $L(\pi)\cap L(\tau)\neq\phi\Leftrightarrow(A_{\pi}, A_{\tau})\in$$\pi,$

Pref,は既約とし,のとき,をパ$\gamma$$\gamma\not\leq\pi\Leftrightarrow$$L(\gamma)\subseteq L(\Gamma_{\tau})$

ここで, $\Gamma_{\tau*}=\{\xi\in\Gamma_{\tau}|L(\tau_{\pi})\cap L(\xi)=\emptyset\}$ と定義しておく.

次の結果は, 明らかである.

が既約であるとき, 補題 4.4 より,
またはならば,$\Gamma$を変数を含むパターンとする. $\pi=$$A_{\pi}(x\pi’x’)B_{\pi}$ 及び, $\tau=A_{\tau}(x\tau’x’)B_{\tau}$に対して,を含むとする. このとき,は部分列として,,$\pi,$$\Gamma=(\pi, \tau)$$L(\gamma)\subseteq L(\Gamma)$$\tau$$(B_{\pi}, B_{\tau})\in \mathrm{S}\mathrm{u}\mathrm{f}\mathrm{f}$補題 45.

補題 48. EFS
ターンとする.

$\tau$$(A\epsilon, A_{\tau_{\pi}})\not\in Pref$$\xi\in\Gamma_{\tau*}$$(B\epsilon, B_{\tau_{\pi}})\not\in$$Suff$ が成立する.

$\pi’$$\tau’$

補題 4.9. 既約な EFS $\Gamma=(\pi, \tau)$ に対して,$\Gamma_{\tau},$

補題 46. $\Gamma=(\pi, \tau)$ とする. $A_{\pi}=B_{\pi}=\epsilon$ ならば,$L(\Gamma_{\tau})\subseteq L(\pi)$, すなわち, $L(\Gamma)=L(\pi)$ .

$L(\xi)\cap L(\tau_{\pi})\neq\emptyset\Rightarrow\xi\preceq\tau_{\pi}$

なわち,

, す
のときである. 本節では,が既約となるのは,$L(\Gamma_{\tau})\not\subset L(\pi)$$L(\pi)\subseteq L(\Gamma)$

既約 EFS の性質について論じる.

補題 46 より,$\pi$

が変数で始まり, 変数で終わる

パターン (v-v パターンという) ならば, $\Gamma=(\pi, \tau)$は既約ではない. また,ならば, $\Gamma=(\pi, \tau)$は既約である. 以下, EFS が既約となる条件について考察する. 文字列$i\geq 0$ が存在するとき,も同様に定義する.
補題 47.

$\pi\in\Sigma^{*}$$w\in\Sigma^{*}$

は,
で表す.

$W\preceq_{p}\mathrm{t}^{\mathrm{t}}i$$W\preceq_{p}\mathrm{t}’*$$w\in\Sigma^{*},$ $v\in\Sigma^{+}$$\Gamma$$\Gamma=(\pi, \tau)$は既約とし,のとき,$L(\gamma)\subseteq L(\Gamma_{\tau})$$\gamma$を$\gamma\not\leq$$\tau_{\pi}\Leftrightarrow L(\gamma)\subseteq L(\Gamma_{\tau*})$の各変数に かまたは, 1 定
数文字を代入して得られる $L(\pi)$ の有限部分集合
を $S(\pi)$ で表す.
パターン$\pi\in \mathcal{R}\mathcal{P}$

補題 411. EFS
ターンとする.

$\Gamma=(\pi, \tau)$$S(\gamma)\subseteq L(\Gamma_{\tau})$$\epsilon$は既約とし,のとき,$\gamma$をパとなる$”\preceq_{S}v^{*}$$S(\gamma)\not\subset L(\tau_{\pi})\Leftrightarrow L(\gamma)\subseteq L(\Gamma_{\tau*})$

定理 43. EFSとする.

$L(\Gamma_{\tau})=L(\tau_{\pi})\cup$$L(\Gamma_{\tau*})=\emptyset$

補題 410. EFS
パターンとする.

既約 EFS の特徴付け$\Gamma=(\pi, \tau)$が既約であるとき,, L(\mbox{\boldmath $\tau$} ２

系 43.
$L(\Gamma_{\tau*})$$4.\acute{1}$$\xi\in$$B_{\pi}\preceq_{\mathit{8}}B_{\tau}$$\tau\preceq\pi\Leftrightarrow A_{\pi}\preceq_{\mathrm{P}}A_{\tau}$$\Gamma=(\pi, \tau),$ $\Gamma’=(\alpha, \beta)$とする. このとき,$L(\Gamma’)\subseteq L(\Gamma)$は既約ならば, 次の等121 121

価性が成り立つ.

(i)$L(\Gamma’)\subseteq L(\pi)\Leftrightarrow\alpha\preceq\pi,$(ii)$L(\alpha)\subseteq L(\pi),$ $L(\Gamma_{\beta}’)\subseteq L(\Gamma_{\mathcal{T}})$$\Leftrightarrow\alpha\preceq\pi$

(iii)

,

$L(\alpha)\subseteq L(\Gamma_{\tau}),$$\beta_{\alpha}\not\leq\pi$,

ence, 775, 646-660, (1994).

,[5] D. Reidenbach: Result on Inductive Inference Exof

tended Patte.m Languages, Lecture Notes in Artificial Intellegence, 2533, 308-320, (2002).

$L(\Gamma_{\beta}’)\subseteq L(\pi)$$\Leftrightarrow\alpha\not\leq\pi,$ $\beta_{\alpha}\preceq\pi,$4.2$\beta_{\alpha}\preceq\pi$$\beta_{\beta\alpha}\preceq\pi$.

の有限証拠集合$L(\Gamma)$[4] H. Arimura, T. Shinohara and S. Otsuki: Finding minimal generalizations for unionsof patternlanguages and its aPPlication to inductive inference
from positive data, Lecture Notes in Computer Sci-

この節では, 正規 EFS 言語の族が正例から帰納推論可能であることにつぃて考える. そのためには, この族が $M$-有限の厚さをもっこと, 各 EFS

言語が有限証拠集合をもっことを確認する必要がある.

[6] E. M. Gold: Language ident(6cati0n in the limit,
Information and Control, 10, 447-474, (1967).
[7] T. Moriyama and M. Sato: Properties of language
classes with finite elasticity, IEICE ’Ransactions
on lnformation and Systems, E78-D(5), 532-538,(1995).

[8] T. Motoki, T. Shinohara and K. Wright: The correct
definition of finite elasticity: corrigendum to identification of unions, in Proceedings of the Fourth
Annual ACM Workshop on Computational Learning Theory, 375-373, (1991).
[9] M. Sato: Inductive lnference of Fomal Language,
Bull.
. Cybern., 27-1, 85-106, (1995).
[10] M. Sato, Y. Mukouchi and D. Zheng: Characteristic sets for unions of regedar Pattem languages andcomPactness, Lecture Notes in Artificial Intelligence,
1501, 220-233, (1998).
[11] T.Shinohara: Polynomial time inference of extended
regular pattern languages, RIMS Symposia on So&
ware Science and Engineering, Kyoto, 1982, Pro
ceedings, Lecture Notes in Computer Science, 147,
115-127, (1982).
[12] T.Shinohara: Rich classes infemble from positive
data: length-bounded elementary forrnal systems,
Information and compulation, 108, 175-186, (1994).
[13] T. Shinohara and H. Arimura: Inductive injerenceof unbounded unions of pattern languages $fmm$ positive data, Lecture Notes in Artificial Intelligence,
1160, 256-271, (1996).
$\mathrm{l}\mathrm{n}\mathrm{f}$定理 4.4. 正規 EFS 言語の族の厚さをもつ.

EFS合$\Gamma=\{\pi, \tau\}$を定義する$S(\Gamma)$

に対して,

:

$\mathcal{R}\mathcal{E}\mathcal{L}^{2}$$L(\Gamma)$

は, M-有限の有限部分集$S(\Gamma)=S(\pi)\cup S(\tau)$.

$\#\Sigma\geq 4$のとき, これはの有限証拠集合となることが示されている ([15]).
$L(\Gamma)$

また, induction step を含む既約な EFSに対して,$(\pi, \tau)$の最短の定数列は,,の最短の定数列は,だけであること$S(\tau_{\tau_{\tau_{\pi}}})L(\Gamma),$$L(\Gamma_{\tau})$$\Gamma=$$S(\Gamma)=S(\pi)\cup S(\tau_{\pi})\cup S(\tau_{\tau_{\pi}})\cup$$L(\pi)$$c(\pi)$$c(\tau_{\pi})$に注意する.
定理 4.5. 任意の既約正規 EFS

は,証拠集合であるて,$S(\Gamma)$$L(\Gamma)$の(族$\mathcal{R}\mathcal{E}\mathcal{L}^{2}$$\Gamma\in \mathcal{R}\mathcal{E}^{2}$に対しにおける) 有限定理 4.4, 4.5 より, 次の結果が得られる.
定理 46. 正規 EFS 言語の族$\mathcal{R}\mathcal{E}\mathcal{L}^{2}$は, 正例から帰納推論可能である.

参考文献[1] D.Angluin: Finding pattems common to a setofstrings, Information and Control, 21, 4662, (1980).
[2] D. Angluin: Inductive inference offomal languages$fompos:tive$ data, lnformation and Control, 45,
117-135, (1980).
[3] S. Arikawa , T.Shinohara and A. Yamamoto: Elementary Formal Systems as a Unifying Fbmeworkfor Language Learning, Proc. 2nd COLT, 312-327,/1OQO$\backslash$[14].Smullyan: Theory of Fomal Systems, Princ&
ton University Press, Prinston, New Jersey, (1961).
$\mathrm{R}.\mathrm{M}$[15] J. Uemura and M. Sato: Compactness and Learningof Unions of Erasing Regular Pattern Languages,
Lecture Notes in Artificial lntellig\’ence, 2533, 293307, (2002).

[16] K.Wright: Identification of unions of languqges
drawn from positive data, Proc. the 2nd Annual
Workshop on Computational Learning Theory, 328333, (1989).