Certification Problem

Input (COPS 689)

We consider the TRS containing the following rules:

b h(h(b,a),f(a)) (1)
h(h(a,c),b) b (2)
c h(h(a,h(a,h(c,b))),f(f(h(h(a,h(h(f(a),c),f(c))),f(h(b,a)))))) (3)

The underlying signature is as follows:

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

Property / Task

Prove or disprove confluence.

Answer / Result

No.

Proof (by csi @ CoCo 2020)

1 Non-Joinable Fork

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

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

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

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