数理解析研究所講究録
第 833 巻 1993 年 214-224

214

正データからの EFS の帰納推論可能性について–有限の弾力性をもつ言語族の Closure Properties とその特徴付け–
大阪府立大学総合科学部
大阪府立大学総合科学部

1

森山隆史
佐藤優子

(Takashi Moriyama)(Masako Sato)

Abstract
In this paper, we consider a subfamily of language classes to be recursively inferable frompositive data, which is closed under various operations such as sum, intersection, concatenationand so on. It is shown that the family of language classes$L$with finite elasticity is closed undersuch operations. It implies that any language class obtained by finitely applying operations togiven ones contained in$L$is inferable from positive data.

The above discussions on closure operations are developed for an elementary formal system(EFS for short) as a unifying framework for inductive inference of various language classes. We

introduce $\max$ length bounded EFSs by which any contex sensitive language can be represented,

and for which operations corresponding to language operations can naturally be defined. It isshown that any EFS language class obtained by applying such operations to given $\max$ length

bouded EFSs defining language classes with finite elasticity is inferable from positive data.
Furthermore, we obtain two theorems characterizing a $\max$ length bouded EFS language classto have finite elasticity, and to be inferable from positive data, respectively.

2

言語族の帰納推論

2.1

準備$L_{1},$$L_{2},$$\cdots$をアルファベッ ト$\Sigma$

上の言語とする. 言語族の添字付き族であるとは, 任意の $i\in N$ と任意の語$\mathcal{L}=L_{1},$$w\in\Sigma^{*}$$L_{2},$$\cdots$が帰納的言語に対して) $w\in L_{i}$ かどうかを決定する計算可能関数 $f$ が存在することをいう. 以降, 言語族は帰納的言語の添字付き族とする.
$w_{1},$ $w_{2},$$\cdots$$\mathcal{L}$

の言語

を言語

$L$

$L$

に対して,

$L$

のすべての語が少なくとも一度は現れるような無限列の正提示という. 推論機械とは, ときどき入力を要求し, ときどき推測を生成するような実行的手続きである. 推論機械 $M$ が正データから$L$を推論するとは,の任意の正提示を $M$ に与えたとき, $M$ の生成する推測の列が $L=L_{j}$ となるることをいう. 言語族$\mathcal{L}$が正データから帰納推論可能であるとは, 任意のタから推論する推論機械 $JI$ が存在することである.

$L$

$j$

に収束す

$L\in \mathcal{L}$

を正デー

215
定義 2.1

:

$T$

を言語族,

$\mathcal{L}$とする.

$T\subseteq\Sigma^{*}$

で $L$ の有限証拠集合 (以下, ftt)$\mathcal{L}$$T$$\Leftrightarrow(1)$: ftt をもつ$\mathcal{L}$$L\in \mathcal{L},$:$\Leftrightarrow\forall L\in \mathcal{L},$の有限部分集合, (2)$L$$\exists T\subseteq\sum^{*}s.t$. $T$ :$\mathcal{L}$s.t.

$/\Xi L’\in \mathcal{L}$$T\subseteq L’\subsetneq L$.

で $L$ の ftt.

Angluin [1] は, 言語族が正データから帰納推論可能であるための必要十分条件は, その任意の言語の ftt の要素を枚挙する実行的な手続きが存在することであることを示した. さらに, 次にのべる有限の厚さという条件が帰納推論可能であるための十分条件であることを示し, それを用いてパターン言語と呼ばれる言語族が正データから帰納推論可能であることを示した [1].

定義 22を言語族とする.

$\mathcal{L}$: 有限の厚さ$\mathcal{L}$集合$S\subseteq\Sigma^{*}$$\#\{L\in \mathcal{L}|w\in L\}<\infty$$\Leftrightarrow\forall w\in\Sigma^{*},$

が集合対 $I=(T, F)(T, F\subseteq\Sigma^{*})$ と無矛盾であるとは,$T\subseteq S$

かつ $F\subseteq S^{C}$となることである.

定義 23
$I$

:

$\mathcal{L}$$\mathcal{L}$を言語族,$L\in \mathcal{L},$$I=(T, F)$ を有限な集合対とする.

で $L$ の有限証拠集合対 (以下, pftt)$\Leftrightarrow(1)L$:に無矛盾, (2)$I$$/\not\geq$]$L’\in \mathcal{L}$s.t.

$L\not\in L’$

かつ $L’$ :

$I$

に無矛盾

pftt をもつ言語族は正データから帰納推論可能であることが示されている [4].
定義 24
$L$

:

$\mathcal{L}$

を言語族,

の極小言語

$S$

空でない有限集合

定義 2.5$\mathcal{L}$$\mathcal{L}$$\Leftrightarrow S\subseteq L$$S\subseteq\Sigma^{*}$(1)$\mathcal{L}$$S\subseteq\Sigma^{*}$

かっ

とする.

$\exists L’\in \mathcal{L}s.t$.

$S\subseteq L’\subsetneq L$に対して, $MIN(S, \mathcal{L})=$ {$L\in \mathcal{L}|L:\prime 5^{-}$の極小言語} とする.

