Certification Problem
Input (TPDB Runtime_Complexity_Innermost_Rewriting/Frederiksen_Others/div2)
The relative rewrite relation R/S is considered where R is the following TRS
|
div2(S(S(x))) |
→ |
+(S(0),div2(x)) |
(1) |
|
div2(S(0)) |
→ |
0 |
(2) |
|
div2(0) |
→ |
0 |
(3) |
and S is the following TRS.
|
+(x,S(0)) |
→ |
S(x) |
(4) |
|
+(S(0),y) |
→ |
S(y) |
(5) |
The evaluation strategy is innermost.Property / Task
Determine bounds on the runtime complexity.Answer / Result
An upperbound for the complexity is O(n).Proof (by AProVE @ termCOMP 2023)
1 Dependency Tuples
We get the following set of dependency tuples:
|
div2#(S(S(z0))) |
→ |
c2(+#(S(0),div2(z0)),div2#(z0)) |
(7) |
|
originates from |
|
div2(S(S(z0))) |
→ |
+(S(0),div2(z0)) |
(6) |
|
|
originates from |
|
|
originates from |
|
|
originates from |
|
|
originates from |
|
Moreover, we add the following terms to the innermost strategy.
|
+#(z0,S(0)) |
|
+#(S(0),z0) |
|
div2#(S(S(z0))) |
|
div2#(S(0)) |
|
div2#(0) |
1.1 Rule Shifting
The rules
|
div2#(S(0)) |
→ |
c3 |
(8) |
|
div2#(0) |
→ |
c4 |
(9) |
are strictly oriented by the following
linear polynomial interpretation over the naturals
| [c] |
= |
0 |
| [c1] |
= |
0 |
| [c2(x1, x2)] |
= |
1 · x1 + 0 + 1 · x2
|
| [c3] |
= |
0 |
| [c4] |
= |
0 |
| [div2(x1)] |
= |
1 |
| [+(x1, x2)] |
= |
1 + 1 · x1 + 1 · x2
|
| [+#(x1, x2)] |
= |
1 · x1 + 0 |
| [div2#(x1)] |
= |
1 + 1 · x1
|
| [S(x1)] |
= |
1 + 1 · x1
|
| [0] |
= |
1 |
which has the intended complexity.
Here, only the following usable rules have been considered:
|
+#(z0,S(0)) |
→ |
c |
(11) |
|
+#(S(0),z0) |
→ |
c1 |
(13) |
|
div2#(S(S(z0))) |
→ |
c2(+#(S(0),div2(z0)),div2#(z0)) |
(7) |
|
div2#(S(0)) |
→ |
c3 |
(8) |
|
div2#(0) |
→ |
c4 |
(9) |
1.1.1 Rule Shifting
The rules
|
div2#(S(S(z0))) |
→ |
c2(+#(S(0),div2(z0)),div2#(z0)) |
(7) |
are strictly oriented by the following
linear polynomial interpretation over the naturals
| [c] |
= |
0 |
| [c1] |
= |
0 |
| [c2(x1, x2)] |
= |
1 · x1 + 0 + 1 · x2
|
| [c3] |
= |
0 |
| [c4] |
= |
0 |
| [div2(x1)] |
= |
3 |
| [+(x1, x2)] |
= |
3 |
| [+#(x1, x2)] |
= |
1 |
| [div2#(x1)] |
= |
2 · x1 + 0 |
| [S(x1)] |
= |
2 + 1 · x1
|
| [0] |
= |
0 |
which has the intended complexity.
Here, only the following usable rules have been considered:
|
+#(z0,S(0)) |
→ |
c |
(11) |
|
+#(S(0),z0) |
→ |
c1 |
(13) |
|
div2#(S(S(z0))) |
→ |
c2(+#(S(0),div2(z0)),div2#(z0)) |
(7) |
|
div2#(S(0)) |
→ |
c3 |
(8) |
|
div2#(0) |
→ |
c4 |
(9) |
1.1.1.1 R is empty
There are no rules in the TRS R. Hence, R/S has complexity O(1).