details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	3.63658499718 seconds
cpu usage	6.314920306
max memory	3.0255104E8

stage attributes

key	value
output-size	19273
starexec-result	WORST_CASE(?, O(n^1))

output

/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) 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(1, max(2, 203 + -2 * Arg_1 + -2 * Arg_3 + 2 * Arg_5) + max(11, 112 + -1 * Arg_1 + -1 * Arg_3 + Arg_5)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 1849 ms] (2) BOUNDS(1, max(2, 203 + -2 * Arg_1 + -2 * Arg_3 + 2 * Arg_5) + max(11, 112 + -1 * Arg_1 + -1 * Arg_3 + Arg_5)) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_terminate_start(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb0_in(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_bb0_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_0(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_0(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_1(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_1(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_2(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_2(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_3(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_3(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_4(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_4(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_5(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_5(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_6(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_6(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_7(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE eval_terminate_7(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb1_in(v_i, v_j, v_k, v_i, v_j, v_k)) :|: TRUE eval_terminate_bb1_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb2_in(v__0, v__01, v__02, v_i, v_j, v_k)) :|: v__0 <= 100 && v__01 <= v__02 eval_terminate_bb1_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb3_in(v__0, v__01, v__02, v_i, v_j, v_k)) :|: v__0 > 100 eval_terminate_bb1_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb3_in(v__0, v__01, v__02, v_i, v_j, v_k)) :|: v__01 > v__02 eval_terminate_bb2_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_bb1_in(v__01, v__0 + 1, v__02 - 1, v_i, v_j, v_k)) :|: TRUE eval_terminate_bb3_in(v__0, v__01, v__02, v_i, v_j, v_k) -> Com_1(eval_terminate_stop(v__0, v__01, v__02, v_i, v_j, v_k)) :|: TRUE The start-symbols are:[eval_terminate_start_6] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 2+max([0, 201+-2*Arg_1+-2*Arg_3+2*Arg_5])+max([11, 112+Arg_5+-(Arg_3)-Arg_1]) {O(n)}) Initial Complexity Problem: Start: evalterminatestart Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5 Temp_Vars: Locations: evalterminate0, evalterminate1, evalterminate2, evalterminate3, evalterminate4, evalterminate5, evalterminate6, evalterminate7, evalterminatebb0in, evalterminatebb1in, evalterminatebb2in, evalterminatebb3in, evalterminatestart, evalterminatestop Transitions: evalterminate0(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate1(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate2(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate3(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate3(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate4(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate4(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate5(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate6(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate6(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate7(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminate7(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb1in(Arg_1,Arg_1,Arg_3,Arg_3,Arg_5,Arg_5):|: evalterminatebb0in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminate0(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalterminatebb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb2in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_5 && Arg_0 <= 100 && Arg_2 <= Arg_4 evalterminatebb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_5 && 101 <= Arg_0 evalterminatebb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_5 && Arg_4+1 <= Arg_2 evalterminatebb2in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb1in(Arg_2,Arg_1,Arg_0+1,Arg_3,Arg_4-1,Arg_5):|:Arg_4 <= Arg_5 && Arg_2 <= Arg_5 && Arg_2 <= Arg_4 && Arg_0 <= 100 evalterminatebb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatestop(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_5 evalterminatestart(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalterminatebb0in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: Timebounds: Overall timebound: 2+max([0, 201+-2*Arg_1+-2*Arg_3+2*Arg_5])+max([11, 112+Arg_5+-(Arg_3)-Arg_1]) {O(n)} 2: evalterminate0->evalterminate1: 1 {O(1)} 3: evalterminate1->evalterminate2: 1 {O(1)} popout

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

job log

popout

actions

all output return to Compl Integ Trans Syste 26843