/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^2), O(n^3))
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).

(0) CpxTRS
(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(2) CdtProblem
    (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (4) CdtProblem
    (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CdtProblem
    (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 527 ms]
    (12) CdtProblem
    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 27 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 23 ms]
    (16) CdtProblem
    (17) CdtKnowledgeProof [FINISHED, 0 ms]
    (18) BOUNDS(1, 1)
(19) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(20) CpxTRS
    (21) SlicingProof [LOWER BOUND(ID), 0 ms]
    (22) CpxTRS
    (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (24) typed CpxTrs
    (25) OrderProof [LOWER BOUND(ID), 0 ms]
    (26) typed CpxTrs
    (27) RewriteLemmaProof [LOWER BOUND(ID), 301 ms]
    (28) BEST
        (29) proven lower bound
            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
            (31) BOUNDS(n^1, INF)
        (32) typed CpxTrs
            (33) RewriteLemmaProof [LOWER BOUND(ID), 49 ms]
            (34) BEST
                (35) proven lower bound
                    (36) LowerBoundPropagationProof [FINISHED, 0 ms]
                    (37) BOUNDS(n^2, INF)
                (38) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).


The TRS R consists of the following rules:

   from(X) -> cons(X, n__from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z)))
   2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z)))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z)))
   2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z)))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)
   from(X) -> n__from(X)
   activate(n__from(X)) -> from(X)
   activate(X) -> X

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
   2ndspos(0, z0) -> rnil
   2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2)))
   2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3)))
   2ndsneg(0, z0) -> rnil
   2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2)))
   2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3)))
   pi(z0) -> 2ndspos(z0, from(0))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   square(z0) -> times(z0, z0)
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
Tuples:
   FROM(z0) -> c
   FROM(z0) -> c1
   2NDSPOS(0, z0) -> c2
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3))
   2NDSNEG(0, z0) -> c5
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3))
   PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0))
   PLUS(0, z0) -> c9
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(0, z0) -> c11
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   SQUARE(z0) -> c13(TIMES(z0, z0))
   ACTIVATE(n__from(z0)) -> c14(FROM(z0))
   ACTIVATE(z0) -> c15
S tuples:
   FROM(z0) -> c
   FROM(z0) -> c1
   2NDSPOS(0, z0) -> c2
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3))
   2NDSNEG(0, z0) -> c5
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3))
   PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0))
   PLUS(0, z0) -> c9
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(0, z0) -> c11
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   SQUARE(z0) -> c13(TIMES(z0, z0))
   ACTIVATE(n__from(z0)) -> c14(FROM(z0))
   ACTIVATE(z0) -> c15
K tuples:none
Defined Rule Symbols:   from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1

Defined Pair Symbols:   FROM_1, 2NDSPOS_2, 2NDSNEG_2, PI_1, PLUS_2, TIMES_2, SQUARE_1, ACTIVATE_1

Compound Symbols:   c, c1, c2, c3_2, c4_2, c5, c6_2, c7_2, c8_2, c9, c10_1, c11, c12_2, c13_1, c14_1, c15


----------------------------------------

(3) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 1 leading nodes:
   SQUARE(z0) -> c13(TIMES(z0, z0))
Removed 8 trailing nodes:
   PLUS(0, z0) -> c9
   TIMES(0, z0) -> c11
   FROM(z0) -> c
   ACTIVATE(z0) -> c15
   2NDSPOS(0, z0) -> c2
   FROM(z0) -> c1
   2NDSNEG(0, z0) -> c5
   ACTIVATE(n__from(z0)) -> c14(FROM(z0))

----------------------------------------

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
   2ndspos(0, z0) -> rnil
   2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2)))
   2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3)))
   2ndsneg(0, z0) -> rnil
   2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2)))
   2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3)))
   pi(z0) -> 2ndspos(z0, from(0))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   square(z0) -> times(z0, z0)
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
Tuples:
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3))
   PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0))
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
S tuples:
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3))
   PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0))
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
K tuples:none
Defined Rule Symbols:   from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1

Defined Pair Symbols:   2NDSPOS_2, 2NDSNEG_2, PI_1, PLUS_2, TIMES_2

Compound Symbols:   c3_2, c4_2, c6_2, c7_2, c8_2, c10_1, c12_2


----------------------------------------

(5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 5 trailing tuple parts
----------------------------------------

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
   2ndspos(0, z0) -> rnil
   2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2)))
   2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3)))
   2ndsneg(0, z0) -> rnil
   2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2)))
   2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3)))
   pi(z0) -> 2ndspos(z0, from(0))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   square(z0) -> times(z0, z0)
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
K tuples:none
Defined Rule Symbols:   from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))

