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.

• 一般社団法人 情報処理学会の論文

著者

• MITSUHASHI ICHIRO

  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

関連論文

• The Joinability and Related Decision Problems for Semi-constructor TRSs(計算理論)
• 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)
• 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)
• On the Church-Rosser Property of Non-E-overlapping and Strongly Depth-preserving Term Rewriting Systems
• 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
• 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)
• The Joinability and Related Decision Problems for Semi-constructor TRSs
• The Joinability and Related Decision Problems for Semi-constructor TRSs

もっと見る 閉じる

スポンサーリンク