/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


MAYBE
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 408 ms]
(2) BOUNDS(1, INF)


----------------------------------------

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_speedFails1_start(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb0_in(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_bb0_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_0(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_0(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_1(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_1(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_2(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_2(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_3(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_3(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_4(v__0, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_4(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb1_in(v_i, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_bb1_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb2_in(v__0, v_i, v_m, v_n)) :|: v__0 <= v_n
eval_speedFails1_bb1_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb3_in(v__0, v_i, v_m, v_n)) :|: v__0 > v_n
eval_speedFails1_bb2_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_bb1_in(v__0 + v_m, v_i, v_m, v_n)) :|: TRUE
eval_speedFails1_bb3_in(v__0, v_i, v_m, v_n) -> Com_1(eval_speedFails1_stop(v__0, v_i, v_m, v_n)) :|: TRUE

The start-symbols are:[eval_speedFails1_start_4]


----------------------------------------

(1) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalspeedFails1start

      0: evalspeedFails1start -> evalspeedFails1bb0in : [], cost: 1

      1: evalspeedFails1bb0in -> evalspeedFails10 : [], cost: 1

      2: evalspeedFails10 -> evalspeedFails11 : [], cost: 1

      3: evalspeedFails11 -> evalspeedFails12 : [], cost: 1

      4: evalspeedFails12 -> evalspeedFails13 : [], cost: 1

      5: evalspeedFails13 -> evalspeedFails14 : [], cost: 1

      6: evalspeedFails14 -> evalspeedFails1bb1in : A'=B, [], cost: 1

      7: evalspeedFails1bb1in -> evalspeedFails1bb2in : [ C>=A ], cost: 1

      8: evalspeedFails1bb1in -> evalspeedFails1bb3in : [ A>=1+C ], cost: 1

      9: evalspeedFails1bb2in -> evalspeedFails1bb1in : A'=D+A, [], cost: 1

     10: evalspeedFails1bb3in -> evalspeedFails1stop : [], cost: 1



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

      0: evalspeedFails1start -> evalspeedFails1bb0in : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalspeedFails1start

      0: evalspeedFails1start -> evalspeedFails1bb0in : [], cost: 1

      1: evalspeedFails1bb0in -> evalspeedFails10 : [], cost: 1

      2: evalspeedFails10 -> evalspeedFails11 : [], cost: 1

      3: evalspeedFails11 -> evalspeedFails12 : [], cost: 1

      4: evalspeedFails12 -> evalspeedFails13 : [], cost: 1

      5: evalspeedFails13 -> evalspeedFails14 : [], cost: 1

      6: evalspeedFails14 -> evalspeedFails1bb1in : A'=B, [], cost: 1

      7: evalspeedFails1bb1in -> evalspeedFails1bb2in : [ C>=A ], cost: 1

      9: evalspeedFails1bb2in -> evalspeedFails1bb1in : A'=D+A, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalspeedFails1start

     16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7

     17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2



Accelerating simple loops of location 7.

   Accelerating the following rules:

     17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2



   Found no metering function for rule 17.

   Removing the simple loops:.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalspeedFails1start

     16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7

     17: evalspeedFails1bb1in -> evalspeedFails1bb1in : A'=D+A, [ C>=A ], cost: 2



Chained accelerated rules (with incoming rules):

   Start location: evalspeedFails1start

     16: evalspeedFails1start -> evalspeedFails1bb1in : A'=B, [], cost: 7

     18: evalspeedFails1start -> evalspeedFails1bb1in : A'=D+B, [ C>=B ], cost: 9



Removed unreachable locations (and leaf rules with constant cost):

   Start location: evalspeedFails1start

     <empty>



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalspeedFails1start

     <empty>



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Constant

   Cpx degree:  0

   Solved cost: 1

   Rule cost:   1

   Rule guard:  []



WORST_CASE(Omega(1),?)


----------------------------------------

(2)
BOUNDS(1, INF)