Certification Problem

Input (COPS 213)

We consider the TRS containing the following rules:

a	→	b	(1)
a	→	f(a)	(2)
b	→	f(f(b))	(3)
f(f(f(b)))	→	b	(4)

The underlying signature is as follows:

{a/0, b/0, f/1}

Property / Task

Prove or disprove confluence.

Answer / Result

Yes.

Proof (by csi @ CoCo 2022)

1 Redundant Rules Transformation

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

f(f(f(b)))	→	b	(4)
b	→	f(f(b))	(3)
a	→	f(a)	(2)
a	→	b	(1)
f(f(f(b)))	→	f(f(b))	(5)
b	→	f(f(f(f(b))))	(6)
a	→	f(f(a))	(7)
a	→	f(b)	(8)
a	→	f(f(b))	(9)

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

1.1 Decreasing Diagrams

1.1.2 Rule Labeling

Confluence is proven, because all critical peaks can be joined decreasingly using the following rule labeling function (rules that are not shown have label 0).

f(f(f(b))) → b (4)
↦ 0
b → f(f(b)) (3)
↦ 0
a → f(a) (2)
↦ 3
a → b (1)
↦ 2
f(f(f(b))) → f(f(b)) (5)
↦ 1
b → f(f(f(f(b)))) (6)
↦ 0
a → f(f(a)) (7)
↦ 1
a → f(b) (8)
↦ 1
a → f(f(b)) (9)
↦ 1

The critical pairs can be joined as follows. Here, ↔ is always chosen as an appropriate rewrite relation which is automatically inferred by the certifier.

The critical peak s = b←→_ε f(f(b)) = t can be joined as follows.
s ↔ t
The critical peak s = b←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(f(b)))))←→_ε b = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(f(f(f(b)))))←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(f(b)))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ t
The critical peak s = f(f(f(f(f(b)))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε f(f(f(f(b)))) = t can be joined as follows.
s ↔ t
The critical peak s = f(f(b))←→_ε f(f(f(f(b)))) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(a)←→_ε b = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(a)←→_ε f(f(a)) = t can be joined as follows.
s ↔ t
The critical peak s = f(a)←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(f(a))) ↔ t
The critical peak s = f(a)←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(a)←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(a)←→_ε f(b) = t can be joined as follows.
s ↔ t
The critical peak s = f(a)←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(a)←→_ε f(f(b)) = t can be joined as follows.
s ↔ t
The critical peak s = b←→_ε f(a) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = b←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = b←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ b ↔ f(f(f(b))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(b)) ↔ f(f(f(b))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(b)) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(b)) ↔ f(f(f(f(b)))) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = b←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ f(f(f(b))) ↔ t
The critical peak s = b←→_ε f(f(b)) = t can be joined as follows.
s ↔ t
The critical peak s = b←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε b = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(b))←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(f(f(f(b)))))))←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(b))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(b))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(f(f(f(f(f(f(b)))))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(f(f(f(f(f(b)))))))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(f(a))←→_ε f(a) = t can be joined as follows.
s ↔ f(f(a)) ↔ t
The critical peak s = f(f(a))←→_ε f(a) = t can be joined as follows.
s ↔ f(f(f(a))) ↔ t
The critical peak s = f(f(a))←→_ε f(a) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(a))←→_ε f(a) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(f(a))←→_ε b = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(a))←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(a))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(f(a))←→_ε f(f(b)) = t can be joined as follows.
s ↔ t
The critical peak s = f(f(a))←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε f(a) = t can be joined as follows.
s ↔ f(b) ↔ t
The critical peak s = f(b)←→_ε f(a) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(b) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(b))) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(b))) ↔ f(f(b)) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ f(f(b)) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ f(f(f(f(b)))) ↔ f(f(b)) ↔ t
The critical peak s = f(b)←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(b) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ f(f(f(f(f(b))))) ↔ f(f(f(f(f(f(b)))))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(b))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = f(b)←→_ε f(f(b)) = t can be joined as follows.
s ↔ f(f(f(f(f(b))))) ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε f(a) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(b))←→_ε b = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(b))←→_ε b = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(b)) ↔ t
The critical peak s = f(f(b))←→_ε f(f(a)) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(b)) ↔ f(f(f(b))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(b)) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(b)))) ↔ f(f(f(b))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ f(f(f(b))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ f(f(f(f(f(b))))) ↔ t
The critical peak s = f(f(b))←→_ε f(b) = t can be joined as follows.
s ↔ f(f(f(f(f(f(b)))))) ↔ f(f(f(f(f(b))))) ↔ f(f(f(b))) ↔ t