Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744773
details
property
value
status
complete
benchmark
ex_paper3.c.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n103.star.cs.uiowa.edu
space
Flores-Montoya_16
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
14.6364839077 seconds
cpu usage
20.251146449
max memory
5.03283712E8
stage attributes
key
value
output-size
56960
starexec-result
WORST_CASE(Omega(n^1), O(n^2))
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^1), O(n^2)) 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^1, max(10 + Arg_1, 10) + nat(2 + 2 * Arg_1) + nat(2 * Arg_1) + nat(-3 * Arg_1 + 3 * Arg_1 * Arg_7 + 3 * Arg_1^2) + nat(2 * Arg_1 + 2 * Arg_3) + nat(4 * Arg_1 * Arg_7 + Arg_1 * nat(-4 + 4 * Arg_1)) + max(2, 2 + Arg_1 + Arg_3) + nat(9 * Arg_1) + nat(2 + 8 * Arg_1) + nat(-1 * Arg_1 + Arg_1 * Arg_7 + Arg_1 * max(6, 6 * Arg_1)) + nat(6 * Arg_1 + Arg_3) + nat(4 * Arg_1 + 4 * Arg_3)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 12.1 s] (2) BOUNDS(1, max(10 + Arg_1, 10) + nat(2 + 2 * Arg_1) + nat(2 * Arg_1) + nat(-3 * Arg_1 + 3 * Arg_1 * Arg_7 + 3 * Arg_1^2) + nat(2 * Arg_1 + 2 * Arg_3) + nat(4 * Arg_1 * Arg_7 + Arg_1 * nat(-4 + 4 * Arg_1)) + max(2, 2 + Arg_1 + Arg_3) + nat(9 * Arg_1) + nat(2 + 8 * Arg_1) + nat(-1 * Arg_1 + Arg_1 * Arg_7 + Arg_1 * max(6, 6 * Arg_1)) + nat(6 * Arg_1 + Arg_3) + nat(4 * Arg_1 + 4 * Arg_3)) (3) Loat Proof [FINISHED, 2152 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_p3_start(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb0_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_bb0_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_0(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_0(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_1(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_1(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_2(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_2(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_3(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_3(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_4(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_4(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_5(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_5(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_6(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_6(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_7(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_7(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb1_in(v_x, v_y, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_bb1_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb2_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: v__0 > 0 eval_p3_bb1_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb7_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: v__0 <= 0 eval_p3_bb2_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb3_in(v__0, v__01, v__01, v__3, v_12, v_x, v_y, v_z)) :|: nondef_0 < 0 eval_p3_bb2_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb3_in(v__0, v__01, v__01, v__3, v_12, v_x, v_y, v_z)) :|: nondef_0 > 0 eval_p3_bb2_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb5_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: nondef_0 >= 0 && nondef_0 <= 0 eval_p3_bb3_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb4_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: nondef_1 < 0 && v__1 > 0 eval_p3_bb3_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb4_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: nondef_1 > 0 && v__1 > 0 eval_p3_bb3_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb6_in(v__0, v__01, v__1, v__1, v_12, v_x, v_y, v_z)) :|: nondef_1 >= 0 && nondef_1 <= 0 eval_p3_bb3_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb6_in(v__0, v__01, v__1, v__1, v_12, v_x, v_y, v_z)) :|: v__1 <= 0 eval_p3_bb4_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_15(v__0, v__01, v__1, v__3, v__1 - 1, v_x, v_y, v_z)) :|: TRUE eval_p3_15(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_16(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_16(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb3_in(v__0, v__01, v_12, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_bb5_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb6_in(v__0, v__01, v__1, v__01 + 1, v_12, v_x, v_y, v_z)) :|: nondef_2 < 0 eval_p3_bb5_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb6_in(v__0, v__01, v__1, v__01 + 1, v_12, v_x, v_y, v_z)) :|: nondef_2 > 0 eval_p3_bb5_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb6_in(v__0, v__01, v__1, v_z, v_12, v_x, v_y, v_z)) :|: nondef_2 >= 0 && nondef_2 <= 0 eval_p3_bb6_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_bb1_in(v__0 - 1, v__3, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE eval_p3_bb7_in(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z) -> Com_1(eval_p3_stop(v__0, v__01, v__1, v__3, v_12, v_x, v_y, v_z)) :|: TRUE The start-symbols are:[eval_p3_start_8] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 10+max([0, Arg_1])+max([0, 1+Arg_1])+max([0, Arg_1])+max([0, Arg_1*(-1+Arg_7+Arg_1)])+max([0, 3*Arg_1])+max([0, 1+4*Arg_1])+max([0, Arg_1])+max([0, Arg_1*(-1+Arg_7+max([6, 6*Arg_1]))])+max([0, Arg_3+6*Arg_1])+max([0, 4*Arg_1+4*Arg_3])+max([0, 3*Arg_1])+max([0, 1+4*Arg_1])+max([0, 3*Arg_1])+max([0, Arg_1*(-1+Arg_7+Arg_1)])+max([0, Arg_1+Arg_3])+max([0, Arg_1*(-1+Arg_7+Arg_1)])+max([0, Arg_1+Arg_3])+max([0, Arg_1*(4*Arg_7+max([0, -4+4*Arg_1]))])+max([0, 1+Arg_1])+max([2, 2+Arg_1+Arg_3]) {O(n^2)}) Initial Complexity Problem: Start: evalp3start Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7 Temp_Vars: I Locations: evalp30, evalp31, evalp315, evalp316, evalp32, evalp33, evalp34, evalp35, evalp36, evalp37, evalp3bb0in, evalp3bb1in, evalp3bb2in, evalp3bb3in, evalp3bb4in, evalp3bb5in, evalp3bb6in, evalp3bb7in, evalp3start, evalp3stop Transitions: evalp30(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp31(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp31(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp32(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp315(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp316(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|:1+Arg_6 <= Arg_4 && 1+Arg_6 <= Arg_2 && 0 <= Arg_6 && 1 <= Arg_4+Arg_6 && Arg_4 <= 1+Arg_6 && 1 <= Arg_2+Arg_6 && 1 <= Arg_1+Arg_6 && 1 <= Arg_0+Arg_6 && Arg_4 <= Arg_2 && 1 <= Arg_4 && 2 <= Arg_2+Arg_4 && 2 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 1 <= Arg_0 evalp316(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp3bb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_6,Arg_5,Arg_6,Arg_7):|:1+Arg_6 <= Arg_4 && 1+Arg_6 <= Arg_2 && 0 <= Arg_6 && 1 <= Arg_4+Arg_6 && Arg_4 <= 1+Arg_6 && 1 <= Arg_2+Arg_6 && 1 <= Arg_1+Arg_6 && 1 <= Arg_0+Arg_6 && Arg_4 <= Arg_2 && 1 <= Arg_4 && 2 <= Arg_2+Arg_4 && 2 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 1 <= Arg_0 evalp32(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp33(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp33(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp34(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp34(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp35(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp35(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp36(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp36(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp37(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp37(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp3bb1in(Arg_1,Arg_1,Arg_3,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp3bb0in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp30(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|: evalp3bb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp3bb2in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|:Arg_0 <= Arg_1 && 1 <= Arg_0 evalp3bb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7) -> evalp3bb7in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5,Arg_6,Arg_7):|:Arg_0 <= Arg_1 && Arg_0 <= 0
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843