1112.15/291.56 WORST_CASE(Omega(n^2), O(n^3)) 1112.41/291.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1112.41/291.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1112.41/291.61 1112.41/291.61 1112.41/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3). 1112.41/291.61 1112.41/291.61 (0) CpxTRS 1112.41/291.61 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 7 ms] 1112.41/291.61 (2) CpxTRS 1112.41/291.61 (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 10 ms] 1112.41/291.61 (4) CpxTRS 1112.41/291.61 (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (6) CpxWeightedTrs 1112.41/291.61 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (8) CpxTypedWeightedTrs 1112.41/291.61 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (10) CpxTypedWeightedCompleteTrs 1112.41/291.61 (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (12) CpxTypedWeightedCompleteTrs 1112.41/291.61 (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (14) CpxRNTS 1112.41/291.61 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (16) CpxRNTS 1112.41/291.61 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (18) CpxRNTS 1112.41/291.61 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (20) CpxRNTS 1112.41/291.61 (21) IntTrsBoundProof [UPPER BOUND(ID), 353 ms] 1112.41/291.61 (22) CpxRNTS 1112.41/291.61 (23) IntTrsBoundProof [UPPER BOUND(ID), 190 ms] 1112.41/291.61 (24) CpxRNTS 1112.41/291.61 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (26) CpxRNTS 1112.41/291.61 (27) IntTrsBoundProof [UPPER BOUND(ID), 979 ms] 1112.41/291.61 (28) CpxRNTS 1112.41/291.61 (29) IntTrsBoundProof [UPPER BOUND(ID), 543 ms] 1112.41/291.61 (30) CpxRNTS 1112.41/291.61 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (32) CpxRNTS 1112.41/291.61 (33) IntTrsBoundProof [UPPER BOUND(ID), 479 ms] 1112.41/291.61 (34) CpxRNTS 1112.41/291.61 (35) IntTrsBoundProof [UPPER BOUND(ID), 94 ms] 1112.41/291.61 (36) CpxRNTS 1112.41/291.61 (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (38) CpxRNTS 1112.41/291.61 (39) IntTrsBoundProof [UPPER BOUND(ID), 844 ms] 1112.41/291.61 (40) CpxRNTS 1112.41/291.61 (41) IntTrsBoundProof [UPPER BOUND(ID), 206 ms] 1112.41/291.61 (42) CpxRNTS 1112.41/291.61 (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (44) CpxRNTS 1112.41/291.61 (45) IntTrsBoundProof [UPPER BOUND(ID), 666 ms] 1112.41/291.61 (46) CpxRNTS 1112.41/291.61 (47) IntTrsBoundProof [UPPER BOUND(ID), 69 ms] 1112.41/291.61 (48) CpxRNTS 1112.41/291.61 (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (50) CpxRNTS 1112.41/291.61 (51) IntTrsBoundProof [UPPER BOUND(ID), 242 ms] 1112.41/291.61 (52) CpxRNTS 1112.41/291.61 (53) IntTrsBoundProof [UPPER BOUND(ID), 3 ms] 1112.41/291.61 (54) CpxRNTS 1112.41/291.61 (55) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (56) CpxRNTS 1112.41/291.61 (57) IntTrsBoundProof [UPPER BOUND(ID), 97 ms] 1112.41/291.61 (58) CpxRNTS 1112.41/291.61 (59) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 1112.41/291.61 (60) CpxRNTS 1112.41/291.61 (61) FinalProof [FINISHED, 0 ms] 1112.41/291.61 (62) BOUNDS(1, n^3) 1112.41/291.61 (63) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (64) CpxTRS 1112.41/291.61 (65) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1112.41/291.61 (66) typed CpxTrs 1112.41/291.61 (67) OrderProof [LOWER BOUND(ID), 0 ms] 1112.41/291.61 (68) typed CpxTrs 1112.41/291.61 (69) RewriteLemmaProof [LOWER BOUND(ID), 271 ms] 1112.41/291.61 (70) BEST 1112.41/291.61 (71) proven lower bound 1112.41/291.61 (72) LowerBoundPropagationProof [FINISHED, 0 ms] 1112.41/291.61 (73) BOUNDS(n^1, INF) 1112.41/291.61 (74) typed CpxTrs 1112.41/291.61 (75) RewriteLemmaProof [LOWER BOUND(ID), 55 ms] 1112.41/291.61 (76) BEST 1112.41/291.61 (77) proven lower bound 1112.41/291.61 (78) LowerBoundPropagationProof [FINISHED, 0 ms] 1112.41/291.61 (79) BOUNDS(n^2, INF) 1112.41/291.61 (80) typed CpxTrs 1112.41/291.61 (81) RewriteLemmaProof [LOWER BOUND(ID), 41 ms] 1112.41/291.61 (82) typed CpxTrs 1112.41/291.61 (83) RewriteLemmaProof [LOWER BOUND(ID), 79 ms] 1112.41/291.61 (84) typed CpxTrs 1112.41/291.61 1112.41/291.61 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (0) 1112.41/291.61 Obligation: 1112.41/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3). 1112.41/291.61 1112.41/291.61 1112.41/291.61 The TRS R consists of the following rules: 1112.41/291.61 1112.41/291.61 plus(x, 0) -> x 1112.41/291.61 plus(0, y) -> y 1112.41/291.61 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.61 times(0, y) -> 0 1112.41/291.61 times(s(0), y) -> y 1112.41/291.61 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.61 div(0, y) -> 0 1112.41/291.61 div(x, y) -> quot(x, y, y) 1112.41/291.61 quot(0, s(y), z) -> 0 1112.41/291.61 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.61 quot(x, 0, s(z)) -> s(div(x, s(z))) 1112.41/291.61 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.61 eq(0, 0) -> true 1112.41/291.61 eq(s(x), 0) -> false 1112.41/291.61 eq(0, s(y)) -> false 1112.41/291.61 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.61 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.61 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.61 pr(x, s(0)) -> true 1112.41/291.61 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.61 if(true, x, y) -> false 1112.41/291.61 if(false, x, y) -> pr(x, y) 1112.41/291.61 1112.41/291.61 S is empty. 1112.41/291.61 Rewrite Strategy: FULL 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 1112.41/291.61 The following defined symbols can occur below the 0th argument of if: plus, eq, divides, div, times, quot 1112.41/291.61 The following defined symbols can occur below the 1th argument of plus: plus, times, div, quot 1112.41/291.61 The following defined symbols can occur below the 1th argument of eq: plus, div, times, quot 1112.41/291.61 The following defined symbols can occur below the 0th argument of times: div, quot 1112.41/291.61 1112.41/291.61 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 1112.41/291.61 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.61 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (2) 1112.41/291.61 Obligation: 1112.41/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 1112.41/291.61 1112.41/291.61 1112.41/291.61 The TRS R consists of the following rules: 1112.41/291.61 1112.41/291.61 plus(x, 0) -> x 1112.41/291.61 plus(0, y) -> y 1112.41/291.61 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.61 times(0, y) -> 0 1112.41/291.61 times(s(0), y) -> y 1112.41/291.61 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.61 div(0, y) -> 0 1112.41/291.61 div(x, y) -> quot(x, y, y) 1112.41/291.61 quot(0, s(y), z) -> 0 1112.41/291.61 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.61 quot(x, 0, s(z)) -> s(div(x, s(z))) 1112.41/291.61 eq(0, 0) -> true 1112.41/291.61 eq(s(x), 0) -> false 1112.41/291.61 eq(0, s(y)) -> false 1112.41/291.61 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.61 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.61 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.61 pr(x, s(0)) -> true 1112.41/291.61 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.61 if(true, x, y) -> false 1112.41/291.61 if(false, x, y) -> pr(x, y) 1112.41/291.61 1112.41/291.61 S is empty. 1112.41/291.61 Rewrite Strategy: FULL 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) 1112.41/291.61 Converted rc-obligation to irc-obligation. 1112.41/291.61 1112.41/291.61 The duplicating contexts are: 1112.41/291.61 times(s(x), []) 1112.41/291.61 div(x, []) 1112.41/291.61 divides(y, []) 1112.41/291.61 divides([], x) 1112.41/291.61 prime(s(s([]))) 1112.41/291.61 pr(x, s(s([]))) 1112.41/291.61 pr([], s(s(y))) 1112.41/291.61 1112.41/291.61 1112.41/291.61 The defined contexts are: 1112.41/291.61 if([], x1, s(x2)) 1112.41/291.61 eq(x0, []) 1112.41/291.61 times([], x1) 1112.41/291.61 plus(x0, []) 1112.41/291.61 1112.41/291.61 1112.41/291.61 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (4) 1112.41/291.61 Obligation: 1112.41/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3). 1112.41/291.61 1112.41/291.61 1112.41/291.61 The TRS R consists of the following rules: 1112.41/291.61 1112.41/291.61 plus(x, 0) -> x 1112.41/291.61 plus(0, y) -> y 1112.41/291.61 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.61 times(0, y) -> 0 1112.41/291.61 times(s(0), y) -> y 1112.41/291.61 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.61 div(0, y) -> 0 1112.41/291.61 div(x, y) -> quot(x, y, y) 1112.41/291.61 quot(0, s(y), z) -> 0 1112.41/291.61 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.61 quot(x, 0, s(z)) -> s(div(x, s(z))) 1112.41/291.61 eq(0, 0) -> true 1112.41/291.61 eq(s(x), 0) -> false 1112.41/291.61 eq(0, s(y)) -> false 1112.41/291.61 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.61 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.61 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.61 pr(x, s(0)) -> true 1112.41/291.61 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.61 if(true, x, y) -> false 1112.41/291.61 if(false, x, y) -> pr(x, y) 1112.41/291.61 1112.41/291.61 S is empty. 1112.41/291.61 Rewrite Strategy: INNERMOST 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1112.41/291.61 Transformed relative TRS to weighted TRS 1112.41/291.61 ---------------------------------------- 1112.41/291.61 1112.41/291.61 (6) 1112.41/291.61 Obligation: 1112.41/291.61 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 1112.41/291.61 1112.41/291.61 1112.41/291.61 The TRS R consists of the following rules: 1112.41/291.61 1112.41/291.61 plus(x, 0) -> x [1] 1112.41/291.61 plus(0, y) -> y [1] 1112.41/291.61 plus(s(x), y) -> s(plus(x, y)) [1] 1112.41/291.61 times(0, y) -> 0 [1] 1112.41/291.61 times(s(0), y) -> y [1] 1112.41/291.61 times(s(x), y) -> plus(y, times(x, y)) [1] 1112.41/291.61 div(0, y) -> 0 [1] 1112.41/291.61 div(x, y) -> quot(x, y, y) [1] 1112.41/291.61 quot(0, s(y), z) -> 0 [1] 1112.41/291.61 quot(s(x), s(y), z) -> quot(x, y, z) [1] 1112.41/291.61 quot(x, 0, s(z)) -> s(div(x, s(z))) [1] 1112.41/291.61 eq(0, 0) -> true [1] 1112.41/291.61 eq(s(x), 0) -> false [1] 1112.41/291.61 eq(0, s(y)) -> false [1] 1112.41/291.61 eq(s(x), s(y)) -> eq(x, y) [1] 1112.41/291.61 divides(y, x) -> eq(x, times(div(x, y), y)) [1] 1112.41/291.61 prime(s(s(x))) -> pr(s(s(x)), s(x)) [1] 1112.41/291.61 pr(x, s(0)) -> true [1] 1112.41/291.61 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) [1] 1112.41/291.61 if(true, x, y) -> false [1] 1112.41/291.61 if(false, x, y) -> pr(x, y) [1] 1112.41/291.61 1112.41/291.61 Rewrite Strategy: INNERMOST 1112.41/291.61 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1112.41/291.62 Infered types. 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (8) 1112.41/291.62 Obligation: 1112.41/291.62 Runtime Complexity Weighted TRS with Types. 1112.41/291.62 The TRS R consists of the following rules: 1112.41/291.62 1112.41/291.62 plus(x, 0) -> x [1] 1112.41/291.62 plus(0, y) -> y [1] 1112.41/291.62 plus(s(x), y) -> s(plus(x, y)) [1] 1112.41/291.62 times(0, y) -> 0 [1] 1112.41/291.62 times(s(0), y) -> y [1] 1112.41/291.62 times(s(x), y) -> plus(y, times(x, y)) [1] 1112.41/291.62 div(0, y) -> 0 [1] 1112.41/291.62 div(x, y) -> quot(x, y, y) [1] 1112.41/291.62 quot(0, s(y), z) -> 0 [1] 1112.41/291.62 quot(s(x), s(y), z) -> quot(x, y, z) [1] 1112.41/291.62 quot(x, 0, s(z)) -> s(div(x, s(z))) [1] 1112.41/291.62 eq(0, 0) -> true [1] 1112.41/291.62 eq(s(x), 0) -> false [1] 1112.41/291.62 eq(0, s(y)) -> false [1] 1112.41/291.62 eq(s(x), s(y)) -> eq(x, y) [1] 1112.41/291.62 divides(y, x) -> eq(x, times(div(x, y), y)) [1] 1112.41/291.62 prime(s(s(x))) -> pr(s(s(x)), s(x)) [1] 1112.41/291.62 pr(x, s(0)) -> true [1] 1112.41/291.62 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) [1] 1112.41/291.62 if(true, x, y) -> false [1] 1112.41/291.62 if(false, x, y) -> pr(x, y) [1] 1112.41/291.62 1112.41/291.62 The TRS has the following type information: 1112.41/291.62 plus :: 0:s -> 0:s -> 0:s 1112.41/291.62 0 :: 0:s 1112.41/291.62 s :: 0:s -> 0:s 1112.41/291.62 times :: 0:s -> 0:s -> 0:s 1112.41/291.62 div :: 0:s -> 0:s -> 0:s 1112.41/291.62 quot :: 0:s -> 0:s -> 0:s -> 0:s 1112.41/291.62 eq :: 0:s -> 0:s -> true:false 1112.41/291.62 true :: true:false 1112.41/291.62 false :: true:false 1112.41/291.62 divides :: 0:s -> 0:s -> true:false 1112.41/291.62 prime :: 0:s -> true:false 1112.41/291.62 pr :: 0:s -> 0:s -> true:false 1112.41/291.62 if :: true:false -> 0:s -> 0:s -> true:false 1112.41/291.62 1112.41/291.62 Rewrite Strategy: INNERMOST 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (9) CompletionProof (UPPER BOUND(ID)) 1112.41/291.62 The transformation into a RNTS is sound, since: 1112.41/291.62 1112.41/291.62 (a) The obligation is a constructor system where every type has a constant constructor, 1112.41/291.62 1112.41/291.62 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1112.41/291.62 1112.41/291.62 prime_1 1112.41/291.62 pr_2 1112.41/291.62 if_3 1112.41/291.62 1112.41/291.62 (c) The following functions are completely defined: 1112.41/291.62 1112.41/291.62 times_2 1112.41/291.62 div_2 1112.41/291.62 divides_2 1112.41/291.62 plus_2 1112.41/291.62 eq_2 1112.41/291.62 quot_3 1112.41/291.62 1112.41/291.62 Due to the following rules being added: 1112.41/291.62 1112.41/291.62 quot(v0, v1, v2) -> 0 [0] 1112.41/291.62 1112.41/291.62 And the following fresh constants: none 1112.41/291.62 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (10) 1112.41/291.62 Obligation: 1112.41/291.62 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1112.41/291.62 1112.41/291.62 Runtime Complexity Weighted TRS with Types. 1112.41/291.62 The TRS R consists of the following rules: 1112.41/291.62 1112.41/291.62 plus(x, 0) -> x [1] 1112.41/291.62 plus(0, y) -> y [1] 1112.41/291.62 plus(s(x), y) -> s(plus(x, y)) [1] 1112.41/291.62 times(0, y) -> 0 [1] 1112.41/291.62 times(s(0), y) -> y [1] 1112.41/291.62 times(s(x), y) -> plus(y, times(x, y)) [1] 1112.41/291.62 div(0, y) -> 0 [1] 1112.41/291.62 div(x, y) -> quot(x, y, y) [1] 1112.41/291.62 quot(0, s(y), z) -> 0 [1] 1112.41/291.62 quot(s(x), s(y), z) -> quot(x, y, z) [1] 1112.41/291.62 quot(x, 0, s(z)) -> s(div(x, s(z))) [1] 1112.41/291.62 eq(0, 0) -> true [1] 1112.41/291.62 eq(s(x), 0) -> false [1] 1112.41/291.62 eq(0, s(y)) -> false [1] 1112.41/291.62 eq(s(x), s(y)) -> eq(x, y) [1] 1112.41/291.62 divides(y, x) -> eq(x, times(div(x, y), y)) [1] 1112.41/291.62 prime(s(s(x))) -> pr(s(s(x)), s(x)) [1] 1112.41/291.62 pr(x, s(0)) -> true [1] 1112.41/291.62 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) [1] 1112.41/291.62 if(true, x, y) -> false [1] 1112.41/291.62 if(false, x, y) -> pr(x, y) [1] 1112.41/291.62 quot(v0, v1, v2) -> 0 [0] 1112.41/291.62 1112.41/291.62 The TRS has the following type information: 1112.41/291.62 plus :: 0:s -> 0:s -> 0:s 1112.41/291.62 0 :: 0:s 1112.41/291.62 s :: 0:s -> 0:s 1112.41/291.62 times :: 0:s -> 0:s -> 0:s 1112.41/291.62 div :: 0:s -> 0:s -> 0:s 1112.41/291.62 quot :: 0:s -> 0:s -> 0:s -> 0:s 1112.41/291.62 eq :: 0:s -> 0:s -> true:false 1112.41/291.62 true :: true:false 1112.41/291.62 false :: true:false 1112.41/291.62 divides :: 0:s -> 0:s -> true:false 1112.41/291.62 prime :: 0:s -> true:false 1112.41/291.62 pr :: 0:s -> 0:s -> true:false 1112.41/291.62 if :: true:false -> 0:s -> 0:s -> true:false 1112.41/291.62 1112.41/291.62 Rewrite Strategy: INNERMOST 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (11) NarrowingProof (BOTH BOUNDS(ID, ID)) 1112.41/291.62 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (12) 1112.41/291.62 Obligation: 1112.41/291.62 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1112.41/291.62 1112.41/291.62 Runtime Complexity Weighted TRS with Types. 1112.41/291.62 The TRS R consists of the following rules: 1112.41/291.62 1112.41/291.62 plus(x, 0) -> x [1] 1112.41/291.62 plus(0, y) -> y [1] 1112.41/291.62 plus(s(x), y) -> s(plus(x, y)) [1] 1112.41/291.62 times(0, y) -> 0 [1] 1112.41/291.62 times(s(0), y) -> y [1] 1112.41/291.62 times(s(0), y) -> plus(y, 0) [2] 1112.41/291.62 times(s(s(0)), y) -> plus(y, y) [2] 1112.41/291.62 times(s(s(x')), y) -> plus(y, plus(y, times(x', y))) [2] 1112.41/291.62 div(0, y) -> 0 [1] 1112.41/291.62 div(x, y) -> quot(x, y, y) [1] 1112.41/291.62 quot(0, s(y), z) -> 0 [1] 1112.41/291.62 quot(s(x), s(y), z) -> quot(x, y, z) [1] 1112.41/291.62 quot(x, 0, s(z)) -> s(div(x, s(z))) [1] 1112.41/291.62 eq(0, 0) -> true [1] 1112.41/291.62 eq(s(x), 0) -> false [1] 1112.41/291.62 eq(0, s(y)) -> false [1] 1112.41/291.62 eq(s(x), s(y)) -> eq(x, y) [1] 1112.41/291.62 divides(y, 0) -> eq(0, times(0, y)) [2] 1112.41/291.62 divides(y, x) -> eq(x, times(quot(x, y, y), y)) [2] 1112.41/291.62 prime(s(s(x))) -> pr(s(s(x)), s(x)) [1] 1112.41/291.62 pr(x, s(0)) -> true [1] 1112.41/291.62 pr(x, s(s(y))) -> if(eq(x, times(div(x, s(s(y))), s(s(y)))), x, s(y)) [2] 1112.41/291.62 if(true, x, y) -> false [1] 1112.41/291.62 if(false, x, y) -> pr(x, y) [1] 1112.41/291.62 quot(v0, v1, v2) -> 0 [0] 1112.41/291.62 1112.41/291.62 The TRS has the following type information: 1112.41/291.62 plus :: 0:s -> 0:s -> 0:s 1112.41/291.62 0 :: 0:s 1112.41/291.62 s :: 0:s -> 0:s 1112.41/291.62 times :: 0:s -> 0:s -> 0:s 1112.41/291.62 div :: 0:s -> 0:s -> 0:s 1112.41/291.62 quot :: 0:s -> 0:s -> 0:s -> 0:s 1112.41/291.62 eq :: 0:s -> 0:s -> true:false 1112.41/291.62 true :: true:false 1112.41/291.62 false :: true:false 1112.41/291.62 divides :: 0:s -> 0:s -> true:false 1112.41/291.62 prime :: 0:s -> true:false 1112.41/291.62 pr :: 0:s -> 0:s -> true:false 1112.41/291.62 if :: true:false -> 0:s -> 0:s -> true:false 1112.41/291.62 1112.41/291.62 Rewrite Strategy: INNERMOST 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1112.41/291.62 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1112.41/291.62 The constant constructors are abstracted as follows: 1112.41/291.62 1112.41/291.62 0 => 0 1112.41/291.62 true => 1 1112.41/291.62 false => 0 1112.41/291.62 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (14) 1112.41/291.62 Obligation: 1112.41/291.62 Complexity RNTS consisting of the following rules: 1112.41/291.62 1112.41/291.62 div(z', z'') -{ 1 }-> quot(x, y, y) :|: z' = x, z'' = y, x >= 0, y >= 0 1112.41/291.62 div(z', z'') -{ 1 }-> 0 :|: z'' = y, y >= 0, z' = 0 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(x, times(quot(x, y, y), y)) :|: y >= 0, x >= 0, z'' = x, z' = y 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(0, times(0, y)) :|: z'' = 0, y >= 0, z' = y 1112.41/291.62 eq(z', z'') -{ 1 }-> eq(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 1112.41/291.62 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x, x >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: y >= 0, z'' = 1 + y, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> pr(x, y) :|: z1 = y, x >= 0, y >= 0, z'' = x, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> 0 :|: z1 = y, x >= 0, y >= 0, z'' = x, z' = 1 1112.41/291.62 plus(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0 1112.41/291.62 plus(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 1112.41/291.62 plus(z', z'') -{ 1 }-> 1 + plus(x, y) :|: z' = 1 + x, z'' = y, x >= 0, y >= 0 1112.41/291.62 pr(z', z'') -{ 2 }-> if(eq(x, times(div(x, 1 + (1 + y)), 1 + (1 + y))), x, 1 + y) :|: z' = x, x >= 0, y >= 0, z'' = 1 + (1 + y) 1112.41/291.62 pr(z', z'') -{ 1 }-> 1 :|: z' = x, x >= 0, z'' = 1 + 0 1112.41/291.62 prime(z') -{ 1 }-> pr(1 + (1 + x), 1 + x) :|: x >= 0, z' = 1 + (1 + x) 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> quot(x, y, z) :|: z' = 1 + x, z1 = z, z >= 0, x >= 0, y >= 0, z'' = 1 + y 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 = z, z >= 0, y >= 0, z'' = 1 + y, z' = 0 1112.41/291.62 quot(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 1 + div(x, 1 + z) :|: z'' = 0, z >= 0, z' = x, x >= 0, z1 = 1 + z 1112.41/291.62 times(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 1 + 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(y, y) :|: z' = 1 + (1 + 0), z'' = y, y >= 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(y, plus(y, times(x', y))) :|: z' = 1 + (1 + x'), z'' = y, x' >= 0, y >= 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(y, 0) :|: z'' = y, y >= 0, z' = 1 + 0 1112.41/291.62 times(z', z'') -{ 1 }-> 0 :|: z'' = y, y >= 0, z' = 0 1112.41/291.62 1112.41/291.62 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 1112.41/291.62 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (16) 1112.41/291.62 Obligation: 1112.41/291.62 Complexity RNTS consisting of the following rules: 1112.41/291.62 1112.41/291.62 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.62 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> eq(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.62 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.62 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.62 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.62 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.62 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.62 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.62 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.62 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.62 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.62 1112.41/291.62 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1112.41/291.62 Found the following analysis order by SCC decomposition: 1112.41/291.62 1112.41/291.62 { eq } 1112.41/291.62 { div, quot } 1112.41/291.62 { plus } 1112.41/291.62 { times } 1112.41/291.62 { if, pr } 1112.41/291.62 { divides } 1112.41/291.62 { prime } 1112.41/291.62 1112.41/291.62 ---------------------------------------- 1112.41/291.62 1112.41/291.62 (18) 1112.41/291.62 Obligation: 1112.41/291.62 Complexity RNTS consisting of the following rules: 1112.41/291.62 1112.41/291.62 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.62 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.62 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> eq(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.62 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.62 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.62 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.62 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.62 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.62 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.62 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.62 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.62 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.62 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.62 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.62 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {eq}, {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (19) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.63 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (20) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> eq(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.63 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {eq}, {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (21) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.63 1112.41/291.63 Computed SIZE bound using CoFloCo for: eq 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(1) with polynomial bound: 1 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (22) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> eq(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.63 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {eq}, {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 Previous analysis results are: 1112.41/291.63 eq: runtime: ?, size: O(1) [1] 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (23) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.63 1112.41/291.63 Computed RUNTIME bound using KoAT for: eq 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(n^1) with polynomial bound: 3 + z'' 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (24) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> eq(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.63 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 Previous analysis results are: 1112.41/291.63 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (25) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.63 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (26) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.63 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 Previous analysis results are: 1112.41/291.63 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (27) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.63 1112.41/291.63 Computed SIZE bound using KoAT for: div 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(n^1) with polynomial bound: z' 1112.41/291.63 1112.41/291.63 Computed SIZE bound using KoAT for: quot 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(n^1) with polynomial bound: 1 + z' 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (28) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.63 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.63 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.63 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 1112.41/291.63 Function symbols to be analyzed: {div,quot}, {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.63 Previous analysis results are: 1112.41/291.63 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.63 div: runtime: ?, size: O(n^1) [z'] 1112.41/291.63 quot: runtime: ?, size: O(n^1) [1 + z'] 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (29) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.63 1112.41/291.63 Computed RUNTIME bound using KoAT for: div 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(n^1) with polynomial bound: 3 + 3*z' 1112.41/291.63 1112.41/291.63 Computed RUNTIME bound using KoAT for: quot 1112.41/291.63 after applying outer abstraction to obtain an ITS, 1112.41/291.63 resulting in: O(n^1) with polynomial bound: 5 + 3*z' + z'' 1112.41/291.63 1112.41/291.63 ---------------------------------------- 1112.41/291.63 1112.41/291.63 (30) 1112.41/291.63 Obligation: 1112.41/291.63 Complexity RNTS consisting of the following rules: 1112.41/291.63 1112.41/291.63 div(z', z'') -{ 1 }-> quot(z', z'', z'') :|: z' >= 0, z'' >= 0 1112.41/291.63 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(z'', times(quot(z'', z', z'), z')) :|: z' >= 0, z'' >= 0 1112.41/291.63 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.63 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.63 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.63 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.63 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.63 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.63 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.63 pr(z', z'') -{ 2 }-> if(eq(z', times(div(z', 1 + (1 + (z'' - 2))), 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: z' >= 0, z'' - 2 >= 0 1112.41/291.63 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.63 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> quot(z' - 1, z'' - 1, z1) :|: z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.63 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.63 quot(z', z'', z1) -{ 1 }-> 1 + div(z', 1 + (z1 - 1)) :|: z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (31) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.64 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (32) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (33) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: plus 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^1) with polynomial bound: z' + z'' 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (34) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {plus}, {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: ?, size: O(n^1) [z' + z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (35) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using CoFloCo for: plus 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^1) with polynomial bound: 1 + z' 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (36) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 }-> 1 + plus(z' - 1, z'') :|: z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', z'') :|: z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', 0) :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (37) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.64 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (38) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (39) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: times 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^2) with polynomial bound: 2*z'*z'' + 4*z'' 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (40) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {times}, {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: ?, size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (41) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using KoAT for: times 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^2) with polynomial bound: 8 + 4*z' + 2*z'*z'' + 2*z'' 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (42) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 7 + z' + 3*z'' }-> eq(z'', times(s2, z')) :|: s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 divides(z', z'') -{ 2 }-> eq(0, times(0, z')) :|: z'' = 0, z' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 5 + 3*z' }-> if(eq(z', times(s3, 1 + (1 + (z'' - 2)))), z', 1 + (z'' - 2)) :|: s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 2 }-> plus(z'', plus(z'', times(z' - 2, z''))) :|: z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (43) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.64 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (44) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 16 + s14 + 4*s3 + 2*s3*z'' + 3*z' + 2*z'' }-> if(s15, z', 1 + (z'' - 2)) :|: s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (45) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: if 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(1) with polynomial bound: 1 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: pr 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(1) with polynomial bound: 1 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (46) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 16 + s14 + 4*s3 + 2*s3*z'' + 3*z' + 2*z'' }-> if(s15, z', 1 + (z'' - 2)) :|: s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {if,pr}, {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: ?, size: O(1) [1] 1112.41/291.64 pr: runtime: ?, size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (47) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using KoAT for: if 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^3) with polynomial bound: 19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using KoAT for: pr 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^3) with polynomial bound: 8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (48) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> pr(z'', z1) :|: z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 16 + s14 + 4*s3 + 2*s3*z'' + 3*z' + 2*z'' }-> if(s15, z', 1 + (z'' - 2)) :|: s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ 1 }-> pr(1 + (1 + (z' - 2)), 1 + (z' - 2)) :|: z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (49) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.64 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (50) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (51) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: divides 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(1) with polynomial bound: 1 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (52) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {divides}, {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 divides: runtime: ?, size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (53) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using KoAT for: divides 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(n^2) with polynomial bound: 35 + 17*z' + 4*z'*z'' + 7*z'' 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (54) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 divides: runtime: O(n^2) [35 + 17*z' + 4*z'*z'' + 7*z''], size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (55) ResultPropagationProof (UPPER BOUND(ID)) 1112.41/291.64 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (56) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 divides: runtime: O(n^2) [35 + 17*z' + 4*z'*z'' + 7*z''], size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (57) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed SIZE bound using CoFloCo for: prime 1112.41/291.64 after applying outer abstraction to obtain an ITS, 1112.41/291.64 resulting in: O(1) with polynomial bound: 1 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (58) 1112.41/291.64 Obligation: 1112.41/291.64 Complexity RNTS consisting of the following rules: 1112.41/291.64 1112.41/291.64 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.64 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.64 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.64 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.64 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.64 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.64 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.64 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.64 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.64 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.64 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.64 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.64 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.64 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.64 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.64 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.64 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.64 1112.41/291.64 Function symbols to be analyzed: {prime} 1112.41/291.64 Previous analysis results are: 1112.41/291.64 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.64 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.64 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.64 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.64 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.64 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.64 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.64 divides: runtime: O(n^2) [35 + 17*z' + 4*z'*z'' + 7*z''], size: O(1) [1] 1112.41/291.64 prime: runtime: ?, size: O(1) [1] 1112.41/291.64 1112.41/291.64 ---------------------------------------- 1112.41/291.64 1112.41/291.64 (59) IntTrsBoundProof (UPPER BOUND(ID)) 1112.41/291.64 1112.41/291.64 Computed RUNTIME bound using KoAT for: prime 1112.41/291.66 after applying outer abstraction to obtain an ITS, 1112.41/291.66 resulting in: O(n^3) with polynomial bound: 4*z' + 2*z'^2 + 8*z'^3 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (60) 1112.41/291.66 Obligation: 1112.41/291.66 Complexity RNTS consisting of the following rules: 1112.41/291.66 1112.41/291.66 div(z', z'') -{ 6 + 3*z' + z'' }-> s' :|: s' >= 0, s' <= z' + 1, z' >= 0, z'' >= 0 1112.41/291.66 div(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.66 divides(z', z'') -{ 13 + s10 + 2*z' }-> s11 :|: s10 >= 0, s10 <= 2 * (0 * z') + 4 * z', s11 >= 0, s11 <= 1, z'' = 0, z' >= 0 1112.41/291.66 divides(z', z'') -{ 18 + s12 + 4*s2 + 2*s2*z' + 3*z' + 3*z'' }-> s13 :|: s12 >= 0, s12 <= 2 * (s2 * z') + 4 * z', s13 >= 0, s13 <= 1, s2 >= 0, s2 <= z'' + 1, z' >= 0, z'' >= 0 1112.41/291.66 eq(z', z'') -{ 3 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.66 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1112.41/291.66 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' - 1 >= 0 1112.41/291.66 eq(z', z'') -{ 1 }-> 0 :|: z'' - 1 >= 0, z' = 0 1112.41/291.66 if(z', z'', z1) -{ 9 + 4*z'' + 6*z''*z1 + 8*z''*z1^2 + 22*z1 + 12*z1^2 }-> s18 :|: s18 >= 0, s18 <= 1, z'' >= 0, z1 >= 0, z' = 0 1112.41/291.66 if(z', z'', z1) -{ 1 }-> 0 :|: z'' >= 0, z1 >= 0, z' = 1 1112.41/291.66 plus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 1112.41/291.66 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 1112.41/291.66 plus(z', z'') -{ 1 + z' }-> 1 + s4 :|: s4 >= 0, s4 <= z' - 1 + z'', z' - 1 >= 0, z'' >= 0 1112.41/291.66 pr(z', z'') -{ 7 + s14 + 4*s3 + 2*s3*z'' + 2*z'*z'' + 8*z'*z''^2 + 18*z'' + 12*z''^2 }-> s17 :|: s17 >= 0, s17 <= 1, s14 >= 0, s14 <= 2 * (s3 * (1 + (1 + (z'' - 2)))) + 4 * (1 + (1 + (z'' - 2))), s15 >= 0, s15 <= 1, s3 >= 0, s3 <= z', z' >= 0, z'' - 2 >= 0 1112.41/291.66 pr(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 + 0 1112.41/291.66 prime(z') -{ -1 + 4*z' + 2*z'^2 + 8*z'^3 }-> s16 :|: s16 >= 0, s16 <= 1, z' - 2 >= 0 1112.41/291.66 quot(z', z'', z1) -{ 2 + 3*z' + z'' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + 1, z1 >= 0, z' - 1 >= 0, z'' - 1 >= 0 1112.41/291.66 quot(z', z'', z1) -{ 1 }-> 0 :|: z1 >= 0, z'' - 1 >= 0, z' = 0 1112.41/291.66 quot(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 1112.41/291.66 quot(z', z'', z1) -{ 4 + 3*z' }-> 1 + s1 :|: s1 >= 0, s1 <= z', z'' = 0, z1 - 1 >= 0, z' >= 0 1112.41/291.66 times(z', z'') -{ 3 + z'' }-> s5 :|: s5 >= 0, s5 <= z'' + 0, z'' >= 0, z' = 1 + 0 1112.41/291.66 times(z', z'') -{ 3 + z'' }-> s6 :|: s6 >= 0, s6 <= z'' + z'', z' = 1 + (1 + 0), z'' >= 0 1112.41/291.66 times(z', z'') -{ 4 + 4*z' + 2*z'*z'' }-> s9 :|: s7 >= 0, s7 <= 2 * ((z' - 2) * z'') + 4 * z'', s8 >= 0, s8 <= z'' + s7, s9 >= 0, s9 <= z'' + s8, z' - 2 >= 0, z'' >= 0 1112.41/291.66 times(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 1 + 0 1112.41/291.66 times(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1112.41/291.66 1112.41/291.66 Function symbols to be analyzed: 1112.41/291.66 Previous analysis results are: 1112.41/291.66 eq: runtime: O(n^1) [3 + z''], size: O(1) [1] 1112.41/291.66 div: runtime: O(n^1) [3 + 3*z'], size: O(n^1) [z'] 1112.41/291.66 quot: runtime: O(n^1) [5 + 3*z' + z''], size: O(n^1) [1 + z'] 1112.41/291.66 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 1112.41/291.66 times: runtime: O(n^2) [8 + 4*z' + 2*z'*z'' + 2*z''], size: O(n^2) [2*z'*z'' + 4*z''] 1112.41/291.66 if: runtime: O(n^3) [19 + 7*z'' + 18*z''*z1 + 8*z''*z1^2 + 40*z1 + 12*z1^2], size: O(1) [1] 1112.41/291.66 pr: runtime: O(n^3) [8 + 4*z' + 6*z'*z'' + 8*z'*z''^2 + 22*z'' + 12*z''^2], size: O(1) [1] 1112.41/291.66 divides: runtime: O(n^2) [35 + 17*z' + 4*z'*z'' + 7*z''], size: O(1) [1] 1112.41/291.66 prime: runtime: O(n^3) [4*z' + 2*z'^2 + 8*z'^3], size: O(1) [1] 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (61) FinalProof (FINISHED) 1112.41/291.66 Computed overall runtime complexity 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (62) 1112.41/291.66 BOUNDS(1, n^3) 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (63) RenamingProof (BOTH BOUNDS(ID, ID)) 1112.41/291.66 Renamed function symbols to avoid clashes with predefined symbol. 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (64) 1112.41/291.66 Obligation: 1112.41/291.66 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1112.41/291.66 1112.41/291.66 1112.41/291.66 The TRS R consists of the following rules: 1112.41/291.66 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 S is empty. 1112.41/291.66 Rewrite Strategy: FULL 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (65) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1112.41/291.66 Infered types. 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (66) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (67) OrderProof (LOWER BOUND(ID)) 1112.41/291.66 Heuristically decided to analyse the following defined symbols: 1112.41/291.66 plus, times, div, quot, eq, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 plus < times 1112.41/291.66 times < div 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (68) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 plus, times, div, quot, eq, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 plus < times 1112.41/291.66 times < div 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (69) RewriteLemmaProof (LOWER BOUND(ID)) 1112.41/291.66 Proved the following rewrite lemma: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 1112.41/291.66 Induction Base: 1112.41/291.66 plus(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 1112.41/291.66 gen_0':s3_0(b) 1112.41/291.66 1112.41/291.66 Induction Step: 1112.41/291.66 plus(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 1112.41/291.66 s(plus(gen_0':s3_0(n5_0), gen_0':s3_0(b))) ->_IH 1112.41/291.66 s(gen_0':s3_0(+(b, c6_0))) 1112.41/291.66 1112.41/291.66 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (70) 1112.41/291.66 Complex Obligation (BEST) 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (71) 1112.41/291.66 Obligation: 1112.41/291.66 Proved the lower bound n^1 for the following obligation: 1112.41/291.66 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 plus, times, div, quot, eq, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 plus < times 1112.41/291.66 times < div 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (72) LowerBoundPropagationProof (FINISHED) 1112.41/291.66 Propagated lower bound. 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (73) 1112.41/291.66 BOUNDS(n^1, INF) 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (74) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Lemmas: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 times, div, quot, eq, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 times < div 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (75) RewriteLemmaProof (LOWER BOUND(ID)) 1112.41/291.66 Proved the following rewrite lemma: 1112.41/291.66 times(gen_0':s3_0(n758_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n758_0, b)), rt in Omega(1 + b*n758_0 + n758_0) 1112.41/291.66 1112.41/291.66 Induction Base: 1112.41/291.66 times(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 1112.41/291.66 0' 1112.41/291.66 1112.41/291.66 Induction Step: 1112.41/291.66 times(gen_0':s3_0(+(n758_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 1112.41/291.66 plus(gen_0':s3_0(b), times(gen_0':s3_0(n758_0), gen_0':s3_0(b))) ->_IH 1112.41/291.66 plus(gen_0':s3_0(b), gen_0':s3_0(*(c759_0, b))) ->_L^Omega(1 + b) 1112.41/291.66 gen_0':s3_0(+(b, *(n758_0, b))) 1112.41/291.66 1112.41/291.66 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (76) 1112.41/291.66 Complex Obligation (BEST) 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (77) 1112.41/291.66 Obligation: 1112.41/291.66 Proved the lower bound n^2 for the following obligation: 1112.41/291.66 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Lemmas: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 times, div, quot, eq, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 times < div 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (78) LowerBoundPropagationProof (FINISHED) 1112.41/291.66 Propagated lower bound. 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (79) 1112.41/291.66 BOUNDS(n^2, INF) 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (80) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Lemmas: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 times(gen_0':s3_0(n758_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n758_0, b)), rt in Omega(1 + b*n758_0 + n758_0) 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 eq, div, quot, pr 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (81) RewriteLemmaProof (LOWER BOUND(ID)) 1112.41/291.66 Proved the following rewrite lemma: 1112.41/291.66 eq(gen_0':s3_0(n1791_0), gen_0':s3_0(n1791_0)) -> true, rt in Omega(1 + n1791_0) 1112.41/291.66 1112.41/291.66 Induction Base: 1112.41/291.66 eq(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 1112.41/291.66 true 1112.41/291.66 1112.41/291.66 Induction Step: 1112.41/291.66 eq(gen_0':s3_0(+(n1791_0, 1)), gen_0':s3_0(+(n1791_0, 1))) ->_R^Omega(1) 1112.41/291.66 eq(gen_0':s3_0(n1791_0), gen_0':s3_0(n1791_0)) ->_IH 1112.41/291.66 true 1112.41/291.66 1112.41/291.66 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (82) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Lemmas: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 times(gen_0':s3_0(n758_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n758_0, b)), rt in Omega(1 + b*n758_0 + n758_0) 1112.41/291.66 eq(gen_0':s3_0(n1791_0), gen_0':s3_0(n1791_0)) -> true, rt in Omega(1 + n1791_0) 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 pr, div, quot 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 div = quot 1112.41/291.66 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (83) RewriteLemmaProof (LOWER BOUND(ID)) 1112.41/291.66 Proved the following rewrite lemma: 1112.41/291.66 quot(gen_0':s3_0(n2446_0), gen_0':s3_0(+(1, n2446_0)), gen_0':s3_0(c)) -> gen_0':s3_0(0), rt in Omega(1 + n2446_0) 1112.41/291.66 1112.41/291.66 Induction Base: 1112.41/291.66 quot(gen_0':s3_0(0), gen_0':s3_0(+(1, 0)), gen_0':s3_0(c)) ->_R^Omega(1) 1112.41/291.66 0' 1112.41/291.66 1112.41/291.66 Induction Step: 1112.41/291.66 quot(gen_0':s3_0(+(n2446_0, 1)), gen_0':s3_0(+(1, +(n2446_0, 1))), gen_0':s3_0(c)) ->_R^Omega(1) 1112.41/291.66 quot(gen_0':s3_0(n2446_0), gen_0':s3_0(+(1, n2446_0)), gen_0':s3_0(c)) ->_IH 1112.41/291.66 gen_0':s3_0(0) 1112.41/291.66 1112.41/291.66 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1112.41/291.66 ---------------------------------------- 1112.41/291.66 1112.41/291.66 (84) 1112.41/291.66 Obligation: 1112.41/291.66 TRS: 1112.41/291.66 Rules: 1112.41/291.66 plus(x, 0') -> x 1112.41/291.66 plus(0', y) -> y 1112.41/291.66 plus(s(x), y) -> s(plus(x, y)) 1112.41/291.66 times(0', y) -> 0' 1112.41/291.66 times(s(0'), y) -> y 1112.41/291.66 times(s(x), y) -> plus(y, times(x, y)) 1112.41/291.66 div(0', y) -> 0' 1112.41/291.66 div(x, y) -> quot(x, y, y) 1112.41/291.66 quot(0', s(y), z) -> 0' 1112.41/291.66 quot(s(x), s(y), z) -> quot(x, y, z) 1112.41/291.66 quot(x, 0', s(z)) -> s(div(x, s(z))) 1112.41/291.66 div(div(x, y), z) -> div(x, times(y, z)) 1112.41/291.66 eq(0', 0') -> true 1112.41/291.66 eq(s(x), 0') -> false 1112.41/291.66 eq(0', s(y)) -> false 1112.41/291.66 eq(s(x), s(y)) -> eq(x, y) 1112.41/291.66 divides(y, x) -> eq(x, times(div(x, y), y)) 1112.41/291.66 prime(s(s(x))) -> pr(s(s(x)), s(x)) 1112.41/291.66 pr(x, s(0')) -> true 1112.41/291.66 pr(x, s(s(y))) -> if(divides(s(s(y)), x), x, s(y)) 1112.41/291.66 if(true, x, y) -> false 1112.41/291.66 if(false, x, y) -> pr(x, y) 1112.41/291.66 1112.41/291.66 Types: 1112.41/291.66 plus :: 0':s -> 0':s -> 0':s 1112.41/291.66 0' :: 0':s 1112.41/291.66 s :: 0':s -> 0':s 1112.41/291.66 times :: 0':s -> 0':s -> 0':s 1112.41/291.66 div :: 0':s -> 0':s -> 0':s 1112.41/291.66 quot :: 0':s -> 0':s -> 0':s -> 0':s 1112.41/291.66 eq :: 0':s -> 0':s -> true:false 1112.41/291.66 true :: true:false 1112.41/291.66 false :: true:false 1112.41/291.66 divides :: 0':s -> 0':s -> true:false 1112.41/291.66 prime :: 0':s -> true:false 1112.41/291.66 pr :: 0':s -> 0':s -> true:false 1112.41/291.66 if :: true:false -> 0':s -> 0':s -> true:false 1112.41/291.66 hole_0':s1_0 :: 0':s 1112.41/291.66 hole_true:false2_0 :: true:false 1112.41/291.66 gen_0':s3_0 :: Nat -> 0':s 1112.41/291.66 1112.41/291.66 1112.41/291.66 Lemmas: 1112.41/291.66 plus(gen_0':s3_0(n5_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n5_0, b)), rt in Omega(1 + n5_0) 1112.41/291.66 times(gen_0':s3_0(n758_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n758_0, b)), rt in Omega(1 + b*n758_0 + n758_0) 1112.41/291.66 eq(gen_0':s3_0(n1791_0), gen_0':s3_0(n1791_0)) -> true, rt in Omega(1 + n1791_0) 1112.41/291.66 quot(gen_0':s3_0(n2446_0), gen_0':s3_0(+(1, n2446_0)), gen_0':s3_0(c)) -> gen_0':s3_0(0), rt in Omega(1 + n2446_0) 1112.41/291.66 1112.41/291.66 1112.41/291.66 Generator Equations: 1112.41/291.66 gen_0':s3_0(0) <=> 0' 1112.41/291.66 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 1112.41/291.66 1112.41/291.66 1112.41/291.66 The following defined symbols remain to be analysed: 1112.41/291.66 div 1112.41/291.66 1112.41/291.66 They will be analysed ascendingly in the following order: 1112.41/291.66 div = quot 1112.78/291.73 EOF