優先順序付き項書換え系の頭必須戦略の決定可能性

スポンサーリンク

概要

論文の詳細を見る
関数型言語の実行では、複数の規則が適用可能な場合に上方に書かれた規則が優先的に適用される。優先順序付き項書換え系は規則間に順序の付いた項書換え系であり、これらの機能を考慮した上で関数型プログラムの性質の解析が可能となる。本論文では、優先順序付き項書換え系のリデックスの集合と頭正規形の集合が木オートマトンで受理できること、また、どの規則の両辺も共通変数を持たない線形な優先順序付き項書換え系の到達可能性が決定可能であることを示す。また、それらの結果を用いることにより、Durandらが示した項書換え系の頭必須計算戦略の決定可能性が優先順序付き項書換え系でも成立することを示す。
社団法人電子情報通信学会の論文
2002-01-23

著者

関連論文

もっと見る

スポンサーリンク