On the Word Problem for Right-Ground Term-Rewriting Systems
Summary :
A term-rewriting system (for short, TRS) is said to be a right-ground system if no variable occurs on the right-hand side of a rewrite rule, and a left-linear system if no variable occurs more than once on the left-hand side of a rewrite rule. This paper shows that the word or equivalence problem is undecidable for right-ground TRS's even if they are finite-terminating (i.e., noetherian). Next, we show that the word problem is decidable for left-linear and right-ground TRS's and there exists an efficient algorithm solving this problem. These results show a gap between right-ground TRS's and left-linear and right-ground TRS's.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E73-E No.5 pp.718-723
- Publication Date
- 1990/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Automation, Language and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Michio OYAMAGUCHI, "On the Word Problem for Right-Ground Term-Rewriting Systems" in IEICE TRANSACTIONS on transactions,
vol. E73-E, no. 5, pp. 718-723, May 1990, doi: .
Abstract: A term-rewriting system (for short, TRS) is said to be a right-ground system if no variable occurs on the right-hand side of a rewrite rule, and a left-linear system if no variable occurs more than once on the left-hand side of a rewrite rule. This paper shows that the word or equivalence problem is undecidable for right-ground TRS's even if they are finite-terminating (i.e., noetherian). Next, we show that the word problem is decidable for left-linear and right-ground TRS's and there exists an efficient algorithm solving this problem. These results show a gap between right-ground TRS's and left-linear and right-ground TRS's.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e73-e_5_718/_p
Copy
@ARTICLE{e73-e_5_718,
author={Michio OYAMAGUCHI, },
journal={IEICE TRANSACTIONS on transactions},
title={On the Word Problem for Right-Ground Term-Rewriting Systems},
year={1990},
volume={E73-E},
number={5},
pages={718-723},
abstract={A term-rewriting system (for short, TRS) is said to be a right-ground system if no variable occurs on the right-hand side of a rewrite rule, and a left-linear system if no variable occurs more than once on the left-hand side of a rewrite rule. This paper shows that the word or equivalence problem is undecidable for right-ground TRS's even if they are finite-terminating (i.e., noetherian). Next, we show that the word problem is decidable for left-linear and right-ground TRS's and there exists an efficient algorithm solving this problem. These results show a gap between right-ground TRS's and left-linear and right-ground TRS's.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - On the Word Problem for Right-Ground Term-Rewriting Systems
T2 - IEICE TRANSACTIONS on transactions
SP - 718
EP - 723
AU - Michio OYAMAGUCHI
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 5
JA - IEICE TRANSACTIONS on transactions
Y1 - May 1990
AB - A term-rewriting system (for short, TRS) is said to be a right-ground system if no variable occurs on the right-hand side of a rewrite rule, and a left-linear system if no variable occurs more than once on the left-hand side of a rewrite rule. This paper shows that the word or equivalence problem is undecidable for right-ground TRS's even if they are finite-terminating (i.e., noetherian). Next, we show that the word problem is decidable for left-linear and right-ground TRS's and there exists an efficient algorithm solving this problem. These results show a gap between right-ground TRS's and left-linear and right-ground TRS's.
ER -
English
