0.00/0.72
0.00/0.72
(0) Obligation:
Runtime Complexity TRS:
The TRS R consists of the following rules:
sum(0) → 0
0.00/0.72
sum(s(x)) → +(sqr(s(x)), sum(x))
0.00/0.72
sqr(x) → *(x, x)
0.00/0.72
sum(s(x)) → +(*(s(x), s(x)), sum(x))
Rewrite Strategy: INNERMOST
0.00/0.72
0.00/0.72
(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)
Converted CpxTRS to CDT
0.00/0.72
0.00/0.72
(2) Obligation:
Complexity Dependency Tuples Problem
Rules:
sum(0) → 0
0.00/0.72
sum(s(z0)) → +(sqr(s(z0)), sum(z0))
0.00/0.72
sum(s(z0)) → +(*(s(z0), s(z0)), sum(z0))
0.00/0.72
sqr(z0) → *(z0, z0)
Tuples:
SUM(s(z0)) → c1(SQR(s(z0)), SUM(z0))
0.00/0.72
SUM(s(z0)) → c2(SUM(z0))
S tuples:
SUM(s(z0)) → c1(SQR(s(z0)), SUM(z0))
0.00/0.72
SUM(s(z0)) → c2(SUM(z0))
K tuples:none
Defined Rule Symbols:
sum, sqr
Defined Pair Symbols:
SUM
Compound Symbols:
c1, c2
0.00/0.72
0.00/0.72
(3) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID) transformation)
Removed 1 trailing tuple parts
0.00/0.72
0.00/0.72
(4) Obligation:
Complexity Dependency Tuples Problem
Rules:
sum(0) → 0
0.00/0.72
sum(s(z0)) → +(sqr(s(z0)), sum(z0))
0.00/0.72
sum(s(z0)) → +(*(s(z0), s(z0)), sum(z0))
0.00/0.72
sqr(z0) → *(z0, z0)
Tuples:
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
S tuples:
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
K tuples:none
Defined Rule Symbols:
sum, sqr
Defined Pair Symbols:
SUM
Compound Symbols:
c2, c1
0.00/0.72
0.00/0.72
(5) CdtPolyRedPairProof (UPPER BOUND (ADD(O(n^1))) transformation)
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
We considered the (Usable) Rules:none
And the Tuples:
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
The order we found is given by the following interpretation:
Polynomial interpretation :
0.00/0.72
POL(SUM(x1)) = [2]x1
0.00/0.72
POL(c1(x1)) = x1
0.00/0.72
POL(c2(x1)) = x1
0.00/0.72
POL(s(x1)) = [1] + x1
0.00/0.72
0.00/0.72
(6) Obligation:
Complexity Dependency Tuples Problem
Rules:
sum(0) → 0
0.00/0.72
sum(s(z0)) → +(sqr(s(z0)), sum(z0))
0.00/0.72
sum(s(z0)) → +(*(s(z0), s(z0)), sum(z0))
0.00/0.72
sqr(z0) → *(z0, z0)
Tuples:
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
S tuples:none
K tuples:
SUM(s(z0)) → c2(SUM(z0))
0.00/0.72
SUM(s(z0)) → c1(SUM(z0))
Defined Rule Symbols:
sum, sqr
Defined Pair Symbols:
SUM
Compound Symbols:
c2, c1
0.00/0.72
0.00/0.72
(7) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)
The set S is empty
0.00/0.72
0.00/0.72
(8) BOUNDS(O(1), O(1))
0.00/0.72