/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 2442 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_counterex1a_start(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb0_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_bb0_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_0(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_0(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_1(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_1(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_2(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_2(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_3(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_3(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_4(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_4(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_5(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_5(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_6(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_6(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_7(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_7(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_8(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_8(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_9(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_9(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v_b, v_x, v_y, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__01 >= 0 && 0 <= v__04 && v__04 <= v_n eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__01 < 0 eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: 0 > v__04 eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__04 > v_n eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb3_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 >= 0 && v__0 <= 0 eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 < 0 eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 > 0 eval_counterex1a_bb3_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_11(v__0, v__01, v__04, v__04 + 1, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_11(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_12(v__0, v__01, v__04, v_4, nondef_0, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_12(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(1, v__01, v_4, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_5 > 0 eval_counterex1a_12(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01, v_4, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_5 <= 0 eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_15(v__0, v__01, v__04, v_4, v_5, v__04 - 1, v_8, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_15(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, nondef_1, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(0, v__01 - 1, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 > 0 eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01 - 1, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 > 0 && v_8 <= 0 eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(0, v__01, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 <= 0 && v_8 > 0 eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 <= 0 eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_stop(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE The start-symbols are:[eval_counterex1a_start_11] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalcounterex1astart 0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1 1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1 2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1 3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1 4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1 5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1 6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1 7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1 8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1 9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1 10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1 11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 13: evalcounterex1abb1in -> evalcounterex1acritedgein : [ 0>=1+C ], cost: 1 14: evalcounterex1abb1in -> evalcounterex1acritedgein : [ 0>=1+E ], cost: 1 15: evalcounterex1abb1in -> evalcounterex1acritedgein : [ E>=1+G ], cost: 1 16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1 17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1 18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1 19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1 20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1 21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1 23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1 24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1 25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 26: evalcounterex1a16 -> evalcounterex1abb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1 27: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1 28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1 29: evalcounterex1acritedgein -> evalcounterex1astop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalcounterex1astart 0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1 1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1 2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1 3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1 4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1 5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1 6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1 7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1 8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1 9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1 10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1 11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1 17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1 18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1 19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1 20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1 21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1 23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1 24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1 25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 26: evalcounterex1a16 -> evalcounterex1abb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1 27: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1 28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1 Removed rules with unsatisfiable guard: Start location: evalcounterex1astart 0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1 1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1 2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1 3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1 4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1 5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1 6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1 7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1 8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1 9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1 10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1 11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1 17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1 18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1 19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1 20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1 21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1 23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1 24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1 25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalcounterex1astart 40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12 12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1 18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1 42: evalcounterex1abb2in -> evalcounterex1a12 : H'=1+E, Q'=free, [ A==0 ], cost: 3 21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1 43: evalcounterex1abb4in -> evalcounterex1a16 : J'=-1+E, K'=free_1, [], cost: 2 25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalcounterex1astart 40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12 44: evalcounterex1abb1in -> evalcounterex1abb4in : [ C>=0 && E>=0 && G>=E && 0>=1+A ], cost: 2 45: evalcounterex1abb1in -> evalcounterex1abb4in : [ C>=0 && E>=0 && G>=E && A>=1 ], cost: 2 46: evalcounterex1abb1in -> evalcounterex1a12 : H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 ], cost: 4 21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1 47: evalcounterex1abb4in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ free_1>=1 ], cost: 3 48: evalcounterex1abb4in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ 0>=free_1 ], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalcounterex1astart 40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12 49: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 5 50: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5 51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5 52: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5 53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5 54: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5 Accelerating simple loops of location 12. Accelerating the following rules: 49: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 5 50: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5 51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5 52: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5 53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5 54: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5 Accelerated rule 49 with metering function -A, yielding the new rule 55. Accelerated rule 50 with metering function 1+G-E, yielding the new rule 56. Found no metering function for rule 51. Accelerated rule 52 with metering function 1+E, yielding the new rule 57. Found no metering function for rule 53. Accelerated rule 54 with metering function 1+E, yielding the new rule 58. Removing the simple loops: 49 50 52 54. Accelerated all simple loops using metering functions (where possible): Start location: evalcounterex1astart 40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12 51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5 53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5 55: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=-A+E, H'=-A+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 && -A>=1 ], cost: -5*A 56: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+G, H'=1+G, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5+5*G-5*E 57: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1, J'=-1, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5+5*E 58: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1, J'=-1, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5+5*E Chained accelerated rules (with incoming rules): Start location: evalcounterex1astart 40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12 59: evalcounterex1astart -> evalcounterex1abb1in : A'=0, C'=-1+D, E'=-1+F, J'=-1+F, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && free_1>=1 ], cost: 17 60: evalcounterex1astart -> evalcounterex1abb1in : A'=0, C'=-1+D, E'=-1+F, J'=-1+F, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && free_1>=1 ], cost: 17 61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G 62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F 63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F Removed unreachable locations (and leaf rules with constant cost): Start location: evalcounterex1astart 61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G 62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F 63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalcounterex1astart 61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G 62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F 63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F Computing asymptotic complexity for rule 61 Solved the limit problem by the following transformations: Created initial limit problem: 1+F (+/+!), 1-F+G (+/+!), 1-B (+/+!), 17-5*F+5*G (+), 1+B (+/+!), 1-free (+/+!), 1+D (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {F==0,free==-n,G==n,D==n,B==0} resulting limit problem: [solved] Solution: F / 0 free / -n G / n D / n B / 0 Resulting cost 17+5*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: 17+5*n Rule cost: 17-5*F+5*G Rule guard: [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (2) BOUNDS(n^1, INF)