を言語族とする.

: $M-$ 有限の厚さ

定理 2.1 [3]$L\in \mathcal{L},$$\Leftrightarrow\forall S(\subseteq\Sigma^{*})$

言語族$\mathcal{L}$: 有限集合, $\neq MIN()9,$$\mathcal{L}$) $<\infty$

を有限の厚さとする. 次の (1), (2), (3) は同値である:: 正データから帰納推論可能, (2)$\mathcal{L}$: ftt をもつ, (3)$\mathcal{L}$: pftt をもつ

216
有限な弾力性をもつ族の Closure Properties

2.2

Wright [7] は有限の厚さを一般化した有限の弾力性という概念を導入し, この性質が正データから帰納推論可能であるための十分条件であることを示した. この節では言語族の演算 (和, 共通部分, 連接等) を導入し) 有限の弾力性という言語族の性質がこれらの演算に関して保持されることを示す.
定義 26$\mathcal{L}$$\mathcal{L}$を言語族とする.

: 有限の弾力性をもつ$\Leftrightarrow\not\subset$]$w_{0}.,$$w_{1},$$\forall k\in N,$$\cdots(\in\Sigma^{*}),$$/\Xi L_{1},$ $L_{2},$$\cdots(\in \mathcal{L})$$\{w_{0}, w_{1}, \cdots, w_{k-1}\}\subseteq L_{k},$s.t.

$w_{k}\not\in L_{k}$有限の弾力性をもつ言語族は正データから帰納推論可能である.

定理 22[7]有限の弾力性をもつ言語族のすべての集まりを $L$ とおく.
言語族$\mathcal{L}_{1},$$\mathcal{L}_{2}$定理 23 [7]の和演算$\cup\sim$, 共通部分演算$\overline{\cap}$, 連接演算$-$を次のように定義する:$\mathcal{L}_{1}\cup-\mathcal{L}_{2}$$=$$\{L_{1}\cup L_{2}|L_{1}\in \mathcal{L}_{1}, L_{2}\in \mathcal{L}_{2}\}$$\mathcal{L}_{1}\overline{\cap}\mathcal{L}_{2}$$=$$\{L_{1}\cap L_{2}|L_{1}\in \mathcal{L}_{1}, L_{2}\in \mathcal{L}_{2}\}$$\mathcal{L}_{I}^{-}\mathcal{L}_{2}$$=$$\{L_{I}\cdot L_{2}|L_{I}\in \mathcal{L}_{1}, L_{2}\in \mathcal{L}_{2}\}$言語族$\mathcal{L}_{1},$$\mathcal{L}_{2}$が有限の弾力性をもつならば,$\mathcal{L}_{1}\cup-\mathcal{L}_{2}$

も有限の弾力性を

もつ.

定理 24

言語族

$\mathcal{L}_{1},$$\mathcal{L}_{2}$が有限の弾力性をもつならば,$\mathcal{L}_{1}\overline{\cap}\mathcal{L}_{2},$$\mathcal{L}_{1}^{-}\mathcal{L}_{2},$$\mathcal{L}_{1}\cup \mathcal{L}_{2}$も有限の弾力性をもつ.

proof. ここでは$\mathcal{L}_{1}^{\sim}\mathcal{L}_{2}$についてのみ証明する. 任意の $k\in N$ に対して,$\{w_{0}, w_{1}, \cdots w_{k-1}\}\subseteq L_{k}^{1}\cdot L_{k}^{2}$となる無限列$w_{0},$ $w_{1},$$\cdots$と$L_{1}^{1}\cdot L_{1}^{2},$$L_{2}^{1}\cdot L_{2}^{2},$$\cdots$$0$$w_{k}\not\in L_{k}^{1}\cdot L_{k}^{2}$(ただし,定する. 次のような方法で砺を帰納的に構成する:

step :,$L_{i}^{1}\in \mathcal{L}_{1},$$L_{l}^{2}\in \mathcal{L}_{2}$) が存在すると仮217$w_{0}$の 2 分割の仕方は有限であり, 任意の $k\geq 1$ に対して,

で $\#\{k\in N|w_{0}^{1}\in L_{k}^{1}, w_{0}^{2}\in L_{k}^{2}\}=\infty$ となる$w_{0}^{1},$$w_{0}^{2}$$W_{0}\in L_{k}^{1}\cdot L_{k}^{2}$だから,$w_{0}=w_{0}^{1}w_{0}^{2}$が存在する.

$N_{0}=\{k\in N|w_{0}^{1}\in L_{k}^{1}, w_{0}^{2}\in L_{k}^{2}\}$$k_{1}= \min\{k|k\in N_{0}\}$とし, step 1 へ行く.

step $n(n>0)$ :$w_{k_{n}}$$L_{k}^{1}\cdot L_{k}^{2}$$w_{k_{n}}^{2}$の 2 分割の仕方は有限であり, 任意の $k\in N_{n-1}$ (ただし, $k\neq k_{n}$ ) #こ対して,だから,$w_{k_{n}}\in$

