Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Compl Integ Trans Syste 26843 pair #381744749
details
property
value
status
complete
benchmark
perfect1.c.koat
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n035.star.cs.uiowa.edu
space
Flores-Montoya_16
run statistics
property
value
solver
AProVE
configuration
complexity
runtime (wallclock)
19.7012650967 seconds
cpu usage
26.416299338
max memory
5.27548416E8
stage attributes
key
value
output-size
19453
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(23, 15 + 4 * Arg_0) + max(4, 2 * Arg_0) * nat(Arg_0) + nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) * nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) + max(3, 2 + Arg_0) + max(10, -10 + 10 * Arg_0) + max(9, -9 + 9 * Arg_0) + max(5, -5 + 5 * Arg_0) + nat(-2 + 2 * Arg_0) + max(-14 + 14 * Arg_0, 14) + max(8, -8 + 8 * Arg_0)). (0) CpxIntTrs (1) Loat Proof [FINISHED, 2154 ms] (2) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_perfect1_start(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x <= 1 eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x > 1 eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_6(v__y3_0, v_x - 1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_6(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_1, v_y2_1, v_x)) :|: TRUE eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_x, v_y3_0)) :|: v_y1_0 > 0 eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y1_0 <= 0 eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= v_y1_0 eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < v_y1_0 eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1 - v_y1_0, v_y3_0)) :|: TRUE eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_12(v__y3_0, v_1, v_y3_0 - v_y1_0, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_12(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_6, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= 0 && v_y2_1 <= 0 eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < 0 eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 > 0 eval_perfect1_14(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_16(v__y3_0, v_1, v_6, v_y1_0 - 1, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_16(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_7, v_y2_1, v__y3_0)) :|: TRUE eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 < 0 eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 > 0 eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 >= 0 && v_y3_0 <= 0 eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_stop(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE The start-symbols are:[eval_perfect1_start_8] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalperfect1start 0: evalperfect1start -> evalperfect1bb0in : [], cost: 1 1: evalperfect1bb0in -> evalperfect10 : [], cost: 1 2: evalperfect10 -> evalperfect11 : [], cost: 1 3: evalperfect11 -> evalperfect1bb7in : [ 1>=A ], cost: 1 4: evalperfect11 -> evalperfect1bb1in : [ A>=2 ], cost: 1 5: evalperfect1bb1in -> evalperfect12 : [], cost: 1 6: evalperfect12 -> evalperfect13 : [], cost: 1 7: evalperfect13 -> evalperfect14 : [], cost: 1 8: evalperfect14 -> evalperfect15 : [], cost: 1 9: evalperfect15 -> evalperfect16 : B'=-1+A, [], cost: 1 10: evalperfect16 -> evalperfect17 : [], cost: 1 11: evalperfect17 -> evalperfect18 : [], cost: 1 12: evalperfect18 -> evalperfect1bb2in : C'=B, D'=A, [], cost: 1 13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1 14: evalperfect1bb2in -> evalperfect1bb6in : [ 0>=C ], cost: 1
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Compl Integ Trans Syste 26843