976.75/291.49 WORST_CASE(Omega(n^1), O(n^2)) 976.96/291.51 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 976.96/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 976.96/291.51 976.96/291.51 976.96/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 976.96/291.51 976.96/291.51 (0) CpxTRS 976.96/291.51 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 976.96/291.51 (2) CpxWeightedTrs 976.96/291.51 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 976.96/291.51 (4) CpxTypedWeightedTrs 976.96/291.51 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (6) CpxTypedWeightedCompleteTrs 976.96/291.51 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 976.96/291.51 (8) CpxTypedWeightedCompleteTrs 976.96/291.51 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 9 ms] 976.96/291.51 (10) CpxRNTS 976.96/291.51 (11) InliningProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (12) CpxRNTS 976.96/291.51 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 976.96/291.51 (14) CpxRNTS 976.96/291.51 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 976.96/291.51 (16) CpxRNTS 976.96/291.51 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (18) CpxRNTS 976.96/291.51 (19) IntTrsBoundProof [UPPER BOUND(ID), 435 ms] 976.96/291.51 (20) CpxRNTS 976.96/291.51 (21) IntTrsBoundProof [UPPER BOUND(ID), 179 ms] 976.96/291.51 (22) CpxRNTS 976.96/291.51 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (24) CpxRNTS 976.96/291.51 (25) IntTrsBoundProof [UPPER BOUND(ID), 100 ms] 976.96/291.51 (26) CpxRNTS 976.96/291.51 (27) IntTrsBoundProof [UPPER BOUND(ID), 53 ms] 976.96/291.51 (28) CpxRNTS 976.96/291.51 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (30) CpxRNTS 976.96/291.51 (31) IntTrsBoundProof [UPPER BOUND(ID), 265 ms] 976.96/291.51 (32) CpxRNTS 976.96/291.51 (33) IntTrsBoundProof [UPPER BOUND(ID), 83 ms] 976.96/291.51 (34) CpxRNTS 976.96/291.51 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (36) CpxRNTS 976.96/291.51 (37) IntTrsBoundProof [UPPER BOUND(ID), 176 ms] 976.96/291.51 (38) CpxRNTS 976.96/291.51 (39) IntTrsBoundProof [UPPER BOUND(ID), 42 ms] 976.96/291.51 (40) CpxRNTS 976.96/291.51 (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (42) CpxRNTS 976.96/291.51 (43) IntTrsBoundProof [UPPER BOUND(ID), 1954 ms] 976.96/291.51 (44) CpxRNTS 976.96/291.51 (45) IntTrsBoundProof [UPPER BOUND(ID), 948 ms] 976.96/291.51 (46) CpxRNTS 976.96/291.51 (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (48) CpxRNTS 976.96/291.51 (49) IntTrsBoundProof [UPPER BOUND(ID), 169 ms] 976.96/291.51 (50) CpxRNTS 976.96/291.51 (51) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 976.96/291.51 (52) CpxRNTS 976.96/291.51 (53) FinalProof [FINISHED, 0 ms] 976.96/291.51 (54) BOUNDS(1, n^2) 976.96/291.51 (55) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 976.96/291.51 (56) TRS for Loop Detection 976.96/291.51 (57) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 976.96/291.51 (58) BEST 976.96/291.51 (59) proven lower bound 976.96/291.51 (60) LowerBoundPropagationProof [FINISHED, 0 ms] 976.96/291.51 (61) BOUNDS(n^1, INF) 976.96/291.51 (62) TRS for Loop Detection 976.96/291.51 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (0) 976.96/291.51 Obligation: 976.96/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 976.96/291.51 976.96/291.51 976.96/291.51 The TRS R consists of the following rules: 976.96/291.51 976.96/291.51 minus(0, y) -> 0 976.96/291.51 minus(x, 0) -> x 976.96/291.51 minus(s(x), s(y)) -> minus(x, y) 976.96/291.51 plus(0, y) -> y 976.96/291.51 plus(s(x), y) -> plus(x, s(y)) 976.96/291.51 zero(s(x)) -> false 976.96/291.51 zero(0) -> true 976.96/291.51 p(s(x)) -> x 976.96/291.51 div(x, y) -> quot(x, y, 0) 976.96/291.51 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) 976.96/291.51 if(true, x, y, z) -> p(z) 976.96/291.51 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) 976.96/291.51 976.96/291.51 S is empty. 976.96/291.51 Rewrite Strategy: INNERMOST 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 976.96/291.51 Transformed relative TRS to weighted TRS 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (2) 976.96/291.51 Obligation: 976.96/291.51 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 976.96/291.51 976.96/291.51 976.96/291.51 The TRS R consists of the following rules: 976.96/291.51 976.96/291.51 minus(0, y) -> 0 [1] 976.96/291.51 minus(x, 0) -> x [1] 976.96/291.51 minus(s(x), s(y)) -> minus(x, y) [1] 976.96/291.51 plus(0, y) -> y [1] 976.96/291.51 plus(s(x), y) -> plus(x, s(y)) [1] 976.96/291.51 zero(s(x)) -> false [1] 976.96/291.51 zero(0) -> true [1] 976.96/291.51 p(s(x)) -> x [1] 976.96/291.51 div(x, y) -> quot(x, y, 0) [1] 976.96/291.51 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) [1] 976.96/291.51 if(true, x, y, z) -> p(z) [1] 976.96/291.51 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) [1] 976.96/291.51 976.96/291.51 Rewrite Strategy: INNERMOST 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 976.96/291.51 Infered types. 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (4) 976.96/291.51 Obligation: 976.96/291.51 Runtime Complexity Weighted TRS with Types. 976.96/291.51 The TRS R consists of the following rules: 976.96/291.51 976.96/291.51 minus(0, y) -> 0 [1] 976.96/291.51 minus(x, 0) -> x [1] 976.96/291.51 minus(s(x), s(y)) -> minus(x, y) [1] 976.96/291.51 plus(0, y) -> y [1] 976.96/291.51 plus(s(x), y) -> plus(x, s(y)) [1] 976.96/291.51 zero(s(x)) -> false [1] 976.96/291.51 zero(0) -> true [1] 976.96/291.51 p(s(x)) -> x [1] 976.96/291.51 div(x, y) -> quot(x, y, 0) [1] 976.96/291.51 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) [1] 976.96/291.51 if(true, x, y, z) -> p(z) [1] 976.96/291.51 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) [1] 976.96/291.51 976.96/291.51 The TRS has the following type information: 976.96/291.51 minus :: 0:s -> 0:s -> 0:s 976.96/291.51 0 :: 0:s 976.96/291.51 s :: 0:s -> 0:s 976.96/291.51 plus :: 0:s -> 0:s -> 0:s 976.96/291.51 zero :: 0:s -> false:true 976.96/291.51 false :: false:true 976.96/291.51 true :: false:true 976.96/291.51 p :: 0:s -> 0:s 976.96/291.51 div :: 0:s -> 0:s -> 0:s 976.96/291.51 quot :: 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 if :: false:true -> 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 976.96/291.51 Rewrite Strategy: INNERMOST 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (5) CompletionProof (UPPER BOUND(ID)) 976.96/291.51 The transformation into a RNTS is sound, since: 976.96/291.51 976.96/291.51 (a) The obligation is a constructor system where every type has a constant constructor, 976.96/291.51 976.96/291.51 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 976.96/291.51 976.96/291.51 p_1 976.96/291.51 div_2 976.96/291.51 quot_3 976.96/291.51 if_4 976.96/291.51 976.96/291.51 (c) The following functions are completely defined: 976.96/291.51 976.96/291.51 minus_2 976.96/291.51 zero_1 976.96/291.51 plus_2 976.96/291.51 976.96/291.51 Due to the following rules being added: 976.96/291.51 none 976.96/291.51 976.96/291.51 And the following fresh constants: none 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (6) 976.96/291.51 Obligation: 976.96/291.51 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 976.96/291.51 976.96/291.51 Runtime Complexity Weighted TRS with Types. 976.96/291.51 The TRS R consists of the following rules: 976.96/291.51 976.96/291.51 minus(0, y) -> 0 [1] 976.96/291.51 minus(x, 0) -> x [1] 976.96/291.51 minus(s(x), s(y)) -> minus(x, y) [1] 976.96/291.51 plus(0, y) -> y [1] 976.96/291.51 plus(s(x), y) -> plus(x, s(y)) [1] 976.96/291.51 zero(s(x)) -> false [1] 976.96/291.51 zero(0) -> true [1] 976.96/291.51 p(s(x)) -> x [1] 976.96/291.51 div(x, y) -> quot(x, y, 0) [1] 976.96/291.51 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) [1] 976.96/291.51 if(true, x, y, z) -> p(z) [1] 976.96/291.51 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) [1] 976.96/291.51 976.96/291.51 The TRS has the following type information: 976.96/291.51 minus :: 0:s -> 0:s -> 0:s 976.96/291.51 0 :: 0:s 976.96/291.51 s :: 0:s -> 0:s 976.96/291.51 plus :: 0:s -> 0:s -> 0:s 976.96/291.51 zero :: 0:s -> false:true 976.96/291.51 false :: false:true 976.96/291.51 true :: false:true 976.96/291.51 p :: 0:s -> 0:s 976.96/291.51 div :: 0:s -> 0:s -> 0:s 976.96/291.51 quot :: 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 if :: false:true -> 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 976.96/291.51 Rewrite Strategy: INNERMOST 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 976.96/291.51 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (8) 976.96/291.51 Obligation: 976.96/291.51 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 976.96/291.51 976.96/291.51 Runtime Complexity Weighted TRS with Types. 976.96/291.51 The TRS R consists of the following rules: 976.96/291.51 976.96/291.51 minus(0, y) -> 0 [1] 976.96/291.51 minus(x, 0) -> x [1] 976.96/291.51 minus(s(x), s(y)) -> minus(x, y) [1] 976.96/291.51 plus(0, y) -> y [1] 976.96/291.51 plus(s(x), y) -> plus(x, s(y)) [1] 976.96/291.51 zero(s(x)) -> false [1] 976.96/291.51 zero(0) -> true [1] 976.96/291.51 p(s(x)) -> x [1] 976.96/291.51 div(x, y) -> quot(x, y, 0) [1] 976.96/291.51 quot(s(x'), y, 0) -> if(false, s(x'), y, s(0)) [3] 976.96/291.51 quot(s(x'), y, s(x'')) -> if(false, s(x'), y, plus(x'', s(s(0)))) [3] 976.96/291.51 quot(0, y, 0) -> if(true, 0, y, s(0)) [3] 976.96/291.51 quot(0, y, s(x1)) -> if(true, 0, y, plus(x1, s(s(0)))) [3] 976.96/291.51 if(true, x, y, z) -> p(z) [1] 976.96/291.51 if(false, 0, s(y), z) -> quot(0, s(y), z) [2] 976.96/291.51 if(false, s(x2), s(y), z) -> quot(minus(x2, y), s(y), z) [2] 976.96/291.51 976.96/291.51 The TRS has the following type information: 976.96/291.51 minus :: 0:s -> 0:s -> 0:s 976.96/291.51 0 :: 0:s 976.96/291.51 s :: 0:s -> 0:s 976.96/291.51 plus :: 0:s -> 0:s -> 0:s 976.96/291.51 zero :: 0:s -> false:true 976.96/291.51 false :: false:true 976.96/291.51 true :: false:true 976.96/291.51 p :: 0:s -> 0:s 976.96/291.51 div :: 0:s -> 0:s -> 0:s 976.96/291.51 quot :: 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 if :: false:true -> 0:s -> 0:s -> 0:s -> 0:s 976.96/291.51 976.96/291.51 Rewrite Strategy: INNERMOST 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 976.96/291.51 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 976.96/291.51 The constant constructors are abstracted as follows: 976.96/291.51 976.96/291.51 0 => 0 976.96/291.51 false => 0 976.96/291.51 true => 1 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (10) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(x, y, 0) :|: z' = x, z'' = y, x >= 0, y >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(x2, y), 1 + y, z) :|: z >= 0, z2 = z, y >= 0, z'' = 1 + x2, z1 = 1 + y, x2 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + y, z) :|: z'' = 0, z >= 0, z2 = z, y >= 0, z1 = 1 + y, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 1 }-> p(z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 976.96/291.51 minus(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' = y, y >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(x, 1 + y) :|: z' = 1 + x, z'' = y, x >= 0, y >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, y, plus(x1, 1 + (1 + 0))) :|: x1 >= 0, z'' = y, y >= 0, z1 = 1 + x1, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, y, 1 + 0) :|: z1 = 0, z'' = y, y >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + x', y, plus(x'', 1 + (1 + 0))) :|: z1 = 1 + x'', z' = 1 + x', z'' = y, x' >= 0, y >= 0, x'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + x', y, 1 + 0) :|: z1 = 0, z' = 1 + x', z'' = y, x' >= 0, y >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' = 1 + x, x >= 0 976.96/291.51 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (11) InliningProof (UPPER BOUND(ID)) 976.96/291.51 Inlined the following terminating rules on right-hand sides where appropriate: 976.96/291.51 976.96/291.51 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (12) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(x, y, 0) :|: z' = x, z'' = y, x >= 0, y >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> x' :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1, z = 1 + x', x' >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(x2, y), 1 + y, z) :|: z >= 0, z2 = z, y >= 0, z'' = 1 + x2, z1 = 1 + y, x2 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + y, z) :|: z'' = 0, z >= 0, z2 = z, y >= 0, z1 = 1 + y, z' = 0 976.96/291.51 minus(z', z'') -{ 1 }-> x :|: z'' = 0, z' = x, x >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' = y, y >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(x, 1 + y) :|: z' = 1 + x, z'' = y, x >= 0, y >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, y, plus(x1, 1 + (1 + 0))) :|: x1 >= 0, z'' = y, y >= 0, z1 = 1 + x1, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, y, 1 + 0) :|: z1 = 0, z'' = y, y >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + x', y, plus(x'', 1 + (1 + 0))) :|: z1 = 1 + x'', z' = 1 + x', z'' = y, x' >= 0, y >= 0, x'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + x', y, 1 + 0) :|: z1 = 0, z' = 1 + x', z'' = y, x' >= 0, y >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' = 1 + x, x >= 0 976.96/291.51 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 976.96/291.51 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (14) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(z'' - 1, z1 - 1), 1 + (z1 - 1), z2) :|: z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.51 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 976.96/291.51 Found the following analysis order by SCC decomposition: 976.96/291.51 976.96/291.51 { minus } 976.96/291.51 { zero } 976.96/291.51 { plus } 976.96/291.51 { p } 976.96/291.51 { if, quot } 976.96/291.51 { div } 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (16) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(z'' - 1, z1 - 1), 1 + (z1 - 1), z2) :|: z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.51 976.96/291.51 Function symbols to be analyzed: {minus}, {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (17) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.51 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (18) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(z'' - 1, z1 - 1), 1 + (z1 - 1), z2) :|: z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.51 976.96/291.51 Function symbols to be analyzed: {minus}, {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (19) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.51 976.96/291.51 Computed SIZE bound using KoAT for: minus 976.96/291.51 after applying outer abstraction to obtain an ITS, 976.96/291.51 resulting in: O(n^1) with polynomial bound: z' 976.96/291.51 976.96/291.51 ---------------------------------------- 976.96/291.51 976.96/291.51 (20) 976.96/291.51 Obligation: 976.96/291.51 Complexity RNTS consisting of the following rules: 976.96/291.51 976.96/291.51 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(minus(z'' - 1, z1 - 1), 1 + (z1 - 1), z2) :|: z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.51 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 976.96/291.51 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.51 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.51 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.51 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.51 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.51 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.51 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.51 976.96/291.51 Function symbols to be analyzed: {minus}, {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: ?, size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (21) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using KoAT for: minus 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: 2 + z'' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (22) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(minus(z'' - 1, z1 - 1), 1 + (z1 - 1), z2) :|: z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> minus(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (23) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (24) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (25) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed SIZE bound using CoFloCo for: zero 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(1) with polynomial bound: 1 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (26) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {zero}, {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: ?, size: O(1) [1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (27) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using CoFloCo for: zero 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(1) with polynomial bound: 1 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (28) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (29) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (30) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (31) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed SIZE bound using CoFloCo for: plus 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: z' + z'' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (32) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {plus}, {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: ?, size: O(n^1) [z' + z''] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (33) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using CoFloCo for: plus 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: 1 + z' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (34) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 plus(z', z'') -{ 1 }-> plus(z' - 1, 1 + z'') :|: z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', plus(z1 - 1, 1 + (1 + 0))) :|: z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', plus(z1 - 1, 1 + (1 + 0))) :|: z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (35) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (36) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (37) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed SIZE bound using KoAT for: p 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: z' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (38) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {p}, {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: ?, size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (39) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using CoFloCo for: p 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(1) with polynomial bound: 1 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (40) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (41) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (42) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (43) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed SIZE bound using CoFloCo for: if 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: 1 + z'' + z2 976.96/291.52 976.96/291.52 Computed SIZE bound using CoFloCo for: quot 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: 2 + z' + z1 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (44) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {if,quot}, {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 if: runtime: ?, size: O(n^1) [1 + z'' + z2] 976.96/291.52 quot: runtime: ?, size: O(n^1) [2 + z' + z1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (45) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using CoFloCo for: if 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^2) with polynomial bound: 18 + 12*z'' + 2*z''*z1 + z''*z2 + z''^2 + 3*z1 + 2*z2 976.96/291.52 976.96/291.52 Computed RUNTIME bound using KoAT for: quot 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^2) with polynomial bound: 92 + 26*z' + 4*z'*z'' + z'*z1 + 2*z'^2 + 12*z'' + 6*z1 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (46) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 1 }-> quot(z', z'', 0) :|: z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 3 + z1 }-> quot(s', 1 + (z1 - 1), z2) :|: s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> quot(0, 1 + (z1 - 1), z2) :|: z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(1, 0, z'', s2) :|: s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(1, 0, z'', 1 + 0) :|: z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 3 + z1 }-> if(0, 1 + (z' - 1), z'', s1) :|: s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 3 }-> if(0, 1 + (z' - 1), z'', 1 + 0) :|: z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 if: runtime: O(n^2) [18 + 12*z'' + 2*z''*z1 + z''*z2 + z''^2 + 3*z1 + 2*z2], size: O(n^1) [1 + z'' + z2] 976.96/291.52 quot: runtime: O(n^2) [92 + 26*z' + 4*z'*z'' + z'*z1 + 2*z'^2 + 12*z'' + 6*z1], size: O(n^1) [2 + z' + z1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (47) ResultPropagationProof (UPPER BOUND(ID)) 976.96/291.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (48) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 93 + 26*z' + 4*z'*z'' + 2*z'^2 + 12*z'' }-> s3 :|: s3 >= 0, s3 <= z' + 0 + 2, z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 94 + 12*z1 + 6*z2 }-> s8 :|: s8 >= 0, s8 <= 0 + z2 + 2, z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 95 + 26*s' + 4*s'*z1 + s'*z2 + 2*s'^2 + 13*z1 + 6*z2 }-> s9 :|: s9 >= 0, s9 <= s' + z2 + 2, s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 13*z' + 2*z'*z'' + z'^2 + 3*z'' }-> s4 :|: s4 >= 0, s4 <= 1 + 0 + 1 + (1 + (z' - 1)), z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s1 + s1*z' + 12*z' + 2*z'*z'' + z'^2 + 3*z'' + z1 }-> s5 :|: s5 >= 0, s5 <= s1 + 1 + (1 + (z' - 1)), s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 3*z'' }-> s6 :|: s6 >= 0, s6 <= 1 + 0 + 1 + 0, z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s2 + 3*z'' + z1 }-> s7 :|: s7 >= 0, s7 <= s2 + 1 + 0, s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 if: runtime: O(n^2) [18 + 12*z'' + 2*z''*z1 + z''*z2 + z''^2 + 3*z1 + 2*z2], size: O(n^1) [1 + z'' + z2] 976.96/291.52 quot: runtime: O(n^2) [92 + 26*z' + 4*z'*z'' + z'*z1 + 2*z'^2 + 12*z'' + 6*z1], size: O(n^1) [2 + z' + z1] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (49) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed SIZE bound using CoFloCo for: div 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^1) with polynomial bound: 2 + z' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (50) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 93 + 26*z' + 4*z'*z'' + 2*z'^2 + 12*z'' }-> s3 :|: s3 >= 0, s3 <= z' + 0 + 2, z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 94 + 12*z1 + 6*z2 }-> s8 :|: s8 >= 0, s8 <= 0 + z2 + 2, z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 95 + 26*s' + 4*s'*z1 + s'*z2 + 2*s'^2 + 13*z1 + 6*z2 }-> s9 :|: s9 >= 0, s9 <= s' + z2 + 2, s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 13*z' + 2*z'*z'' + z'^2 + 3*z'' }-> s4 :|: s4 >= 0, s4 <= 1 + 0 + 1 + (1 + (z' - 1)), z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s1 + s1*z' + 12*z' + 2*z'*z'' + z'^2 + 3*z'' + z1 }-> s5 :|: s5 >= 0, s5 <= s1 + 1 + (1 + (z' - 1)), s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 3*z'' }-> s6 :|: s6 >= 0, s6 <= 1 + 0 + 1 + 0, z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s2 + 3*z'' + z1 }-> s7 :|: s7 >= 0, s7 <= s2 + 1 + 0, s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: {div} 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 if: runtime: O(n^2) [18 + 12*z'' + 2*z''*z1 + z''*z2 + z''^2 + 3*z1 + 2*z2], size: O(n^1) [1 + z'' + z2] 976.96/291.52 quot: runtime: O(n^2) [92 + 26*z' + 4*z'*z'' + z'*z1 + 2*z'^2 + 12*z'' + 6*z1], size: O(n^1) [2 + z' + z1] 976.96/291.52 div: runtime: ?, size: O(n^1) [2 + z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (51) IntTrsBoundProof (UPPER BOUND(ID)) 976.96/291.52 976.96/291.52 Computed RUNTIME bound using KoAT for: div 976.96/291.52 after applying outer abstraction to obtain an ITS, 976.96/291.52 resulting in: O(n^2) with polynomial bound: 93 + 26*z' + 4*z'*z'' + 2*z'^2 + 12*z'' 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (52) 976.96/291.52 Obligation: 976.96/291.52 Complexity RNTS consisting of the following rules: 976.96/291.52 976.96/291.52 div(z', z'') -{ 93 + 26*z' + 4*z'*z'' + 2*z'^2 + 12*z'' }-> s3 :|: s3 >= 0, s3 <= z' + 0 + 2, z' >= 0, z'' >= 0 976.96/291.52 if(z', z'', z1, z2) -{ 94 + 12*z1 + 6*z2 }-> s8 :|: s8 >= 0, s8 <= 0 + z2 + 2, z'' = 0, z2 >= 0, z1 - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 95 + 26*s' + 4*s'*z1 + s'*z2 + 2*s'^2 + 13*z1 + 6*z2 }-> s9 :|: s9 >= 0, s9 <= s' + z2 + 2, s' >= 0, s' <= z'' - 1, z2 >= 0, z1 - 1 >= 0, z'' - 1 >= 0, z' = 0 976.96/291.52 if(z', z'', z1, z2) -{ 2 }-> z2 - 1 :|: z2 >= 0, z'' >= 0, z1 >= 0, z' = 1, z2 - 1 >= 0 976.96/291.52 minus(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= z' - 1, z' - 1 >= 0, z'' - 1 >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> z' :|: z'' = 0, z' >= 0 976.96/291.52 minus(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 976.96/291.52 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 976.96/291.52 plus(z', z'') -{ 1 + z' }-> s'' :|: s'' >= 0, s'' <= z' - 1 + (1 + z''), z' - 1 >= 0, z'' >= 0 976.96/291.52 plus(z', z'') -{ 1 }-> z'' :|: z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 13*z' + 2*z'*z'' + z'^2 + 3*z'' }-> s4 :|: s4 >= 0, s4 <= 1 + 0 + 1 + (1 + (z' - 1)), z1 = 0, z' - 1 >= 0, z'' >= 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s1 + s1*z' + 12*z' + 2*z'*z'' + z'^2 + 3*z'' + z1 }-> s5 :|: s5 >= 0, s5 <= s1 + 1 + (1 + (z' - 1)), s1 >= 0, s1 <= z1 - 1 + (1 + (1 + 0)), z' - 1 >= 0, z'' >= 0, z1 - 1 >= 0 976.96/291.52 quot(z', z'', z1) -{ 23 + 3*z'' }-> s6 :|: s6 >= 0, s6 <= 1 + 0 + 1 + 0, z1 = 0, z'' >= 0, z' = 0 976.96/291.52 quot(z', z'', z1) -{ 21 + 2*s2 + 3*z'' + z1 }-> s7 :|: s7 >= 0, s7 <= s2 + 1 + 0, s2 >= 0, s2 <= z1 - 1 + (1 + (1 + 0)), z1 - 1 >= 0, z'' >= 0, z' = 0 976.96/291.52 zero(z') -{ 1 }-> 1 :|: z' = 0 976.96/291.52 zero(z') -{ 1 }-> 0 :|: z' - 1 >= 0 976.96/291.52 976.96/291.52 Function symbols to be analyzed: 976.96/291.52 Previous analysis results are: 976.96/291.52 minus: runtime: O(n^1) [2 + z''], size: O(n^1) [z'] 976.96/291.52 zero: runtime: O(1) [1], size: O(1) [1] 976.96/291.52 plus: runtime: O(n^1) [1 + z'], size: O(n^1) [z' + z''] 976.96/291.52 p: runtime: O(1) [1], size: O(n^1) [z'] 976.96/291.52 if: runtime: O(n^2) [18 + 12*z'' + 2*z''*z1 + z''*z2 + z''^2 + 3*z1 + 2*z2], size: O(n^1) [1 + z'' + z2] 976.96/291.52 quot: runtime: O(n^2) [92 + 26*z' + 4*z'*z'' + z'*z1 + 2*z'^2 + 12*z'' + 6*z1], size: O(n^1) [2 + z' + z1] 976.96/291.52 div: runtime: O(n^2) [93 + 26*z' + 4*z'*z'' + 2*z'^2 + 12*z''], size: O(n^1) [2 + z'] 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (53) FinalProof (FINISHED) 976.96/291.52 Computed overall runtime complexity 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (54) 976.96/291.52 BOUNDS(1, n^2) 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (55) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 976.96/291.52 Transformed a relative TRS into a decreasing-loop problem. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (56) 976.96/291.52 Obligation: 976.96/291.52 Analyzing the following TRS for decreasing loops: 976.96/291.52 976.96/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 976.96/291.52 976.96/291.52 976.96/291.52 The TRS R consists of the following rules: 976.96/291.52 976.96/291.52 minus(0, y) -> 0 976.96/291.52 minus(x, 0) -> x 976.96/291.52 minus(s(x), s(y)) -> minus(x, y) 976.96/291.52 plus(0, y) -> y 976.96/291.52 plus(s(x), y) -> plus(x, s(y)) 976.96/291.52 zero(s(x)) -> false 976.96/291.52 zero(0) -> true 976.96/291.52 p(s(x)) -> x 976.96/291.52 div(x, y) -> quot(x, y, 0) 976.96/291.52 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) 976.96/291.52 if(true, x, y, z) -> p(z) 976.96/291.52 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) 976.96/291.52 976.96/291.52 S is empty. 976.96/291.52 Rewrite Strategy: INNERMOST 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (57) DecreasingLoopProof (LOWER BOUND(ID)) 976.96/291.52 The following loop(s) give(s) rise to the lower bound Omega(n^1): 976.96/291.52 976.96/291.52 The rewrite sequence 976.96/291.52 976.96/291.52 minus(s(x), s(y)) ->^+ minus(x, y) 976.96/291.52 976.96/291.52 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 976.96/291.52 976.96/291.52 The pumping substitution is [x / s(x), y / s(y)]. 976.96/291.52 976.96/291.52 The result substitution is [ ]. 976.96/291.52 976.96/291.52 976.96/291.52 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (58) 976.96/291.52 Complex Obligation (BEST) 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (59) 976.96/291.52 Obligation: 976.96/291.52 Proved the lower bound n^1 for the following obligation: 976.96/291.52 976.96/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 976.96/291.52 976.96/291.52 976.96/291.52 The TRS R consists of the following rules: 976.96/291.52 976.96/291.52 minus(0, y) -> 0 976.96/291.52 minus(x, 0) -> x 976.96/291.52 minus(s(x), s(y)) -> minus(x, y) 976.96/291.52 plus(0, y) -> y 976.96/291.52 plus(s(x), y) -> plus(x, s(y)) 976.96/291.52 zero(s(x)) -> false 976.96/291.52 zero(0) -> true 976.96/291.52 p(s(x)) -> x 976.96/291.52 div(x, y) -> quot(x, y, 0) 976.96/291.52 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) 976.96/291.52 if(true, x, y, z) -> p(z) 976.96/291.52 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) 976.96/291.52 976.96/291.52 S is empty. 976.96/291.52 Rewrite Strategy: INNERMOST 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (60) LowerBoundPropagationProof (FINISHED) 976.96/291.52 Propagated lower bound. 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (61) 976.96/291.52 BOUNDS(n^1, INF) 976.96/291.52 976.96/291.52 ---------------------------------------- 976.96/291.52 976.96/291.52 (62) 976.96/291.52 Obligation: 976.96/291.52 Analyzing the following TRS for decreasing loops: 976.96/291.52 976.96/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 976.96/291.52 976.96/291.52 976.96/291.52 The TRS R consists of the following rules: 976.96/291.52 976.96/291.52 minus(0, y) -> 0 976.96/291.52 minus(x, 0) -> x 976.96/291.52 minus(s(x), s(y)) -> minus(x, y) 976.96/291.52 plus(0, y) -> y 976.96/291.52 plus(s(x), y) -> plus(x, s(y)) 976.96/291.52 zero(s(x)) -> false 976.96/291.52 zero(0) -> true 976.96/291.52 p(s(x)) -> x 976.96/291.52 div(x, y) -> quot(x, y, 0) 976.96/291.52 quot(x, y, z) -> if(zero(x), x, y, plus(z, s(0))) 976.96/291.52 if(true, x, y, z) -> p(z) 976.96/291.52 if(false, x, s(y), z) -> quot(minus(x, s(y)), s(y), z) 976.96/291.52 976.96/291.52 S is empty. 976.96/291.52 Rewrite Strategy: INNERMOST 977.10/291.57 EOF