YES Confluence Proof

Confluence Proof

by csi

Input

The rewrite relation of the following TRS is considered.

a1 → b1
a1 → c1
b1 → b2
c1 → c2
a2 → b2
a2 → c2
b2 → b3
c2 → c3
a3 → b3
a3 → c3
b3 → b4
c3 → c4
a4 → b4
a4 → c4
b4 → b5
c4 → c5
a5 → b5
a5 → c5
b5 → b6
c5 → c6
a6 → b6
a6 → c6
b6 → b7
c6 → c7
a7 → b7
a7 → c7
b7 → b8
c7 → c8
a8 → b8
a8 → c8
b8 → b9
c8 → c9
a9 → b9
a9 → c9
b9 → b10
c9 → c10
a10 → b11
b10 → b11
c10 → b11

Proof

1 Redundant Rules Transformation

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

c10 → b11
b10 → b11
a10 → b11
c9 → c10
b9 → b10
a9 → c9
a9 → b9
c8 → c9
b8 → b9
a8 → c8
a8 → b8
c7 → c8
b7 → b8
a7 → c7
a7 → b7
c6 → c7
b6 → b7
a6 → c6
a6 → b6
c5 → c6
b5 → b6
a5 → c5
a5 → b5
c4 → c5
b4 → b5
a4 → c4
a4 → b4
c3 → c4
b3 → b4
a3 → c3
a3 → b3
c2 → c3
b2 → b3
a2 → c2
a2 → b2
c1 → c2
b1 → b2
a1 → c1
a1 → b1
b1 → b11
c1 → b11
b2 → b11
c2 → b11
b3 → b11
c3 → b11
b4 → b11
c4 → b11
b5 → b11
c5 → b11
b6 → b11
c6 → b11
b7 → b11
c7 → b11
b8 → b11
c8 → b11
b9 → b11
c9 → b11

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

1.1 Development Closed

Confluence is proven since the TRS is development closed.

Tool configuration

csi