書換え系のPerpetual性と一様停止性
スポンサーリンク
概要
- 論文の詳細を見る
無限書換え列を持つ項を,無限書換え列を持つ項にうつす書換えをperpetualという.本稿では,様々なλ計算の体系を含む直交な条件付き高階書換系のフレームワークとしてOrthogonal Conditional Expression Reduction Systemsを用いて, Levy順序に関し極小となるperpetualな戦略の存在を示し,これに基づきperpetualなリデックスの特徴付けを与える二つの定理を証明する.その結果,従来個別に提案や予想をされてきた様々なλ計算のヴァリエーションにおける一様停止性(弱停止性と強停止性の等価性)を統一的かつ簡単に示す.
- 一般社団法人情報処理学会の論文
- 1997-05-21
著者
関連論文
- モデル検査技術を利用したプログラム解析器の生成ツール
- イベント順序証明システムの正当性の形式的証明
- 抽象実行 そのフレームワークと実例(その3)
- 抽象実行 そのフレームワークと実例(その2)
- 抽象解釈におけるLazyな抽象領域の生成
- 抽象実行 そのフレームワークと実例(その1)
- 最小不動点計算に基づくプログラムの帰納的性質の導出 (並列処理)
- 広域データフロー解析に基づく関数型プログラムの変則性検出
- さきがけ「機能と構成」研究1 : 効率的で正しいプログラムの自動生成
- ASIA-PEPM 2002/FLOPS 2002参加報告
- 利得の最適連想規則を求める線形時間アルゴリズムの導出
- 最大重み和問題の線形時間アルゴリズムの導出
- ACM PLI 2000会議報告
- ナップサック問題およびその発展問題の統一的解法
- 非線形TRSのE重なり性について
- 書換え系のPerpetual性と一様停止性
- 高階書換え系の単一正規形性
- 逐次性v.s.ストリクト性 : 非線形項書換え系の最適戦略にむけて
- 高階書き換え系の単一正規形性
- 項グラフ書換え系における単純ギャップ停止性
- 91-37 パラメトリシティの証明論の概略
- 理論計算機科学に関する豊橋シンポジウムに参加して
- グラフマイナー定理に基づく線形時間アルゴリズムの自動生成
- 89-29 ストリクトネス解析に基づく関数型プログラムの計算量解析
- 87-21 関数型プログラムの静的解析
- グリッドコンピューティングにおける代理証明書信任リスト(ディペンダブルソフトウェア)
- 「情報処理学会論文誌 : プログラミング」の編集について
- 「情報処理学会論文誌 : プログラミング」の編集について
- Proxy Certificate Trust List for Grid Computing