YES
Confluence Proof
Confluence Proof
by csi
Input
The rewrite relation of the following TRS is considered.
|
+(x,0) |
→ |
x |
|
+(x,s(y)) |
→ |
s(+(x,y)) |
|
d(0) |
→ |
0 |
|
d(s(x)) |
→ |
s(s(d(x))) |
|
f(0) |
→ |
0 |
|
f(s(x)) |
→ |
+(+(s(x),s(x)),s(x)) |
|
f(g(0)) |
→ |
+(+(g(0),g(0)),g(0)) |
|
g(x) |
→ |
s(d(x)) |
Proof
1 Decreasing Diagrams
1.1 Relative Termination Proof
The duplicating rules (R) terminate relative to the other rules (S).
1.1.1 Rule Removal
Using the
recursive path order with the following precedence and status
| prec(g) |
= |
3 |
|
stat(g) |
= |
lex
|
| prec(f) |
= |
3 |
|
stat(f) |
= |
lex
|
| prec(d) |
= |
1 |
|
stat(d) |
= |
lex
|
| prec(s) |
= |
0 |
|
stat(s) |
= |
lex
|
| prec(+) |
= |
2 |
|
stat(+) |
= |
lex
|
| prec(0) |
= |
0 |
|
stat(0) |
= |
lex
|
all rules of R could be removed.
Moreover,
all rules of S could be removed.
1.1.1.1 R is empty
There are no rules in the TRS R. Hence, R/S is relative terminating.
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).
-
+(x,0)→x ↦ 0
-
+(x,s(y))→s(+(x,y)) ↦ 0
-
d(0)→0 ↦ 0
-
d(s(x))→s(s(d(x))) ↦ 0
-
f(0)→0 ↦ 0
-
f(s(x))→+(+(s(x),s(x)),s(x)) ↦ 0
-
f(g(0))→+(+(g(0),g(0)),g(0)) ↦ 3
-
g(x)→s(d(x)) ↦ 0
All critical pairs are joinable:
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(g(0),s(d(0))),s(d(0)))←+(+(g(0),g(0)),s(d(0)))←+(+(g(0),g(0)),g(0))
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(g(0),s(d(0))),s(d(0)))←+(+(g(0),s(d(0))),g(0))←+(+(g(0),g(0)),g(0))
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(s(d(0)),g(0)),s(d(0)))←+(+(g(0),g(0)),s(d(0)))←+(+(g(0),g(0)),g(0))
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(s(d(0)),g(0)),s(d(0)))←+(+(s(d(0)),g(0)),g(0))←+(+(g(0),g(0)),g(0))
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(s(d(0)),s(d(0))),g(0))←+(+(g(0),s(d(0))),g(0))←+(+(g(0),g(0)),g(0))
-
f(s(d(0)))→+(+(s(d(0)),s(d(0))),s(d(0)))←+(+(s(d(0)),s(d(0))),g(0))←+(+(s(d(0)),g(0)),g(0))←+(+(g(0),g(0)),g(0))
Tool configuration
csi
- version: csi 1.2.5 [hg: unknown]
- strategy:
(if left-linear then (cr -dup;(( lpo -quasi || (matrix -dim 1 -ib 3 -ob 4 | matrix -dim 2 -ib 2 -ob 2 | matrix -dim 3 -ib 1 -ob 2 | arctic -dim 2 -ib 2 -ob 2) || (if duplicating then fail else (bounds -rt || bounds -rt -qc))[1] || poly -ib 2 -ob 4 -nl2 -heuristic 1 || fail )[5]*);shift -lstar);(rule_labeling | rule_labeling -left)?;decreasing else fail)!