/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(23, 15 + 4 * Arg_0) + max(4, 2 * Arg_0) * nat(Arg_0) + nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) * nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) + max(3, 2 + Arg_0) + max(10, -10 + 10 * Arg_0) + max(9, -9 + 9 * Arg_0) + max(5, -5 + 5 * Arg_0) + nat(-2 + 2 * Arg_0) + max(-14 + 14 * Arg_0, 14) + max(8, -8 + 8 * Arg_0)). (0) CpxIntTrs (1) Loat Proof [FINISHED, 2154 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_perfect1_start(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x <= 1 eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x > 1 eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_6(v__y3_0, v_x - 1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_6(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_1, v_y2_1, v_x)) :|: TRUE eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_x, v_y3_0)) :|: v_y1_0 > 0 eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y1_0 <= 0 eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= v_y1_0 eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < v_y1_0 eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1 - v_y1_0, v_y3_0)) :|: TRUE eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_12(v__y3_0, v_1, v_y3_0 - v_y1_0, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_12(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_6, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= 0 && v_y2_1 <= 0 eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < 0 eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 > 0 eval_perfect1_14(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_16(v__y3_0, v_1, v_6, v_y1_0 - 1, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_16(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_7, v_y2_1, v__y3_0)) :|: TRUE eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 < 0 eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 > 0 eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 >= 0 && v_y3_0 <= 0 eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_stop(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE The start-symbols are:[eval_perfect1_start_8] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalperfect1start 0: evalperfect1start -> evalperfect1bb0in : [], cost: 1 1: evalperfect1bb0in -> evalperfect10 : [], cost: 1 2: evalperfect10 -> evalperfect11 : [], cost: 1 3: evalperfect11 -> evalperfect1bb7in : [ 1>=A ], cost: 1 4: evalperfect11 -> evalperfect1bb1in : [ A>=2 ], cost: 1 5: evalperfect1bb1in -> evalperfect12 : [], cost: 1 6: evalperfect12 -> evalperfect13 : [], cost: 1 7: evalperfect13 -> evalperfect14 : [], cost: 1 8: evalperfect14 -> evalperfect15 : [], cost: 1 9: evalperfect15 -> evalperfect16 : B'=-1+A, [], cost: 1 10: evalperfect16 -> evalperfect17 : [], cost: 1 11: evalperfect17 -> evalperfect18 : [], cost: 1 12: evalperfect18 -> evalperfect1bb2in : C'=B, D'=A, [], cost: 1 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 14: evalperfect1bb2in -> evalperfect1bb6in : [ 0>=C ], cost: 1 15: evalperfect1bb3in -> evalperfect1bb4in : [ E>=C ], cost: 1 16: evalperfect1bb3in -> evalperfect1bb5in : [ C>=1+E ], cost: 1 17: evalperfect1bb4in -> evalperfect1bb3in : E'=-C+E, [], cost: 1 18: evalperfect1bb5in -> evalperfect112 : F'=-C+D, [], cost: 1 19: evalperfect112 -> evalperfect113 : [], cost: 1 20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1 21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1 22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1 23: evalperfect114 -> evalperfect115 : [], cost: 1 24: evalperfect115 -> evalperfect116 : H'=-1+C, [], cost: 1 25: evalperfect116 -> evalperfect117 : [], cost: 1 26: evalperfect117 -> evalperfect1bb2in : C'=H, D'=G, [], cost: 1 27: evalperfect1bb6in -> evalperfect1bb7in : [ 0>=1+D ], cost: 1 28: evalperfect1bb6in -> evalperfect1bb7in : [ D>=1 ], cost: 1 29: evalperfect1bb6in -> evalperfect1bb7in : [ D==0 ], cost: 1 30: evalperfect1bb7in -> evalperfect1stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalperfect1start 0: evalperfect1start -> evalperfect1bb0in : [], cost: 1 1: evalperfect1bb0in -> evalperfect10 : [], cost: 1 2: evalperfect10 -> evalperfect11 : [], cost: 1 4: evalperfect11 -> evalperfect1bb1in : [ A>=2 ], cost: 1 5: evalperfect1bb1in -> evalperfect12 : [], cost: 1 6: evalperfect12 -> evalperfect13 : [], cost: 1 7: evalperfect13 -> evalperfect14 : [], cost: 1 8: evalperfect14 -> evalperfect15 : [], cost: 1 9: evalperfect15 -> evalperfect16 : B'=-1+A, [], cost: 1 10: evalperfect16 -> evalperfect17 : [], cost: 1 11: evalperfect17 -> evalperfect18 : [], cost: 1 12: evalperfect18 -> evalperfect1bb2in : C'=B, D'=A, [], cost: 1 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 15: evalperfect1bb3in -> evalperfect1bb4in : [ E>=C ], cost: 1 16: evalperfect1bb3in -> evalperfect1bb5in : [ C>=1+E ], cost: 1 17: evalperfect1bb4in -> evalperfect1bb3in : E'=-C+E, [], cost: 1 18: evalperfect1bb5in -> evalperfect112 : F'=-C+D, [], cost: 1 19: evalperfect112 -> evalperfect113 : [], cost: 1 20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1 21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1 22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1 23: evalperfect114 -> evalperfect115 : [], cost: 1 24: evalperfect115 -> evalperfect116 : H'=-1+C, [], cost: 1 25: evalperfect116 -> evalperfect117 : [], cost: 1 26: evalperfect117 -> evalperfect1bb2in : C'=H, D'=G, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2 44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3 20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1 21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1 22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1 47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4 Accelerating simple loops of location 13. Accelerating the following rules: 42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2 Found no metering function for rule 42. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2 44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3 20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1 21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1 22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1 47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4 Chained accelerated rules (with incoming rules): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 48: evalperfect1bb2in -> evalperfect1bb3in : E'=-C+A, [ C>=1 && A>=C ], cost: 3 44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3 20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1 21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1 22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1 47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4 Eliminated locations (on tree-shaped paths): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 49: evalperfect1bb2in -> evalperfect113 : E'=A, F'=-C+D, [ C>=1 && C>=1+A ], cost: 4 50: evalperfect1bb2in -> evalperfect113 : E'=-C+A, F'=-C+D, [ C>=1 && A>=C && C>=1-C+A ], cost: 6 51: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=F, G'=F, H'=-1+C, [ E==0 ], cost: 5 52: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=D, G'=D, H'=-1+C, [ 0>=1+E ], cost: 5 53: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=D, G'=D, H'=-1+C, [ E>=1 ], cost: 5 Eliminated locations (on tree-shaped paths): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 54: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1+A && A==0 ], cost: 9 55: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9 56: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && A>=1 ], cost: 9 57: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=-C+A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A==0 ], cost: 11 58: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=-C+A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A>=1 ], cost: 11 Accelerating simple loops of location 12. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 54: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1+A && A==0 ], cost: 9 55: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9 56: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && A>=1 ], cost: 9 57: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=-C+A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A==0 ], cost: 11 58: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=-C+A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A>=1 ], cost: 11 Accelerated rule 54 with metering function C-A, yielding the new rule 59. Accelerated rule 55 with metering function C, yielding the new rule 60. Accelerated rule 56 with metering function C-A, yielding the new rule 61. Accelerated rule 57 with metering function C-A, yielding the new rule 62. Accelerated rule 58 with metering function meter (where 2*meter==2*C-A), yielding the new rule 63. During metering: Instantiating temporary variables by {meter==1} Removing the simple loops: 54 55 56 57 58. Accelerated all simple loops using metering functions (where possible): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 59: evalperfect1bb2in -> evalperfect1bb2in : C'=A, D'=-1-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, E'=A, F'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, G'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, H'=A, [ C>=1 && C>=1+A && A==0 ], cost: 9*C-9*A 60: evalperfect1bb2in -> evalperfect1bb2in : C'=0, E'=A, F'=-1+D, G'=D, H'=0, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9*C 61: evalperfect1bb2in -> evalperfect1bb2in : C'=A, E'=A, F'=-1+D-A, G'=D, H'=A, [ C>=1 && C>=1+A && A>=1 ], cost: 9*C-9*A 62: evalperfect1bb2in -> evalperfect1bb2in : C'=A, D'=-1-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, E'=-1, F'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, G'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, H'=A, [ C>=1 && C>=1-C+A && -C+A==0 && C-A>=1 ], cost: 11*C-11*A 63: evalperfect1bb2in -> evalperfect1bb2in : C'=-meter+C, E'=-1+meter-C+A, F'=-1+meter-C+D, G'=D, H'=-meter+C, [ C>=1 && C>=1-C+A && -C+A>=1 && 2*meter==2*C-A && meter>=1 ], cost: 11*meter Chained accelerated rules (with incoming rules): Start location: evalperfect1start 41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12 64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter Removed unreachable locations (and leaf rules with constant cost): Start location: evalperfect1start 64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalperfect1start 64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter Computing asymptotic complexity for rule 64 Solved the limit problem by the following transformations: Created initial limit problem: 3+2*meter-A (+/+!), -1-2*meter+A (+/+!), 12+11*meter (+), -2+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==2+2*meter} resulting limit problem: 1 (+/+!), 2*meter (+/+!), 12+11*meter (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter (+/+!), 12+11*meter (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 3+2*meter-A (+/+!), -1-2*meter+A (+/+!), 12+11*meter (+), -2+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==2+2*meter} resulting limit problem: 1 (+/+!), 2*meter (+/+!), 12+11*meter (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 2*meter (+/+!), 12+11*meter (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter==n} resulting limit problem: [solved] Solution: meter / n A / 2+2*n Resulting cost 12+11*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 12+11*n Rule cost: 12+11*meter Rule guard: [ -1+A>=2 && 2*meter==-2+A ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (2) BOUNDS(n^1, INF)