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