318.34/291.56 WORST_CASE(Omega(n^1), O(n^2)) 318.34/291.58 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 318.34/291.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 318.34/291.58 318.34/291.58 318.34/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 318.34/291.58 318.34/291.58 (0) CpxTRS 318.34/291.58 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (2) CpxWeightedTrs 318.34/291.58 (3) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (4) CpxWeightedTrs 318.34/291.58 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (6) CpxTypedWeightedTrs 318.34/291.58 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (8) CpxTypedWeightedCompleteTrs 318.34/291.58 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (10) CpxTypedWeightedCompleteTrs 318.34/291.58 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (12) CpxRNTS 318.34/291.58 (13) InliningProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (14) CpxRNTS 318.34/291.58 (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (16) CpxRNTS 318.34/291.58 (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 4 ms] 318.34/291.58 (18) CpxRNTS 318.34/291.58 (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (20) CpxRNTS 318.34/291.58 (21) IntTrsBoundProof [UPPER BOUND(ID), 375 ms] 318.34/291.58 (22) CpxRNTS 318.34/291.58 (23) IntTrsBoundProof [UPPER BOUND(ID), 99 ms] 318.34/291.58 (24) CpxRNTS 318.34/291.58 (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (26) CpxRNTS 318.34/291.58 (27) IntTrsBoundProof [UPPER BOUND(ID), 332 ms] 318.34/291.58 (28) CpxRNTS 318.34/291.58 (29) IntTrsBoundProof [UPPER BOUND(ID), 156 ms] 318.34/291.58 (30) CpxRNTS 318.34/291.58 (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (32) CpxRNTS 318.34/291.58 (33) IntTrsBoundProof [UPPER BOUND(ID), 331 ms] 318.34/291.58 (34) CpxRNTS 318.34/291.58 (35) IntTrsBoundProof [UPPER BOUND(ID), 73 ms] 318.34/291.58 (36) CpxRNTS 318.34/291.58 (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 318.34/291.58 (38) CpxRNTS 318.34/291.58 (39) IntTrsBoundProof [UPPER BOUND(ID), 1030 ms] 318.34/291.58 (40) CpxRNTS 318.34/291.58 (41) IntTrsBoundProof [UPPER BOUND(ID), 551 ms] 318.34/291.58 (42) CpxRNTS 318.34/291.58 (43) FinalProof [FINISHED, 0 ms] 318.34/291.58 (44) BOUNDS(1, n^2) 318.34/291.58 (45) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (46) CpxTRS 318.34/291.58 (47) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 318.34/291.58 (48) typed CpxTrs 318.34/291.58 (49) OrderProof [LOWER BOUND(ID), 0 ms] 318.34/291.58 (50) typed CpxTrs 318.34/291.58 (51) RewriteLemmaProof [LOWER BOUND(ID), 271 ms] 318.34/291.58 (52) BEST 318.34/291.58 (53) proven lower bound 318.34/291.58 (54) LowerBoundPropagationProof [FINISHED, 0 ms] 318.34/291.58 (55) BOUNDS(n^1, INF) 318.34/291.58 (56) typed CpxTrs 318.34/291.58 (57) RewriteLemmaProof [LOWER BOUND(ID), 47 ms] 318.34/291.58 (58) typed CpxTrs 318.34/291.58 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (0) 318.34/291.58 Obligation: 318.34/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 318.34/291.58 318.34/291.58 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true 318.34/291.58 leq(s(x), 0) -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0) -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0, y) -> 0 318.34/291.58 mod(s(x), 0) -> 0 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 S is empty. 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Transformed relative TRS to weighted TRS 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (2) 318.34/291.58 Obligation: 318.34/291.58 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 318.34/291.58 318.34/291.58 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true [1] 318.34/291.58 leq(s(x), 0) -> false [1] 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) [1] 318.34/291.58 if(true, x, y) -> x [1] 318.34/291.58 if(false, x, y) -> y [1] 318.34/291.58 -(x, 0) -> x [1] 318.34/291.58 -(s(x), s(y)) -> -(x, y) [1] 318.34/291.58 mod(0, y) -> 0 [1] 318.34/291.58 mod(s(x), 0) -> 0 [1] 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) [1] 318.34/291.58 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Renamed defined symbols to avoid conflicts with arithmetic symbols: 318.34/291.58 318.34/291.58 - => minus 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (4) 318.34/291.58 Obligation: 318.34/291.58 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 318.34/291.58 318.34/291.58 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true [1] 318.34/291.58 leq(s(x), 0) -> false [1] 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) [1] 318.34/291.58 if(true, x, y) -> x [1] 318.34/291.58 if(false, x, y) -> y [1] 318.34/291.58 minus(x, 0) -> x [1] 318.34/291.58 minus(s(x), s(y)) -> minus(x, y) [1] 318.34/291.58 mod(0, y) -> 0 [1] 318.34/291.58 mod(s(x), 0) -> 0 [1] 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 318.34/291.58 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Infered types. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (6) 318.34/291.58 Obligation: 318.34/291.58 Runtime Complexity Weighted TRS with Types. 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true [1] 318.34/291.58 leq(s(x), 0) -> false [1] 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) [1] 318.34/291.58 if(true, x, y) -> x [1] 318.34/291.58 if(false, x, y) -> y [1] 318.34/291.58 minus(x, 0) -> x [1] 318.34/291.58 minus(s(x), s(y)) -> minus(x, y) [1] 318.34/291.58 mod(0, y) -> 0 [1] 318.34/291.58 mod(s(x), 0) -> 0 [1] 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 318.34/291.58 318.34/291.58 The TRS has the following type information: 318.34/291.58 leq :: 0:s -> 0:s -> true:false 318.34/291.58 0 :: 0:s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0:s -> 0:s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0:s -> 0:s -> 0:s 318.34/291.58 minus :: 0:s -> 0:s -> 0:s 318.34/291.58 mod :: 0:s -> 0:s -> 0:s 318.34/291.58 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (7) CompletionProof (UPPER BOUND(ID)) 318.34/291.58 The transformation into a RNTS is sound, since: 318.34/291.58 318.34/291.58 (a) The obligation is a constructor system where every type has a constant constructor, 318.34/291.58 318.34/291.58 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 318.34/291.58 none 318.34/291.58 318.34/291.58 (c) The following functions are completely defined: 318.34/291.58 318.34/291.58 leq_2 318.34/291.58 mod_2 318.34/291.58 minus_2 318.34/291.58 if_3 318.34/291.58 318.34/291.58 Due to the following rules being added: 318.34/291.58 318.34/291.58 minus(v0, v1) -> 0 [0] 318.34/291.58 318.34/291.58 And the following fresh constants: none 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (8) 318.34/291.58 Obligation: 318.34/291.58 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 318.34/291.58 318.34/291.58 Runtime Complexity Weighted TRS with Types. 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true [1] 318.34/291.58 leq(s(x), 0) -> false [1] 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) [1] 318.34/291.58 if(true, x, y) -> x [1] 318.34/291.58 if(false, x, y) -> y [1] 318.34/291.58 minus(x, 0) -> x [1] 318.34/291.58 minus(s(x), s(y)) -> minus(x, y) [1] 318.34/291.58 mod(0, y) -> 0 [1] 318.34/291.58 mod(s(x), 0) -> 0 [1] 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 318.34/291.58 minus(v0, v1) -> 0 [0] 318.34/291.58 318.34/291.58 The TRS has the following type information: 318.34/291.58 leq :: 0:s -> 0:s -> true:false 318.34/291.58 0 :: 0:s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0:s -> 0:s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0:s -> 0:s -> 0:s 318.34/291.58 minus :: 0:s -> 0:s -> 0:s 318.34/291.58 mod :: 0:s -> 0:s -> 0:s 318.34/291.58 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (10) 318.34/291.58 Obligation: 318.34/291.58 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 318.34/291.58 318.34/291.58 Runtime Complexity Weighted TRS with Types. 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0, y) -> true [1] 318.34/291.58 leq(s(x), 0) -> false [1] 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) [1] 318.34/291.58 if(true, x, y) -> x [1] 318.34/291.58 if(false, x, y) -> y [1] 318.34/291.58 minus(x, 0) -> x [1] 318.34/291.58 minus(s(x), s(y)) -> minus(x, y) [1] 318.34/291.58 mod(0, y) -> 0 [1] 318.34/291.58 mod(s(x), 0) -> 0 [1] 318.34/291.58 mod(s(x), s(0)) -> if(true, mod(minus(x, 0), s(0)), s(x)) [3] 318.34/291.58 mod(s(x), s(0)) -> if(true, mod(0, s(0)), s(x)) [2] 318.34/291.58 mod(s(0), s(s(x'))) -> if(false, mod(minus(0, s(x')), s(s(x'))), s(0)) [3] 318.34/291.58 mod(s(0), s(s(x'))) -> if(false, mod(0, s(s(x'))), s(0)) [2] 318.34/291.58 mod(s(s(y')), s(s(x''))) -> if(leq(x'', y'), mod(minus(s(y'), s(x'')), s(s(x''))), s(s(y'))) [3] 318.34/291.58 mod(s(s(y')), s(s(x''))) -> if(leq(x'', y'), mod(0, s(s(x''))), s(s(y'))) [2] 318.34/291.58 minus(v0, v1) -> 0 [0] 318.34/291.58 318.34/291.58 The TRS has the following type information: 318.34/291.58 leq :: 0:s -> 0:s -> true:false 318.34/291.58 0 :: 0:s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0:s -> 0:s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0:s -> 0:s -> 0:s 318.34/291.58 minus :: 0:s -> 0:s -> 0:s 318.34/291.58 mod :: 0:s -> 0:s -> 0:s 318.34/291.58 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 318.34/291.58 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 318.34/291.58 The constant constructors are abstracted as follows: 318.34/291.58 318.34/291.58 0 => 0 318.34/291.58 true => 1 318.34/291.58 false => 0 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (12) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(x'', y'), mod(minus(1 + y', 1 + x''), 1 + (1 + x'')), 1 + (1 + y')) :|: z' = 1 + (1 + x''), z = 1 + (1 + y'), y' >= 0, x'' >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(x'', y'), mod(0, 1 + (1 + x'')), 1 + (1 + y')) :|: z' = 1 + (1 + x''), z = 1 + (1 + y'), y' >= 0, x'' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(x, 0), 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + x'), 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 318.34/291.58 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (13) InliningProof (UPPER BOUND(ID)) 318.34/291.58 Inlined the following terminating rules on right-hand sides where appropriate: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 318.34/291.58 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (14) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(x'', y'), mod(minus(1 + y', 1 + x''), 1 + (1 + x'')), 1 + (1 + y')) :|: z' = 1 + (1 + x''), z = 1 + (1 + y'), y' >= 0, x'' >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(x'', y'), mod(0, 1 + (1 + x'')), 1 + (1 + y')) :|: z' = 1 + (1 + x''), z = 1 + (1 + y'), y' >= 0, x'' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(x, 0), 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + x'), 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 318.34/291.58 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (15) SimplificationProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (16) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(z' - 2, z - 2), mod(minus(1 + (z - 2), 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Found the following analysis order by SCC decomposition: 318.34/291.58 318.34/291.58 { minus } 318.34/291.58 { leq } 318.34/291.58 { if } 318.34/291.58 { mod } 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (18) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(z' - 2, z - 2), mod(minus(1 + (z - 2), 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (19) ResultPropagationProof (UPPER BOUND(ID)) 318.34/291.58 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (20) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(z' - 2, z - 2), mod(minus(1 + (z - 2), 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (21) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed SIZE bound using KoAT for: minus 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^1) with polynomial bound: z 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (22) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(z' - 2, z - 2), mod(minus(1 + (z - 2), 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: ?, size: O(n^1) [z] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (23) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed RUNTIME bound using CoFloCo for: minus 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^1) with polynomial bound: 1 + z' 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (24) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(leq(z' - 2, z - 2), mod(minus(1 + (z - 2), 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {leq}, {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (25) ResultPropagationProof (UPPER BOUND(ID)) 318.34/291.58 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (26) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(leq(z' - 2, z - 2), mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {leq}, {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (27) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed SIZE bound using CoFloCo for: leq 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(1) with polynomial bound: 1 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (28) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(leq(z' - 2, z - 2), mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {leq}, {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: ?, size: O(1) [1] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (29) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed RUNTIME bound using KoAT for: leq 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^1) with polynomial bound: 2 + z' 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (30) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(leq(z' - 2, z - 2), mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(leq(z' - 2, z - 2), mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (31) ResultPropagationProof (UPPER BOUND(ID)) 318.34/291.58 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (32) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (33) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed SIZE bound using CoFloCo for: if 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^1) with polynomial bound: z' + z'' 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (34) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {if}, {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 if: runtime: ?, size: O(n^1) [z' + z''] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (35) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed RUNTIME bound using CoFloCo for: if 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(1) with polynomial bound: 1 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (36) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (37) ResultPropagationProof (UPPER BOUND(ID)) 318.34/291.58 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (38) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (39) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed SIZE bound using CoFloCo for: mod 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^2) with polynomial bound: 1 + z + z^2 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (40) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: {mod} 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 318.34/291.58 mod: runtime: ?, size: O(n^2) [1 + z + z^2] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (41) IntTrsBoundProof (UPPER BOUND(ID)) 318.34/291.58 318.34/291.58 Computed RUNTIME bound using CoFloCo for: mod 318.34/291.58 after applying outer abstraction to obtain an ITS, 318.34/291.58 resulting in: O(n^2) with polynomial bound: 13 + 7*z + z*z' + z^2 + 3*z' 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (42) 318.34/291.58 Obligation: 318.34/291.58 Complexity RNTS consisting of the following rules: 318.34/291.58 318.34/291.58 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 318.34/291.58 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 318.34/291.58 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 318.34/291.58 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 318.34/291.58 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 318.34/291.58 mod(z, z') -{ 3 + z + z' }-> if(s3, mod(s1, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s3 >= 0, s3 <= 1, s1 >= 0, s1 <= 1 + (z - 2), z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 + z }-> if(s4, mod(0, 1 + (1 + (z' - 2))), 1 + (1 + (z - 2))) :|: s4 >= 0, s4 <= 1, z - 2 >= 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 318.34/291.58 mod(z, z') -{ 3 + z' }-> if(0, mod(s'', 1 + (1 + (z' - 2))), 1 + 0) :|: s'' >= 0, s'' <= 0, z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 318.34/291.58 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 318.34/291.58 318.34/291.58 Function symbols to be analyzed: 318.34/291.58 Previous analysis results are: 318.34/291.58 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 318.34/291.58 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 318.34/291.58 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 318.34/291.58 mod: runtime: O(n^2) [13 + 7*z + z*z' + z^2 + 3*z'], size: O(n^2) [1 + z + z^2] 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (43) FinalProof (FINISHED) 318.34/291.58 Computed overall runtime complexity 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (44) 318.34/291.58 BOUNDS(1, n^2) 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (45) RenamingProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Renamed function symbols to avoid clashes with predefined symbol. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (46) 318.34/291.58 Obligation: 318.34/291.58 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 318.34/291.58 318.34/291.58 318.34/291.58 The TRS R consists of the following rules: 318.34/291.58 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 S is empty. 318.34/291.58 Rewrite Strategy: INNERMOST 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (47) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 318.34/291.58 Infered types. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (48) 318.34/291.58 Obligation: 318.34/291.58 Innermost TRS: 318.34/291.58 Rules: 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 Types: 318.34/291.58 leq :: 0':s -> 0':s -> true:false 318.34/291.58 0' :: 0':s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0':s -> 0':s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0':s -> 0':s -> 0':s 318.34/291.58 - :: 0':s -> 0':s -> 0':s 318.34/291.58 mod :: 0':s -> 0':s -> 0':s 318.34/291.58 hole_true:false1_0 :: true:false 318.34/291.58 hole_0':s2_0 :: 0':s 318.34/291.58 gen_0':s3_0 :: Nat -> 0':s 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (49) OrderProof (LOWER BOUND(ID)) 318.34/291.58 Heuristically decided to analyse the following defined symbols: 318.34/291.58 leq, -, mod 318.34/291.58 318.34/291.58 They will be analysed ascendingly in the following order: 318.34/291.58 leq < mod 318.34/291.58 - < mod 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (50) 318.34/291.58 Obligation: 318.34/291.58 Innermost TRS: 318.34/291.58 Rules: 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 Types: 318.34/291.58 leq :: 0':s -> 0':s -> true:false 318.34/291.58 0' :: 0':s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0':s -> 0':s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0':s -> 0':s -> 0':s 318.34/291.58 - :: 0':s -> 0':s -> 0':s 318.34/291.58 mod :: 0':s -> 0':s -> 0':s 318.34/291.58 hole_true:false1_0 :: true:false 318.34/291.58 hole_0':s2_0 :: 0':s 318.34/291.58 gen_0':s3_0 :: Nat -> 0':s 318.34/291.58 318.34/291.58 318.34/291.58 Generator Equations: 318.34/291.58 gen_0':s3_0(0) <=> 0' 318.34/291.58 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 318.34/291.58 318.34/291.58 318.34/291.58 The following defined symbols remain to be analysed: 318.34/291.58 leq, -, mod 318.34/291.58 318.34/291.58 They will be analysed ascendingly in the following order: 318.34/291.58 leq < mod 318.34/291.58 - < mod 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (51) RewriteLemmaProof (LOWER BOUND(ID)) 318.34/291.58 Proved the following rewrite lemma: 318.34/291.58 leq(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 318.34/291.58 318.34/291.58 Induction Base: 318.34/291.58 leq(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 318.34/291.58 true 318.34/291.58 318.34/291.58 Induction Step: 318.34/291.58 leq(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1) 318.34/291.58 leq(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) ->_IH 318.34/291.58 true 318.34/291.58 318.34/291.58 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (52) 318.34/291.58 Complex Obligation (BEST) 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (53) 318.34/291.58 Obligation: 318.34/291.58 Proved the lower bound n^1 for the following obligation: 318.34/291.58 318.34/291.58 Innermost TRS: 318.34/291.58 Rules: 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 Types: 318.34/291.58 leq :: 0':s -> 0':s -> true:false 318.34/291.58 0' :: 0':s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0':s -> 0':s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0':s -> 0':s -> 0':s 318.34/291.58 - :: 0':s -> 0':s -> 0':s 318.34/291.58 mod :: 0':s -> 0':s -> 0':s 318.34/291.58 hole_true:false1_0 :: true:false 318.34/291.58 hole_0':s2_0 :: 0':s 318.34/291.58 gen_0':s3_0 :: Nat -> 0':s 318.34/291.58 318.34/291.58 318.34/291.58 Generator Equations: 318.34/291.58 gen_0':s3_0(0) <=> 0' 318.34/291.58 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 318.34/291.58 318.34/291.58 318.34/291.58 The following defined symbols remain to be analysed: 318.34/291.58 leq, -, mod 318.34/291.58 318.34/291.58 They will be analysed ascendingly in the following order: 318.34/291.58 leq < mod 318.34/291.58 - < mod 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (54) LowerBoundPropagationProof (FINISHED) 318.34/291.58 Propagated lower bound. 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (55) 318.34/291.58 BOUNDS(n^1, INF) 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (56) 318.34/291.58 Obligation: 318.34/291.58 Innermost TRS: 318.34/291.58 Rules: 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 Types: 318.34/291.58 leq :: 0':s -> 0':s -> true:false 318.34/291.58 0' :: 0':s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0':s -> 0':s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0':s -> 0':s -> 0':s 318.34/291.58 - :: 0':s -> 0':s -> 0':s 318.34/291.58 mod :: 0':s -> 0':s -> 0':s 318.34/291.58 hole_true:false1_0 :: true:false 318.34/291.58 hole_0':s2_0 :: 0':s 318.34/291.58 gen_0':s3_0 :: Nat -> 0':s 318.34/291.58 318.34/291.58 318.34/291.58 Lemmas: 318.34/291.58 leq(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 318.34/291.58 318.34/291.58 318.34/291.58 Generator Equations: 318.34/291.58 gen_0':s3_0(0) <=> 0' 318.34/291.58 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 318.34/291.58 318.34/291.58 318.34/291.58 The following defined symbols remain to be analysed: 318.34/291.58 -, mod 318.34/291.58 318.34/291.58 They will be analysed ascendingly in the following order: 318.34/291.58 - < mod 318.34/291.58 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (57) RewriteLemmaProof (LOWER BOUND(ID)) 318.34/291.58 Proved the following rewrite lemma: 318.34/291.58 -(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) -> gen_0':s3_0(0), rt in Omega(1 + n294_0) 318.34/291.58 318.34/291.58 Induction Base: 318.34/291.58 -(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 318.34/291.58 gen_0':s3_0(0) 318.34/291.58 318.34/291.58 Induction Step: 318.34/291.58 -(gen_0':s3_0(+(n294_0, 1)), gen_0':s3_0(+(n294_0, 1))) ->_R^Omega(1) 318.34/291.58 -(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) ->_IH 318.34/291.58 gen_0':s3_0(0) 318.34/291.58 318.34/291.58 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 318.34/291.58 ---------------------------------------- 318.34/291.58 318.34/291.58 (58) 318.34/291.58 Obligation: 318.34/291.58 Innermost TRS: 318.34/291.58 Rules: 318.34/291.58 leq(0', y) -> true 318.34/291.58 leq(s(x), 0') -> false 318.34/291.58 leq(s(x), s(y)) -> leq(x, y) 318.34/291.58 if(true, x, y) -> x 318.34/291.58 if(false, x, y) -> y 318.34/291.58 -(x, 0') -> x 318.34/291.58 -(s(x), s(y)) -> -(x, y) 318.34/291.58 mod(0', y) -> 0' 318.34/291.58 mod(s(x), 0') -> 0' 318.34/291.58 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 318.34/291.58 318.34/291.58 Types: 318.34/291.58 leq :: 0':s -> 0':s -> true:false 318.34/291.58 0' :: 0':s 318.34/291.58 true :: true:false 318.34/291.58 s :: 0':s -> 0':s 318.34/291.58 false :: true:false 318.34/291.58 if :: true:false -> 0':s -> 0':s -> 0':s 318.34/291.58 - :: 0':s -> 0':s -> 0':s 318.34/291.58 mod :: 0':s -> 0':s -> 0':s 318.34/291.58 hole_true:false1_0 :: true:false 318.34/291.58 hole_0':s2_0 :: 0':s 318.34/291.58 gen_0':s3_0 :: Nat -> 0':s 318.34/291.58 318.34/291.58 318.34/291.58 Lemmas: 318.34/291.58 leq(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 318.34/291.58 -(gen_0':s3_0(n294_0), gen_0':s3_0(n294_0)) -> gen_0':s3_0(0), rt in Omega(1 + n294_0) 318.34/291.58 318.34/291.58 318.34/291.58 Generator Equations: 318.34/291.58 gen_0':s3_0(0) <=> 0' 318.34/291.58 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 318.34/291.58 318.34/291.58 318.34/291.58 The following defined symbols remain to be analysed: 318.34/291.58 mod 318.45/291.61 EOF