NVNF-逐次系におけるインデックスの決定可能性
スポンサーリンク
概要
- 論文の詳細を見る
NV-逐次系は,インデックス簡約と呼ばれる決定可能な1ステップ正規化戦略をもつことが知られている.本論文では,NV-逐次系を拡張したNVNF-逐次系を提案する.NVNF-逐次系におけるインデックスは,書換え規則の左辺と右辺の変数ではない部分から導かれる簡約関係での正規形への到達可能性を考慮して定義される.NVNF-逐次系において,任意に与えられた項のインデックスが決定可能であることを示す.さらに,NV-逐次系と同様に左線形で重なりのないNVNF-逐次系に対してはインデックス簡約が正規化戦略であることを述べる.
- 1994-11-18
著者
関連論文
- 高階項書換え系における改良再帰分解順序について
- 高階項書換え系の停止性について
- 共有メモリ型並列計算機における項書換え系の実現方式
- 依存対を用いた文脈依存書換え系の停止性判定について
- 消去法による項書換え系の停止性判定について
- 消去法による項書換え系の停止性判定について
- Similarity on algebraic specifications toward specification databases
- エラー付き代数的仕様とエラー記述の自動付加
- 項書換え系の合流性を保存する合併条件について
- 依存対を利用したAC停止性の証明法
- 条件付き項書換え系の合流性について
- 重なりのある強逐次系のインデックス簡約について
- 項書き換え系のパーシステント性の順序付きソートによる拡張
- Extending persistency of confluence with ordered sorts
- Top-down labelling and modularity of term rewriting systems
- NVNF-sequentiality of Left-linear Term Rewriting Systems
- Persistency of confluence
- Persistency of confluence
- 単純右線形項書換えシステムの合流性について
- 条件付き項書換え系の合流性について
- NVNF-逐次系におけるインデックスの決定可能性
- E重なりのある単純右線形項書き換えシステムの合流性について
- 項集合書換え系とその合流性
- 項集合書換え系の合流性について
- Decidable/Undecidable Properties of Conditional Term Rewriting Systems (Languages, Algebra and Computer Systems)
- 形式的仕様を用いた再利用モデル