で $\#\{k\in 1V_{n-1}|w_{k_{n}}^{1}\in L_{k}^{1}, w_{k_{n}}^{2}\in L_{k}^{2}\}=\infty$ を満たす

$w_{k_{n}}=w_{k_{n}}^{1}w_{k_{n}}^{2}$$w_{k_{n}}^{1}$,が存在する.

{$N_{n}=$$k\in N_{n-1}|w_{k}^{1}$$\in L_{k}^{1},$$w_{k_{n}}^{2}\in L_{k}^{2}$。

}$k_{n+1}= \min\{k|k\in N_{n}\}$とし, step $n+1$ へ行く.
任意の $n\geq 1$ に対して,の定め方から, 明らかに

$N_{n}$

である. 一方, $k_{n}\in N_{n-1},$ $k_{n+1}\in$ 凡および,$k_{n}\leq k_{n+1}$$N_{n-1}\supseteq$

したがって,

凡である.

$w_{k_{n}}\not\in L_{k_{n}}^{1}$. Lk2。より,$k_{n}\not\in N_{n}$である. ゆえに, $k_{n}<k_{n+1}$ が成り立つ.

この方法で得られる無限列$w_{k_{0}}^{1}w_{k_{\text{。}}}^{2},$$w_{k_{1}}^{1}w_{k_{1}}^{2},$$\cdots$;$L_{k_{1}}^{1}\cdot L_{k_{1}}^{2},$$L_{k_{2}}^{1}\cdot L_{k_{2}}^{2},$$\cdots$(ただし, $k_{0}=0$ )は, 任意の $n\in N$ に対して,$\{w_{k_{0}}^{1}, \cdots, w_{k_{n-1}}^{1}\}\in L_{k_{n}}^{1}$を満たしている.
を満たす$n$$w_{k_{n}}^{1}\not\in L_{k_{n}}^{1}$か$w_{k_{n}}^{1}\not\in L_{k_{n}}^{1}$

ためて$k_{0},$$k_{1},$$\cdots$

を満たす

$n$

定義 27

$w_{k}^{2}$

言語族$\mathcal{L}$$\mathcal{L}^{\sim}\mathcal{L}$

定理 25

性をもつ.

は

$\mathcal{L}^{2}\sim$の少なくとも一方は成り立つ. すなわち,$\not\in L_{k_{n}}^{2}$。

$w_{k_{\text{。}}}^{1},$

を満たす

$n$

$w_{k_{n}}^{1}\not\in L_{k_{n}}^{I}$が無限個存在する. 一般性を失うこ$w_{k_{1}}^{1},$$\cdots;L_{k_{1}}^{1},$$L_{k_{2}}^{I},$$\cdots$が存在し, これは$\mathcal{L}_{1}$が有限の$\blacksquare$に対して, 次の演算を導入する:$\mathcal{L}^{n}\sim=\{L^{n}|L\in \mathcal{L}\}(n\geq 1)$(注$w_{k_{n}}^{1}w_{k_{n}}^{2}\not\in L_{k_{n}}^{1}\cdot L_{k_{n}}^{2}$

が無限個存在するであるとしてよい. そのような添字をあらとすると, 無限列

弾力性をもつことに矛盾する.

$\{w_{k_{0}}^{2}, \cdots, w_{k_{n-1}}^{2}\}\in L_{k_{n})}^{2}$$w_{k_{n}}^{2}\not\in L_{k_{n}}^{2}$

が無限個存在するか

となく

,

,

$\mathcal{L}^{*}=\sim\{L^{*}|L\in \mathcal{L}\}$,$\mathcal{L}^{\mp}=\{L^{+}|L\in \mathcal{L}\}$とは異なる).

言語族$\mathcal{L}$が有限の弾力性をもつならば, 言語族$\mathcal{L}^{n}\sim,$$\mathcal{L}^{\mp},$$\mathcal{L}^{*}-$

は有限の弾力218
proof. これらの証明は定理 2.4 の証明と同様の方法で示すことができる.
言語族

に対して,

$\mathcal{L}$$\blacksquare$とする. 次の例は $L$ が言語族の補集合演算に関$\mathcal{L}^{C}=\{L^{C}|L\in \mathcal{L}\}$

しては閉じていないことを示す:
例 2.1$\mathcal{L}=L_{1},$ $L_{2},$$L_{k}^{C},$の帰納的枚挙を$\Sigma^{*}$$\cdot$.

$w_{k}\not\in L_{k}^{C}$

は有限の厚さであるが,を満たす無限夕|Jとし, $L_{k}=\Sigma^{*}-\{w_{0}, \cdots, w_{k-1}\}(k\in N)$ とする.

$\cdots$$w_{0},$ $w_{1},$$w_{0},$ $w_{1},$$\mathcal{L}^{C}$

では任意の $k\in N$ に対して, $\{w_{0}, \cdots, w_{k-1}\}\subseteq$$\cdots;L_{1}^{C},$$L_{2}^{C},$$\cdots$が存在する. したがって,$\mathcal{L}^{C}$は有限の弾力性をもたない.

