details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	15.110574007 seconds
cpu usage	21.190643612
max memory	4.77196288E8

stage attributes

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

output

/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^3), O(n^4)) proof of /export/starexec/sandbox2/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^3, n^4). (0) CpxIntTrs (1) Koat Proof [FINISHED, 937 ms] (2) BOUNDS(1, n^4) (3) Loat Proof [FINISHED, 2648 ms] (4) BOUNDS(n^3, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_abc_start(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb0_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_bb0_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_0(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_0(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_1(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_1(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_2(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_2(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_3(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_3(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_4(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_4(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_5(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_5(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_6(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_6(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_7(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_7(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_8(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_8(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb1_in(v_6, v_7, v_a, v_b, v_c, v_d, v_a, v_j_0, v_k_0)) :|: TRUE eval_abc_bb1_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb2_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_c, v_k_0)) :|: v_i_0 <= v_b eval_abc_bb1_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb8_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: v_i_0 > v_b eval_abc_bb2_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb3_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: v_j_0 <= v_d eval_abc_bb2_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb7_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: v_j_0 > v_d eval_abc_bb3_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb4_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_i_0 - v_j_0)) :|: TRUE eval_abc_bb4_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb5_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: v_k_0 <= v_i_0 + v_j_0 eval_abc_bb4_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb6_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: v_k_0 > v_i_0 + v_j_0 eval_abc_bb5_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb4_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0 + 1)) :|: TRUE eval_abc_bb6_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_16(v_j_0 + 1, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_16(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_17(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_17(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb2_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_6, v_k_0)) :|: TRUE eval_abc_bb7_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_19(v_6, v_i_0 + 1, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_19(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_20(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE eval_abc_20(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_bb1_in(v_6, v_7, v_a, v_b, v_c, v_d, v_7, v_j_0, v_k_0)) :|: TRUE eval_abc_bb8_in(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0) -> Com_1(eval_abc_stop(v_6, v_7, v_a, v_b, v_c, v_d, v_i_0, v_j_0, v_k_0)) :|: TRUE The start-symbols are:[eval_abc_start_9] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 489*ar_1 + 489*ar_2 + 508*ar_1*ar_4 + 508*ar_2*ar_4 + 504*ar_1*ar_5 + 504*ar_2*ar_5 + 456*ar_4 + 452*ar_5 + 52*ar_1^2*ar_4 + 104*ar_1*ar_2*ar_4 + 52*ar_1^2*ar_5 + 104*ar_1*ar_2*ar_5 + 36*ar_1^2 + 72*ar_1*ar_2 + 52*ar_2^2*ar_4 + 52*ar_2^2*ar_5 + 36*ar_2^2 + 36*ar_1*ar_4^2 + 36*ar_2*ar_4^2 + 68*ar_1*ar_4*ar_5 + 68*ar_2*ar_4*ar_5 + 20*ar_4^2 + 36*ar_4*ar_5 + 16*ar_1^2*ar_4^2 + 32*ar_1*ar_2*ar_4^2 + 32*ar_1^2*ar_4*ar_5 + 64*ar_1*ar_2*ar_4*ar_5 + 16*ar_2^2*ar_4^2 + 32*ar_2^2*ar_4*ar_5 + 16*ar_1^2*ar_5^2 + 32*ar_1*ar_2*ar_5^2 + 32*ar_1*ar_5^2 + 16*ar_2^2*ar_5^2 + 32*ar_2*ar_5^2 + 16*ar_5^2 + 468) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalabcstart(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabcbb0in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc1(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc2(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc2(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc3(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc4(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc4(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc5(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc5(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc6(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc6(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc7(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc7(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabc8(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabc8(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb1in(ar_1, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabcbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb2in(ar_0, ar_1, ar_2, ar_4, ar_4, ar_5, ar_6, ar_7, ar_8)) [ ar_2 >= ar_0 ] (Comp: ?, Cost: 1) evalabcbb1in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb8in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) [ ar_0 >= ar_2 + 1 ] (Comp: ?, Cost: 1) evalabcbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) [ ar_5 >= ar_3 ] (Comp: ?, Cost: 1) evalabcbb2in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb7in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) [ ar_3 >= ar_5 + 1 ] (Comp: ?, Cost: 1) evalabcbb3in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_0 - ar_3, ar_7, ar_8)) (Comp: ?, Cost: 1) evalabcbb4in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8) -> Com_1(evalabcbb5in(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8)) [ ar_0 + ar_3 >= ar_6 ] popout

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

job log

popout

actions

all output return to Compl Integ Trans Syste 26843