YES
Confluence Proof
Confluence Proof
by Hakusan
Input
The rewrite relation of the following TRS is considered.
|
max(x,0) |
→ |
x |
|
max(0,y) |
→ |
y |
|
max(s(x),s(y)) |
→ |
s(max(y,x)) |
|
max(x,y) |
→ |
max(y,x) |
Proof
1 Compositional Rule Labeling with Parallel Critical Pairs
Confluence is proven by compositional rule labeling with parallel critical pairs.
The following labeling functions phi and psi are used (if only one is displayed, then phi = psi).
-
max(x,0)→x ↦ 2
-
max(0,y)→y ↦ 1
-
max(s(x),s(y))→s(max(y,x)) ↦ 6
-
max(x,y)→max(y,x) ↦ 5
-
max(x,0)→x ↦ 4
-
max(0,y)→y ↦ 5
-
max(s(x),s(y))→s(max(y,x)) ↦ 4
-
max(x,y)→max(y,x) ↦ 3
The non-0-0 parallel critical pairs are joined as follows.
-
The parallel-phi-root-psi 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 = 0 {ε}←1 max(0,0) 4→ε 0 = t can be joined as follows.
s
↔ 0 ↔
t
-
The critical peak s = max(0,y1) {ε}←5 max(y1,0) 4→ε y1 = t can be joined as follows.
s
↔ max(y1,0) ↔ y1 ↔
t
-
The critical peak s = 0 {ε}←2 max(0,0) 5→ε 0 = t can be joined as follows.
s
↔ 0 ↔
t
-
The critical peak s = max(y1,0) {ε}←5 max(0,y1) 5→ε y1 = t can be joined as follows.
s
↔ max(y1,0) ↔ y1 ↔
t
-
The critical peak s = max(s(y2),s(y1)) {ε}←5 max(s(y1),s(y2)) 4→ε s(max(y2,y1)) = t can be joined as follows.
s
↔ max(s(y2),s(y1)) ↔ max(s(y1),s(y2)) ↔ s(max(y2,y1)) ↔
t
-
The critical peak s = y1 {ε}←2 max(y1,0) 3→ε max(0,y1) = t can be joined as follows.
s
↔ y1 ↔ max(0,y1) ↔
t
-
The critical peak s = y2 {ε}←1 max(0,y2) 3→ε max(y2,0) = t can be joined as follows.
s
↔ y2 ↔ max(y2,0) ↔
t
-
The critical peak s = s(max(x0_2,x0_1)) {ε}←6 max(s(x0_1),s(x0_2)) 3→ε max(s(x0_2),s(x0_1)) = t can be joined as follows.
s
↔ s(max(x0_2,x0_1)) ↔ s(max(x0_1,x0_2)) ↔
t
-
The parallel-psi-root-phi 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 = 0 {ε}←5 max(0,0) 2→ε 0 = t can be joined as follows.
s
↔ 0 ↔
t
-
The critical peak s = max(0,y1) {ε}←3 max(y1,0) 2→ε y1 = t can be joined as follows.
s
↔ y1 ↔
t
-
The critical peak s = 0 {ε}←4 max(0,0) 1→ε 0 = t can be joined as follows.
s
↔ 0 ↔
t
-
The critical peak s = max(y1,0) {ε}←3 max(0,y1) 1→ε y1 = t can be joined as follows.
s
↔ max(y1,0) ↔ y1 ↔
t
-
The critical peak s = max(s(y2),s(y1)) {ε}←3 max(s(y1),s(y2)) 6→ε s(max(y2,y1)) = t can be joined as follows.
s
↔ s(max(y1,y2)) ↔ s(max(y2,y1)) ↔ s(max(y1,y2)) ↔
t
-
The critical peak s = y1 {ε}←4 max(y1,0) 5→ε max(0,y1) = t can be joined as follows.
s
↔ y1 ↔ max(y1,0) ↔ max(0,y1) ↔
t
-
The critical peak s = y2 {ε}←5 max(0,y2) 5→ε max(y2,0) = t can be joined as follows.
s
↔ y2 ↔ max(y2,0) ↔
t
-
The critical peak s = s(max(x0_2,x0_1)) {ε}←4 max(s(x0_1),s(x0_2)) 5→ε max(s(x0_2),s(x0_1)) = t can be joined as follows.
s
↔ s(max(x0_2,x0_1)) ↔ s(max(x0_1,x0_2)) ↔ max(s(x0_2),s(x0_1)) ↔
t
The remaining rules are handled recursively.
There are no rules.
1.1 (Weakly) Orthogonal
Confluence is proven since the TRS is (weakly) orthogonal.
Tool configuration
Hakusan