Certification Problem

Input (COPS 672)

We consider the TRS containing the following rules:

a a (1)
a h(a,b) (2)
b h(b,f(f(b))) (3)
b b (4)
h(b,h(f(a),a)) a (5)

The underlying signature is as follows:

{a/0, h/2, b/0, f/1}

Property / Task

Prove or disprove confluence.

Answer / Result

No.

Proof (by csi @ CoCo 2021)

1 Non-Joinable Fork

The system is not confluent due to the following forking derivations.

t0 = h(b,h(f(a),a))
h(b,h(f(a),a))
h(b,h(f(a),h(a,b)))
h(b,h(f(a),h(a,h(b,f(f(b))))))
= t3

t0 = h(b,h(f(a),a))
a
h(a,b)
h(a,h(b,f(f(b))))
= t3

The two resulting terms cannot be joined for the following reason: