文字列領域の問題解決における一階論理表現からのプログラム生成

• Item type: Trans(1)
• 公開日: 2000-11-15
• タイトル: 文字列領域の問題解決における一階論理表現からのプログラム生成
• タイトル / 言語: en
• タイトル: Program Generation from First - order Logical Expressions for Problem Solving on a String Domain
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: オリジナル論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 北海道大学大学院システム情報工学専攻
• 著者所属: 北海道大学情報メディア教育研究総合センター
• 著者所属: 北海道大学大学院システム情報工学専攻
• 著者所属(英): en
• 著者所属(英): Division of System and Information Engineering, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Center of Information and Multimedia Studies, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Division of System and Information Engineering, Hokkaido University
• 著者名: 吉田, 忠行; 赤間, 清; 宮本, 衛市
• 著者名(英): Tadayuki, Yoshida; Kiyoshi, Akama; Eiichi, Miyamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 問題解決において，正しく，かつ効率的に問題を解くプログラムを作成するのは重要なことであるが，同時に困難なことでもある．本論文では，正しく効率的なプログラムを自動的に作成するための新しい方法を提案する．本論文では，文字列領域における問題の1つとして言語認識問題を取り上げる．一階述語論理表現を用いて定式化した問題仕様から，問題を高速に解くためのプログラムを生成する．ただし，本方法によって生成されるプログラムは，有限オートマトンに相当する単純なプログラムに限定している．本論文では，問題仕様とプログラムを従来の理論よりも一般的な形で関係づけている，等価変換に基づく計算モデル（等価変換モデル）を採用する．等価変換モデルでは，プログラムは等価変換ルールの集合である．本論文のプログラム生成では，問題仕様から等価変換ルールを次々に生成し，その中から効率的なルールだけを選別する方法を用いる．ルール生成は「メタ計算」と呼ばれる計算によって行い，効率的なルールの評価基準に基づき，生成されたルールを選別する．本論文の提案する方法により，一階述語論理表現を用いて自然な形で記述された言語仕様から，その言語に関する認識問題を効率的に解くプログラムを得ることが可能になる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 41, 号 SIG07(TOM3), p. 12-22, 発行日 2000-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会