Certification Problem

Input (COPS 986)

We consider the TRS containing the following rules:

a(a(x))	→	b(x)	(1)
b(a(x))	→	a(b(x))	(2)
b(b(c(x)))	→	c(a(x))	(3)
b(b(x))	→	a(a(a(x)))	(4)
c(a(x))	→	b(a(c(x)))	(5)

The underlying signature is as follows:

{a/1, b/1, c/1}

Property / Task

Prove or disprove confluence.

Answer / Result

No.

Proof (by csi @ CoCo 2022)

1 Non-Joinable Fork

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

t₀	=	c(a(a(x1013)))
	→	c(b(x1013))
	=	t₁

t₀	=	c(a(a(x1013)))
	→	b(a(c(a(x1013))))
	→	a(b(c(a(x1013))))
	→	a(b(b(a(c(x1013)))))
	→	a(b(a(b(c(x1013)))))
	→	a(a(b(b(c(x1013)))))
	→	b(b(b(c(x1013))))
	→	b(c(a(x1013)))
	→	b(b(a(c(x1013))))
	→	b(a(b(c(x1013))))
	→	a(b(b(c(x1013))))
	→	a(c(a(x1013)))
	→	a(b(a(c(x1013))))
	→	a(a(b(c(x1013))))
	→	b(b(c(x1013)))
	→	c(a(x1013))
	→	b(a(c(x1013)))
	→	a(b(c(x1013)))
	=	t₁₇

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

When applying the cap-function on both terms (where variables may be treated like constants) then the resulting terms do not unify.