NO Non-Confluence Proof

Non-Confluence Proof

by csi

Input

The rewrite relation of the following TRS is considered.

f(u(O),u(y)) A
f(v(x),v(O)) B
O u(O)
O v(O)
u(x) x
v(x) x
f(x,y) f(x,u(y))
f(x,y) f(v(x),y)

Proof

1 Redundant Rules Transformation

To prove that the TRS is (non-)confluent, we show (non-)confluence of the following modified system:

f(u(O),u(y)) A
f(v(x),v(O)) B
O u(O)
O v(O)
u(x) x
v(x) x
f(x,y) f(x,u(y))
f(x,y) f(v(x),y)
O u(u(O))
O u(v(O))
O O
O v(u(O))
O v(v(O))
u(f(u(O),u(y))) A
u(f(v(x),v(O))) B
u(O) u(O)
u(O) v(O)
u(u(x)) x
u(v(x)) x
v(f(u(O),u(y))) A
v(f(v(x),v(O))) B
v(O) u(O)
v(O) v(O)
v(u(x)) x
v(v(x)) x
f(u(O),y) A
f(x146,x) f(x146,x)
f(x,v(O)) B
f(x,x149) f(x,x149)
f(O,u(x134)) A
f(u(O),O) A
f(u(O),u(O)) A
u(f(u(O),u(x134))) A
f(u(u(O)),u(x134)) A
f(u(O),u(u(x134))) A
f(u(O),u(u(x))) A
v(f(u(O),u(x134))) A
f(v(u(O)),u(x134)) A
f(u(v(O)),u(x134)) A
f(u(O),v(u(x134))) A
f(u(O),u(v(x))) A
f(v(O),v(O)) B
f(O,v(O)) B
f(v(x135),O) B
u(f(v(x135),v(O))) B
f(u(v(x135)),v(O)) B
f(v(u(x)),v(O)) B
f(v(x135),u(v(O))) B
f(v(x135),v(u(O))) B
v(f(v(x135),v(O))) B
f(v(v(x135)),v(O)) B
f(v(v(x)),v(O)) B
f(v(x135),v(v(O))) B
u(u(x136)) x136
v(u(x136)) x136
u(v(x137)) x137
v(v(x137)) x137

All redundant rules that were added or removed can be simulated in 3 steps .

1.1 Non-Joinable Fork

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

t0 = f(u(O),v(O))
ε A
= t1

t0 = f(u(O),v(O))
ε B
= t1

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

Tool configuration

csi