----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
   2ndspos(0, z0) -> rnil
   2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2)))
   2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3)))
   2ndsneg(0, z0) -> rnil
   2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2)))
   2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3)))
   pi(z0) -> 2ndspos(z0, from(0))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   square(z0) -> times(z0, z0)
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
K tuples:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
Defined Rule Symbols:   from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   2ndspos(0, z0) -> rnil
   2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2)))
   2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3)))
   2ndsneg(0, z0) -> rnil
   2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2)))
   2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3)))
   pi(z0) -> 2ndspos(z0, from(0))
   square(z0) -> times(z0, z0)

----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
K tuples:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
Defined Rule Symbols:   times_2, plus_2, activate_1, from_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
We considered the (Usable) Rules:none
And the Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(2NDSNEG(x_1, x_2)) = 0
   POL(2NDSPOS(x_1, x_2)) = 0
   POL(PI(x_1)) = 0
   POL(PLUS(x_1, x_2)) = x_1^2
   POL(TIMES(x_1, x_2)) = x_1*x_2^2
   POL(activate(x_1)) = 0
   POL(c10(x_1)) = x_1
   POL(c12(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(cons(x_1, x_2)) = 0
   POL(cons2(x_1, x_2)) = 0
   POL(from(x_1)) = 0
   POL(n__from(x_1)) = [1]
   POL(plus(x_1, x_2)) = [1] + x_1 + x_2 + x_2^2 + x_1*x_2 + x_1^2 + x_1^3 + x_1^2*x_2 + x_1*x_2^2
   POL(s(x_1)) = [1] + x_1
   POL(times(x_1, x_2)) = x_1^3 + x_1*x_2^2 + x_2^3

----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
K tuples:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
Defined Rule Symbols:   times_2, plus_2, activate_1, from_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
We considered the (Usable) Rules:none
And the Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(2NDSNEG(x_1, x_2)) = 0
   POL(2NDSPOS(x_1, x_2)) = 0
   POL(PI(x_1)) = 0
   POL(PLUS(x_1, x_2)) = 0
   POL(TIMES(x_1, x_2)) = x_1
   POL(activate(x_1)) = x_1
   POL(c10(x_1)) = x_1
   POL(c12(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_2
   POL(cons2(x_1, x_2)) = [1] + x_1
   POL(from(x_1)) = [1]
   POL(n__from(x_1)) = [1]
   POL(plus(x_1, x_2)) = [1] + x_1 + x_2
   POL(s(x_1)) = [1] + x_1
   POL(times(x_1, x_2)) = [1] + x_1 + x_2

----------------------------------------

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
K tuples:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
Defined Rule Symbols:   times_2, plus_2, activate_1, from_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
We considered the (Usable) Rules:none
And the Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(2NDSNEG(x_1, x_2)) = x_1
   POL(2NDSPOS(x_1, x_2)) = [1] + x_1
   POL(PI(x_1)) = [1] + x_1
   POL(PLUS(x_1, x_2)) = 0
   POL(TIMES(x_1, x_2)) = 0
   POL(activate(x_1)) = 0
   POL(c10(x_1)) = x_1
   POL(c12(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1
   POL(cons2(x_1, x_2)) = x_1
   POL(from(x_1)) = 0
   POL(n__from(x_1)) = [3] + x_1
   POL(plus(x_1, x_2)) = [3] + [3]x_1
   POL(s(x_1)) = [1] + x_1
   POL(times(x_1, x_2)) = [3] + [3]x_1 + [3]x_2

----------------------------------------

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   times(0, z0) -> 0
   times(s(z0), z1) -> plus(z1, times(z0, z1))
   plus(0, z0) -> z0
   plus(s(z0), z1) -> s(plus(z0, z1))
   activate(n__from(z0)) -> from(z0)
   activate(z0) -> z0
   from(z0) -> cons(z0, n__from(s(z0)))
   from(z0) -> n__from(z0)
Tuples:
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
S tuples:
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
K tuples:
   PI(z0) -> c8(2NDSPOS(z0, from(0)))
   PLUS(s(z0), z1) -> c10(PLUS(z0, z1))
   TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
Defined Rule Symbols:   times_2, plus_2, activate_1, from_1

Defined Pair Symbols:   PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1

Compound Symbols:   c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1


----------------------------------------

(17) CdtKnowledgeProof (FINISHED)
The following tuples could be moved from S to K by knowledge propagation:
   2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)))
   2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
   2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)))
Now S is empty
----------------------------------------

(18)
BOUNDS(1, 1)

----------------------------------------