有限の弾力性をもつ言語族に対して, 演算

定理 26$\cup-,\tilde{\cap},$$\overline{n}*\sim\mp$$-$$\cup,$

を有限回適用して得られる言語族は正データから帰納推論可能である.

3

EFS の帰納推論

3.1

EFS

$\Sigma$を定数記号の有限集合, $X$ を変数記号の可算集合, 垣を述語記号の有限集合とする (た, 垣は互いに素な集合とする). 述語記号は引数の個数を表す非負整数を伴ってだし,$\Sigma,$

いる.

$(\Sigma\cup X)^{+}$$X$の要素をパターンという.

$7\ulcorner_{1}\cdots T_{n}$をパターン,とする. $p(\pi_{1}, \cdots, 7r_{n})$ の形の式をアトムという. パターン$p(\pi_{1}, \cdots, \pi_{n})$

$\pi$

$p$

$\cdots,$$B_{n}$$n$

引数の述語記号の長さを回で表し, アトム

に対しては, $|p(\pi_{1}, \cdots, \pi_{n})|=|7i_{1}|+\cdots$ +|\pi 鴎とする.

をアトムとする. $Aarrow B_{1},$を$A,$ $B_{1},$$\cdots,$$B_{n}(n\geq 0)$の形の式を確定節という. そして, 確定節の有限集合をEFS (elementary formal system) という.
節 $C$ は EFS$\Gamma$から証明可能である ($\Gamma\vdash C$で表す) とは,$C$が$\Gamma$の公理から代入とmodus ponens を有限回適用することにより得られることをいう (ただし, 代入とは変数記
号をパターンに置き換えるもののことをいう).
基礎アトム全体の集合をエルブラン基底といい, $HB$ で表す. エルブラン基底の部分集合$S\subseteq HB$をエルブラン解釈という. EFS$\Gamma$のすべての節を真にするエルブラン解釈$S$を

エルブランモデルといい, その中で最小のモデルを最小モデルという ( $M(\Gamma)$ で表す). EFS$\Gamma$と$n$引数の述語記号

$p$

に対して,

$L(\Gamma, p)=\{(w_{1}, \cdots, w_{n})\in(\Sigma^{+})^{?t}|\Gamma\vdash p(w_{1}, \cdots, w_{n})\}$

219と定義する.
となる EFS$p$$\Gamma$

が 1 引数のとき, $L(\Gamma, p)$ は$\Sigma$

上の言語となる. ある言語

および 1 引数 $p\in$ 垣が存在するなら

$L$

$L$

に対し, $L=L(\Gamma, p)$は言語であるという. また,–般性を失うことなく各言語を定義する 1 引数の述語記号を $p\in$ 垣と固定してもよい. したがって, $L(\Gamma, p)$ を単に
定義 31$L(\Gamma)$

節 $Aarrow B_{1},$とかく.

$\cdots,$$B_{n}$

が任意の代入 に対して, $|A\theta|\geq|B_{1}\theta|+\cdots+|B_{n}\theta|$ とな

るとき, この節は長さ限定であるという. EFS$\theta$$\Gamma$が長さ限定であるとは, 任意の節 $C\in\Gamma$

が長さ限定であることをいう.
言語DO$L\subseteq\Sigma^{+}$$\square$が長さ限定 EFS で定義可能であることと$L$が文脈依存言語であることは同値であることが知られている [2]. また, 長さ限定 EFS ではその最小モデルが帰納的である
ことも示されている [2].

Shinohara [5] は EFS の帰納推論で重要な役割を果たす次のような既約という概念を導入した.

定義 3.2$\Gamma’\subsetneq r$

EFS$\Gamma$が解釈 $S\subseteq HB$ に関して既約であるとは, $S\subseteq M(\Gamma)$ かつ, 任意のに対して, $S\not\in M(\Gamma’)$ が成り立つことをいう.

空でない有限なエルブラン解釈に関して既約な長さ限定 EFS は有限個しか存在しない [5].

3.2

最大長限定 EFS

本節では長さ限定 EFS より構文制約の少ない最大長限定 EFS を定義し, \S 22 で扱った言語族の演算に対応する EFS の演算を最大長限定 EFS の枠組みで表現する.
定義 33$|B_{i}\theta|$

節 $Aarrow B_{1},$$\cdots B_{n}$が任意の代入$\theta$と任意の $i=1,2,$となるとき, この節は最大長限定であるという. EFS$\Gamma$$\cdots,$ $n$に対して,$|A\theta|\geq$

が最大長限定であるとは, 任

意の節 $C\in\Gamma$ が最大長限定であることをいう.
注) 上記の概念は, Yamamoto [8] が weakly reducing EFS として既に定義されているが本論文で扱う既約な EFS という用語と重複するため, 上記の名前を採用した.
定理 3.1か存在しない.

空でない有限なエルブラン解釈に関して, 既約な最大長限定 EFS は有限個し

220$p\prime^{\backslash }oof$. 証明は長さ限定 EFS に関する [5] の定理と同様である.

EFS

定理 3.2$\Gamma$$\blacksquare$

