1034.51/291.45 WORST_CASE(Omega(n^3), O(n^3)) 1034.83/291.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1034.83/291.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1034.83/291.48 1034.83/291.48 1034.83/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 1034.83/291.48 1034.83/291.48 (0) CpxTRS 1034.83/291.48 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (2) CpxTRS 1034.83/291.48 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (4) CpxWeightedTrs 1034.83/291.48 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (6) CpxTypedWeightedTrs 1034.83/291.48 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (8) CpxTypedWeightedCompleteTrs 1034.83/291.48 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (10) CpxTypedWeightedCompleteTrs 1034.83/291.48 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (12) CpxRNTS 1034.83/291.48 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (14) CpxRNTS 1034.83/291.48 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (16) CpxRNTS 1034.83/291.48 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (18) CpxRNTS 1034.83/291.48 (19) IntTrsBoundProof [UPPER BOUND(ID), 182 ms] 1034.83/291.48 (20) CpxRNTS 1034.83/291.48 (21) IntTrsBoundProof [UPPER BOUND(ID), 67 ms] 1034.83/291.48 (22) CpxRNTS 1034.83/291.48 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (24) CpxRNTS 1034.83/291.48 (25) IntTrsBoundProof [UPPER BOUND(ID), 215 ms] 1034.83/291.48 (26) CpxRNTS 1034.83/291.48 (27) IntTrsBoundProof [UPPER BOUND(ID), 105 ms] 1034.83/291.48 (28) CpxRNTS 1034.83/291.48 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (30) CpxRNTS 1034.83/291.48 (31) IntTrsBoundProof [UPPER BOUND(ID), 342 ms] 1034.83/291.48 (32) CpxRNTS 1034.83/291.48 (33) IntTrsBoundProof [UPPER BOUND(ID), 125 ms] 1034.83/291.48 (34) CpxRNTS 1034.83/291.48 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (36) CpxRNTS 1034.83/291.48 (37) IntTrsBoundProof [UPPER BOUND(ID), 564 ms] 1034.83/291.48 (38) CpxRNTS 1034.83/291.48 (39) IntTrsBoundProof [UPPER BOUND(ID), 84 ms] 1034.83/291.48 (40) CpxRNTS 1034.83/291.48 (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (42) CpxRNTS 1034.83/291.48 (43) IntTrsBoundProof [UPPER BOUND(ID), 587 ms] 1034.83/291.48 (44) CpxRNTS 1034.83/291.48 (45) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 1034.83/291.48 (46) CpxRNTS 1034.83/291.48 (47) FinalProof [FINISHED, 0 ms] 1034.83/291.48 (48) BOUNDS(1, n^3) 1034.83/291.48 (49) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (50) CpxTRS 1034.83/291.48 (51) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1034.83/291.48 (52) typed CpxTrs 1034.83/291.48 (53) OrderProof [LOWER BOUND(ID), 0 ms] 1034.83/291.48 (54) typed CpxTrs 1034.83/291.48 (55) RewriteLemmaProof [LOWER BOUND(ID), 256 ms] 1034.83/291.48 (56) BEST 1034.83/291.48 (57) proven lower bound 1034.83/291.48 (58) LowerBoundPropagationProof [FINISHED, 0 ms] 1034.83/291.48 (59) BOUNDS(n^1, INF) 1034.83/291.48 (60) typed CpxTrs 1034.83/291.48 (61) RewriteLemmaProof [LOWER BOUND(ID), 123 ms] 1034.83/291.48 (62) typed CpxTrs 1034.83/291.48 (63) RewriteLemmaProof [LOWER BOUND(ID), 153 ms] 1034.83/291.48 (64) proven lower bound 1034.83/291.48 (65) LowerBoundPropagationProof [FINISHED, 0 ms] 1034.83/291.48 (66) BOUNDS(n^3, INF) 1034.83/291.48 1034.83/291.48 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (0) 1034.83/291.48 Obligation: 1034.83/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 1034.83/291.48 1034.83/291.48 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) 1034.83/291.48 sqr(0) -> 0 1034.83/291.48 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1034.83/291.48 dbl(0) -> 0 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) 1034.83/291.48 add(0, X) -> X 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) 1034.83/291.48 first(0, X) -> nil 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) 1034.83/291.48 1034.83/291.48 S is empty. 1034.83/291.48 Rewrite Strategy: FULL 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 1034.83/291.48 Converted rc-obligation to irc-obligation. 1034.83/291.48 1034.83/291.48 The duplicating contexts are: 1034.83/291.48 sqr(s([])) 1034.83/291.48 1034.83/291.48 1034.83/291.48 The defined contexts are: 1034.83/291.48 add([], x1) 1034.83/291.48 add(x0, []) 1034.83/291.48 1034.83/291.48 1034.83/291.48 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (2) 1034.83/291.48 Obligation: 1034.83/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 1034.83/291.48 1034.83/291.48 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) 1034.83/291.48 sqr(0) -> 0 1034.83/291.48 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1034.83/291.48 dbl(0) -> 0 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) 1034.83/291.48 add(0, X) -> X 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) 1034.83/291.48 first(0, X) -> nil 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) 1034.83/291.48 1034.83/291.48 S is empty. 1034.83/291.48 Rewrite Strategy: INNERMOST 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1034.83/291.48 Transformed relative TRS to weighted TRS 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (4) 1034.83/291.48 Obligation: 1034.83/291.48 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 1034.83/291.48 1034.83/291.48 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) [1] 1034.83/291.48 sqr(0) -> 0 [1] 1034.83/291.48 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1034.83/291.48 dbl(0) -> 0 [1] 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) [1] 1034.83/291.48 add(0, X) -> X [1] 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) [1] 1034.83/291.48 first(0, X) -> nil [1] 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) [1] 1034.83/291.48 1034.83/291.48 Rewrite Strategy: INNERMOST 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1034.83/291.48 Infered types. 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (6) 1034.83/291.48 Obligation: 1034.83/291.48 Runtime Complexity Weighted TRS with Types. 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) [1] 1034.83/291.48 sqr(0) -> 0 [1] 1034.83/291.48 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1034.83/291.48 dbl(0) -> 0 [1] 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) [1] 1034.83/291.48 add(0, X) -> X [1] 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) [1] 1034.83/291.48 first(0, X) -> nil [1] 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) [1] 1034.83/291.48 1034.83/291.48 The TRS has the following type information: 1034.83/291.48 terms :: 0:s -> cons:nil 1034.83/291.48 cons :: recip -> cons:nil 1034.83/291.48 recip :: 0:s -> recip 1034.83/291.48 sqr :: 0:s -> 0:s 1034.83/291.48 0 :: 0:s 1034.83/291.48 s :: 0:s -> 0:s 1034.83/291.48 add :: 0:s -> 0:s -> 0:s 1034.83/291.48 dbl :: 0:s -> 0:s 1034.83/291.48 first :: 0:s -> cons:nil -> cons:nil 1034.83/291.48 nil :: cons:nil 1034.83/291.48 1034.83/291.48 Rewrite Strategy: INNERMOST 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (7) CompletionProof (UPPER BOUND(ID)) 1034.83/291.48 The transformation into a RNTS is sound, since: 1034.83/291.48 1034.83/291.48 (a) The obligation is a constructor system where every type has a constant constructor, 1034.83/291.48 1034.83/291.48 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1034.83/291.48 1034.83/291.48 terms_1 1034.83/291.48 first_2 1034.83/291.48 1034.83/291.48 (c) The following functions are completely defined: 1034.83/291.48 1034.83/291.48 sqr_1 1034.83/291.48 dbl_1 1034.83/291.48 add_2 1034.83/291.48 1034.83/291.48 Due to the following rules being added: 1034.83/291.48 none 1034.83/291.48 1034.83/291.48 And the following fresh constants: const 1034.83/291.48 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (8) 1034.83/291.48 Obligation: 1034.83/291.48 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1034.83/291.48 1034.83/291.48 Runtime Complexity Weighted TRS with Types. 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) [1] 1034.83/291.48 sqr(0) -> 0 [1] 1034.83/291.48 sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1] 1034.83/291.48 dbl(0) -> 0 [1] 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) [1] 1034.83/291.48 add(0, X) -> X [1] 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) [1] 1034.83/291.48 first(0, X) -> nil [1] 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) [1] 1034.83/291.48 1034.83/291.48 The TRS has the following type information: 1034.83/291.48 terms :: 0:s -> cons:nil 1034.83/291.48 cons :: recip -> cons:nil 1034.83/291.48 recip :: 0:s -> recip 1034.83/291.48 sqr :: 0:s -> 0:s 1034.83/291.48 0 :: 0:s 1034.83/291.48 s :: 0:s -> 0:s 1034.83/291.48 add :: 0:s -> 0:s -> 0:s 1034.83/291.48 dbl :: 0:s -> 0:s 1034.83/291.48 first :: 0:s -> cons:nil -> cons:nil 1034.83/291.48 nil :: cons:nil 1034.83/291.48 const :: recip 1034.83/291.48 1034.83/291.48 Rewrite Strategy: INNERMOST 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 1034.83/291.48 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (10) 1034.83/291.48 Obligation: 1034.83/291.48 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1034.83/291.48 1034.83/291.48 Runtime Complexity Weighted TRS with Types. 1034.83/291.48 The TRS R consists of the following rules: 1034.83/291.48 1034.83/291.48 terms(N) -> cons(recip(sqr(N))) [1] 1034.83/291.48 sqr(0) -> 0 [1] 1034.83/291.48 sqr(s(0)) -> s(add(0, 0)) [3] 1034.83/291.48 sqr(s(s(X'))) -> s(add(s(add(sqr(X'), dbl(X'))), s(s(dbl(X'))))) [3] 1034.83/291.48 dbl(0) -> 0 [1] 1034.83/291.48 dbl(s(X)) -> s(s(dbl(X))) [1] 1034.83/291.48 add(0, X) -> X [1] 1034.83/291.48 add(s(X), Y) -> s(add(X, Y)) [1] 1034.83/291.48 first(0, X) -> nil [1] 1034.83/291.48 first(s(X), cons(Y)) -> cons(Y) [1] 1034.83/291.48 1034.83/291.48 The TRS has the following type information: 1034.83/291.48 terms :: 0:s -> cons:nil 1034.83/291.48 cons :: recip -> cons:nil 1034.83/291.48 recip :: 0:s -> recip 1034.83/291.48 sqr :: 0:s -> 0:s 1034.83/291.48 0 :: 0:s 1034.83/291.48 s :: 0:s -> 0:s 1034.83/291.48 add :: 0:s -> 0:s -> 0:s 1034.83/291.48 dbl :: 0:s -> 0:s 1034.83/291.48 first :: 0:s -> cons:nil -> cons:nil 1034.83/291.48 nil :: cons:nil 1034.83/291.48 const :: recip 1034.83/291.48 1034.83/291.48 Rewrite Strategy: INNERMOST 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1034.83/291.48 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1034.83/291.48 The constant constructors are abstracted as follows: 1034.83/291.48 1034.83/291.48 0 => 0 1034.83/291.48 nil => 0 1034.83/291.48 const => 0 1034.83/291.48 1034.83/291.48 ---------------------------------------- 1034.83/291.48 1034.83/291.48 (12) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(X, Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(X)) :|: z = 1 + X, X >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' = X, X >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + Y :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(X'), dbl(X')), 1 + (1 + dbl(X'))) :|: X' >= 0, z = 1 + (1 + X') 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(N)) :|: z = N, N >= 0 1034.83/291.49 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 1034.83/291.49 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (14) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1034.83/291.49 Found the following analysis order by SCC decomposition: 1034.83/291.49 1034.83/291.49 { first } 1034.83/291.49 { dbl } 1034.83/291.49 { add } 1034.83/291.49 { sqr } 1034.83/291.49 { terms } 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (16) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {first}, {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (17) ResultPropagationProof (UPPER BOUND(ID)) 1034.83/291.49 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (18) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {first}, {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (19) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed SIZE bound using CoFloCo for: first 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^1) with polynomial bound: z' 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (20) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {first}, {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: ?, size: O(n^1) [z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (21) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed RUNTIME bound using CoFloCo for: first 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(1) with polynomial bound: 1 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (22) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (23) ResultPropagationProof (UPPER BOUND(ID)) 1034.83/291.49 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (24) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (25) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed SIZE bound using CoFloCo for: dbl 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^1) with polynomial bound: 2*z 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (26) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: ?, size: O(n^1) [2*z] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (27) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed RUNTIME bound using CoFloCo for: dbl 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^1) with polynomial bound: 1 + z 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (28) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (29) ResultPropagationProof (UPPER BOUND(ID)) 1034.83/291.49 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (30) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (31) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed SIZE bound using CoFloCo for: add 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^1) with polynomial bound: z + z' 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (32) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {add}, {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 add: runtime: ?, size: O(n^1) [z + z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (33) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed RUNTIME bound using CoFloCo for: add 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^1) with polynomial bound: 1 + z 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (34) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (35) ResultPropagationProof (UPPER BOUND(ID)) 1034.83/291.49 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (36) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (37) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed SIZE bound using KoAT for: sqr 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^2) with polynomial bound: 1 + 4*z + 4*z^2 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (38) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {sqr}, {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1034.83/291.49 sqr: runtime: ?, size: O(n^2) [1 + 4*z + 4*z^2] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (39) IntTrsBoundProof (UPPER BOUND(ID)) 1034.83/291.49 1034.83/291.49 Computed RUNTIME bound using KoAT for: sqr 1034.83/291.49 after applying outer abstraction to obtain an ITS, 1034.83/291.49 resulting in: O(n^3) with polynomial bound: 5 + 22*z + 8*z^3 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (40) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1034.83/291.49 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 1034.83/291.49 terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0 1034.83/291.49 1034.83/291.49 Function symbols to be analyzed: {terms} 1034.83/291.49 Previous analysis results are: 1034.83/291.49 first: runtime: O(1) [1], size: O(n^1) [z'] 1034.83/291.49 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1034.83/291.49 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1034.83/291.49 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1034.83/291.49 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (41) ResultPropagationProof (UPPER BOUND(ID)) 1034.83/291.49 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1034.83/291.49 ---------------------------------------- 1034.83/291.49 1034.83/291.49 (42) 1034.83/291.49 Obligation: 1034.83/291.49 Complexity RNTS consisting of the following rules: 1034.83/291.49 1034.83/291.49 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1034.83/291.49 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1034.83/291.49 dbl(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1034.83/291.49 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1034.83/291.49 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1034.83/291.49 sqr(z) -{ 1 }-> 0 :|: z = 0 1034.83/291.49 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1034.83/291.49 sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1035.00/291.50 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0 1035.00/291.50 1035.00/291.50 Function symbols to be analyzed: {terms} 1035.00/291.50 Previous analysis results are: 1035.00/291.50 first: runtime: O(1) [1], size: O(n^1) [z'] 1035.00/291.50 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1035.00/291.50 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1035.00/291.50 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (43) IntTrsBoundProof (UPPER BOUND(ID)) 1035.00/291.50 1035.00/291.50 Computed SIZE bound using KoAT for: terms 1035.00/291.50 after applying outer abstraction to obtain an ITS, 1035.00/291.50 resulting in: O(n^2) with polynomial bound: 3 + 4*z + 4*z^2 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (44) 1035.00/291.50 Obligation: 1035.00/291.50 Complexity RNTS consisting of the following rules: 1035.00/291.50 1035.00/291.50 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1035.00/291.50 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1035.00/291.50 dbl(z) -{ 1 }-> 0 :|: z = 0 1035.00/291.50 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1035.00/291.50 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1035.00/291.50 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1035.00/291.50 sqr(z) -{ 1 }-> 0 :|: z = 0 1035.00/291.50 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1035.00/291.50 sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1035.00/291.50 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0 1035.00/291.50 1035.00/291.50 Function symbols to be analyzed: {terms} 1035.00/291.50 Previous analysis results are: 1035.00/291.50 first: runtime: O(1) [1], size: O(n^1) [z'] 1035.00/291.50 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1035.00/291.50 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1035.00/291.50 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1035.00/291.50 terms: runtime: ?, size: O(n^2) [3 + 4*z + 4*z^2] 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (45) IntTrsBoundProof (UPPER BOUND(ID)) 1035.00/291.50 1035.00/291.50 Computed RUNTIME bound using KoAT for: terms 1035.00/291.50 after applying outer abstraction to obtain an ITS, 1035.00/291.50 resulting in: O(n^3) with polynomial bound: 6 + 22*z + 8*z^3 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (46) 1035.00/291.50 Obligation: 1035.00/291.50 Complexity RNTS consisting of the following rules: 1035.00/291.50 1035.00/291.50 add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 1035.00/291.50 add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0 1035.00/291.50 dbl(z) -{ 1 }-> 0 :|: z = 0 1035.00/291.50 dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0 1035.00/291.50 first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 1035.00/291.50 first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0 1035.00/291.50 sqr(z) -{ 1 }-> 0 :|: z = 0 1035.00/291.50 sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0 1035.00/291.50 sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0 1035.00/291.50 terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0 1035.00/291.50 1035.00/291.50 Function symbols to be analyzed: 1035.00/291.50 Previous analysis results are: 1035.00/291.50 first: runtime: O(1) [1], size: O(n^1) [z'] 1035.00/291.50 dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z] 1035.00/291.50 add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z'] 1035.00/291.50 sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2] 1035.00/291.50 terms: runtime: O(n^3) [6 + 22*z + 8*z^3], size: O(n^2) [3 + 4*z + 4*z^2] 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (47) FinalProof (FINISHED) 1035.00/291.50 Computed overall runtime complexity 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (48) 1035.00/291.50 BOUNDS(1, n^3) 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (49) RenamingProof (BOTH BOUNDS(ID, ID)) 1035.00/291.50 Renamed function symbols to avoid clashes with predefined symbol. 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (50) 1035.00/291.50 Obligation: 1035.00/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 1035.00/291.50 1035.00/291.50 1035.00/291.50 The TRS R consists of the following rules: 1035.00/291.50 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 S is empty. 1035.00/291.50 Rewrite Strategy: FULL 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (51) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1035.00/291.50 Infered types. 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (52) 1035.00/291.50 Obligation: 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (53) OrderProof (LOWER BOUND(ID)) 1035.00/291.50 Heuristically decided to analyse the following defined symbols: 1035.00/291.50 sqr, add, dbl 1035.00/291.50 1035.00/291.50 They will be analysed ascendingly in the following order: 1035.00/291.50 add < sqr 1035.00/291.50 dbl < sqr 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (54) 1035.00/291.50 Obligation: 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 1035.00/291.50 Generator Equations: 1035.00/291.50 gen_0':s4_0(0) <=> 0' 1035.00/291.50 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1035.00/291.50 1035.00/291.50 1035.00/291.50 The following defined symbols remain to be analysed: 1035.00/291.50 add, sqr, dbl 1035.00/291.50 1035.00/291.50 They will be analysed ascendingly in the following order: 1035.00/291.50 add < sqr 1035.00/291.50 dbl < sqr 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (55) RewriteLemmaProof (LOWER BOUND(ID)) 1035.00/291.50 Proved the following rewrite lemma: 1035.00/291.50 add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 1035.00/291.50 1035.00/291.50 Induction Base: 1035.00/291.50 add(gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1035.00/291.50 gen_0':s4_0(b) 1035.00/291.50 1035.00/291.50 Induction Step: 1035.00/291.50 add(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1) 1035.00/291.50 s(add(gen_0':s4_0(n6_0), gen_0':s4_0(b))) ->_IH 1035.00/291.50 s(gen_0':s4_0(+(b, c7_0))) 1035.00/291.50 1035.00/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (56) 1035.00/291.50 Complex Obligation (BEST) 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (57) 1035.00/291.50 Obligation: 1035.00/291.50 Proved the lower bound n^1 for the following obligation: 1035.00/291.50 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 1035.00/291.50 Generator Equations: 1035.00/291.50 gen_0':s4_0(0) <=> 0' 1035.00/291.50 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1035.00/291.50 1035.00/291.50 1035.00/291.50 The following defined symbols remain to be analysed: 1035.00/291.50 add, sqr, dbl 1035.00/291.50 1035.00/291.50 They will be analysed ascendingly in the following order: 1035.00/291.50 add < sqr 1035.00/291.50 dbl < sqr 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (58) LowerBoundPropagationProof (FINISHED) 1035.00/291.50 Propagated lower bound. 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (59) 1035.00/291.50 BOUNDS(n^1, INF) 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (60) 1035.00/291.50 Obligation: 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 1035.00/291.50 Lemmas: 1035.00/291.50 add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 1035.00/291.50 1035.00/291.50 1035.00/291.50 Generator Equations: 1035.00/291.50 gen_0':s4_0(0) <=> 0' 1035.00/291.50 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1035.00/291.50 1035.00/291.50 1035.00/291.50 The following defined symbols remain to be analysed: 1035.00/291.50 dbl, sqr 1035.00/291.50 1035.00/291.50 They will be analysed ascendingly in the following order: 1035.00/291.50 dbl < sqr 1035.00/291.50 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (61) RewriteLemmaProof (LOWER BOUND(ID)) 1035.00/291.50 Proved the following rewrite lemma: 1035.00/291.50 dbl(gen_0':s4_0(n495_0)) -> gen_0':s4_0(*(2, n495_0)), rt in Omega(1 + n495_0) 1035.00/291.50 1035.00/291.50 Induction Base: 1035.00/291.50 dbl(gen_0':s4_0(0)) ->_R^Omega(1) 1035.00/291.50 0' 1035.00/291.50 1035.00/291.50 Induction Step: 1035.00/291.50 dbl(gen_0':s4_0(+(n495_0, 1))) ->_R^Omega(1) 1035.00/291.50 s(s(dbl(gen_0':s4_0(n495_0)))) ->_IH 1035.00/291.50 s(s(gen_0':s4_0(*(2, c496_0)))) 1035.00/291.50 1035.00/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (62) 1035.00/291.50 Obligation: 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 1035.00/291.50 Lemmas: 1035.00/291.50 add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 1035.00/291.50 dbl(gen_0':s4_0(n495_0)) -> gen_0':s4_0(*(2, n495_0)), rt in Omega(1 + n495_0) 1035.00/291.50 1035.00/291.50 1035.00/291.50 Generator Equations: 1035.00/291.50 gen_0':s4_0(0) <=> 0' 1035.00/291.50 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1035.00/291.50 1035.00/291.50 1035.00/291.50 The following defined symbols remain to be analysed: 1035.00/291.50 sqr 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (63) RewriteLemmaProof (LOWER BOUND(ID)) 1035.00/291.50 Proved the following rewrite lemma: 1035.00/291.50 sqr(gen_0':s4_0(n739_0)) -> gen_0':s4_0(*(n739_0, n739_0)), rt in Omega(1 + n739_0 + n739_0^2 + n739_0^3) 1035.00/291.50 1035.00/291.50 Induction Base: 1035.00/291.50 sqr(gen_0':s4_0(0)) ->_R^Omega(1) 1035.00/291.50 0' 1035.00/291.50 1035.00/291.50 Induction Step: 1035.00/291.50 sqr(gen_0':s4_0(+(n739_0, 1))) ->_R^Omega(1) 1035.00/291.50 s(add(sqr(gen_0':s4_0(n739_0)), dbl(gen_0':s4_0(n739_0)))) ->_IH 1035.00/291.50 s(add(gen_0':s4_0(*(c740_0, c740_0)), dbl(gen_0':s4_0(n739_0)))) ->_L^Omega(1 + n739_0) 1035.00/291.50 s(add(gen_0':s4_0(*(n739_0, n739_0)), gen_0':s4_0(*(2, n739_0)))) ->_L^Omega(1 + n739_0^2) 1035.00/291.50 s(gen_0':s4_0(+(*(n739_0, n739_0), *(2, n739_0)))) 1035.00/291.50 1035.00/291.50 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (64) 1035.00/291.50 Obligation: 1035.00/291.50 Proved the lower bound n^3 for the following obligation: 1035.00/291.50 1035.00/291.50 TRS: 1035.00/291.50 Rules: 1035.00/291.50 terms(N) -> cons(recip(sqr(N))) 1035.00/291.50 sqr(0') -> 0' 1035.00/291.50 sqr(s(X)) -> s(add(sqr(X), dbl(X))) 1035.00/291.50 dbl(0') -> 0' 1035.00/291.50 dbl(s(X)) -> s(s(dbl(X))) 1035.00/291.50 add(0', X) -> X 1035.00/291.50 add(s(X), Y) -> s(add(X, Y)) 1035.00/291.50 first(0', X) -> nil 1035.00/291.50 first(s(X), cons(Y)) -> cons(Y) 1035.00/291.50 1035.00/291.50 Types: 1035.00/291.50 terms :: 0':s -> cons:nil 1035.00/291.50 cons :: recip -> cons:nil 1035.00/291.50 recip :: 0':s -> recip 1035.00/291.50 sqr :: 0':s -> 0':s 1035.00/291.50 0' :: 0':s 1035.00/291.50 s :: 0':s -> 0':s 1035.00/291.50 add :: 0':s -> 0':s -> 0':s 1035.00/291.50 dbl :: 0':s -> 0':s 1035.00/291.50 first :: 0':s -> cons:nil -> cons:nil 1035.00/291.50 nil :: cons:nil 1035.00/291.50 hole_cons:nil1_0 :: cons:nil 1035.00/291.50 hole_0':s2_0 :: 0':s 1035.00/291.50 hole_recip3_0 :: recip 1035.00/291.50 gen_0':s4_0 :: Nat -> 0':s 1035.00/291.50 1035.00/291.50 1035.00/291.50 Lemmas: 1035.00/291.50 add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 1035.00/291.50 dbl(gen_0':s4_0(n495_0)) -> gen_0':s4_0(*(2, n495_0)), rt in Omega(1 + n495_0) 1035.00/291.50 1035.00/291.50 1035.00/291.50 Generator Equations: 1035.00/291.50 gen_0':s4_0(0) <=> 0' 1035.00/291.50 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1035.00/291.50 1035.00/291.50 1035.00/291.50 The following defined symbols remain to be analysed: 1035.00/291.50 sqr 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (65) LowerBoundPropagationProof (FINISHED) 1035.00/291.50 Propagated lower bound. 1035.00/291.50 ---------------------------------------- 1035.00/291.50 1035.00/291.50 (66) 1035.00/291.50 BOUNDS(n^3, INF) 1035.11/291.58 EOF