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