| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 3A |
| セッション名 |
| アルゴリズム・コンピュテーション一般 |
| 講演日 |
| 2009/09/02 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-011 |
| タイトル |
| 組合せ子の強収束性 |
| 著者名 |
| 岩見 宗弘, |
| キーワード |
| 項書換えシステム, 組合せ子, 組合せ子論理 |
| 抄録 |
|
組合せ子論理は, Curryらにより考案された計算体系であり, 帰納的関数の研究において重要な役割を果してきた. また, 論理や計算の基礎として重要である. さらに, 組合せ子論理は関数型プログラミング言語 の効率的な実装に応用されている. 本稿では, 組合せ子の強収束性について述べる. 最初に組合せ子 ¥Delta ¥in ¥{L, J, B, C, D, E, F, G, Q, Q_{1}, Q_{3}, R, T, V, C^{¥ast}, C^{¥ast ¥ast}¥}に対して, 組合せ子 ¥Delta が持つ1つの書換え規則だけから成る項書換え システム R(Delta)は無限¥Delta-項上で強収 束ではないことを示す. 次にTuringの不動点組合せ子 Uに対して, 組合せ子 U が持つ1つの書換え規則だけから成る項書換えシステム R(U)が無限 U-項上で強収束性を持つことをZantemaと 同様の手法により示す. さらに組合せ子 Uの持つ書換え規則の右辺を一般化し た組合せ子$U^{n}$を提案し, 組合せ子 $U^{n}$が持 つ1つの書換え規則だけから成る項書換えシステム R(BU^{n})が無限 U^{n}-項上で強収束性を持つこと を示す. |
| 本文pdf |
| PDF download (135.7KB) |