が最大長限定であるならば, $M(\Gamma)$ は帰納的である.

長さ限定 EFS は最大長限定 EFS であることから, 最大長限定 EFS 言語からなる言語族

は文脈依存言語をすべて含む. 文脈依存言語族が, 言語の和, 共通部分, 連接等の演算に関して閉じていことはよく知られている. この節で導入した最大長限定 EFS 言語もまた, これらの演算に関して閉じており, さらにそれらの演算で得られる言語をもとの最大長限定

EFS から簡単に生成できる特徴をもっている. 特に, 共通部分を考えるとき下記の例のよ
うに最大長限定 EFS は非常に便利である.
例 3.1$\Sigma=\{a, b\}$

, EFS $\Gamma_{1}=\{p(axb)\},$ $\Gamma_{2}=\{p(xaby)\}$ とする.

長さ限定で表すことができるが, それはもとの EFS$\Gamma$は $L(\Gamma_{1}, p)\cap L(\Gamma_{2},p)=$ {auabvb $|u,$$v\in\Sigma^{*}$$\Gamma_{1},$$\Gamma_{2}$$L(\Gamma_{1}, p)\cap L(\Gamma_{2}, p)$はから簡単に構成できない. 次の} から構成した長さ限定 EFS である:$\Gamma=\{q(ab) ; q(xy)arrow q(x) ; q(xy)arrow q(y) ; p(axb)arrow q(x)\}$

しかし, 最大長限定 EFS で考えると, 次のように変数記号の付け替えと 1 つの節を加える

ことによりもとの EFS から簡単に構成できる:$\Gamma=${$p_{1}(axb)$;$p_{2}$(xaby) ; $p(x)arrow p_{1}(x),$ $p_{2}(x)$ }

次に与えられた最大長限定 EFS 言語の和や共通部分等の言語に対応する EFS の演算を定義する:
最大長限定 EFS

定義 3.4
えた EFS を$\Gamma_{1}’,$

を含まずかつ$\Gamma_{2}’$$\Gamma_{1}’,$$\Gamma_{1}$, F2 に対して, 次の条件を満たすように述語記号を付け替とする: $L(\Gamma_{1}, p)=L(\Gamma_{1}’,p_{1}),$ $L(\Gamma_{2}, p)=L(\Gamma_{2}’, p_{2}),$$\Gamma_{2}’$$\Gamma_{1}’,$$\Gamma_{2}’$

は述語記号

$p$

の述語記号は互いに素最大長限定 EFS に対する 2 項演算を次のように定義する:

1.

$\Gamma_{1}\cup-\Gamma_{2}$$=$$\Gamma_{1}’\cup\Gamma_{2}’\cup\{p(x)arrow p_{1}(x) ; p(x)arrow p_{2}(x)\}$.

$\Gamma_{1}\tilde{\cap}\Gamma_{2}$$=$$\Gamma_{1}’\cup\Gamma_{2}’\cup\{p(x)arrow p_{1}(x),p_{2}(x)\}$3.

$\Gamma_{1}^{-}\Gamma_{2}$$=$$\Gamma_{1}’\cup\Gamma_{2}’\cup\{p(xy)arrow p_{1}(x),p_{2}(y)\}$$2$

最大長限定 EFS$\Gamma$に対して, 次の条件を満たすように述語記号を付け替えた EFS をとする: $L(\Gamma, p)=L(\Gamma’, p’)$ かつ$\Gamma’$

は述語記号

$p$

を含まない

$\Gamma$221
最大長限定 EFS に対する単項演算を次のように定義する:

4.
$5$$\Gamma^{n}\sim$$r\mp$.

$=$$\Gamma’\cup\{p(x_{1}x_{2}\cdots x_{n})arrow p’(x_{1}), p’(x_{2}), \cdots p’(x_{n})\}$$=$$\Gamma’\cup\{p(x)arrow p’(x) ; p(xy)arrow p(x), p(y)\}$これらの定義から明らかに次のことが成り立っ:$L(\Gamma_{1}\cup-\Gamma_{2})$$=$$L(\Gamma_{1})\cup L(\Gamma_{2})$$L(\Gamma_{1}\overline{\cap}\Gamma_{2})$$=$$L(\Gamma_{1})\cap L(\Gamma_{2})$$L(\Gamma_{1}^{-}\Gamma_{2})$$=$$L(\Gamma_{1})\cdot L(\Gamma_{2})$また, 最大長限定 EFS の族$\mathcal{G},$$\mathcal{G}_{1},$$\mathcal{G}$$=$$\{\Gamma_{1}\cup\sim\Gamma_{2}|\Gamma_{1}\in \mathcal{G}_{1}, \Gamma_{2}\in \mathcal{G}_{2}\}$$\mathcal{G}_{1}\tilde{\cap}\mathcal{G}_{2}$$=$$\{\Gamma_{1}\tilde{\cap}\Gamma_{2}|\Gamma_{1}\in \mathcal{G}_{1}, \Gamma_{2}\in \mathcal{G}_{2}\}$$\mathcal{G}_{1}^{-}\mathcal{G}_{2}$$=$$\{\Gamma_{1}^{-}\Gamma_{2}|\Gamma_{1}\in \mathcal{G}_{1}, \Gamma_{2}\in \mathcal{G}_{2}\}$$\mathcal{G}$が定義する言語族を$L(\Gamma^{\mp})$$=$$L(\Gamma)^{n}$$=$$L(\Gamma)^{+}$

