317.05/291.54 WORST_CASE(Omega(n^1), O(n^2)) 317.05/291.56 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 317.05/291.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 317.05/291.56 317.05/291.56 317.05/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 317.05/291.56 317.05/291.56 (0) CpxTRS 317.05/291.56 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (2) CpxTRS 317.05/291.56 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (4) CpxWeightedTrs 317.05/291.56 (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (6) CpxWeightedTrs 317.05/291.56 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (8) CpxTypedWeightedTrs 317.05/291.56 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (10) CpxTypedWeightedCompleteTrs 317.05/291.56 (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (12) CpxTypedWeightedCompleteTrs 317.05/291.56 (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (14) CpxRNTS 317.05/291.56 (15) InliningProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (16) CpxRNTS 317.05/291.56 (17) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 317.05/291.56 (18) CpxRNTS 317.05/291.56 (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 3 ms] 317.05/291.56 (20) CpxRNTS 317.05/291.56 (21) ResultPropagationProof [UPPER BOUND(ID), 1 ms] 317.05/291.56 (22) CpxRNTS 317.05/291.56 (23) IntTrsBoundProof [UPPER BOUND(ID), 479 ms] 317.05/291.56 (24) CpxRNTS 317.05/291.56 (25) IntTrsBoundProof [UPPER BOUND(ID), 159 ms] 317.05/291.56 (26) CpxRNTS 317.05/291.56 (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (28) CpxRNTS 317.05/291.56 (29) IntTrsBoundProof [UPPER BOUND(ID), 272 ms] 317.05/291.56 (30) CpxRNTS 317.05/291.56 (31) IntTrsBoundProof [UPPER BOUND(ID), 117 ms] 317.05/291.56 (32) CpxRNTS 317.05/291.56 (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (34) CpxRNTS 317.05/291.56 (35) IntTrsBoundProof [UPPER BOUND(ID), 281 ms] 317.05/291.56 (36) CpxRNTS 317.05/291.56 (37) IntTrsBoundProof [UPPER BOUND(ID), 73 ms] 317.05/291.56 (38) CpxRNTS 317.05/291.56 (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 317.05/291.56 (40) CpxRNTS 317.05/291.56 (41) IntTrsBoundProof [UPPER BOUND(ID), 1091 ms] 317.05/291.56 (42) CpxRNTS 317.05/291.56 (43) IntTrsBoundProof [UPPER BOUND(ID), 551 ms] 317.05/291.56 (44) CpxRNTS 317.05/291.56 (45) FinalProof [FINISHED, 0 ms] 317.05/291.56 (46) BOUNDS(1, n^2) 317.05/291.56 (47) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 317.05/291.56 (48) TRS for Loop Detection 317.05/291.56 (49) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 317.05/291.56 (50) BEST 317.05/291.56 (51) proven lower bound 317.05/291.56 (52) LowerBoundPropagationProof [FINISHED, 0 ms] 317.05/291.56 (53) BOUNDS(n^1, INF) 317.05/291.56 (54) TRS for Loop Detection 317.05/291.56 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (0) 317.05/291.56 Obligation: 317.05/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true 317.05/291.56 leq(s(x), 0) -> false 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) 317.05/291.56 if(true, x, y) -> x 317.05/291.56 if(false, x, y) -> y 317.05/291.56 -(x, 0) -> x 317.05/291.56 -(s(x), s(y)) -> -(x, y) 317.05/291.56 mod(0, y) -> 0 317.05/291.56 mod(s(x), 0) -> 0 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 317.05/291.56 317.05/291.56 S is empty. 317.05/291.56 Rewrite Strategy: FULL 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Converted rc-obligation to irc-obligation. 317.05/291.56 317.05/291.56 The duplicating contexts are: 317.05/291.56 mod(s(x), s([])) 317.05/291.56 mod(s([]), s(y)) 317.05/291.56 317.05/291.56 317.05/291.56 The defined contexts are: 317.05/291.56 if([], x1, s(x2)) 317.05/291.56 if(x0, [], s(x2)) 317.05/291.56 mod([], s(x1)) 317.05/291.56 leq(x0, []) 317.05/291.56 -(s([]), s(x1)) 317.05/291.56 if(x0, x1, s([])) 317.05/291.56 -([], x1) 317.05/291.56 317.05/291.56 317.05/291.56 [] just represents basic- or constructor-terms in the following defined contexts: 317.05/291.56 if([], x1, s(x2)) 317.05/291.56 mod([], s(x1)) 317.05/291.56 317.05/291.56 317.05/291.56 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (2) 317.05/291.56 Obligation: 317.05/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true 317.05/291.56 leq(s(x), 0) -> false 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) 317.05/291.56 if(true, x, y) -> x 317.05/291.56 if(false, x, y) -> y 317.05/291.56 -(x, 0) -> x 317.05/291.56 -(s(x), s(y)) -> -(x, y) 317.05/291.56 mod(0, y) -> 0 317.05/291.56 mod(s(x), 0) -> 0 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 317.05/291.56 317.05/291.56 S is empty. 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Transformed relative TRS to weighted TRS 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (4) 317.05/291.56 Obligation: 317.05/291.56 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true [1] 317.05/291.56 leq(s(x), 0) -> false [1] 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) [1] 317.05/291.56 if(true, x, y) -> x [1] 317.05/291.56 if(false, x, y) -> y [1] 317.05/291.56 -(x, 0) -> x [1] 317.05/291.56 -(s(x), s(y)) -> -(x, y) [1] 317.05/291.56 mod(0, y) -> 0 [1] 317.05/291.56 mod(s(x), 0) -> 0 [1] 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) [1] 317.05/291.56 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Renamed defined symbols to avoid conflicts with arithmetic symbols: 317.05/291.56 317.05/291.56 - => minus 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (6) 317.05/291.56 Obligation: 317.05/291.56 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true [1] 317.05/291.56 leq(s(x), 0) -> false [1] 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) [1] 317.05/291.56 if(true, x, y) -> x [1] 317.05/291.56 if(false, x, y) -> y [1] 317.05/291.56 minus(x, 0) -> x [1] 317.05/291.56 minus(s(x), s(y)) -> minus(x, y) [1] 317.05/291.56 mod(0, y) -> 0 [1] 317.05/291.56 mod(s(x), 0) -> 0 [1] 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 317.05/291.56 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Infered types. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (8) 317.05/291.56 Obligation: 317.05/291.56 Runtime Complexity Weighted TRS with Types. 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true [1] 317.05/291.56 leq(s(x), 0) -> false [1] 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) [1] 317.05/291.56 if(true, x, y) -> x [1] 317.05/291.56 if(false, x, y) -> y [1] 317.05/291.56 minus(x, 0) -> x [1] 317.05/291.56 minus(s(x), s(y)) -> minus(x, y) [1] 317.05/291.56 mod(0, y) -> 0 [1] 317.05/291.56 mod(s(x), 0) -> 0 [1] 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 317.05/291.56 317.05/291.56 The TRS has the following type information: 317.05/291.56 leq :: 0:s -> 0:s -> true:false 317.05/291.56 0 :: 0:s 317.05/291.56 true :: true:false 317.05/291.56 s :: 0:s -> 0:s 317.05/291.56 false :: true:false 317.05/291.56 if :: true:false -> 0:s -> 0:s -> 0:s 317.05/291.56 minus :: 0:s -> 0:s -> 0:s 317.05/291.56 mod :: 0:s -> 0:s -> 0:s 317.05/291.56 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (9) CompletionProof (UPPER BOUND(ID)) 317.05/291.56 The transformation into a RNTS is sound, since: 317.05/291.56 317.05/291.56 (a) The obligation is a constructor system where every type has a constant constructor, 317.05/291.56 317.05/291.56 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 317.05/291.56 none 317.05/291.56 317.05/291.56 (c) The following functions are completely defined: 317.05/291.56 317.05/291.56 leq_2 317.05/291.56 mod_2 317.05/291.56 minus_2 317.05/291.56 if_3 317.05/291.56 317.05/291.56 Due to the following rules being added: 317.05/291.56 317.05/291.56 minus(v0, v1) -> 0 [0] 317.05/291.56 317.05/291.56 And the following fresh constants: none 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (10) 317.05/291.56 Obligation: 317.05/291.56 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 317.05/291.56 317.05/291.56 Runtime Complexity Weighted TRS with Types. 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true [1] 317.05/291.56 leq(s(x), 0) -> false [1] 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) [1] 317.05/291.56 if(true, x, y) -> x [1] 317.05/291.56 if(false, x, y) -> y [1] 317.05/291.56 minus(x, 0) -> x [1] 317.05/291.56 minus(s(x), s(y)) -> minus(x, y) [1] 317.05/291.56 mod(0, y) -> 0 [1] 317.05/291.56 mod(s(x), 0) -> 0 [1] 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(minus(s(x), s(y)), s(y)), s(x)) [1] 317.05/291.56 minus(v0, v1) -> 0 [0] 317.05/291.56 317.05/291.56 The TRS has the following type information: 317.05/291.56 leq :: 0:s -> 0:s -> true:false 317.05/291.56 0 :: 0:s 317.05/291.56 true :: true:false 317.05/291.56 s :: 0:s -> 0:s 317.05/291.56 false :: true:false 317.05/291.56 if :: true:false -> 0:s -> 0:s -> 0:s 317.05/291.56 minus :: 0:s -> 0:s -> 0:s 317.05/291.56 mod :: 0:s -> 0:s -> 0:s 317.05/291.56 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (11) NarrowingProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (12) 317.05/291.56 Obligation: 317.05/291.56 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 317.05/291.56 317.05/291.56 Runtime Complexity Weighted TRS with Types. 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true [1] 317.05/291.56 leq(s(x), 0) -> false [1] 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) [1] 317.05/291.56 if(true, x, y) -> x [1] 317.05/291.56 if(false, x, y) -> y [1] 317.05/291.56 minus(x, 0) -> x [1] 317.05/291.56 minus(s(x), s(y)) -> minus(x, y) [1] 317.05/291.56 mod(0, y) -> 0 [1] 317.05/291.56 mod(s(x), 0) -> 0 [1] 317.05/291.56 mod(s(x), s(0)) -> if(true, mod(minus(x, 0), s(0)), s(x)) [3] 317.05/291.56 mod(s(x), s(0)) -> if(true, mod(0, s(0)), s(x)) [2] 317.05/291.56 mod(s(0), s(s(x'))) -> if(false, mod(minus(0, s(x')), s(s(x'))), s(0)) [3] 317.05/291.56 mod(s(0), s(s(x'))) -> if(false, mod(0, s(s(x'))), s(0)) [2] 317.05/291.56 mod(s(s(y')), s(s(x''))) -> if(leq(x'', y'), mod(minus(s(y'), s(x'')), s(s(x''))), s(s(y'))) [3] 317.05/291.56 mod(s(s(y')), s(s(x''))) -> if(leq(x'', y'), mod(0, s(s(x''))), s(s(y'))) [2] 317.05/291.56 minus(v0, v1) -> 0 [0] 317.05/291.56 317.05/291.56 The TRS has the following type information: 317.05/291.56 leq :: 0:s -> 0:s -> true:false 317.05/291.56 0 :: 0:s 317.05/291.56 true :: true:false 317.05/291.56 s :: 0:s -> 0:s 317.05/291.56 false :: true:false 317.05/291.56 if :: true:false -> 0:s -> 0:s -> 0:s 317.05/291.56 minus :: 0:s -> 0:s -> 0:s 317.05/291.56 mod :: 0:s -> 0:s -> 0:s 317.05/291.56 317.05/291.56 Rewrite Strategy: INNERMOST 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 317.05/291.56 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 317.05/291.56 The constant constructors are abstracted as follows: 317.05/291.56 317.05/291.56 0 => 0 317.05/291.56 true => 1 317.05/291.56 false => 0 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (14) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(x, 0), 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 317.05/291.56 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (15) InliningProof (UPPER BOUND(ID)) 317.05/291.56 Inlined the following terminating rules on right-hand sides where appropriate: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 317.05/291.56 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (16) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(x, 0), 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + x) :|: x >= 0, z' = 1 + 0, z = 1 + x 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + x')), 1 + 0) :|: z' = 1 + (1 + x'), z = 1 + 0, x' >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 317.05/291.56 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (17) SimplificationProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (18) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (19) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 317.05/291.56 Found the following analysis order by SCC decomposition: 317.05/291.56 317.05/291.56 { minus } 317.05/291.56 { leq } 317.05/291.56 { if } 317.05/291.56 { mod } 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (20) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (21) ResultPropagationProof (UPPER BOUND(ID)) 317.05/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (22) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (23) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed SIZE bound using KoAT for: minus 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^1) with polynomial bound: z 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (24) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {minus}, {leq}, {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: ?, size: O(n^1) [z] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (25) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed RUNTIME bound using CoFloCo for: minus 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^1) with polynomial bound: 1 + z' 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (26) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 3 }-> if(1, mod(minus(z - 1, 0), 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 3 }-> if(0, mod(minus(0, 1 + (z' - 2)), 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {leq}, {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (27) ResultPropagationProof (UPPER BOUND(ID)) 317.05/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (28) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {leq}, {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (29) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed SIZE bound using CoFloCo for: leq 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(1) with polynomial bound: 1 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (30) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {leq}, {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: ?, size: O(1) [1] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (31) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed RUNTIME bound using KoAT for: leq 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^1) with polynomial bound: 2 + z' 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (32) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> leq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (33) ResultPropagationProof (UPPER BOUND(ID)) 317.05/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (34) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (35) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed SIZE bound using CoFloCo for: if 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^1) with polynomial bound: z' + z'' 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (36) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {if}, {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 if: runtime: ?, size: O(n^1) [z' + z''] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (37) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed RUNTIME bound using CoFloCo for: if 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(1) with polynomial bound: 1 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (38) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (39) ResultPropagationProof (UPPER BOUND(ID)) 317.05/291.56 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (40) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (41) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed SIZE bound using CoFloCo for: mod 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^2) with polynomial bound: 1 + z + z^2 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (42) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: {mod} 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 317.05/291.56 mod: runtime: ?, size: O(n^2) [1 + z + z^2] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (43) IntTrsBoundProof (UPPER BOUND(ID)) 317.05/291.56 317.05/291.56 Computed RUNTIME bound using CoFloCo for: mod 317.05/291.56 after applying outer abstraction to obtain an ITS, 317.05/291.56 resulting in: O(n^2) with polynomial bound: 13 + 7*z + z*z' + z^2 + 3*z' 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (44) 317.05/291.56 Obligation: 317.05/291.56 Complexity RNTS consisting of the following rules: 317.05/291.56 317.05/291.56 if(z, z', z'') -{ 1 }-> z' :|: z = 1, z' >= 0, z'' >= 0 317.05/291.56 if(z, z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 2 + z' }-> s2 :|: s2 >= 0, s2 <= 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 leq(z, z') -{ 1 }-> 1 :|: z' >= 0, z = 0 317.05/291.56 leq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0 317.05/291.56 minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 317.05/291.56 minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 317.05/291.56 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 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 4 }-> if(1, mod(s', 1 + 0), 1 + (z - 1)) :|: s' >= 0, s' <= z - 1, z - 1 >= 0, z' = 1 + 0 317.05/291.56 mod(z, z') -{ 2 }-> if(1, mod(0, 1 + 0), 1 + (z - 1)) :|: z - 1 >= 0, z' = 1 + 0 317.05/291.56 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 317.05/291.56 mod(z, z') -{ 2 }-> if(0, mod(0, 1 + (1 + (z' - 2))), 1 + 0) :|: z = 1 + 0, z' - 2 >= 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 317.05/291.56 mod(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0 317.05/291.56 317.05/291.56 Function symbols to be analyzed: 317.05/291.56 Previous analysis results are: 317.05/291.56 minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z] 317.05/291.56 leq: runtime: O(n^1) [2 + z'], size: O(1) [1] 317.05/291.56 if: runtime: O(1) [1], size: O(n^1) [z' + z''] 317.05/291.56 mod: runtime: O(n^2) [13 + 7*z + z*z' + z^2 + 3*z'], size: O(n^2) [1 + z + z^2] 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (45) FinalProof (FINISHED) 317.05/291.56 Computed overall runtime complexity 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (46) 317.05/291.56 BOUNDS(1, n^2) 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (47) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 317.05/291.56 Transformed a relative TRS into a decreasing-loop problem. 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (48) 317.05/291.56 Obligation: 317.05/291.56 Analyzing the following TRS for decreasing loops: 317.05/291.56 317.05/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true 317.05/291.56 leq(s(x), 0) -> false 317.05/291.56 leq(s(x), s(y)) -> leq(x, y) 317.05/291.56 if(true, x, y) -> x 317.05/291.56 if(false, x, y) -> y 317.05/291.56 -(x, 0) -> x 317.05/291.56 -(s(x), s(y)) -> -(x, y) 317.05/291.56 mod(0, y) -> 0 317.05/291.56 mod(s(x), 0) -> 0 317.05/291.56 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 317.05/291.56 317.05/291.56 S is empty. 317.05/291.56 Rewrite Strategy: FULL 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (49) DecreasingLoopProof (LOWER BOUND(ID)) 317.05/291.56 The following loop(s) give(s) rise to the lower bound Omega(n^1): 317.05/291.56 317.05/291.56 The rewrite sequence 317.05/291.56 317.05/291.56 -(s(x), s(y)) ->^+ -(x, y) 317.05/291.56 317.05/291.56 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 317.05/291.56 317.05/291.56 The pumping substitution is [x / s(x), y / s(y)]. 317.05/291.56 317.05/291.56 The result substitution is [ ]. 317.05/291.56 317.05/291.56 317.05/291.56 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (50) 317.05/291.56 Complex Obligation (BEST) 317.05/291.56 317.05/291.56 ---------------------------------------- 317.05/291.56 317.05/291.56 (51) 317.05/291.56 Obligation: 317.05/291.56 Proved the lower bound n^1 for the following obligation: 317.05/291.56 317.05/291.56 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 317.05/291.56 317.05/291.56 317.05/291.56 The TRS R consists of the following rules: 317.05/291.56 317.05/291.56 leq(0, y) -> true 317.05/291.56 leq(s(x), 0) -> false 317.05/291.57 leq(s(x), s(y)) -> leq(x, y) 317.05/291.57 if(true, x, y) -> x 317.05/291.57 if(false, x, y) -> y 317.05/291.57 -(x, 0) -> x 317.05/291.57 -(s(x), s(y)) -> -(x, y) 317.05/291.57 mod(0, y) -> 0 317.05/291.57 mod(s(x), 0) -> 0 317.05/291.57 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 317.05/291.57 317.05/291.57 S is empty. 317.05/291.57 Rewrite Strategy: FULL 317.05/291.57 ---------------------------------------- 317.05/291.57 317.05/291.57 (52) LowerBoundPropagationProof (FINISHED) 317.05/291.57 Propagated lower bound. 317.05/291.57 ---------------------------------------- 317.05/291.57 317.05/291.57 (53) 317.05/291.57 BOUNDS(n^1, INF) 317.05/291.57 317.05/291.57 ---------------------------------------- 317.05/291.57 317.05/291.57 (54) 317.05/291.57 Obligation: 317.05/291.57 Analyzing the following TRS for decreasing loops: 317.05/291.57 317.05/291.57 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 317.05/291.57 317.05/291.57 317.05/291.57 The TRS R consists of the following rules: 317.05/291.57 317.05/291.57 leq(0, y) -> true 317.05/291.57 leq(s(x), 0) -> false 317.05/291.57 leq(s(x), s(y)) -> leq(x, y) 317.05/291.57 if(true, x, y) -> x 317.05/291.57 if(false, x, y) -> y 317.05/291.57 -(x, 0) -> x 317.05/291.57 -(s(x), s(y)) -> -(x, y) 317.05/291.57 mod(0, y) -> 0 317.05/291.57 mod(s(x), 0) -> 0 317.05/291.57 mod(s(x), s(y)) -> if(leq(y, x), mod(-(s(x), s(y)), s(y)), s(x)) 317.05/291.57 317.05/291.57 S is empty. 317.05/291.57 Rewrite Strategy: FULL 317.14/291.61 EOF