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


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


WORST_CASE(NON_POLY, ?)
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(INF, INF).

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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalEx5start(A, B, C, D, E) -> Com_1(evalEx5entryin(A, B, C, D, E)) :|: TRUE
evalEx5entryin(A, B, C, D, E) -> Com_1(evalEx5bb6in(0, A, C, D, E)) :|: TRUE
evalEx5bb6in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, 0, B, E)) :|: B >= A + 1
evalEx5bb6in(A, B, C, D, E) -> Com_1(evalEx5returnin(A, B, C, D, E)) :|: A >= B
evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb1in(A, B, C, D, E)) :|: 0 >= F + 1
evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb1in(A, B, C, D, E)) :|: F >= 1
evalEx5bb3in(A, B, C, D, E) -> Com_1(evalEx5bb4in(A, B, C, D, E)) :|: TRUE
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: 0 >= F + 1
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: 0 >= F + 1 && F >= 1
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D - 1)) :|: F >= 1
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, C, D - 1, E)) :|: 0 >= 1
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb2in(A, B, C, D, D)) :|: 0 >= 1
evalEx5bb1in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, C, D, E)) :|: TRUE
evalEx5bb2in(A, B, C, D, E) -> Com_1(evalEx5bb3in(A, B, 1, E, E)) :|: TRUE
evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A + 1, D, C, D, E)) :|: C >= 0 && C <= 0
evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A, D, C, D, E)) :|: 0 >= C + 1
evalEx5bb4in(A, B, C, D, E) -> Com_1(evalEx5bb6in(A, D, C, D, E)) :|: C >= 1
evalEx5returnin(A, B, C, D, E) -> Com_1(evalEx5stop(A, B, C, D, E)) :|: TRUE

The start-symbols are:[evalEx5start_5]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalEx5start

      0: evalEx5start -> evalEx5entryin : [], cost: 1

      1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

      3: evalEx5bb6in -> evalEx5returnin : [ A>=B ], cost: 1

      4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1

      5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1

      6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1

      7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1

      8: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_3 && free_3>=1 ], cost: 1

      9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1

     10: evalEx5bb1in -> evalEx5bb3in : D'=-1+D, [ 0>=1 ], cost: 1

     11: evalEx5bb1in -> evalEx5bb2in : E'=D, [ 0>=1 ], cost: 1

     12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1

     13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1

     14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1

     15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1

     16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1

     17: evalEx5returnin -> evalEx5stop : [], cost: 1



Checking for constant complexity:

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

      0: evalEx5start -> evalEx5entryin : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalEx5start

      0: evalEx5start -> evalEx5entryin : [], cost: 1

      1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

      4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1

      5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1

      6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1

      7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1

      8: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_3 && free_3>=1 ], cost: 1

      9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1

     10: evalEx5bb1in -> evalEx5bb3in : D'=-1+D, [ 0>=1 ], cost: 1

     11: evalEx5bb1in -> evalEx5bb2in : E'=D, [ 0>=1 ], cost: 1

     12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1

     13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1

     14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1

     15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1

     16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1



Removed rules with unsatisfiable guard:

   Start location: evalEx5start

      0: evalEx5start -> evalEx5entryin : [], cost: 1

      1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

      4: evalEx5bb3in -> evalEx5bb1in : [ 0>=1+free ], cost: 1

      5: evalEx5bb3in -> evalEx5bb1in : [ free_1>=1 ], cost: 1

      6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1

      7: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ 0>=1+free_2 ], cost: 1

      9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [ free_4>=1 ], cost: 1

     12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1

     13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1

     14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1

     15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1

     16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1



