/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, 1735 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_counterex1c_start(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb0_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_bb0_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_0(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_0(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_1(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_1(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_2(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_2(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_3(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_3(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_4(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_4(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_5(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_5(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_6(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_6(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_7(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_7(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_8(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_8(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_9(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_9(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(v_b, v_x, v_y, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_bb1_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb2_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__01 >= 0 && 0 <= v__04 && v__04 <= v_n eval_counterex1c_bb1_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c__critedge_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__01 < 0 eval_counterex1c_bb1_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c__critedge_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: 0 > v__04 eval_counterex1c_bb1_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c__critedge_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__04 > v_n eval_counterex1c_bb2_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_NodeBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_NodeBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_LeafBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 < 1 eval_counterex1c_NodeBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_LeafBlock8_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 >= 1 eval_counterex1c_LeafBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb3_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 >= 0 && v__0 <= 0 eval_counterex1c_LeafBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_NewDefault_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 < 0 eval_counterex1c_LeafBlock_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_NewDefault_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 > 0 eval_counterex1c_bb3_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_11(v__0, v__01, v__04, v__04 + 1, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_11(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_12(v__0, v__01, v__04, v_3, nondef_0, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_12(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(1, v__01, v_3, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_4 > 0 eval_counterex1c_12(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(v__0, v__01, v_3, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_4 <= 0 eval_counterex1c_LeafBlock8_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb4_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 >= 1 && v__0 <= 1 eval_counterex1c_LeafBlock8_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_NewDefault_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 < 1 eval_counterex1c_LeafBlock8_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_NewDefault_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v__0 > 1 eval_counterex1c_bb4_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_15(v__0, v__01, v__04, v_3, v_4, v__04 - 1, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_15(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_16(v__0, v__01, v__04, v_3, v_4, v_6, nondef_1, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c_16(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(0, v__01 - 1, v_6, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_7 > 0 eval_counterex1c_16(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(v__0, v__01 - 1, v_6, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_7 > 0 && v_7 <= 0 eval_counterex1c_16(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(0, v__01, v_6, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_7 <= 0 && v_7 > 0 eval_counterex1c_16(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_bb1_in(v__0, v__01, v_6, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: v_7 <= 0 eval_counterex1c_NewDefault_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c__critedge_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE eval_counterex1c__critedge_in(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1c_stop(v__0, v__01, v__04, v_3, v_4, v_6, v_7, v_b, v_n, v_x, v_y)) :|: TRUE The start-symbols are:[eval_counterex1c_start_11] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalcounterex1cstart 0: evalcounterex1cstart -> evalcounterex1cbb0in : [], cost: 1 1: evalcounterex1cbb0in -> evalcounterex1c0 : [], cost: 1 2: evalcounterex1c0 -> evalcounterex1c1 : [], cost: 1 3: evalcounterex1c1 -> evalcounterex1c2 : [], cost: 1 4: evalcounterex1c2 -> evalcounterex1c3 : [], cost: 1 5: evalcounterex1c3 -> evalcounterex1c4 : [], cost: 1 6: evalcounterex1c4 -> evalcounterex1c5 : [], cost: 1 7: evalcounterex1c5 -> evalcounterex1c6 : [], cost: 1 8: evalcounterex1c6 -> evalcounterex1c7 : [], cost: 1 9: evalcounterex1c7 -> evalcounterex1c8 : [], cost: 1 10: evalcounterex1c8 -> evalcounterex1c9 : [], cost: 1 11: evalcounterex1c9 -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1cbb1in -> evalcounterex1cbb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 13: evalcounterex1cbb1in -> evalcounterex1ccritedgein : [ 0>=1+C ], cost: 1 14: evalcounterex1cbb1in -> evalcounterex1ccritedgein : [ 0>=1+E ], cost: 1 15: evalcounterex1cbb1in -> evalcounterex1ccritedgein : [ E>=1+G ], cost: 1 16: evalcounterex1cbb2in -> evalcounterex1cNodeBlockin : [], cost: 1 17: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlockin : [ 0>=A ], cost: 1 18: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlock8in : [ A>=1 ], cost: 1 19: evalcounterex1cLeafBlockin -> evalcounterex1cbb3in : [ A==0 ], cost: 1 20: evalcounterex1cLeafBlockin -> evalcounterex1cNewDefaultin : [ 0>=1+A ], cost: 1 21: evalcounterex1cLeafBlockin -> evalcounterex1cNewDefaultin : [ A>=1 ], cost: 1 22: evalcounterex1cbb3in -> evalcounterex1c11 : H'=1+E, [], cost: 1 23: evalcounterex1c11 -> evalcounterex1c12 : Q'=free, [], cost: 1 24: evalcounterex1c12 -> evalcounterex1cbb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 25: evalcounterex1c12 -> evalcounterex1cbb1in : E'=H, [ 0>=Q ], cost: 1 26: evalcounterex1cLeafBlock8in -> evalcounterex1cbb4in : [ A==1 ], cost: 1 27: evalcounterex1cLeafBlock8in -> evalcounterex1cNewDefaultin : [ 0>=A ], cost: 1 28: evalcounterex1cLeafBlock8in -> evalcounterex1cNewDefaultin : [ A>=2 ], cost: 1 29: evalcounterex1cbb4in -> evalcounterex1c15 : J'=-1+E, [], cost: 1 30: evalcounterex1c15 -> evalcounterex1c16 : K'=free_1, [], cost: 1 31: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 32: evalcounterex1c16 -> evalcounterex1cbb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1 33: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1 34: evalcounterex1c16 -> evalcounterex1cbb1in : E'=J, [ 0>=K ], cost: 1 35: evalcounterex1cNewDefaultin -> evalcounterex1ccritedgein : [], cost: 1 36: evalcounterex1ccritedgein -> evalcounterex1cstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalcounterex1cstart -> evalcounterex1cbb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalcounterex1cstart 0: evalcounterex1cstart -> evalcounterex1cbb0in : [], cost: 1 1: evalcounterex1cbb0in -> evalcounterex1c0 : [], cost: 1 2: evalcounterex1c0 -> evalcounterex1c1 : [], cost: 1 3: evalcounterex1c1 -> evalcounterex1c2 : [], cost: 1 4: evalcounterex1c2 -> evalcounterex1c3 : [], cost: 1 5: evalcounterex1c3 -> evalcounterex1c4 : [], cost: 1 6: evalcounterex1c4 -> evalcounterex1c5 : [], cost: 1 7: evalcounterex1c5 -> evalcounterex1c6 : [], cost: 1 8: evalcounterex1c6 -> evalcounterex1c7 : [], cost: 1 9: evalcounterex1c7 -> evalcounterex1c8 : [], cost: 1 10: evalcounterex1c8 -> evalcounterex1c9 : [], cost: 1 11: evalcounterex1c9 -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1cbb1in -> evalcounterex1cbb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 16: evalcounterex1cbb2in -> evalcounterex1cNodeBlockin : [], cost: 1 17: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlockin : [ 0>=A ], cost: 1 18: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlock8in : [ A>=1 ], cost: 1 19: evalcounterex1cLeafBlockin -> evalcounterex1cbb3in : [ A==0 ], cost: 1 22: evalcounterex1cbb3in -> evalcounterex1c11 : H'=1+E, [], cost: 1 23: evalcounterex1c11 -> evalcounterex1c12 : Q'=free, [], cost: 1 24: evalcounterex1c12 -> evalcounterex1cbb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 25: evalcounterex1c12 -> evalcounterex1cbb1in : E'=H, [ 0>=Q ], cost: 1 26: evalcounterex1cLeafBlock8in -> evalcounterex1cbb4in : [ A==1 ], cost: 1 29: evalcounterex1cbb4in -> evalcounterex1c15 : J'=-1+E, [], cost: 1 30: evalcounterex1c15 -> evalcounterex1c16 : K'=free_1, [], cost: 1 31: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 32: evalcounterex1c16 -> evalcounterex1cbb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1 33: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1 34: evalcounterex1c16 -> evalcounterex1cbb1in : E'=J, [ 0>=K ], cost: 1 Removed rules with unsatisfiable guard: Start location: evalcounterex1cstart 0: evalcounterex1cstart -> evalcounterex1cbb0in : [], cost: 1 1: evalcounterex1cbb0in -> evalcounterex1c0 : [], cost: 1 2: evalcounterex1c0 -> evalcounterex1c1 : [], cost: 1 3: evalcounterex1c1 -> evalcounterex1c2 : [], cost: 1 4: evalcounterex1c2 -> evalcounterex1c3 : [], cost: 1 5: evalcounterex1c3 -> evalcounterex1c4 : [], cost: 1 6: evalcounterex1c4 -> evalcounterex1c5 : [], cost: 1 7: evalcounterex1c5 -> evalcounterex1c6 : [], cost: 1 8: evalcounterex1c6 -> evalcounterex1c7 : [], cost: 1 9: evalcounterex1c7 -> evalcounterex1c8 : [], cost: 1 10: evalcounterex1c8 -> evalcounterex1c9 : [], cost: 1 11: evalcounterex1c9 -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 1 12: evalcounterex1cbb1in -> evalcounterex1cbb2in : [ C>=0 && E>=0 && G>=E ], cost: 1 16: evalcounterex1cbb2in -> evalcounterex1cNodeBlockin : [], cost: 1 17: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlockin : [ 0>=A ], cost: 1 18: evalcounterex1cNodeBlockin -> evalcounterex1cLeafBlock8in : [ A>=1 ], cost: 1 19: evalcounterex1cLeafBlockin -> evalcounterex1cbb3in : [ A==0 ], cost: 1 22: evalcounterex1cbb3in -> evalcounterex1c11 : H'=1+E, [], cost: 1 23: evalcounterex1c11 -> evalcounterex1c12 : Q'=free, [], cost: 1 24: evalcounterex1c12 -> evalcounterex1cbb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 25: evalcounterex1c12 -> evalcounterex1cbb1in : E'=H, [ 0>=Q ], cost: 1 26: evalcounterex1cLeafBlock8in -> evalcounterex1cbb4in : [ A==1 ], cost: 1 29: evalcounterex1cbb4in -> evalcounterex1c15 : J'=-1+E, [], cost: 1 30: evalcounterex1c15 -> evalcounterex1c16 : K'=free_1, [], cost: 1 31: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 34: evalcounterex1c16 -> evalcounterex1cbb1in : E'=J, [ 0>=K ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalcounterex1cstart 47: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 12 48: evalcounterex1cbb1in -> evalcounterex1cNodeBlockin : [ C>=0 && E>=0 && G>=E ], cost: 2 53: evalcounterex1cNodeBlockin -> evalcounterex1c12 : H'=1+E, Q'=free, [ A==0 ], cost: 4 54: evalcounterex1cNodeBlockin -> evalcounterex1c16 : J'=-1+E, K'=free_1, [ A==1 ], cost: 4 24: evalcounterex1c12 -> evalcounterex1cbb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 25: evalcounterex1c12 -> evalcounterex1cbb1in : E'=H, [ 0>=Q ], cost: 1 31: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 34: evalcounterex1c16 -> evalcounterex1cbb1in : E'=J, [ 0>=K ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalcounterex1cstart 47: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 12 55: evalcounterex1cbb1in -> evalcounterex1c12 : H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 ], cost: 6 56: evalcounterex1cbb1in -> evalcounterex1c16 : J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A==1 ], cost: 6 24: evalcounterex1c12 -> evalcounterex1cbb1in : A'=1, E'=H, [ Q>=1 ], cost: 1 25: evalcounterex1c12 -> evalcounterex1cbb1in : E'=H, [ 0>=Q ], cost: 1 31: evalcounterex1c16 -> evalcounterex1cbb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1 34: evalcounterex1c16 -> evalcounterex1cbb1in : E'=J, [ 0>=K ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalcounterex1cstart 47: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 12 57: evalcounterex1cbb1in -> evalcounterex1cbb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 7 58: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 7 59: evalcounterex1cbb1in -> evalcounterex1cbb1in : 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: 7 60: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A==1 && 0>=free_1 ], cost: 7 Accelerating simple loops of location 12. Accelerating the following rules: 57: evalcounterex1cbb1in -> evalcounterex1cbb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 7 58: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 7 59: evalcounterex1cbb1in -> evalcounterex1cbb1in : 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: 7 60: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A==1 && 0>=free_1 ], cost: 7 Accelerated rule 57 with metering function -A, yielding the new rule 61. Accelerated rule 58 with metering function 1+G-E, yielding the new rule 62. Accelerated rule 59 with metering function -1+A, yielding the new rule 63. Accelerated rule 60 with metering function 1+E, yielding the new rule 64. Removing the simple loops: 57 58 59 60. Accelerated all simple loops using metering functions (where possible): Start location: evalcounterex1cstart 47: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 12 61: evalcounterex1cbb1in -> evalcounterex1cbb1in : A'=1, E'=-A+E, H'=-A+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 && -A>=1 ], cost: -7*A 62: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=1+G, H'=1+G, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 7+7*G-7*E 63: evalcounterex1cbb1in -> evalcounterex1cbb1in : A'=0, C'=1+C-A, E'=1-A+E, J'=1-A+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A==1 && free_1>=1 && -1+A>=1 ], cost: -7+7*A 64: evalcounterex1cbb1in -> evalcounterex1cbb1in : E'=-1, J'=-1, K'=free_1, [ C>=0 && E>=0 && G>=E && A==1 && 0>=free_1 ], cost: 7+7*E Chained accelerated rules (with incoming rules): Start location: evalcounterex1cstart 47: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=F, [], cost: 12 65: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 19-7*F+7*G 66: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B==1 && 0>=free_1 ], cost: 19+7*F Removed unreachable locations (and leaf rules with constant cost): Start location: evalcounterex1cstart 65: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 19-7*F+7*G 66: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B==1 && 0>=free_1 ], cost: 19+7*F ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalcounterex1cstart 65: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 19-7*F+7*G 66: evalcounterex1cstart -> evalcounterex1cbb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B==1 && 0>=free_1 ], cost: 19+7*F Computing asymptotic complexity for rule 65 Solved the limit problem by the following transformations: Created initial limit problem: 1+F (+/+!), 1-F+G (+/+!), 1-B (+/+!), 1+B (+/+!), 19-7*F+7*G (+), 1-free (+/+!), 1+D (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {F==n,free==-n,G==2*n,D==n,B==0} resulting limit problem: [solved] Solution: F / n free / -n G / 2*n D / n B / 0 Resulting cost 19+7*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: 19+7*n Rule cost: 19-7*F+7*G Rule guard: [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (2) BOUNDS(n^1, INF)