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