(19) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(20)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   from(X) -> cons(X, n__from(s(X)))
   2ndspos(0', Z) -> rnil
   2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z)))
   2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z)))
   2ndsneg(0', Z) -> rnil
   2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z)))
   2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z)))
   pi(X) -> 2ndspos(X, from(0'))
   plus(0', Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0', Y) -> 0'
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)
   from(X) -> n__from(X)
   activate(n__from(X)) -> from(X)
   activate(X) -> X

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(21) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
from/0
cons/0
n__from/0
cons2/0
rcons/0
posrecip/0
negrecip/0

----------------------------------------

(22)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   from -> cons(n__from)
   2ndspos(0', Z) -> rnil
   2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
   2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
   2ndsneg(0', Z) -> rnil
   2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
   2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
   pi(X) -> 2ndspos(X, from)
   plus(0', Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0', Y) -> 0'
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)
   from -> n__from
   activate(n__from) -> from
   activate(X) -> X

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(23) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(24)
Obligation:
Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s

----------------------------------------

(25) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
2ndspos, 2ndsneg, plus, times

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg
plus < times

----------------------------------------

(26)
Obligation:
Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s


Generator Equations:
gen_n__from:cons:cons24_0(0) <=> n__from
gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x))
gen_rnil:rcons5_0(0) <=> rnil
gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
plus, 2ndspos, 2ndsneg, times

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg
plus < times

----------------------------------------

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0)

Induction Base:
plus(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1)
gen_0':s6_0(b)

Induction Step:
plus(gen_0':s6_0(+(n8_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1)
s(plus(gen_0':s6_0(n8_0), gen_0':s6_0(b))) ->_IH
s(gen_0':s6_0(+(b, c9_0)))

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(28)
Complex Obligation (BEST)

----------------------------------------

(29)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s


Generator Equations:
gen_n__from:cons:cons24_0(0) <=> n__from
gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x))
gen_rnil:rcons5_0(0) <=> rnil
gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
plus, 2ndspos, 2ndsneg, times

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg
plus < times

----------------------------------------

(30) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(31)
BOUNDS(n^1, INF)

----------------------------------------

(32)
Obligation:
Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0)


Generator Equations:
gen_n__from:cons:cons24_0(0) <=> n__from
gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x))
gen_rnil:rcons5_0(0) <=> rnil
gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
times, 2ndspos, 2ndsneg

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg

----------------------------------------

(33) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
times(gen_0':s6_0(n1067_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1067_0, b)), rt in Omega(1 + b*n1067_0 + n1067_0)

Induction Base:
times(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1)
0'

Induction Step:
times(gen_0':s6_0(+(n1067_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1)
plus(gen_0':s6_0(b), times(gen_0':s6_0(n1067_0), gen_0':s6_0(b))) ->_IH
plus(gen_0':s6_0(b), gen_0':s6_0(*(c1068_0, b))) ->_L^Omega(1 + b)
gen_0':s6_0(+(b, *(n1067_0, b)))

We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
----------------------------------------

(34)
Complex Obligation (BEST)

----------------------------------------

(35)
Obligation:
Proved the lower bound n^2 for the following obligation:

Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0)


Generator Equations:
gen_n__from:cons:cons24_0(0) <=> n__from
gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x))
gen_rnil:rcons5_0(0) <=> rnil
gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
times, 2ndspos, 2ndsneg

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg

----------------------------------------

(36) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(37)
BOUNDS(n^2, INF)

----------------------------------------

(38)
Obligation:
Innermost TRS:
Rules:
from -> cons(n__from)
2ndspos(0', Z) -> rnil
2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z)))
2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z)))
2ndsneg(0', Z) -> rnil
2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z)))
2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z)))
pi(X) -> 2ndspos(X, from)
plus(0', Y) -> Y
plus(s(X), Y) -> s(plus(X, Y))
times(0', Y) -> 0'
times(s(X), Y) -> plus(Y, times(X, Y))
square(X) -> times(X, X)
from -> n__from
activate(n__from) -> from
activate(X) -> X

Types:
from :: n__from:cons:cons2
cons :: n__from:cons:cons2 -> n__from:cons:cons2
n__from :: n__from:cons:cons2
2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons
0' :: 0':s
rnil :: rnil:rcons
s :: 0':s -> 0':s
cons2 :: n__from:cons:cons2 -> n__from:cons:cons2
activate :: n__from:cons:cons2 -> n__from:cons:cons2
rcons :: rnil:rcons -> rnil:rcons
2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons
pi :: 0':s -> rnil:rcons
plus :: 0':s -> 0':s -> 0':s
times :: 0':s -> 0':s -> 0':s
square :: 0':s -> 0':s
hole_n__from:cons:cons21_0 :: n__from:cons:cons2
hole_rnil:rcons2_0 :: rnil:rcons
hole_0':s3_0 :: 0':s
gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2
gen_rnil:rcons5_0 :: Nat -> rnil:rcons
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0)
times(gen_0':s6_0(n1067_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1067_0, b)), rt in Omega(1 + b*n1067_0 + n1067_0)


Generator Equations:
gen_n__from:cons:cons24_0(0) <=> n__from
gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x))
gen_rnil:rcons5_0(0) <=> rnil
gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
2ndsneg, 2ndspos

They will be analysed ascendingly in the following order:
2ndspos = 2ndsneg