に対する演算を次のように定義する:$\mathcal{G}_{1}\cup-\mathcal{G}_{2}$

EFS の族$L(\Gamma^{\overline{n}})$$\mathcal{G}^{\overline{n}}$$=$$\mathcal{G}^{+}\sim$$=$$L(\mathcal{G})=\{L(\Gamma)|\Gamma\in \mathcal{G}\}$$\{\Gamma^{\overline{n}}|\Gamma\in \mathcal{G}\}$$\{r\mp|\Gamma\in \mathcal{G}\}$とかく.

EFS の族に関する演算はそれらが定義する言語族に関する (\S 2.2 で述べた) 演算に対応する. すなわち, 次のことが成り立つ :$L(\mathcal{G}_{1}\cup-\mathcal{G}_{2})$$=$$L(\mathcal{G}_{1})\cup L(\mathcal{G}_{2})\sim$$L(\mathcal{G}_{1}\overline{\cap}\mathcal{G}_{2})$$=$$L(\mathcal{G}_{1})\overline{\cap}L(\mathcal{G}_{2})$$L(\mathcal{G}_{1}^{-}\mathcal{G}_{2})$$=$$L(\mathcal{G}_{1})^{\sim}L(\mathcal{G}_{2})$また, 明らかに$L(\mathcal{G}_{1}\cup \mathcal{G}_{2})=L(\mathcal{G}_{1})\cup L(\mathcal{G}_{2})$$L(\mathcal{G}^{\overline{n}})$$L(\mathcal{G}^{\mp})$

$=$

$=$

$L(\mathcal{G})^{\overline{n}}$$L(\mathcal{G})^{\mp}$である.

\S 22 の定理 26 より, 最大長限定 EFS の族の演算に関して次の結果が成り立っ:
定理 33$L(\mathcal{G}_{1}),$$L(\mathcal{G}_{2})$$L(\mathcal{G}_{1}\cup \mathcal{G}_{2}),$

3.3$\mathcal{G},$$\mathcal{G}_{1},$を帰納的枚挙可能な最大長限定 EFS の族とする.

$\mathcal{G}_{2}$が有限の弾力性をもつならば, 言語族$L(\mathcal{G}^{\overline{n}})$および$L(\mathcal{G}^{+})\sim$$L(\mathcal{G}_{1}\cup \mathcal{G}_{2})\sim,$$L(\mathcal{G})$,$L(\mathcal{G}_{1}^{-}\mathcal{G}_{2})$,言語族$L(\mathcal{G}_{1}\overline{\cap}\mathcal{G}_{2}),$はすべて正データから帰納推論可能である.

有限の弾力性をもつ最大長限定 EFS 言語族

この節では最大長限定 EFS 言語族が有限の弾力性をもつための必要十分条件について論じる. この節で扱う族のとする. 集合$\mathcal{G}$$S\subseteq\Sigma^{+}$

は, 任意のと述語記号$\Gamma\in \mathcal{G}$

$p$

と任意の

$\Gamma’\subseteq\Gamma$

に対して,$\Gamma’\in \mathcal{G}$を満たすもに対して, $p(S)=\{p(w)|w\in S\}$ とする.

222
最大長限定 EFS の族を

定理 3.4とする. 言語族$\mathcal{G}$$L(\mathcal{G})$

分条件は, 次の (1), (2) を満たす空でない有限集合の無限列$(\Gamma_{i})_{i\in N}$

が存在しないことである (ただし,(1)

pro 砿必要性) (1), (2) を満たす無限列
ならば,
から,

かつ

$T\dot,\subseteq L(\Gamma_{j})$無限夕|J$(\Gamma_{i})_{i\in N}$は$w_{0},$ $w_{1},$;$\cdots$であり,$r_{i}\subsetneq r_{i}$$L(\mathcal{G})$が $p(T_{i})$ に関して既約$\Gamma_{j}$がに関して既約であること$T_{j}$$L(\Gamma_{i})\subsetneq L(\Gamma_{j})$. このことから, この$(i\in N)$,$w_{k}\not\in L(\Gamma_{k})$が有限の弾力性をもつことに矛盾する.

十分性) 任意の $k\in N$ に対して, $\{w_{0}, w_{1}, \cdots, w_{k-1}\}\subseteq L(\Gamma_{k}),$の無限列

まず, $i<j$は任意の $k\in N$ に対して,$\cdots$$\{w_{0}, w_{1}, \cdots w_{k-1}\}\subseteq L(\Gamma_{k})$

を満たし

):

$w_{i}\in L(\Gamma_{i+l})-L(\Gamma_{i})$$L(\Gamma_{1}),$ $L(\Gamma_{2}),$および EFS の無限列を満たしている.

