例からのLISPプログラムの帰納的推論における典型例の検討

概要

論文の詳細を見る
LISTのS式上の関数を，その有限個の入出力例から推測し，プログラムとして導出しようという問題は帰納的数論の基本的な問題である．本論文では，LISPのプログラムを推測するためのある種の推論アルゴリズムに対し，それに与えるのにふさわしい入出力例の集合（サンプル）を，典型的なサンプルとして特徴づける．この典型的なサンプルは，関数の各側面を記述する最も簡単な例の集合であり，全体として，関数を最も一般的に記述するものである．また，関数が典型性条件と呼ぶ条件を満たすことで，その関数の典型的な例の集合が常に存在することを示す．そのとき，典型的な入出力例の集合を推論アルゴリズムに与えることで，推論アルゴリズムでは意図する関数を出力することを示す．すなわち，典型性を満たす関数を推論アルゴリズムの領域としたとき，ある意味での部分正当性が成り立つことを示す．また，本論文の考え方を用いることで，与えられたサンプルが典型的なものであることを確認できる．これにより任意に与えられた入出力例を，会話的に典型的な例に変換する手続きについても述べる．
Institute of Electronics, Information and Communication Engineersの論文
1990-10-00