The Joinability and Related Decision Problems for Semi-constructor TRSs(計算理論)
スポンサーリンク
概要
- 論文の詳細を見る
The word and unification problems for term rewriting systems (TRSs) are most important ones and their decision algorithms have various useful applications in computer science. Algorithms of deciding joinability for TRSs are often used to obtain algorithms that decide these problems. In this paper, we first show that the joinability problem is undecidable for linear semi-constructor TRSs. Here, a semi-constructor TRS is such a TRS that all defined symbols appearing in the right-hand side of each rewrite rule occur only in its ground subterms. Next, we show that this problem is decidable both for confluent semi-constructor TRSs and for confluent semi-monadic TRSs. This result implies that the word problem is decidable for these classes, and will be used to show that unification is decidable for confluent semi-constructor TRSs in our forthcoming paper.
- 一般社団法人情報処理学会の論文
- 2006-05-15
著者
-
太田 義勝
Faculty Of Engineering Mie University
-
山田 俊行
三重大学大学院工学研究科情報工学専攻
-
三橋 一郎
三重大学総合情報処理センター
-
MITSUHASHI ICHIRO
Faculty of Engineering, Mie University
-
OYAMAGUCHI MICHIO
Faculty of Engineering, Mie University
-
OHTA YOSHIKATSU
Faculty of Engineering, Mie University
-
YAMADA TOSHIYUKI
Faculty of Engineering, Mie University
-
Ohta Yoshikatsu
Faculty Of Engineering Mie University
-
Oyamaguchi Michio
Faculty Of Engineering Mie University
-
大山口 通夫
三重大学大学院工学研究科情報工学専攻
-
Mitsuhashi Ichiro
Mie Univ. Tsu‐shi Jpn
関連論文
- ツーバイフォーパネル部材の最適木取ソフトウェアの開発
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- ルートE重なりな深さ保存項書き換えシステムのチャーチ・ロッサー性について
- On the Church-Rosser Property of Non-E-overlapping and Weight-Preserving TRS's
- 再帰手続きに対する新しいコード最適化
- 非線形TRSの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分野:モデル・アルゴリズム・プログラミング)
- 通信遅延を考慮したタスクスケジューリングアルゴリズムについて(研究速報)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論とその応用)
- 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論の新展開)
- 巡回セールスマン問題の近似アルゴリズムについて
- Some Results on the CR property of non-E-overlapping and depth-preserving TRS's(Theory of Rewriting Systems and Its Applications)
- On the Church-Rosser Property of Root-E-overlapping and Strogly Depth-preserving Term Rewriting Systems(Special Issue on Generation Database Technology for Internet, Multimedia and Mobile computing)
- 3大プロセッサスケジューリングに関する一考察
- 単純右線形項書換えシステムの合流性について
- 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以下に制限したタスクスケジューリングの近似アルゴリズムについて(計算機科学の理論とその応用)
- Church-Rosser Property and Unique Normal Form Property of Non-Duplicating Term Rewriting Systems(Theory of Rewriting Systems and Its Applications)
- The Reachability and Joinability Problems for Right-Ground Term-Rewriting Systems
- タスクスケジューリングに関する新しい近似アルゴリズムについて (計算機科学基礎理論の新展開)
- マルチプロセッサ向き目的コードスケジューリングについて
- レベル付き依存グラフを用いた効率のよいソフトウェア・パイプライン化法について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- マルチプロセッサ向き目的コードスケジューリングについて
- The Reachability Problem for Quasi-Ground Term Rewriting Systems
- On the Open Problems Concerning Church-Rosser of Left-Linear Term Rewriting Systems(Foundations of Computer Science)
- On the Task Scheduling with Communication Delay
- On the Church-Rosser Property of Left-Linear Term Rewriting Systems(Regular Section)
- マルチプロセッサ向き目的コードスケジューリングについて
- マルチプロセッサ向き目的コードスケジューリングについて (アルゴリズムと計算の理論)
- 弱単項TRSのE重なり性について
- Shibboleth・CAS連携による東海アカデミッククラウド認証基盤の構築(学生セッション,一般)
- Shibboleth・CAS連携による東海アカデミッククラウド認証基盤の構築
- 左線形項書換えシステムのチャーチ・ロッサー性に対する新しいParallel Closed条件
- The Joinability and Related Decision Problems for Semi-constructor TRSs
- レジスタ割り当てにおける循環区間グラフの彩色アルゴリズムについて
- 右定項-項書換えシステムの合流性について
- 分散オペレーティング・システムISEとその並列処理言語について
- The Joinability and Related Decision Problems for Semi-constructor TRSs