If a term rewriting system is confluent, then every term has at most one normal form. Is the converse also true, or is confluence a strictly stronger property? I.e. if every term has at most one normal form, does the rewriting system need to be confluent? My intuition is that the answer is no; for example, it seems to me that you could theoretically have a term rewriting system in which every non-variable term has NO normal form (and thus, at most one normal form), but which is NOT confluent, because you might have one term that has infinite reductions in two different 'directions'. But this is just intuition, not a formal proof or counterexample.

Any help would be appreciated!

  • 1
    $\begingroup$ Wouldn't it be trivial to produce such a term rewriting system... $\endgroup$ – Derek Elkins left SE Jul 9 '18 at 18:28
  • 1
    $\begingroup$ Yes, you're right. This might not be the most trivial example, but take a term rewriting system over a signature with three constants $c, d, e$, whose rules are $c \to d$, $c \to e$, $d \to d$, and $e \to e$. Then this system is not confluent (since $c \to d$ and $c \to e$ but $d$ and $e$ do not have a common reduct), but each term has at most one normal form (since every non-variable term, i.e. every constant, has NO normal form). $\endgroup$ – User7819 Jul 10 '18 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.