著者

吉田 忠行 赤間 清 宮本 衛市

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.41, no.7, pp.12-22, 2000-11-15

---

問題解決において,正しく,かつ効率的に問題を解くプログラムを作成するのは重要なことであるが,同時に困難なことでもある.本論文では,正しく効率的なプログラムを自動的に作成するための新しい方法を提案する.本論文では,文字列領域における問題の1つとして言語認識問題を取り上げる.一階述語論理表現を用いて定式化した問題仕様から,問題を高速に解くためのプログラムを生成する.ただし,本方法によって生成されるプログラムは,有限オートマトンに相当する単純なプログラムに限定している.本論文では,問題仕様とプログラムを従来の理論よりも一般的な形で関係づけている,等価変換に基づく計算モデル(等価変換モデル)を採用する.等価変換モデルでは,プログラムは等価変換ルールの集合である.本論文のプログラム生成では,問題仕様から等価変換ルールを次々に生成し,その中から効率的なルールだけを選別する方法を用いる.ルール生成は「メタ計算」と呼ばれる計算によって行い,効率的なルールの評価基準に基づき,生成されたルールを選別する.本論文の提案する方法により,一階述語論理表現を用いて自然な形で記述された言語仕様から,その言語に関する認識問題を効率的に解くプログラムを得ることが可能になる.It is very important but not easy to write correct and efficient programs for solving problems. In this paper, we propose a new method for automatic generation of correct and efficient programs. We assume that we are given a language recognition problem that is Formalized by using first-order logical expressions. Correct and efficient programs are then generated from the problem specification. The class of programs generated by the proposed method correspond to the one of finite automatons. In this paper we adopt a computation model based on equivalent transformation (ET model), which formalizes the relation between specifications and programs more generally than other existing models. In the ET model, a program consists of equivalent transformation rules (ET rules). We generate many ET rules from a given specification represented by first-order logical expressions and select ``efficient'' rules among them. We generate ET rules by ``meta computation'' and select efficient rules based on an evaluation function. We can obtain correct and efficient programs to solve language recognition Problems from their language specifications naturally represented by first-order logical expressions.