/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, 628 ms]
(2) BOUNDS(INF, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalcousot9start(A, B, C) -> Com_1(evalcousot9entryin(A, B, C)) :|: TRUE
evalcousot9entryin(A, B, C) -> Com_1(evalcousot9bb3in(D, C, C)) :|: TRUE
evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9bbin(A, B, C)) :|: B >= 1
evalcousot9bb3in(A, B, C) -> Com_1(evalcousot9returnin(A, B, C)) :|: 0 >= B
evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb1in(A, B, C)) :|: A >= 1
evalcousot9bbin(A, B, C) -> Com_1(evalcousot9bb2in(A, B, C)) :|: 0 >= A
evalcousot9bb1in(A, B, C) -> Com_1(evalcousot9bb3in(A - 1, B, C)) :|: TRUE
evalcousot9bb2in(A, B, C) -> Com_1(evalcousot9bb3in(C, B - 1, C)) :|: TRUE
evalcousot9returnin(A, B, C) -> Com_1(evalcousot9stop(A, B, C)) :|: TRUE

The start-symbols are:[evalcousot9start_3]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalcousot9start

      0: evalcousot9start -> evalcousot9entryin : [], cost: 1

      1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1

      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1

      3: evalcousot9bb3in -> evalcousot9returnin : [ 0>=B ], cost: 1

      4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1

      5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1

      6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1

      7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1

      8: evalcousot9returnin -> evalcousot9stop : [], cost: 1



Checking for constant complexity:

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

      0: evalcousot9start -> evalcousot9entryin : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalcousot9start

      0: evalcousot9start -> evalcousot9entryin : [], cost: 1

      1: evalcousot9entryin -> evalcousot9bb3in : A'=free, B'=C, [], cost: 1

      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1

      4: evalcousot9bbin -> evalcousot9bb1in : [ A>=1 ], cost: 1

      5: evalcousot9bbin -> evalcousot9bb2in : [ 0>=A ], cost: 1

      6: evalcousot9bb1in -> evalcousot9bb3in : A'=-1+A, [], cost: 1

      7: evalcousot9bb2in -> evalcousot9bb3in : A'=C, B'=-1+B, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalcousot9start

      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2

      2: evalcousot9bb3in -> evalcousot9bbin : [ B>=1 ], cost: 1

     10: evalcousot9bbin -> evalcousot9bb3in : A'=-1+A, [ A>=1 ], cost: 2

     11: evalcousot9bbin -> evalcousot9bb3in : A'=C, B'=-1+B, [ 0>=A ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalcousot9start

      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2

     12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3

     13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3



Accelerating simple loops of location 2.

   Accelerating the following rules:

     12: evalcousot9bb3in -> evalcousot9bb3in : A'=-1+A, [ B>=1 && A>=1 ], cost: 3

     13: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=-1+B, [ B>=1 && 0>=A ], cost: 3



   Accelerated rule 12 with metering function A, yielding the new rule 14.

   Accelerated rule 13 with metering function B (after strengthening guard), yielding the new rule 15.

   Nested simple loops 13 (outer loop) and 14 (inner loop) with metering function -1+B, resulting in the new rules: 16, 17.

   Removing the simple loops: 12 13.



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

   Start location: evalcousot9start

      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2

     14: evalcousot9bb3in -> evalcousot9bb3in : A'=0, [ B>=1 && A>=1 ], cost: 3*A

     15: evalcousot9bb3in -> evalcousot9bb3in : A'=C, B'=0, [ B>=1 && 0>=A && 0>=C ], cost: 3*B

     16: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ 0>=A && -1+B>=1 && C>=1 ], cost: -3+3*C*(-1+B)+3*B

     17: evalcousot9bb3in -> evalcousot9bb3in : A'=0, B'=1, [ A>=1 && -1+B>=1 && C>=1 ], cost: -3+3*A+3*C*(-1+B)+3*B



Chained accelerated rules (with incoming rules):

   Start location: evalcousot9start

      9: evalcousot9start -> evalcousot9bb3in : A'=free, B'=C, [], cost: 2

     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free

     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)

     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*free+3*C*(-1+C)



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

   Start location: evalcousot9start

     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free

     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)

     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*free+3*C*(-1+C)



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalcousot9start

     18: evalcousot9start -> evalcousot9bb3in : A'=0, B'=C, [ C>=1 && free>=1 ], cost: 2+3*free

     19: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ -1+C>=1 ], cost: -1+3*C+3*C*(-1+C)

     20: evalcousot9start -> evalcousot9bb3in : A'=0, B'=1, [ free>=1 && -1+C>=1 ], cost: -1+3*C+3*free+3*C*(-1+C)



Computing asymptotic complexity for rule 18

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      C (+/+!), 2+3*free (+), free (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {C==1,free==n}

      resulting limit problem:

      [solved]



   Solution:

      C / 1

      free / n

   Resulting cost 2+3*n has complexity: Unbounded



Found new complexity Unbounded.



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

   Complexity:  Unbounded

   Cpx degree:  Unbounded

   Solved cost: 2+3*n

   Rule cost:   2+3*free

   Rule guard:  [ C>=1 && free>=1 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)