[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
Originator: Michio Oyamaguchi
Date: June 1993
Summary: Is any “strongly” non-overlapping right-linear term-rewriting system confluent?
Is any “strongly” non-overlapping right-linear term-rewriting system confluent? (“Strong” in the sense that left-hand sides are non-overlapping even when the occurrences of variables have been renamed apart [Che81].) On the one hand, strongly non-overlapping systems need not be confluent [Hue80]; on the other hand, strongly non-overlapping right-ground systems are [OO93].
A partial positive solution is given in [OOTar][TO94], namely, any strongly non-overlapping right-linear term-rewriting system is confluent if it satisfies the condition that for any rewrite rule, no variables occurring more than once in the left-hand-side occur in the right-hand-side.
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |