details

property	value
status	complete
benchmark	counterex1b.c.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n053.star.cs.uiowa.edu
space	Flores-Montoya_16

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	31.2991120815 seconds
cpu usage	44.793603721
max memory	5.1329024E8

stage attributes

key	value
output-size	89379
starexec-result	WORST_CASE(Omega(n^2), O(n^3))

output

/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^3)) 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^2, nat(-5 * Arg_3 + 5 * Arg_8) + nat(20 * Arg_1 * max(1, 2 + 2 * Arg_1 + 2 * Arg_1 * Arg_8 + 2 * Arg_1 * max(1, -1 * Arg_3) + Arg_8 + max(1, -1 * Arg_3)) + 20 * Arg_1 * nat(-1 * Arg_3 + Arg_8) + 20 * Arg_1 * max(Arg_3, -1) + max(5 * Arg_3, -5) + max(10 + 10 * Arg_1 + 10 * Arg_1 * Arg_8 + 10 * Arg_1 * max(1, -1 * Arg_3) + 5 * Arg_8 + max(5, -5 * Arg_3), 5) + nat(-5 * Arg_3 + 5 * Arg_8)) + nat(1 + 4 * Arg_1) + nat(5 + 10 * Arg_1 + 10 * Arg_1 * Arg_8 + 10 * Arg_1 * max(1, -1 * Arg_3) + 5 * Arg_8 + max(5, -5 * Arg_3)) + max(7, 9 + 2 * Arg_1) + nat(1 + 2 * Arg_1) + max(2, 3 + Arg_1) + nat(4 + 4 * Arg_1)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 29.6 s] (2) BOUNDS(1, nat(-5 * Arg_3 + 5 * Arg_8) + nat(20 * Arg_1 * max(1, 2 + 2 * Arg_1 + 2 * Arg_1 * Arg_8 + 2 * Arg_1 * max(1, -1 * Arg_3) + Arg_8 + max(1, -1 * Arg_3)) + 20 * Arg_1 * nat(-1 * Arg_3 + Arg_8) + 20 * Arg_1 * max(Arg_3, -1) + max(5 * Arg_3, -5) + max(10 + 10 * Arg_1 + 10 * Arg_1 * Arg_8 + 10 * Arg_1 * max(1, -1 * Arg_3) + 5 * Arg_8 + max(5, -5 * Arg_3), 5) + nat(-5 * Arg_3 + 5 * Arg_8)) + nat(1 + 4 * Arg_1) + nat(5 + 10 * Arg_1 + 10 * Arg_1 * Arg_8 + 10 * Arg_1 * max(1, -1 * Arg_3) + 5 * Arg_8 + max(5, -5 * Arg_3)) + max(7, 9 + 2 * Arg_1) + nat(1 + 2 * Arg_1) + max(2, 3 + Arg_1) + nat(4 + 4 * Arg_1)) (3) Loat Proof [FINISHED, 3252 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_counterex1b_start(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb0_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_bb0_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_0(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_0(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_1(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_1(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_2(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_2(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_3(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_3(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_4(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_4(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_x, v_y, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b__critedge2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb1_in(v__0, v__01, v__01, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__0 >= 0 eval_counterex1b__critedge2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb7_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__0 < 0 eval_counterex1b_bb1_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__1 >= 0 eval_counterex1b_bb1_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__1 < 0 eval_counterex1b_bb2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_5(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_5(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_6(v__0, v__01, v__1, v__2, nondef_0, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_6(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb3_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_2 > 0 eval_counterex1b_6(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_2 <= 0 eval_counterex1b_bb3_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb1_in(v__0, v__01, v__1 - 1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_10(v__0, v__01, v__1, v__2, v_2, v__0 - 1, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_10(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_11(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_11(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_12(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_12(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb4_in(v__0, v__01, v__1, v__1, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb5_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__2 <= v_n eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_5, v__2, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__2 > v_n eval_counterex1b_bb5_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_13(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_13(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, nondef_1, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb6_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_7 > 0 eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_5, v__2, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_7 <= 0 eval_counterex1b_bb6_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2 + 1, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE eval_counterex1b_bb7_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_stop(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE The start-symbols are:[eval_counterex1b_start_10] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 7+2*max([0, 1+Arg_1])+max([0, 1+2*Arg_1])+max([0, (1+4*Arg_1)*(1+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([-1, Arg_3]))])+max([0, 1+4*Arg_1])+max([0, Arg_8-Arg_3])+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([2, 3+Arg_1])+max([0, 1+Arg_1])+max([0, Arg_8-Arg_3])+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, 1+Arg_1])+max([0, (1+4*Arg_1)*(1+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([-1, Arg_3]))])+max([0, Arg_8-Arg_3])+max([0, (1+4*Arg_1)*(1+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([-1, Arg_3]))])+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, 1+Arg_1])+max([0, Arg_8-Arg_3])+max([0, (1+4*Arg_1)*(1+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([-1, Arg_3]))])+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, (1+4*Arg_1)*(1+max([0, (1+2*Arg_1)*(1+Arg_8+max([1, -(Arg_3)]))])+max([0, Arg_8-Arg_3])+max([-1, Arg_3]))])+max([0, 1+Arg_1]) {O(n^3)}) Initial Complexity Problem: Start: evalcounterex1bstart Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7, Arg_8, Arg_9 Temp_Vars: K Locations: evalcounterex1b0, evalcounterex1b1, evalcounterex1b10, evalcounterex1b11, evalcounterex1b12, evalcounterex1b13, evalcounterex1b14, evalcounterex1b2, evalcounterex1b3, evalcounterex1b4, evalcounterex1b5, evalcounterex1b6, evalcounterex1bbb0in, evalcounterex1bbb1in, evalcounterex1bbb2in, evalcounterex1bbb3in, evalcounterex1bbb4in, evalcounterex1bbb5in, evalcounterex1bbb6in, evalcounterex1bbb7in, evalcounterex1bcritedge2in, evalcounterex1bcritedgein, evalcounterex1bstart, evalcounterex1bstop Transitions: evalcounterex1b0(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|: evalcounterex1b1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|: evalcounterex1b10(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b11(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|:1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 evalcounterex1b11(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b12(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|:1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 evalcounterex1b12(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1bbb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_4,Arg_8,Arg_9):|:1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 evalcounterex1b13(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b14(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,K):|:Arg_7 <= Arg_8 && Arg_4 <= Arg_8 && Arg_4 <= Arg_7 && 1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 evalcounterex1b14(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1bbb6in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|:Arg_7 <= Arg_8 && Arg_4 <= Arg_8 && Arg_4 <= Arg_7 && 1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 && 1 <= Arg_9 evalcounterex1b14(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1bcritedge2in(Arg_6,Arg_1,Arg_7,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|:Arg_7 <= Arg_8 && Arg_4 <= Arg_8 && Arg_4 <= Arg_7 && 1+Arg_6 <= Arg_1 && 1+Arg_6 <= Arg_0 && 0 <= 1+Arg_6 && 0 <= 1+Arg_1+Arg_6 && 0 <= 1+Arg_0+Arg_6 && Arg_0 <= 1+Arg_6 && Arg_4 <= Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 && Arg_9 <= 0 evalcounterex1b2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b3(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|: evalcounterex1b3(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b4(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|: evalcounterex1b4(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1bcritedge2in(Arg_1,Arg_1,Arg_3,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9):|: evalcounterex1b5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7,Arg_8,Arg_9) -> evalcounterex1b6(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,K,Arg_6,Arg_7,Arg_8,Arg_9):|:Arg_4 <= Arg_2 && 0 <= Arg_4 && 0 <= Arg_2+Arg_4 && 0 <= Arg_1+Arg_4 && 0 <= Arg_0+Arg_4 && 0 <= Arg_2 && 0 <= Arg_1+Arg_2 && 0 <= Arg_0+Arg_2 && 0 <= Arg_1 && 0 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 0 <= Arg_0 popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Compl Integ Trans Syste 26843