details

property	value
status	complete
benchmark	CPU2006_load_mems.c
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n160.star.cs.uiowa.edu
space	Sinn_2016

run statistics

property	value
solver	AProVE
configuration	c_complexity
runtime (wallclock)	5.62792 seconds
cpu usage	6.98402
user time	6.43152
system time	0.552503
max virtual memory	1.8756396E7
max residence set size	312104.0

stage attributes

key	value
starexec-result	WORST_CASE(?, O(n^3))

output

6.88/5.56 WORST_CASE(?, O(n^3)) 6.88/5.58 proof of /export/starexec/sandbox/output/output_files/bench.koat 6.88/5.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.88/5.58 6.88/5.58 6.88/5.58 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, n^3). 6.88/5.58 6.88/5.58 (0) CpxIntTrs 6.88/5.58 (1) Koat Proof [FINISHED, 4294 ms] 6.88/5.58 (2) BOUNDS(1, n^3) 6.88/5.58 6.88/5.58 6.88/5.58 ---------------------------------------- 6.88/5.58 6.88/5.58 (0) 6.88/5.58 Obligation: 6.88/5.58 Complexity Int TRS consisting of the following rules: 6.88/5.58 eval_load_mems_start(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb0_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_bb0_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb1_in(v_ptr, v_word_num_, v_bit_num_, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_bb1_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb2_in(v_.0, v_.01, v_.02, v_.01, v_.02, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.0 > 0 6.88/5.58 eval_load_mems_bb1_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb9_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.0 <= 0 6.88/5.58 eval_load_mems_bb2_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb3_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.1 < 2 6.88/5.58 eval_load_mems_bb2_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb8_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.1 >= 2 6.88/5.58 eval_load_mems_bb3_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_0(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_0(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_2(eval_random_start(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_), eval_load_mems_1(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, nondef.0, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_1(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb4_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.13, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_2 < 0 6.88/5.58 eval_load_mems_1(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb4_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.13, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_2 > 0 6.88/5.58 eval_load_mems_1(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb7_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_2 >= 0 && v_2 <= 0 6.88/5.58 eval_load_mems_bb4_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb5_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.2 < 64 6.88/5.58 eval_load_mems_bb4_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb7_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_.2 >= 64 6.88/5.58 eval_load_mems_bb5_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_2(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_2(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_2(eval_random_start(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_), eval_load_mems_3(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, nondef.1, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_3(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb7_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_5 < 0 6.88/5.58 eval_load_mems_3(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb7_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_5 > 0 6.88/5.58 eval_load_mems_3(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb6_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: v_5 >= 0 && v_5 <= 0 6.88/5.58 eval_load_mems_bb6_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb4_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2 + 1, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_bb7_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb2_in(v_.0, v_.01, v_.02, v_.1 + 1, 0, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_bb8_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_bb1_in(v_.0 - 1, 0, v_.13, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 eval_load_mems_bb9_in(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_) -> Com_1(eval_load_mems_stop(v_.0, v_.01, v_.02, v_.1, v_.13, v_.2, v_2, v_5, v_bit_num_, v_ptr, v_word_num_)) :|: TRUE 6.88/5.58 6.88/5.58 The start-symbols are:[eval_load_mems_start_11] 6.88/5.58 6.88/5.58 6.88/5.58 ---------------------------------------- 6.88/5.58 6.88/5.58 (1) Koat Proof (FINISHED) 6.88/5.58 YES(?, 13297*ar_1 + 126560*ar_1^2 + 50912*ar_1*ar_3 + 320*ar_3 + 262248*ar_1^3 + 149856*ar_1^2*ar_3 + 4116*ar_1^2*ar_5 + 2352*ar_1*ar_3*ar_5 + 1960*ar_1*ar_5 + 784*ar_3*ar_5 + 196*ar_5 + 89) 6.88/5.58 6.88/5.58 6.88/5.58 6.88/5.58 Initial complexity problem: 6.88/5.58 6.88/5.58 1: T: 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb1in(ar_1, ar_1, ar_3, ar_3, ar_5, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_2, ar_4, ar_8, ar_9, ar_10, ar_11)) [ ar_0 >= 1 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb9in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_0 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 1 >= ar_6 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_6 >= 2 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmems0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems00(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalrandomstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems01(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmems1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_9, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_2(evalloadmems00(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, m, ar_10, ar_11), evalloadmems01(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, m, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_7, ar_11)) [ 0 >= ar_8 + 1 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_7, ar_11)) [ ar_8 >= 1 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_8 = 0 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 63 >= ar_10 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_10 >= 64 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmems2(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems20(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalrandomstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmems3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_9)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems2(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_2(evalloadmems20(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, m, ar_10, ar_11), evalloadmems21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, m, ar_10, ar_11)) 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ 0 >= ar_11 + 1 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_11 >= 1 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmems3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11)) [ ar_11 = 0 ] 6.88/5.58 6.88/5.58 (Comp: ?, Cost: 1) evalloadmemsbb6in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10, ar_11) -> Com_1(evalloadmemsbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9, ar_10 + 1, ar_11)) 6.88/5.58 popout

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

job log

popout

actions

all output return to Complexity_C_Integer 2019-03-21 04.38