Simplified all rules, resulting in:

   Start location: evalEx5start

      0: evalEx5start -> evalEx5entryin : [], cost: 1

      1: evalEx5entryin -> evalEx5bb6in : A'=0, B'=A, [], cost: 1

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

      5: evalEx5bb3in -> evalEx5bb1in : [], cost: 1

      6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1

      9: evalEx5bb1in -> evalEx5bb2in : E'=-1+D, [], cost: 1

     12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1

     13: evalEx5bb2in -> evalEx5bb3in : C'=1, D'=E, [], cost: 1

     14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1

     15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1

     16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

      5: evalEx5bb3in -> evalEx5bb1in : [], cost: 1

      6: evalEx5bb3in -> evalEx5bb4in : [], cost: 1

     12: evalEx5bb1in -> evalEx5bb3in : [], cost: 1

     19: evalEx5bb1in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 2

     14: evalEx5bb4in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 1

     15: evalEx5bb4in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 1

     16: evalEx5bb4in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

     20: evalEx5bb3in -> evalEx5bb3in : [], cost: 2

     21: evalEx5bb3in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 3

     22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2

     23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2

     24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2



Accelerating simple loops of location 3.

   Accelerating the following rules:

     20: evalEx5bb3in -> evalEx5bb3in : [], cost: 2

     21: evalEx5bb3in -> evalEx5bb3in : C'=1, D'=-1+D, E'=-1+D, [], cost: 3



   Accelerated rule 20 with NONTERM, yielding the new rule 25.

   Accelerated rule 21 with NONTERM, yielding the new rule 26.

   Removing the simple loops: 20 21.

   Also removing duplicate rules: 25.



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

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

     22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2

     23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2

     24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2

     26: evalEx5bb3in -> [9] : [], cost: NONTERM



Chained accelerated rules (with incoming rules):

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

      2: evalEx5bb6in -> evalEx5bb3in : C'=0, D'=B, [ B>=1+A ], cost: 1

     27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: NONTERM

     22: evalEx5bb3in -> evalEx5bb6in : A'=1+A, B'=D, [ C==0 ], cost: 2

     23: evalEx5bb3in -> evalEx5bb6in : B'=D, [ 0>=1+C ], cost: 2

     24: evalEx5bb3in -> evalEx5bb6in : B'=D, [ C>=1 ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

     27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: NONTERM

     28: evalEx5bb6in -> evalEx5bb6in : A'=1+A, B'=B, C'=0, D'=B, [ B>=1+A ], cost: 3



Accelerating simple loops of location 2.

   Simplified some of the simple loops (and removed duplicate rules).

   Accelerating the following rules:

     28: evalEx5bb6in -> evalEx5bb6in : A'=1+A, C'=0, D'=B, [ B>=1+A ], cost: 3



   Accelerated rule 28 with metering function -A+B, yielding the new rule 29.

   Removing the simple loops: 28.



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

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

     27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: NONTERM

     29: evalEx5bb6in -> evalEx5bb6in : A'=B, C'=0, D'=B, [ B>=1+A ], cost: -3*A+3*B



Chained accelerated rules (with incoming rules):

   Start location: evalEx5start

     18: evalEx5start -> evalEx5bb6in : A'=0, B'=A, [], cost: 2

     30: evalEx5start -> evalEx5bb6in : B'=A, C'=0, D'=A, [ A>=1 ], cost: 2+3*A

     27: evalEx5bb6in -> [9] : C'=0, D'=B, [ B>=1+A ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: evalEx5start

     31: evalEx5start -> [9] : A'=0, B'=A, C'=0, D'=A, [ A>=1 ], cost: NONTERM

     32: evalEx5start -> [11] : [ A>=1 ], cost: 2+3*A



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalEx5start

     31: evalEx5start -> [9] : A'=0, B'=A, C'=0, D'=A, [ A>=1 ], cost: NONTERM

     32: evalEx5start -> [11] : [ A>=1 ], cost: 2+3*A



Computing asymptotic complexity for rule 31

   Guard is satisfiable, yielding nontermination

   Resulting cost NONTERM has complexity: Nonterm



Found new complexity Nonterm.



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

   Complexity:  Nonterm

   Cpx degree:  Nonterm

   Solved cost: NONTERM

   Rule cost:   NONTERM

   Rule guard:  [ A>=1 ]



NO


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

(2)
BOUNDS(INF, INF)