| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 7A |
| セッション名 |
| プログラミング |
| 講演日 |
| 2009/09/04 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-034 |
| タイトル |
| 基底項書き換え系の合流性自動判定 |
| 著者名 |
| 村井 正勝, 青戸 等人, 外山 芳人, |
| キーワード |
| 基底項書き換え系, 合流性自動判定, フラット変換 |
| 抄録 |
|
合流性は項書き換え系（TRS）の重要な性質であるが, 一般的には決定不能であることが知られている. しかし,基底TRSや線形シャローTRSの合流性判定を多項式時間で 実行するアルゴリズムが提案されている. これらのアルゴリズムに共通しているのは, 項書き換え系の書き換え規則をフラットな形に変換して 適当な閉包操作を行う点である. しかし,基底TRSの合流性判定アルゴリズムでは, フラット変換は書き換え規則数を大幅に増やすため 効率的な合流性条件の検証を困難にする場合がある. 本研究では,基底項書き換え系に焦点を絞り, フラット変換を改良した効率的な合流性判定アルゴリズムを提案し, 実験結果を報告する. |
| 本文pdf |
| PDF download (75.8KB) |