単純右線形項書換えシステムの合流性について
スポンサーリンク
概要
- 論文の詳細を見る
項書換えシステム(TRS)の重要な性質の一つに合流性(またはChurch-Rosser性)があり,これまで主に停止性を満たすTRSまたは線形TRSについて研究が行われてきた.非線形TRSの合流性について,筆者らにより,右定項TRSは非E重なりならば合流性を満たすことが示されている.本論文では,文献(10)で提案したE-グラフの解析手法を自然に拡張することにより,右定項TRSを含むより大きなクラスである単純右線形TRSが非E重なりならば合流性を満たすことを示す.ここで,TRSが単純右線形であるとは,右線形,かつ,すべての書換え規則について,規則の左辺に2度以上現れる変数が右辺に現れないことを言う.
- 1995-03-25
著者
関連論文
- 文脈を考慮したJavaプログラムの参照先解析に関する一考察 (アルゴリズムと計算機科学の数理的基盤とその応用)
- ソフトウェア科学会第4回大会
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- On the Church-Rosser Property of Non-E-overlapping and Weight-Preserving TRS's
- 再帰手続きに対する新しいコード最適化
- 非線形TRSのE重なり性について
- 単純型付き等式系に基づく定理自動証明に関する一考察(計算機科学の理論とその応用)
- 非線形項書き換えシステムのE-非オーバーラップ性について(理論計算機科学とその周辺)
- 高階項書換え系における改良再帰分解順序について
- 高階項書換え系の停止性について
- プロセス間通信に基づく並列処理言語の表示的意味記述について
- 非同期通信に基づく並列処理言語の表示的意味記述について(計算アルゴリズムと計算量の基礎理論)
- A-011 An Extension of E-overlapping Notion in Term Rewriting Systems and its Applications
- 非線形TRSのE重なり性判定問題について(計算量理論)
- A-017 厳密解法と発見的手法の組合せによるサイズ可変ビンパッキング問題の解法(モデル・アルゴリズム・プログラミング,一般論文)
- The Joinability and Related Decision Problems for Semi-constructor TRSs(計算理論)
- The Confluence Problem for Flat TRSs(New Trends in Theory of Computation and Algorithm)
- The Reachability and Related Decision Problems for Semi-Constructor TRSs (Theoretical Computer Science and its Applications)
- The Joinability and Unification Problems for Confluent Semi-Constructor TRSs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- 単項的TRSにおける単ー化問題について
- 並列処理を考慮した目的コードスケジューリング
- 依存対を用いた文脈依存書換え系の停止性判定について
- 消去法による項書換え系の停止性判定について
- 消去法による項書換え系の停止性判定について
- A-016 DAGの高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(A分野:モデル・アルゴリズム・プログラミング)
- 通信遅延を考慮したタスクスケジューリングアルゴリズムについて(研究速報)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論の新展開)
- 巡回セールスマン問題の近似アルゴリズムについて
- 項書換え系の合流性を保存する合併条件について
- 3大プロセッサスケジューリングに関する一考察
- 依存対を利用したAC停止性の証明法
- 条件付き項書換え系の合流性について
- 重なりのある強逐次系のインデックス簡約について
- 項書き換え系のパーシステント性の順序付きソートによる拡張
- Extending persistency of confluence with ordered sorts
- Top-down labelling and modularity of term rewriting systems
- Persistency of confluence
- Persistency of confluence
- 単純右線形項書換えシステムの合流性について
- 条件付き項書換え系の合流性について
- NVNF-逐次系におけるインデックスの決定可能性
- E重なりのある単純右線形項書き換えシステムの合流性について
- D-3-4 教育用C言語とそのコンパイラに関する一考察(D-3.ソフトウェアサイエンス,一般講演)
- On the Church-Rosser Property of Non-E-overlapping and Strongly Depth-preserving Term Rewriting Systems
- DAG の高さを4以下に制限したタスクスケジューリングの近似アルゴリズムについて(計算機科学の理論とその応用)
- タスクスケジューリングに関する新しい近似アルゴリズムについて (計算機科学基礎理論の新展開)
- マルチプロセッサ向き目的コードスケジューリングについて
- レベル付き依存グラフを用いた効率のよいソフトウェア・パイプライン化法について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- マルチプロセッサ向き目的コードスケジューリングについて
- 構文解析法からみた最近の計算機言語理論の動向
- マルチプロセッサ向き目的コードスケジューリングについて
- マルチプロセッサ向き目的コードスケジューリングについて (アルゴリズムと計算の理論)
- 左線形項書換えシステムのチャーチ・ロッサー性に対する新しいParallel Closed条件
- レジスタ割り当てにおける循環区間グラフの彩色アルゴリズムについて
- 右定項-項書換えシステムの合流性について
- 分散オペレーティング・システムISEとその並列処理言語について