The Reachability Problem for Quasi-Ground Term Rewriting Systems
スポンサーリンク
概要
- 論文の詳細を見る
A term rewriting system is said to be a quasi-ground system if, for every rewrite rule in the system, the left-hand-side is linear and the right-hand-side is a ground term. This paper shows that the reachability problem for quasi-ground systems (i.e., the problem of deciding, for a quasi-ground system and two terms, whether one of the terms can reduce to the other) is decidable, and there exists an efficient algorithm solving this problem under the assumption that the number of the variable occurrences appearing in the left-hand-side for each rewrite rule is bounded by a fixed constant.
- 一般社団法人情報処理学会の論文
- 1987-03-15
著者
関連論文
- The Joinability and Related Decision Problems for Semi-constructor TRSs(計算理論)
- 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)
- 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