$L(\Gamma_{1})\subsetneq L(\Gamma_{2})\subsetneq L(\Gamma_{3})\subsetneq\cdots$,$\Gamma_{\dot{t}}$$(T_{i})_{i\in N}$が存在すると仮定する$(\Gamma_{i})_{i\in N}$

である. したがって,$T_{\dot{j}}\not\in L(\Gamma_{i})$$w_{0}\in L(\Gamma_{1})$とすると,$(T_{i})_{i\in N},$を示す. 仮定から$L(\Gamma_{i})\subsetneq L(\Gamma_{j})$$\Gamma_{i}\in \mathcal{G}$(2) 任意の $i\in N$ に対して,,$\Gamma_{1}\subsetneq\Gamma_{2\subsetneq}\cdots$$T_{i}\subseteq\Sigma^{+},$

が有限の弾力性をもつ必要十$w_{0},$ $w_{1},$$\cdots;L(\Gamma_{1}),$ $L(\Gamma_{2}),$

次のように帰納的に$k_{n}$と$\overline{\mathcal{F}}_{n}$$\cdots$$w_{k}\not\in L(\Gamma_{k})$を満たす 2 つが存在すると仮定する.

を定義する (ただし, $k_{0}=0$ ):step $n(n\geq 0)$ :$=${$\overline{\mathcal{F}}_{n}$$=$$\mathcal{F}_{n}-$$k_{n+1}$$=$$\min$$\mathcal{F}_{n}$$\Gamma\in \mathcal{G}|\Gamma${{: $p(\{w_{0},$$w_{1},$$\cdots,$$\Gamma\in \mathcal{F}_{n}|w_{0},$ $w_{1},$

$k|$

任意の

$\Gamma\in\overline{\mathcal{F}}_{n}$$\cdots$$w_{k_{n}}\})$

に関して既約}

がすべて

に対して,

$L(\Gamma)$$\{w_{0},$ $w_{1},$に属する}$\cdots,$$w_{k}\}\not\in L(\Gamma)$}とし, step $n+1$ へ行く.

上記で定義される$k_{n},\overline{\mathcal{F}}_{n}$に関して次のことが成り立つ :(i) 任意の $n\geq 0$ に対して,$\overline{\mathcal{F}}_{n}\neq\phi,$$k_{n}<k_{n+1}$

任意の $k\in N$ に対して, $w_{0}\in L(\Gamma_{k})$ より,$\Gamma_{k}’\subsetneq\Gamma_{k}$となるであるから,$\Gamma_{k^{\wedge}}’\in \mathcal{F}_{0}$$\overline{\mathcal{F}}_{0}\neq\phi$が存在する. また,であること$\Gamma_{k}\in \mathcal{F}_{0}$$w_{k}\not\in L(\Gamma_{k})$であるか, または$\Gamma_{k}\not\in \mathcal{F}_{0}$より, 後者についてもならば$w_{k}\not\in L(\Gamma_{k}’)$が成り立つ. 定理 3.1 より, $p(\{w_{0}\})$ に既約な最大長限定 EFS の個数

223
は有限であり, またして,$\overline{\mathcal{F}}_{n}\neq\phi$$\tilde{\mathcal{F}}_{0}$の定義から,て,$\Gamma\in\overline{\mathcal{F}}_{n+1}$の定め方から, 任意のしたがって,$\{w_{0}, w_{1}, \cdots\}\not\in L(\Gamma)$$\Gamma_{i}\in\overline{\mathcal{F}}_{i}(i=0,1, \cdots)$

このような$\Gamma_{i}$である.

$\Gamma’\in \mathcal{F}_{n}$. ゆえに,$\Gamma\in\overline{\mathcal{F}}_{n+1}$が存在する.

$\Gamma’\in\tilde{\mathcal{F}}_{n}$

に対し

また,

.

が存在すること$\Gamma_{n}\in\overline{\mathcal{F}}_{n}$が存在する.

. 一方, 任意のとなる$\{w_{0}, w_{1}, \cdots\}\not\in L(\Gamma’)$$\Gamma_{i}\in\tilde{\mathcal{F}}_{i}(i\geq 0)$$\Gamma_{i}\in\overline{\mathcal{F}}_{i}(i=0, \cdots, n-1)$$\Gamma’\subset’\Gamma$が存在すること$\Gamma’\in\overline{\mathcal{F}}_{n}$$\{w_{0}, w_{1}, \cdots, w_{k_{n+1}}\}\not\in L(\Gamma’)$$\overline{\mathcal{F}}_{n}\cap\overline{\mathcal{F}}_{n+1}=\phi$(ii) より, 任意の $n\in N$ と任意のとなる

$r’\subsetneq r$に対して,であるから,

であるから,となる$\Gamma_{0\subsetneq}\Gamma_{1}\subsetneq$

に対して,$\Gamma’\in\overline{\mathcal{F}}_{n}$となるので$\Gamma’\not\in\overline{\mathcal{F}}_{n+1}$$\{w_{0}, w_{1}, \cdots, w_{k_{n}}\}\subseteq L(\Gamma)$(iii)

