1124.13/291.78 WORST_CASE(Omega(n^1), O(n^2)) 1124.27/291.83 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1124.27/291.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1124.27/291.83 1124.27/291.83 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1124.27/291.83 1124.27/291.83 (0) CpxTRS 1124.27/291.83 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.27/291.83 (2) CpxWeightedTrs 1124.27/291.83 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.27/291.83 (4) CpxTypedWeightedTrs 1124.27/291.83 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (6) CpxTypedWeightedCompleteTrs 1124.27/291.83 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.27/291.83 (8) CpxTypedWeightedCompleteTrs 1124.27/291.83 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (10) CpxRNTS 1124.27/291.83 (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.27/291.83 (12) CpxRNTS 1124.27/291.83 (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 3 ms] 1124.27/291.83 (14) CpxRNTS 1124.27/291.83 (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (16) CpxRNTS 1124.27/291.83 (17) IntTrsBoundProof [UPPER BOUND(ID), 222 ms] 1124.27/291.83 (18) CpxRNTS 1124.27/291.83 (19) IntTrsBoundProof [UPPER BOUND(ID), 98 ms] 1124.27/291.83 (20) CpxRNTS 1124.27/291.83 (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (22) CpxRNTS 1124.27/291.83 (23) IntTrsBoundProof [UPPER BOUND(ID), 354 ms] 1124.27/291.83 (24) CpxRNTS 1124.27/291.83 (25) IntTrsBoundProof [UPPER BOUND(ID), 135 ms] 1124.27/291.83 (26) CpxRNTS 1124.27/291.83 (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (28) CpxRNTS 1124.27/291.83 (29) IntTrsBoundProof [UPPER BOUND(ID), 360 ms] 1124.27/291.83 (30) CpxRNTS 1124.27/291.83 (31) IntTrsBoundProof [UPPER BOUND(ID), 155 ms] 1124.27/291.83 (32) CpxRNTS 1124.27/291.83 (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (34) CpxRNTS 1124.27/291.83 (35) IntTrsBoundProof [UPPER BOUND(ID), 97 ms] 1124.27/291.83 (36) CpxRNTS 1124.27/291.83 (37) IntTrsBoundProof [UPPER BOUND(ID), 12 ms] 1124.27/291.83 (38) CpxRNTS 1124.27/291.83 (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1124.27/291.83 (40) CpxRNTS 1124.27/291.83 (41) IntTrsBoundProof [UPPER BOUND(ID), 4253 ms] 1124.27/291.83 (42) CpxRNTS 1124.27/291.83 (43) IntTrsBoundProof [UPPER BOUND(ID), 1373 ms] 1124.27/291.83 (44) CpxRNTS 1124.27/291.83 (45) FinalProof [FINISHED, 0 ms] 1124.27/291.83 (46) BOUNDS(1, n^2) 1124.27/291.83 (47) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1124.27/291.83 (48) TRS for Loop Detection 1124.27/291.83 (49) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1124.27/291.83 (50) BEST 1124.27/291.83 (51) proven lower bound 1124.27/291.83 (52) LowerBoundPropagationProof [FINISHED, 0 ms] 1124.27/291.83 (53) BOUNDS(n^1, INF) 1124.27/291.83 (54) TRS for Loop Detection 1124.27/291.83 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (0) 1124.27/291.83 Obligation: 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1124.27/291.83 1124.27/291.83 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true 1124.27/291.83 le(s(x), 0) -> false 1124.27/291.83 le(s(x), s(y)) -> le(x, y) 1124.27/291.83 zero(0) -> true 1124.27/291.83 zero(s(x)) -> false 1124.27/291.83 id(0) -> 0 1124.27/291.83 id(s(x)) -> s(id(x)) 1124.27/291.83 minus(x, 0) -> x 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) 1124.27/291.83 if2(true, b2, x, y) -> 0 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) 1124.27/291.83 if3(false, x, y) -> x 1124.27/291.83 1124.27/291.83 S is empty. 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1124.27/291.83 Transformed relative TRS to weighted TRS 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (2) 1124.27/291.83 Obligation: 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1124.27/291.83 1124.27/291.83 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true [1] 1124.27/291.83 le(s(x), 0) -> false [1] 1124.27/291.83 le(s(x), s(y)) -> le(x, y) [1] 1124.27/291.83 zero(0) -> true [1] 1124.27/291.83 zero(s(x)) -> false [1] 1124.27/291.83 id(0) -> 0 [1] 1124.27/291.83 id(s(x)) -> s(id(x)) [1] 1124.27/291.83 minus(x, 0) -> x [1] 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) [1] 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) [1] 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 [1] 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) [1] 1124.27/291.83 if2(true, b2, x, y) -> 0 [1] 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) [1] 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) [1] 1124.27/291.83 if3(false, x, y) -> x [1] 1124.27/291.83 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1124.27/291.83 Infered types. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (4) 1124.27/291.83 Obligation: 1124.27/291.83 Runtime Complexity Weighted TRS with Types. 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true [1] 1124.27/291.83 le(s(x), 0) -> false [1] 1124.27/291.83 le(s(x), s(y)) -> le(x, y) [1] 1124.27/291.83 zero(0) -> true [1] 1124.27/291.83 zero(s(x)) -> false [1] 1124.27/291.83 id(0) -> 0 [1] 1124.27/291.83 id(s(x)) -> s(id(x)) [1] 1124.27/291.83 minus(x, 0) -> x [1] 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) [1] 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) [1] 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 [1] 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) [1] 1124.27/291.83 if2(true, b2, x, y) -> 0 [1] 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) [1] 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) [1] 1124.27/291.83 if3(false, x, y) -> x [1] 1124.27/291.83 1124.27/291.83 The TRS has the following type information: 1124.27/291.83 le :: 0:s -> 0:s -> true:false 1124.27/291.83 0 :: 0:s 1124.27/291.83 true :: true:false 1124.27/291.83 s :: 0:s -> 0:s 1124.27/291.83 false :: true:false 1124.27/291.83 zero :: 0:s -> true:false 1124.27/291.83 id :: 0:s -> 0:s 1124.27/291.83 minus :: 0:s -> 0:s -> 0:s 1124.27/291.83 mod :: 0:s -> 0:s -> 0:s 1124.27/291.83 if_mod :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if2 :: true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if3 :: true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (5) CompletionProof (UPPER BOUND(ID)) 1124.27/291.83 The transformation into a RNTS is sound, since: 1124.27/291.83 1124.27/291.83 (a) The obligation is a constructor system where every type has a constant constructor, 1124.27/291.83 1124.27/291.83 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1124.27/291.83 1124.27/291.83 mod_2 1124.27/291.83 if_mod_5 1124.27/291.83 if2_4 1124.27/291.83 if3_3 1124.27/291.83 1124.27/291.83 (c) The following functions are completely defined: 1124.27/291.83 1124.27/291.83 minus_2 1124.27/291.83 zero_1 1124.27/291.83 le_2 1124.27/291.83 id_1 1124.27/291.83 1124.27/291.83 Due to the following rules being added: 1124.27/291.83 1124.27/291.83 minus(v0, v1) -> 0 [0] 1124.27/291.83 1124.27/291.83 And the following fresh constants: none 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (6) 1124.27/291.83 Obligation: 1124.27/291.83 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1124.27/291.83 1124.27/291.83 Runtime Complexity Weighted TRS with Types. 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true [1] 1124.27/291.83 le(s(x), 0) -> false [1] 1124.27/291.83 le(s(x), s(y)) -> le(x, y) [1] 1124.27/291.83 zero(0) -> true [1] 1124.27/291.83 zero(s(x)) -> false [1] 1124.27/291.83 id(0) -> 0 [1] 1124.27/291.83 id(s(x)) -> s(id(x)) [1] 1124.27/291.83 minus(x, 0) -> x [1] 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) [1] 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) [1] 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 [1] 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) [1] 1124.27/291.83 if2(true, b2, x, y) -> 0 [1] 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) [1] 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) [1] 1124.27/291.83 if3(false, x, y) -> x [1] 1124.27/291.83 minus(v0, v1) -> 0 [0] 1124.27/291.83 1124.27/291.83 The TRS has the following type information: 1124.27/291.83 le :: 0:s -> 0:s -> true:false 1124.27/291.83 0 :: 0:s 1124.27/291.83 true :: true:false 1124.27/291.83 s :: 0:s -> 0:s 1124.27/291.83 false :: true:false 1124.27/291.83 zero :: 0:s -> true:false 1124.27/291.83 id :: 0:s -> 0:s 1124.27/291.83 minus :: 0:s -> 0:s -> 0:s 1124.27/291.83 mod :: 0:s -> 0:s -> 0:s 1124.27/291.83 if_mod :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if2 :: true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if3 :: true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 1124.27/291.83 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (8) 1124.27/291.83 Obligation: 1124.27/291.83 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1124.27/291.83 1124.27/291.83 Runtime Complexity Weighted TRS with Types. 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true [1] 1124.27/291.83 le(s(x), 0) -> false [1] 1124.27/291.83 le(s(x), s(y)) -> le(x, y) [1] 1124.27/291.83 zero(0) -> true [1] 1124.27/291.83 zero(s(x)) -> false [1] 1124.27/291.83 id(0) -> 0 [1] 1124.27/291.83 id(s(x)) -> s(id(x)) [1] 1124.27/291.83 minus(x, 0) -> x [1] 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) [1] 1124.27/291.83 mod(0, 0) -> if_mod(true, true, true, 0, 0) [6] 1124.27/291.83 mod(0, s(x'')) -> if_mod(true, false, false, 0, s(id(x''))) [6] 1124.27/291.83 mod(s(x'), 0) -> if_mod(false, true, true, s(id(x')), 0) [6] 1124.27/291.83 mod(s(x'), s(x1)) -> if_mod(false, false, le(x1, x'), s(id(x')), s(id(x1))) [6] 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 [1] 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) [1] 1124.27/291.83 if2(true, b2, x, y) -> 0 [1] 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) [1] 1124.27/291.83 if3(true, x, 0) -> mod(x, s(0)) [2] 1124.27/291.83 if3(true, s(x2), s(y')) -> mod(minus(x2, y'), s(s(y'))) [2] 1124.27/291.83 if3(true, x, y) -> mod(0, s(y)) [1] 1124.27/291.83 if3(false, x, y) -> x [1] 1124.27/291.83 minus(v0, v1) -> 0 [0] 1124.27/291.83 1124.27/291.83 The TRS has the following type information: 1124.27/291.83 le :: 0:s -> 0:s -> true:false 1124.27/291.83 0 :: 0:s 1124.27/291.83 true :: true:false 1124.27/291.83 s :: 0:s -> 0:s 1124.27/291.83 false :: true:false 1124.27/291.83 zero :: 0:s -> true:false 1124.27/291.83 id :: 0:s -> 0:s 1124.27/291.83 minus :: 0:s -> 0:s -> 0:s 1124.27/291.83 mod :: 0:s -> 0:s -> 0:s 1124.27/291.83 if_mod :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if2 :: true:false -> true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 if3 :: true:false -> 0:s -> 0:s -> 0:s 1124.27/291.83 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1124.27/291.83 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1124.27/291.83 The constant constructors are abstracted as follows: 1124.27/291.83 1124.27/291.83 0 => 0 1124.27/291.83 true => 1 1124.27/291.83 false => 0 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (10) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(x) :|: x >= 0, z = 1 + x 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(b2, x, y) :|: b2 >= 0, z1 = y, x >= 0, y >= 0, z' = b2, z'' = x, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: b2 >= 0, z1 = y, z = 1, x >= 0, y >= 0, z' = b2, z'' = x 1124.27/291.83 if3(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(x, 1 + 0) :|: z'' = 0, z' = x, z = 1, x >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(x2, y'), 1 + (1 + y')) :|: z' = 1 + x2, z = 1, y' >= 0, x2 >= 0, z'' = 1 + y' 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + y) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(b1, b2, x, y) :|: b2 >= 0, z2 = y, b1 >= 0, x >= 0, y >= 0, z' = b1, z = 0, z1 = x, z'' = b2 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: b2 >= 0, z2 = y, b1 >= 0, z = 1, x >= 0, y >= 0, z' = b1, z1 = x, z'' = b2 1124.27/291.83 le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(x'')) :|: z' = 1 + x'', x'' >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(x'), 0) :|: z = 1 + x', x' >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(x1, x'), 1 + id(x'), 1 + id(x1)) :|: z = 1 + x', x1 >= 0, x' >= 0, z' = 1 + x1 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: x >= 0, z = 1 + x 1124.27/291.83 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (11) SimplificationProof (BOTH BOUNDS(ID, ID)) 1124.27/291.83 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (12) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(z - 1) :|: z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(z' - 1)) :|: z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(z - 1), 0) :|: z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + id(z - 1), 1 + id(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1124.27/291.83 Found the following analysis order by SCC decomposition: 1124.27/291.83 1124.27/291.83 { id } 1124.27/291.83 { minus } 1124.27/291.83 { le } 1124.27/291.83 { zero } 1124.27/291.83 { mod, if_mod, if2, if3 } 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (14) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(z - 1) :|: z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(z' - 1)) :|: z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(z - 1), 0) :|: z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + id(z - 1), 1 + id(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {id}, {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (15) ResultPropagationProof (UPPER BOUND(ID)) 1124.27/291.83 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (16) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(z - 1) :|: z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(z' - 1)) :|: z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(z - 1), 0) :|: z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + id(z - 1), 1 + id(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {id}, {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (17) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed SIZE bound using CoFloCo for: id 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (18) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(z - 1) :|: z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(z' - 1)) :|: z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(z - 1), 0) :|: z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + id(z - 1), 1 + id(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {id}, {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: ?, size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (19) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using CoFloCo for: id 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: 1 + z 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (20) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 }-> 1 + id(z - 1) :|: z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 0, 0, 0, 1 + id(z' - 1)) :|: z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 1, 1, 1 + id(z - 1), 0) :|: z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + id(z - 1), 1 + id(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (21) ResultPropagationProof (UPPER BOUND(ID)) 1124.27/291.83 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (22) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (23) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed SIZE bound using KoAT for: minus 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (24) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {minus}, {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: ?, size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (25) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using CoFloCo for: minus 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: 1 + z' 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (26) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(minus(z' - 1, z'' - 1), 1 + (1 + (z'' - 1))) :|: z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (27) ResultPropagationProof (UPPER BOUND(ID)) 1124.27/291.83 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (28) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (29) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed SIZE bound using CoFloCo for: le 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(1) with polynomial bound: 1 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (30) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {le}, {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: ?, size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (31) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using KoAT for: le 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: 2 + z' 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (32) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z + z' }-> if_mod(0, 0, le(z' - 1, z - 1), 1 + s1, 1 + s2) :|: s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (33) ResultPropagationProof (UPPER BOUND(ID)) 1124.27/291.83 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (34) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (35) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed SIZE bound using CoFloCo for: zero 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(1) with polynomial bound: 1 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (36) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {zero}, {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 zero: runtime: ?, size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (37) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using CoFloCo for: zero 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(1) with polynomial bound: 1 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (38) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 zero: runtime: O(1) [1], size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (39) ResultPropagationProof (UPPER BOUND(ID)) 1124.27/291.83 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (40) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 zero: runtime: O(1) [1], size: O(1) [1] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (41) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed SIZE bound using KoAT for: mod 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z 1124.27/291.83 1124.27/291.83 Computed SIZE bound using KoAT for: if_mod 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z1 1124.27/291.83 1124.27/291.83 Computed SIZE bound using KoAT for: if2 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z'' 1124.27/291.83 1124.27/291.83 Computed SIZE bound using KoAT for: if3 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^1) with polynomial bound: z' 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (42) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: {mod,if_mod,if2,if3} 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 zero: runtime: O(1) [1], size: O(1) [1] 1124.27/291.83 mod: runtime: ?, size: O(n^1) [z] 1124.27/291.83 if_mod: runtime: ?, size: O(n^1) [z1] 1124.27/291.83 if2: runtime: ?, size: O(n^1) [z''] 1124.27/291.83 if3: runtime: ?, size: O(n^1) [z'] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (43) IntTrsBoundProof (UPPER BOUND(ID)) 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using KoAT for: mod 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^2) with polynomial bound: 51 + 31*z + 3*z*z' + 5*z^2 + 4*z' 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using KoAT for: if_mod 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^2) with polynomial bound: 146 + 58*z1 + 3*z1*z2 + 10*z1^2 + 6*z2 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using KoAT for: if2 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^2) with polynomial bound: 144 + 58*z'' + 3*z''*z1 + 10*z''^2 + 6*z1 1124.27/291.83 1124.27/291.83 Computed RUNTIME bound using KoAT for: if3 1124.27/291.83 after applying outer abstraction to obtain an ITS, 1124.27/291.83 resulting in: O(n^2) with polynomial bound: 142 + 58*z' + 3*z'*z'' + 10*z'^2 + 6*z'' 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (44) 1124.27/291.83 Obligation: 1124.27/291.83 Complexity RNTS consisting of the following rules: 1124.27/291.83 1124.27/291.83 id(z) -{ 1 }-> 0 :|: z = 0 1124.27/291.83 id(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> if3(z', z'', z1) :|: z' >= 0, z'' >= 0, z1 >= 0, z = 0 1124.27/291.83 if2(z, z', z'', z1) -{ 1 }-> 0 :|: z' >= 0, z = 1, z'' >= 0, z1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0, z = 0 1124.27/291.83 if3(z, z', z'') -{ 2 + z'' }-> mod(s4, 1 + (1 + (z'' - 1))) :|: s4 >= 0, s4 <= z' - 1, z = 1, z'' - 1 >= 0, z' - 1 >= 0 1124.27/291.83 if3(z, z', z'') -{ 2 }-> mod(z', 1 + 0) :|: z'' = 0, z = 1, z' >= 0 1124.27/291.83 if3(z, z', z'') -{ 1 }-> mod(0, 1 + z'') :|: z = 1, z' >= 0, z'' >= 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> if2(z', z'', z1, z2) :|: z'' >= 0, z' >= 0, z1 >= 0, z2 >= 0, z = 0 1124.27/291.83 if_mod(z, z', z'', z1, z2) -{ 1 }-> 0 :|: z'' >= 0, z' >= 0, z = 1, z1 >= 0, z2 >= 0 1124.27/291.83 le(z, z') -{ 2 + z' }-> s5 :|: s5 >= 0, s5 <= 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 le(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 1124.27/291.83 le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 1 + z' }-> s3 :|: s3 >= 0, s3 <= z - 1, z - 1 >= 0, z' - 1 >= 0 1124.27/291.83 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 1124.27/291.83 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 1124.27/291.83 mod(z, z') -{ 6 }-> if_mod(1, 1, 1, 0, 0) :|: z = 0, z' = 0 1124.27/291.83 mod(z, z') -{ 6 + z' }-> if_mod(1, 0, 0, 0, 1 + s') :|: s' >= 0, s' <= z' - 1, z' - 1 >= 0, z = 0 1124.27/291.83 mod(z, z') -{ 6 + z }-> if_mod(0, 1, 1, 1 + s'', 0) :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0, z' = 0 1124.27/291.83 mod(z, z') -{ 7 + 2*z + z' }-> if_mod(0, 0, s6, 1 + s1, 1 + s2) :|: s6 >= 0, s6 <= 1, s1 >= 0, s1 <= z - 1, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 1124.27/291.83 zero(z) -{ 1 }-> 1 :|: z = 0 1124.27/291.83 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 1124.27/291.83 1124.27/291.83 Function symbols to be analyzed: 1124.27/291.83 Previous analysis results are: 1124.27/291.83 id: runtime: O(n^1) [1 + z], size: O(n^1) [z] 1124.27/291.83 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 1124.27/291.83 le: runtime: O(n^1) [2 + z'], size: O(1) [1] 1124.27/291.83 zero: runtime: O(1) [1], size: O(1) [1] 1124.27/291.83 mod: runtime: O(n^2) [51 + 31*z + 3*z*z' + 5*z^2 + 4*z'], size: O(n^1) [z] 1124.27/291.83 if_mod: runtime: O(n^2) [146 + 58*z1 + 3*z1*z2 + 10*z1^2 + 6*z2], size: O(n^1) [z1] 1124.27/291.83 if2: runtime: O(n^2) [144 + 58*z'' + 3*z''*z1 + 10*z''^2 + 6*z1], size: O(n^1) [z''] 1124.27/291.83 if3: runtime: O(n^2) [142 + 58*z' + 3*z'*z'' + 10*z'^2 + 6*z''], size: O(n^1) [z'] 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (45) FinalProof (FINISHED) 1124.27/291.83 Computed overall runtime complexity 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (46) 1124.27/291.83 BOUNDS(1, n^2) 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (47) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1124.27/291.83 Transformed a relative TRS into a decreasing-loop problem. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (48) 1124.27/291.83 Obligation: 1124.27/291.83 Analyzing the following TRS for decreasing loops: 1124.27/291.83 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1124.27/291.83 1124.27/291.83 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true 1124.27/291.83 le(s(x), 0) -> false 1124.27/291.83 le(s(x), s(y)) -> le(x, y) 1124.27/291.83 zero(0) -> true 1124.27/291.83 zero(s(x)) -> false 1124.27/291.83 id(0) -> 0 1124.27/291.83 id(s(x)) -> s(id(x)) 1124.27/291.83 minus(x, 0) -> x 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) 1124.27/291.83 if2(true, b2, x, y) -> 0 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) 1124.27/291.83 if3(false, x, y) -> x 1124.27/291.83 1124.27/291.83 S is empty. 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (49) DecreasingLoopProof (LOWER BOUND(ID)) 1124.27/291.83 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1124.27/291.83 1124.27/291.83 The rewrite sequence 1124.27/291.83 1124.27/291.83 le(s(x), s(y)) ->^+ le(x, y) 1124.27/291.83 1124.27/291.83 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1124.27/291.83 1124.27/291.83 The pumping substitution is [x / s(x), y / s(y)]. 1124.27/291.83 1124.27/291.83 The result substitution is [ ]. 1124.27/291.83 1124.27/291.83 1124.27/291.83 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (50) 1124.27/291.83 Complex Obligation (BEST) 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (51) 1124.27/291.83 Obligation: 1124.27/291.83 Proved the lower bound n^1 for the following obligation: 1124.27/291.83 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1124.27/291.83 1124.27/291.83 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true 1124.27/291.83 le(s(x), 0) -> false 1124.27/291.83 le(s(x), s(y)) -> le(x, y) 1124.27/291.83 zero(0) -> true 1124.27/291.83 zero(s(x)) -> false 1124.27/291.83 id(0) -> 0 1124.27/291.83 id(s(x)) -> s(id(x)) 1124.27/291.83 minus(x, 0) -> x 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) 1124.27/291.83 if2(true, b2, x, y) -> 0 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) 1124.27/291.83 if3(false, x, y) -> x 1124.27/291.83 1124.27/291.83 S is empty. 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (52) LowerBoundPropagationProof (FINISHED) 1124.27/291.83 Propagated lower bound. 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (53) 1124.27/291.83 BOUNDS(n^1, INF) 1124.27/291.83 1124.27/291.83 ---------------------------------------- 1124.27/291.83 1124.27/291.83 (54) 1124.27/291.83 Obligation: 1124.27/291.83 Analyzing the following TRS for decreasing loops: 1124.27/291.83 1124.27/291.83 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1124.27/291.83 1124.27/291.83 1124.27/291.83 The TRS R consists of the following rules: 1124.27/291.83 1124.27/291.83 le(0, y) -> true 1124.27/291.83 le(s(x), 0) -> false 1124.27/291.83 le(s(x), s(y)) -> le(x, y) 1124.27/291.83 zero(0) -> true 1124.27/291.83 zero(s(x)) -> false 1124.27/291.83 id(0) -> 0 1124.27/291.83 id(s(x)) -> s(id(x)) 1124.27/291.83 minus(x, 0) -> x 1124.27/291.83 minus(s(x), s(y)) -> minus(x, y) 1124.27/291.83 mod(x, y) -> if_mod(zero(x), zero(y), le(y, x), id(x), id(y)) 1124.27/291.83 if_mod(true, b1, b2, x, y) -> 0 1124.27/291.83 if_mod(false, b1, b2, x, y) -> if2(b1, b2, x, y) 1124.27/291.83 if2(true, b2, x, y) -> 0 1124.27/291.83 if2(false, b2, x, y) -> if3(b2, x, y) 1124.27/291.83 if3(true, x, y) -> mod(minus(x, y), s(y)) 1124.27/291.83 if3(false, x, y) -> x 1124.27/291.83 1124.27/291.83 S is empty. 1124.27/291.83 Rewrite Strategy: INNERMOST 1124.36/291.91 EOF