1099.96/291.54 WORST_CASE(Omega(n^3), O(n^3)) 1099.96/291.57 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1099.96/291.57 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1099.96/291.57 1099.96/291.57 1099.96/291.57 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 1099.96/291.57 1099.96/291.57 (0) CpxTRS 1099.96/291.57 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 6 ms] 1099.96/291.57 (2) CpxTRS 1099.96/291.57 (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 9 ms] 1099.96/291.57 (4) CpxTRS 1099.96/291.57 (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (6) CpxWeightedTrs 1099.96/291.57 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (8) CpxTypedWeightedTrs 1099.96/291.57 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (10) CpxTypedWeightedCompleteTrs 1099.96/291.57 (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (12) CpxTypedWeightedCompleteTrs 1099.96/291.57 (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (14) CpxRNTS 1099.96/291.57 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (16) CpxRNTS 1099.96/291.57 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 4 ms] 1099.96/291.57 (18) CpxRNTS 1099.96/291.57 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (20) CpxRNTS 1099.96/291.57 (21) IntTrsBoundProof [UPPER BOUND(ID), 202 ms] 1099.96/291.57 (22) CpxRNTS 1099.96/291.57 (23) IntTrsBoundProof [UPPER BOUND(ID), 87 ms] 1099.96/291.57 (24) CpxRNTS 1099.96/291.57 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (26) CpxRNTS 1099.96/291.57 (27) IntTrsBoundProof [UPPER BOUND(ID), 269 ms] 1099.96/291.57 (28) CpxRNTS 1099.96/291.57 (29) IntTrsBoundProof [UPPER BOUND(ID), 85 ms] 1099.96/291.57 (30) CpxRNTS 1099.96/291.57 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (32) CpxRNTS 1099.96/291.57 (33) IntTrsBoundProof [UPPER BOUND(ID), 252 ms] 1099.96/291.57 (34) CpxRNTS 1099.96/291.57 (35) IntTrsBoundProof [UPPER BOUND(ID), 83 ms] 1099.96/291.57 (36) CpxRNTS 1099.96/291.57 (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (38) CpxRNTS 1099.96/291.57 (39) IntTrsBoundProof [UPPER BOUND(ID), 514 ms] 1099.96/291.57 (40) CpxRNTS 1099.96/291.57 (41) IntTrsBoundProof [UPPER BOUND(ID), 34 ms] 1099.96/291.57 (42) CpxRNTS 1099.96/291.57 (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (44) CpxRNTS 1099.96/291.57 (45) IntTrsBoundProof [UPPER BOUND(ID), 679 ms] 1099.96/291.57 (46) CpxRNTS 1099.96/291.57 (47) IntTrsBoundProof [UPPER BOUND(ID), 2 ms] 1099.96/291.57 (48) CpxRNTS 1099.96/291.57 (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1099.96/291.57 (50) CpxRNTS 1099.96/291.57 (51) IntTrsBoundProof [UPPER BOUND(ID), 2788 ms] 1099.96/291.57 (52) CpxRNTS 1099.96/291.57 (53) IntTrsBoundProof [UPPER BOUND(ID), 10 ms] 1099.96/291.57 (54) CpxRNTS 1099.96/291.57 (55) FinalProof [FINISHED, 0 ms] 1099.96/291.57 (56) BOUNDS(1, n^3) 1099.96/291.57 (57) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (58) CpxTRS 1099.96/291.57 (59) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.96/291.57 (60) typed CpxTrs 1099.96/291.57 (61) OrderProof [LOWER BOUND(ID), 0 ms] 1099.96/291.57 (62) typed CpxTrs 1099.96/291.57 (63) RewriteLemmaProof [LOWER BOUND(ID), 307 ms] 1099.96/291.57 (64) BEST 1099.96/291.57 (65) proven lower bound 1099.96/291.57 (66) LowerBoundPropagationProof [FINISHED, 0 ms] 1099.96/291.57 (67) BOUNDS(n^1, INF) 1099.96/291.57 (68) typed CpxTrs 1099.96/291.57 (69) RewriteLemmaProof [LOWER BOUND(ID), 78 ms] 1099.96/291.57 (70) typed CpxTrs 1099.96/291.57 (71) RewriteLemmaProof [LOWER BOUND(ID), 66 ms] 1099.96/291.57 (72) BEST 1099.96/291.57 (73) proven lower bound 1099.96/291.57 (74) LowerBoundPropagationProof [FINISHED, 0 ms] 1099.96/291.57 (75) BOUNDS(n^3, INF) 1099.96/291.57 (76) typed CpxTrs 1099.96/291.57 (77) RewriteLemmaProof [LOWER BOUND(ID), 30 ms] 1099.96/291.57 (78) BOUNDS(1, INF) 1099.96/291.57 1099.96/291.57 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (0) 1099.96/291.57 Obligation: 1099.96/291.57 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 1099.96/291.57 1099.96/291.57 1099.96/291.57 The TRS R consists of the following rules: 1099.96/291.57 1099.96/291.57 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1099.96/291.57 sqr(0) -> 0 1099.96/291.57 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1099.96/291.57 dbl(0) -> 0 1099.96/291.57 dbl(s(X)) -> s(s(dbl(X))) 1099.96/291.57 add(0, X) -> X 1099.96/291.57 add(s(X), Y) -> s(add(X, Y)) 1099.96/291.57 first(0, X) -> nil 1099.96/291.57 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1099.96/291.57 half(0) -> 0 1099.96/291.57 half(s(0)) -> 0 1099.96/291.57 half(s(s(X))) -> s(half(X)) 1099.96/291.57 half(dbl(X)) -> X 1099.96/291.57 terms(X) -> n__terms(X) 1099.96/291.57 first(X1, X2) -> n__first(X1, X2) 1099.96/291.57 activate(n__terms(X)) -> terms(X) 1099.96/291.57 activate(n__first(X1, X2)) -> first(X1, X2) 1099.96/291.57 activate(X) -> X 1099.96/291.57 1099.96/291.57 S is empty. 1099.96/291.57 Rewrite Strategy: FULL 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 1099.96/291.57 The following defined symbols can occur below the 0th argument of add: sqr, add, dbl 1099.96/291.57 The following defined symbols can occur below the 1th argument of add: dbl 1099.96/291.57 1099.96/291.57 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 1099.96/291.57 half(dbl(X)) -> X 1099.96/291.57 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (2) 1099.96/291.57 Obligation: 1099.96/291.57 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 1099.96/291.57 1099.96/291.57 1099.96/291.57 The TRS R consists of the following rules: 1099.96/291.57 1099.96/291.57 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1099.96/291.57 sqr(0) -> 0 1099.96/291.57 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1099.96/291.57 dbl(0) -> 0 1099.96/291.57 dbl(s(X)) -> s(s(dbl(X))) 1099.96/291.57 add(0, X) -> X 1099.96/291.57 add(s(X), Y) -> s(add(X, Y)) 1099.96/291.57 first(0, X) -> nil 1099.96/291.57 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1099.96/291.57 half(0) -> 0 1099.96/291.57 half(s(0)) -> 0 1099.96/291.57 half(s(s(X))) -> s(half(X)) 1099.96/291.57 terms(X) -> n__terms(X) 1099.96/291.57 first(X1, X2) -> n__first(X1, X2) 1099.96/291.57 activate(n__terms(X)) -> terms(X) 1099.96/291.57 activate(n__first(X1, X2)) -> first(X1, X2) 1099.96/291.57 activate(X) -> X 1099.96/291.57 1099.96/291.57 S is empty. 1099.96/291.57 Rewrite Strategy: FULL 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) 1099.96/291.57 Converted rc-obligation to irc-obligation. 1099.96/291.57 1099.96/291.57 The duplicating contexts are: 1099.96/291.57 terms([]) 1099.96/291.57 sqr(s([])) 1099.96/291.57 1099.96/291.57 1099.96/291.57 The defined contexts are: 1099.96/291.57 add([], x1) 1099.96/291.57 add(x0, []) 1099.96/291.57 1099.96/291.57 1099.96/291.57 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (4) 1099.96/291.57 Obligation: 1099.96/291.57 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 1099.96/291.57 1099.96/291.57 1099.96/291.57 The TRS R consists of the following rules: 1099.96/291.57 1099.96/291.57 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1099.96/291.57 sqr(0) -> 0 1099.96/291.57 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1099.96/291.57 dbl(0) -> 0 1099.96/291.57 dbl(s(X)) -> s(s(dbl(X))) 1099.96/291.57 add(0, X) -> X 1099.96/291.57 add(s(X), Y) -> s(add(X, Y)) 1099.96/291.57 first(0, X) -> nil 1099.96/291.57 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1099.96/291.57 half(0) -> 0 1099.96/291.57 half(s(0)) -> 0 1099.96/291.57 half(s(s(X))) -> s(half(X)) 1099.96/291.57 terms(X) -> n__terms(X) 1099.96/291.57 first(X1, X2) -> n__first(X1, X2) 1099.96/291.57 activate(n__terms(X)) -> terms(X) 1099.96/291.57 activate(n__first(X1, X2)) -> first(X1, X2) 1099.96/291.57 activate(X) -> X 1099.96/291.57 1099.96/291.57 S is empty. 1099.96/291.57 Rewrite Strategy: INNERMOST 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1099.96/291.57 Transformed relative TRS to weighted TRS 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (6) 1099.96/291.57 Obligation: 1099.96/291.57 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 1099.96/291.57 1099.96/291.57 1099.96/291.57 The TRS R consists of the following rules: 1099.96/291.57 1099.96/291.57 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1] 1099.96/291.57 sqr(0) -> 0 [1] 1099.96/291.57 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1099.96/291.57 dbl(0) -> 0 [1] 1099.96/291.57 dbl(s(X)) -> s(s(dbl(X))) [1] 1099.96/291.57 add(0, X) -> X [1] 1099.96/291.57 add(s(X), Y) -> s(add(X, Y)) [1] 1099.96/291.57 first(0, X) -> nil [1] 1099.96/291.57 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1] 1099.96/291.57 half(0) -> 0 [1] 1099.96/291.57 half(s(0)) -> 0 [1] 1099.96/291.57 half(s(s(X))) -> s(half(X)) [1] 1099.96/291.57 terms(X) -> n__terms(X) [1] 1099.96/291.57 first(X1, X2) -> n__first(X1, X2) [1] 1099.96/291.57 activate(n__terms(X)) -> terms(X) [1] 1099.96/291.57 activate(n__first(X1, X2)) -> first(X1, X2) [1] 1099.96/291.57 activate(X) -> X [1] 1099.96/291.57 1099.96/291.57 Rewrite Strategy: INNERMOST 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1099.96/291.57 Infered types. 1099.96/291.57 ---------------------------------------- 1099.96/291.57 1099.96/291.57 (8) 1099.96/291.57 Obligation: 1099.96/291.57 Runtime Complexity Weighted TRS with Types. 1099.96/291.57 The TRS R consists of the following rules: 1099.96/291.57 1099.96/291.57 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1] 1099.96/291.57 sqr(0) -> 0 [1] 1099.96/291.57 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1099.96/291.57 dbl(0) -> 0 [1] 1099.96/291.57 dbl(s(X)) -> s(s(dbl(X))) [1] 1099.96/291.57 add(0, X) -> X [1] 1099.96/291.57 add(s(X), Y) -> s(add(X, Y)) [1] 1099.96/291.57 first(0, X) -> nil [1] 1099.96/291.57 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1] 1099.96/291.57 half(0) -> 0 [1] 1099.96/291.57 half(s(0)) -> 0 [1] 1099.96/291.57 half(s(s(X))) -> s(half(X)) [1] 1099.96/291.57 terms(X) -> n__terms(X) [1] 1099.96/291.57 first(X1, X2) -> n__first(X1, X2) [1] 1099.96/291.57 activate(n__terms(X)) -> terms(X) [1] 1099.96/291.57 activate(n__first(X1, X2)) -> first(X1, X2) [1] 1099.96/291.57 activate(X) -> X [1] 1099.96/291.57 1099.96/291.57 The TRS has the following type information: 1099.96/291.57 terms :: s:0 -> n__terms:cons:nil:n__first 1099.96/291.57 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1099.96/291.57 recip :: s:0 -> recip 1099.96/291.57 sqr :: s:0 -> s:0 1099.96/291.57 n__terms :: s:0 -> n__terms:cons:nil:n__first 1100.24/291.58 s :: s:0 -> s:0 1100.24/291.58 0 :: s:0 1100.24/291.58 add :: s:0 -> s:0 -> s:0 1100.24/291.58 dbl :: s:0 -> s:0 1100.24/291.58 first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 nil :: n__terms:cons:nil:n__first 1100.24/291.58 n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 half :: s:0 -> s:0 1100.24/291.58 1100.24/291.58 Rewrite Strategy: INNERMOST 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (9) CompletionProof (UPPER BOUND(ID)) 1100.24/291.58 The transformation into a RNTS is sound, since: 1100.24/291.58 1100.24/291.58 (a) The obligation is a constructor system where every type has a constant constructor, 1100.24/291.58 1100.24/291.58 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1100.24/291.58 1100.24/291.58 terms_1 1100.24/291.58 first_2 1100.24/291.58 half_1 1100.24/291.58 activate_1 1100.24/291.58 1100.24/291.58 (c) The following functions are completely defined: 1100.24/291.58 1100.24/291.58 sqr_1 1100.24/291.58 dbl_1 1100.24/291.58 add_2 1100.24/291.58 1100.24/291.58 Due to the following rules being added: 1100.24/291.58 none 1100.24/291.58 1100.24/291.58 And the following fresh constants: const 1100.24/291.58 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (10) 1100.24/291.58 Obligation: 1100.24/291.58 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1100.24/291.58 1100.24/291.58 Runtime Complexity Weighted TRS with Types. 1100.24/291.58 The TRS R consists of the following rules: 1100.24/291.58 1100.24/291.58 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1] 1100.24/291.58 sqr(0) -> 0 [1] 1100.24/291.58 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1100.24/291.58 dbl(0) -> 0 [1] 1100.24/291.58 dbl(s(X)) -> s(s(dbl(X))) [1] 1100.24/291.58 add(0, X) -> X [1] 1100.24/291.58 add(s(X), Y) -> s(add(X, Y)) [1] 1100.24/291.58 first(0, X) -> nil [1] 1100.24/291.58 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1] 1100.24/291.58 half(0) -> 0 [1] 1100.24/291.58 half(s(0)) -> 0 [1] 1100.24/291.58 half(s(s(X))) -> s(half(X)) [1] 1100.24/291.58 terms(X) -> n__terms(X) [1] 1100.24/291.58 first(X1, X2) -> n__first(X1, X2) [1] 1100.24/291.58 activate(n__terms(X)) -> terms(X) [1] 1100.24/291.58 activate(n__first(X1, X2)) -> first(X1, X2) [1] 1100.24/291.58 activate(X) -> X [1] 1100.24/291.58 1100.24/291.58 The TRS has the following type information: 1100.24/291.58 terms :: s:0 -> n__terms:cons:nil:n__first 1100.24/291.58 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 recip :: s:0 -> recip 1100.24/291.58 sqr :: s:0 -> s:0 1100.24/291.58 n__terms :: s:0 -> n__terms:cons:nil:n__first 1100.24/291.58 s :: s:0 -> s:0 1100.24/291.58 0 :: s:0 1100.24/291.58 add :: s:0 -> s:0 -> s:0 1100.24/291.58 dbl :: s:0 -> s:0 1100.24/291.58 first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 nil :: n__terms:cons:nil:n__first 1100.24/291.58 n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 half :: s:0 -> s:0 1100.24/291.58 const :: recip 1100.24/291.58 1100.24/291.58 Rewrite Strategy: INNERMOST 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (11) NarrowingProof (BOTH BOUNDS(ID, ID)) 1100.24/291.58 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (12) 1100.24/291.58 Obligation: 1100.24/291.58 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1100.24/291.58 1100.24/291.58 Runtime Complexity Weighted TRS with Types. 1100.24/291.58 The TRS R consists of the following rules: 1100.24/291.58 1100.24/291.58 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1] 1100.24/291.58 sqr(0) -> 0 [1] 1100.24/291.58 sqr(s(0)) -> s(add(0, 0)) [3] 1100.24/291.58 sqr(s(s(X'))) -> s(add(s(add(sqr(X'), dbl(X'))), s(s(dbl(X'))))) [3] 1100.24/291.58 dbl(0) -> 0 [1] 1100.24/291.58 dbl(s(X)) -> s(s(dbl(X))) [1] 1100.24/291.58 add(0, X) -> X [1] 1100.24/291.58 add(s(X), Y) -> s(add(X, Y)) [1] 1100.24/291.58 first(0, X) -> nil [1] 1100.24/291.58 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1] 1100.24/291.58 half(0) -> 0 [1] 1100.24/291.58 half(s(0)) -> 0 [1] 1100.24/291.58 half(s(s(X))) -> s(half(X)) [1] 1100.24/291.58 terms(X) -> n__terms(X) [1] 1100.24/291.58 first(X1, X2) -> n__first(X1, X2) [1] 1100.24/291.58 activate(n__terms(X)) -> terms(X) [1] 1100.24/291.58 activate(n__first(X1, X2)) -> first(X1, X2) [1] 1100.24/291.58 activate(X) -> X [1] 1100.24/291.58 1100.24/291.58 The TRS has the following type information: 1100.24/291.58 terms :: s:0 -> n__terms:cons:nil:n__first 1100.24/291.58 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 recip :: s:0 -> recip 1100.24/291.58 sqr :: s:0 -> s:0 1100.24/291.58 n__terms :: s:0 -> n__terms:cons:nil:n__first 1100.24/291.58 s :: s:0 -> s:0 1100.24/291.58 0 :: s:0 1100.24/291.58 add :: s:0 -> s:0 -> s:0 1100.24/291.58 dbl :: s:0 -> s:0 1100.24/291.58 first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 nil :: n__terms:cons:nil:n__first 1100.24/291.58 n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.24/291.58 half :: s:0 -> s:0 1100.24/291.58 const :: recip 1100.24/291.58 1100.24/291.58 Rewrite Strategy: INNERMOST 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1100.24/291.58 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1100.24/291.58 The constant constructors are abstracted as follows: 1100.24/291.58 1100.24/291.58 0 => 0 1100.24/291.58 nil => 0 1100.24/291.58 const => 0 1100.24/291.58 1100.24/291.58 ---------------------------------------- 1100.24/291.58 1100.24/291.58 (14) 1100.24/291.58 Obligation: 1100.24/291.58 Complexity RNTS consisting of the following rules: 1100.24/291.58 1100.24/291.58 activate(z) -{ 1 }-> X :|: X >= 0, z = X 1100.24/291.58 activate(z) -{ 1 }-> terms(X) :|: z = 1 + X, X >= 0 1100.24/291.58 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.24/291.58 add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0 1100.24/291.58 add(z, z') -{ 1 }-> 1 + add(X, Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 1100.24/291.58 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.24/291.58 dbl(z) -{ 1 }-> 1 + (1 + dbl(X)) :|: z = 1 + X, X >= 0 1100.24/291.58 first(z, z') -{ 1 }-> 0 :|: z' = X, X >= 0, z = 0 1100.24/291.58 first(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 1100.24/291.58 first(z, z') -{ 1 }-> 1 + Y + (1 + X + activate(Z)) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z 1100.24/291.58 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.58 half(z) -{ 1 }-> 1 + half(X) :|: z = 1 + (1 + X), X >= 0 1100.26/291.58 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(X'), dbl(X')), 1 + (1 + dbl(X'))) :|: X' >= 0, z = 1 + (1 + X') 1100.26/291.58 terms(z) -{ 1 }-> 1 + X :|: X >= 0, z = X 1100.26/291.58 terms(z) -{ 1 }-> 1 + (1 + sqr(N)) + (1 + (1 + N)) :|: z = N, N >= 0 1100.26/291.58 1100.26/291.58 1100.26/291.58 ---------------------------------------- 1100.26/291.58 1100.26/291.58 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 1100.26/291.58 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1100.26/291.58 ---------------------------------------- 1100.26/291.58 1100.26/291.58 (16) 1100.26/291.58 Obligation: 1100.26/291.58 Complexity RNTS consisting of the following rules: 1100.26/291.58 1100.26/291.58 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.58 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.58 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.58 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.58 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.58 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1100.26/291.58 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.58 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.58 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.58 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.58 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.58 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1100.26/291.58 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.58 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.58 1100.26/291.58 1100.26/291.58 ---------------------------------------- 1100.26/291.58 1100.26/291.58 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1100.26/291.58 Found the following analysis order by SCC decomposition: 1100.26/291.58 1100.26/291.58 { dbl } 1100.26/291.58 { add } 1100.26/291.58 { half } 1100.26/291.58 { sqr } 1100.26/291.58 { terms } 1100.26/291.58 { first, activate } 1100.26/291.58 1100.26/291.58 ---------------------------------------- 1100.26/291.58 1100.26/291.58 (18) 1100.26/291.58 Obligation: 1100.26/291.58 Complexity RNTS consisting of the following rules: 1100.26/291.58 1100.26/291.58 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.58 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.58 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.58 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.58 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.58 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1100.26/291.58 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.58 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.58 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.58 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.58 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.58 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.58 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1100.26/291.58 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.58 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.58 1100.26/291.58 Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (19) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (20) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (21) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using CoFloCo for: dbl 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: 2*z 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (22) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: ?, size: O(n^1) [2*z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (23) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using CoFloCo for: dbl 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: 1 + z 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (24) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (25) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (26) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (27) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using CoFloCo for: add 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: z + z' 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (28) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: ?, size: O(n^1) [z + z'] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (29) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using CoFloCo for: add 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: 1 + z 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (30) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (31) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (32) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (33) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using KoAT for: half 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: z 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (34) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {half}, {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: ?, size: O(n^1) [z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (35) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using CoFloCo for: half 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^1) with polynomial bound: 2 + z 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (36) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (37) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (38) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (39) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using KoAT for: sqr 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^2) with polynomial bound: 1 + 4*z + 4*z^2 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (40) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {sqr}, {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: ?, size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (41) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using KoAT for: sqr 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^3) with polynomial bound: 5 + 22*z + 8*z^3 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (42) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (43) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (44) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (45) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using KoAT for: terms 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^2) with polynomial bound: 6 + 6*z + 4*z^2 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (46) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {terms}, {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 terms: runtime: ?, size: O(n^2) [6 + 6*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (47) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using KoAT for: terms 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^3) with polynomial bound: 7 + 22*z + 8*z^3 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (48) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (49) ResultPropagationProof (UPPER BOUND(ID)) 1100.26/291.59 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (50) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s8 :|: s8 >= 0, s8 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2] 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (51) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed SIZE bound using CoFloCo for: first 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: INF with polynomial bound: ? 1100.26/291.59 1100.26/291.59 Computed SIZE bound using CoFloCo for: activate 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: INF with polynomial bound: ? 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (52) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s8 :|: s8 >= 0, s8 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: {first,activate} 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2] 1100.26/291.59 first: runtime: ?, size: INF 1100.26/291.59 activate: runtime: ?, size: INF 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (53) IntTrsBoundProof (UPPER BOUND(ID)) 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using KoAT for: first 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^3) with polynomial bound: 3 + 48*z' + 8*z'^3 1100.26/291.59 1100.26/291.59 Computed RUNTIME bound using KoAT for: activate 1100.26/291.59 after applying outer abstraction to obtain an ITS, 1100.26/291.59 resulting in: O(n^3) with polynomial bound: 5 + 94*z + 16*z^3 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (54) 1100.26/291.59 Obligation: 1100.26/291.59 Complexity RNTS consisting of the following rules: 1100.26/291.59 1100.26/291.59 activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s8 :|: s8 >= 0, s8 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0 1100.26/291.59 activate(z) -{ 1 }-> z :|: z >= 0 1100.26/291.59 activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 1100.26/291.59 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1100.26/291.59 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1100.26/291.59 dbl(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1100.26/291.59 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1100.26/291.59 first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z 1100.26/291.59 first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1100.26/291.59 half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0 1100.26/291.59 sqr(z) -{ 1 }-> 0 :|: z = 0 1100.26/291.59 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1100.26/291.59 sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1100.26/291.59 terms(z) -{ 1 }-> 1 + z :|: z >= 0 1100.26/291.59 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) + (1 + (1 + z)) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0 1100.26/291.59 1100.26/291.59 Function symbols to be analyzed: 1100.26/291.59 Previous analysis results are: 1100.26/291.59 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1100.26/291.59 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1100.26/291.59 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 1100.26/291.59 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1100.26/291.59 terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2] 1100.26/291.59 first: runtime: O(n^3) [3 + 48*z' + 8*z'^3], size: INF 1100.26/291.59 activate: runtime: O(n^3) [5 + 94*z + 16*z^3], size: INF 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (55) FinalProof (FINISHED) 1100.26/291.59 Computed overall runtime complexity 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (56) 1100.26/291.59 BOUNDS(1, n^3) 1100.26/291.59 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (57) RenamingProof (BOTH BOUNDS(ID, ID)) 1100.26/291.59 Renamed function symbols to avoid clashes with predefined symbol. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (58) 1100.26/291.59 Obligation: 1100.26/291.59 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 1100.26/291.59 1100.26/291.59 1100.26/291.59 The TRS R consists of the following rules: 1100.26/291.59 1100.26/291.59 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.26/291.59 sqr(0') -> 0' 1100.26/291.59 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.26/291.59 dbl(0') -> 0' 1100.26/291.59 dbl(s(X)) -> s(s(dbl(X))) 1100.26/291.59 add(0', X) -> X 1100.26/291.59 add(s(X), Y) -> s(add(X, Y)) 1100.26/291.59 first(0', X) -> nil 1100.26/291.59 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.26/291.59 half(0') -> 0' 1100.26/291.59 half(s(0')) -> 0' 1100.26/291.59 half(s(s(X))) -> s(half(X)) 1100.26/291.59 half(dbl(X)) -> X 1100.26/291.59 terms(X) -> n__terms(X) 1100.26/291.59 first(X1, X2) -> n__first(X1, X2) 1100.26/291.59 activate(n__terms(X)) -> terms(X) 1100.26/291.59 activate(n__first(X1, X2)) -> first(X1, X2) 1100.26/291.59 activate(X) -> X 1100.26/291.59 1100.26/291.59 S is empty. 1100.26/291.59 Rewrite Strategy: FULL 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (59) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1100.26/291.59 Infered types. 1100.26/291.59 ---------------------------------------- 1100.26/291.59 1100.26/291.59 (60) 1100.26/291.59 Obligation: 1100.26/291.59 TRS: 1100.26/291.59 Rules: 1100.26/291.59 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (61) OrderProof (LOWER BOUND(ID)) 1100.33/291.61 Heuristically decided to analyse the following defined symbols: 1100.33/291.61 sqr, add, dbl, activate, half 1100.33/291.61 1100.33/291.61 They will be analysed ascendingly in the following order: 1100.33/291.61 add < sqr 1100.33/291.61 dbl < sqr 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (62) 1100.33/291.61 Obligation: 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 add, sqr, dbl, activate, half 1100.33/291.61 1100.33/291.61 They will be analysed ascendingly in the following order: 1100.33/291.61 add < sqr 1100.33/291.61 dbl < sqr 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (63) RewriteLemmaProof (LOWER BOUND(ID)) 1100.33/291.61 Proved the following rewrite lemma: 1100.33/291.61 add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1100.33/291.61 1100.33/291.61 Induction Base: 1100.33/291.61 add(gen_s:0'5_0(0), gen_s:0'5_0(b)) ->_R^Omega(1) 1100.33/291.61 gen_s:0'5_0(b) 1100.33/291.61 1100.33/291.61 Induction Step: 1100.33/291.61 add(gen_s:0'5_0(+(n7_0, 1)), gen_s:0'5_0(b)) ->_R^Omega(1) 1100.33/291.61 s(add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b))) ->_IH 1100.33/291.61 s(gen_s:0'5_0(+(b, c8_0))) 1100.33/291.61 1100.33/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (64) 1100.33/291.61 Complex Obligation (BEST) 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (65) 1100.33/291.61 Obligation: 1100.33/291.61 Proved the lower bound n^1 for the following obligation: 1100.33/291.61 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 add, sqr, dbl, activate, half 1100.33/291.61 1100.33/291.61 They will be analysed ascendingly in the following order: 1100.33/291.61 add < sqr 1100.33/291.61 dbl < sqr 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (66) LowerBoundPropagationProof (FINISHED) 1100.33/291.61 Propagated lower bound. 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (67) 1100.33/291.61 BOUNDS(n^1, INF) 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (68) 1100.33/291.61 Obligation: 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Lemmas: 1100.33/291.61 add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 dbl, sqr, activate, half 1100.33/291.61 1100.33/291.61 They will be analysed ascendingly in the following order: 1100.33/291.61 dbl < sqr 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (69) RewriteLemmaProof (LOWER BOUND(ID)) 1100.33/291.61 Proved the following rewrite lemma: 1100.33/291.61 dbl(gen_s:0'5_0(n860_0)) -> gen_s:0'5_0(*(2, n860_0)), rt in Omega(1 + n860_0) 1100.33/291.61 1100.33/291.61 Induction Base: 1100.33/291.61 dbl(gen_s:0'5_0(0)) ->_R^Omega(1) 1100.33/291.61 0' 1100.33/291.61 1100.33/291.61 Induction Step: 1100.33/291.61 dbl(gen_s:0'5_0(+(n860_0, 1))) ->_R^Omega(1) 1100.33/291.61 s(s(dbl(gen_s:0'5_0(n860_0)))) ->_IH 1100.33/291.61 s(s(gen_s:0'5_0(*(2, c861_0)))) 1100.33/291.61 1100.33/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (70) 1100.33/291.61 Obligation: 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Lemmas: 1100.33/291.61 add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1100.33/291.61 dbl(gen_s:0'5_0(n860_0)) -> gen_s:0'5_0(*(2, n860_0)), rt in Omega(1 + n860_0) 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 sqr, activate, half 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (71) RewriteLemmaProof (LOWER BOUND(ID)) 1100.33/291.61 Proved the following rewrite lemma: 1100.33/291.61 sqr(gen_s:0'5_0(n1182_0)) -> gen_s:0'5_0(*(n1182_0, n1182_0)), rt in Omega(1 + n1182_0 + n1182_0^2 + n1182_0^3) 1100.33/291.61 1100.33/291.61 Induction Base: 1100.33/291.61 sqr(gen_s:0'5_0(0)) ->_R^Omega(1) 1100.33/291.61 0' 1100.33/291.61 1100.33/291.61 Induction Step: 1100.33/291.61 sqr(gen_s:0'5_0(+(n1182_0, 1))) ->_R^Omega(1) 1100.33/291.61 s(add(sqr(gen_s:0'5_0(n1182_0)), dbl(gen_s:0'5_0(n1182_0)))) ->_IH 1100.33/291.61 s(add(gen_s:0'5_0(*(c1183_0, c1183_0)), dbl(gen_s:0'5_0(n1182_0)))) ->_L^Omega(1 + n1182_0) 1100.33/291.61 s(add(gen_s:0'5_0(*(n1182_0, n1182_0)), gen_s:0'5_0(*(2, n1182_0)))) ->_L^Omega(1 + n1182_0^2) 1100.33/291.61 s(gen_s:0'5_0(+(*(n1182_0, n1182_0), *(2, n1182_0)))) 1100.33/291.61 1100.33/291.61 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (72) 1100.33/291.61 Complex Obligation (BEST) 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (73) 1100.33/291.61 Obligation: 1100.33/291.61 Proved the lower bound n^3 for the following obligation: 1100.33/291.61 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Lemmas: 1100.33/291.61 add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1100.33/291.61 dbl(gen_s:0'5_0(n860_0)) -> gen_s:0'5_0(*(2, n860_0)), rt in Omega(1 + n860_0) 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 sqr, activate, half 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (74) LowerBoundPropagationProof (FINISHED) 1100.33/291.61 Propagated lower bound. 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (75) 1100.33/291.61 BOUNDS(n^3, INF) 1100.33/291.61 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (76) 1100.33/291.61 Obligation: 1100.33/291.61 TRS: 1100.33/291.61 Rules: 1100.33/291.61 terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) 1100.33/291.61 sqr(0') -> 0' 1100.33/291.61 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1100.33/291.61 dbl(0') -> 0' 1100.33/291.61 dbl(s(X)) -> s(s(dbl(X))) 1100.33/291.61 add(0', X) -> X 1100.33/291.61 add(s(X), Y) -> s(add(X, Y)) 1100.33/291.61 first(0', X) -> nil 1100.33/291.61 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 1100.33/291.61 half(0') -> 0' 1100.33/291.61 half(s(0')) -> 0' 1100.33/291.61 half(s(s(X))) -> s(half(X)) 1100.33/291.61 half(dbl(X)) -> X 1100.33/291.61 terms(X) -> n__terms(X) 1100.33/291.61 first(X1, X2) -> n__first(X1, X2) 1100.33/291.61 activate(n__terms(X)) -> terms(X) 1100.33/291.61 activate(n__first(X1, X2)) -> first(X1, X2) 1100.33/291.61 activate(X) -> X 1100.33/291.61 1100.33/291.61 Types: 1100.33/291.61 terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 recip :: s:0' -> recip 1100.33/291.61 sqr :: s:0' -> s:0' 1100.33/291.61 n__terms :: s:0' -> n__terms:cons:nil:n__first 1100.33/291.61 s :: s:0' -> s:0' 1100.33/291.61 0' :: s:0' 1100.33/291.61 add :: s:0' -> s:0' -> s:0' 1100.33/291.61 dbl :: s:0' -> s:0' 1100.33/291.61 first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 nil :: n__terms:cons:nil:n__first 1100.33/291.61 n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first 1100.33/291.61 half :: s:0' -> s:0' 1100.33/291.61 hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first 1100.33/291.61 hole_s:0'2_0 :: s:0' 1100.33/291.61 hole_recip3_0 :: recip 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first 1100.33/291.61 gen_s:0'5_0 :: Nat -> s:0' 1100.33/291.61 1100.33/291.61 1100.33/291.61 Lemmas: 1100.33/291.61 add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1100.33/291.61 dbl(gen_s:0'5_0(n860_0)) -> gen_s:0'5_0(*(2, n860_0)), rt in Omega(1 + n860_0) 1100.33/291.61 sqr(gen_s:0'5_0(n1182_0)) -> gen_s:0'5_0(*(n1182_0, n1182_0)), rt in Omega(1 + n1182_0 + n1182_0^2 + n1182_0^3) 1100.33/291.61 1100.33/291.61 1100.33/291.61 Generator Equations: 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0') 1100.33/291.61 gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x)) 1100.33/291.61 gen_s:0'5_0(0) <=> 0' 1100.33/291.61 gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x)) 1100.33/291.61 1100.33/291.61 1100.33/291.61 The following defined symbols remain to be analysed: 1100.33/291.61 activate, half 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (77) RewriteLemmaProof (LOWER BOUND(ID)) 1100.33/291.61 Proved the following rewrite lemma: 1100.33/291.61 half(gen_s:0'5_0(*(2, n1601_0))) -> gen_s:0'5_0(n1601_0), rt in Omega(1 + n1601_0) 1100.33/291.61 1100.33/291.61 Induction Base: 1100.33/291.61 half(gen_s:0'5_0(*(2, 0))) ->_R^Omega(1) 1100.33/291.61 0' 1100.33/291.61 1100.33/291.61 Induction Step: 1100.33/291.61 half(gen_s:0'5_0(*(2, +(n1601_0, 1)))) ->_R^Omega(1) 1100.33/291.61 s(half(gen_s:0'5_0(*(2, n1601_0)))) ->_IH 1100.33/291.61 s(gen_s:0'5_0(c1602_0)) 1100.33/291.61 1100.33/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1100.33/291.61 ---------------------------------------- 1100.33/291.61 1100.33/291.61 (78) 1100.33/291.61 BOUNDS(1, INF) 1100.43/291.69 EOF