は定まり, $k_{0}(=0)<k_{1}$ である. 任意の $n\in N$ に対, および $k_{n}<k_{n+1}$ であることも同様に示される.

(ii) 任意の $n\geq 0$ , 任意の$k_{n+1}$$k_{1}$

に対して,$\neq\overline{\mathcal{F}}_{0}<\infty$$r_{0}\subsetneq r_{1}\subsetneq\cdots\subsetneq\Gamma_{n}$であるから,$\Gamma_{0}\subsetneq\Gamma_{1}\subsetneq\cdots$が存在する. また, $T_{i}=\{w_{0}, w_{1}, \cdots, w_{k_{\iota}}\}$ とすると,が $p(\{w_{0}, \cdots, w_{k_{\iota}}\})$ に関して既約である.

この定理から, Shinohara [5] による高々$n$$\overline{\mathcal{F}}_{i}$

を満たす
を満たす

の定義より,$\blacksquare$

個の節をもつ長さ限定 EFS に関する結果が最大長限定 EFS でも成り立つことがわかる.
系 3.5$\mathcal{G}=${$\Gamma|\Gamma$をもつ. したがって,

3.4: 最大長限定 EFS,

$L(\mathcal{G})$$\neq\Gamma\leq n$} とする. 言語族$L(\mathcal{G})$は有限の弾力性

は正データから帰納推論可能である.

帰納推論可能性の特徴づけ定理

この節では最大長限定 EFS の言語族に対する正データからの帰納推論可能性を特徴づける定理を与える. 証明等は長さ限定 EFS に関する論文 [3] と同様なので詳細は省く. 本節

でも, 最大長限定 EFS の族の$\Gamma\in \mathcal{G}$と任意の$\Gamma’\subseteq\Gamma$

は部分集合に関して閉じているものとする. すなわち, 任意$\mathcal{G}$に対して,$\Gamma’\in \mathcal{G}$

補題 3.1

最大長限定 EFS の族を

定理 36

最大長限定 EFS の族をこと,$L(\mathcal{G})$定理 37が ftt をもつこと,$L(\mathcal{G})$$\mathcal{G}$

とする.
とする.

$L(\mathcal{G})$$L(\mathcal{G})$は $M-$ 有限の厚さである.

が正データから帰納推論可能であるが pftt をもつことは等価である.

最大長限定 EFS の族をための必要十分条件は, 任意の$\mathcal{G}$とする.

$\Gamma\in \mathcal{G}$$\mathcal{G}$とする.

$L(\mathcal{G})$が正データから帰納推論可能であるに対して, 次の (1) から (5) を満たす$\Sigma^{+}$

の空でない

224
有限部分集合の無限列
だし,て,$\Gamma_{i}$$\Gamma_{i}\in \mathcal{G}$)$(T_{i})_{i\in N}$$:(1)T_{1}\subsetneq\tau_{2}\subsetneq\cdots,$

および EFS の無限列

(2)$\bigcup_{i=1}^{\infty}T_{i}=L(\Gamma),$(3)$(\Gamma_{i})_{i\in N}$

が存在しないことである (た$\Gamma_{1}\subsetneq r_{2}\subsetneq\cdots,$

が $p(T_{i})$ に関して既約, (5) 任意 $i\in N$ に対して,(4) 任意 $i\in N$ に対し$L(\Gamma_{i})\subsetneq L(\Gamma)$

論文 [3] では, 長さ限定 EFS の最小モデル族の正データからの帰納推論可能性についても論じているが, そこで得られた結果は本稿で導入した最大長限定 EFS においても同様に成立する. それらの結果は紙面の都合上省略する.

参考文献[1] D. Angluin. Inducti ve inference of formal lan guag es from positi ve data. Information
and Control, 45:117-135, (1980).
[2] S. Arikawa, T. Shinohara, and A. Yamamoto. Elemetary formal sys em as a unifying$t$framework for language learning. Proc. 2nd Workshop Comput. Learning Theorey,
312-327, (1989).
[3] 佐藤優子, 森山隆史. 正データからの EFS の帰納推論. November (1992). 重点領域研究(1) 研究会資料.
[4] M. Sato and K. Umayahara. Inductive inferability for formal 1 anguages from positive
data. IEICE Trans. $Inf$ . &Syst., $E75-D(4):84-92$ , (1992).

[5] T. Shinohara. Indu $cti$ ve inference from positive data is $po$ werful. Proc. 3rd Workshop
Comput. Learning Theory, 97-110, (1990).
[6] T. Shinohara. Inductive inferen ce of mon oton
Generation Computing, 8;371-384, (1991).

$ic$

formal $systems$ from positi ve data. New[7] K. Wright. Identifica tion of union of laligu ages rafrom an identifia $ble$ clas . Proc.
2nd Workshop on Comput. Learning Theory, 328-333, (1989).
$\mathfrak{l}5$

$d$

$Wl1$

$s$

[8] A. Yamamoto. Element ary formal system as a logic rogramm $ing1$ anguage. Proc. Logic
Program. Conf. 89, ICOT, 123-132, (1989).
$p$