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


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


WORST_CASE(Omega(n^1), O(n^2))
proof of /export/starexec/sandbox2/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(4, 4 + 2 * Arg_0) + nat(2 + 2 * Arg_0) + nat(Arg_0 + Arg_0^2)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 856 ms]
(2) BOUNDS(1, max(4, 4 + 2 * Arg_0) + nat(2 + 2 * Arg_0) + nat(Arg_0 + Arg_0^2))
(3) Loat Proof [FINISHED, 318 ms]
(4) BOUNDS(n^1, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalfstart(A, B, C) -> Com_1(evalfentryin(A, B, C)) :|: TRUE
evalfentryin(A, B, C) -> Com_1(evalfbb4in(B, A, C)) :|: TRUE
evalfbb4in(A, B, C) -> Com_1(evalfbb2in(A, B, A)) :|: B >= 1
evalfbb4in(A, B, C) -> Com_1(evalfreturnin(A, B, C)) :|: 0 >= B
evalfbb2in(A, B, C) -> Com_1(evalfbb1in(A, B, C)) :|: C >= A
evalfbb2in(A, B, C) -> Com_1(evalfbb3in(A, B, C)) :|: A >= C + 1
evalfbb1in(A, B, C) -> Com_1(evalfbb2in(A, B, C - 1)) :|: TRUE
evalfbb3in(A, B, C) -> Com_1(evalfbb4in(A, B - 1, C)) :|: TRUE
evalfreturnin(A, B, C) -> Com_1(evalfstop(A, B, C)) :|: TRUE

The start-symbols are:[evalfstart_3]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 4+2*max([0, Arg_0])+max([0, 1+Arg_0])+max([0, Arg_0*(1+Arg_0)])+max([0, 1+Arg_0]) {O(n^2)})



Initial Complexity Problem:

  Start:  evalfstart  

  Program_Vars:  Arg_0, Arg_1, Arg_2  

  Temp_Vars:    

  Locations:  evalfbb1in, evalfbb2in, evalfbb3in, evalfbb4in, evalfentryin, evalfreturnin, evalfstart, evalfstop  

  Transitions:

  evalfbb1in(Arg_0,Arg_1,Arg_2) -> evalfbb2in(Arg_0,Arg_1,Arg_2-1):|:Arg_2 <= Arg_0 && Arg_0 <= Arg_2 && 1 <= Arg_1

  evalfbb2in(Arg_0,Arg_1,Arg_2) -> evalfbb1in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_0 && 1 <= Arg_1 && Arg_0 <= Arg_2

  evalfbb2in(Arg_0,Arg_1,Arg_2) -> evalfbb3in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_0 && 1 <= Arg_1 && Arg_2+1 <= Arg_0

  evalfbb3in(Arg_0,Arg_1,Arg_2) -> evalfbb4in(Arg_0,Arg_1-1,Arg_2):|:1+Arg_2 <= Arg_0 && 1 <= Arg_1

  evalfbb4in(Arg_0,Arg_1,Arg_2) -> evalfbb2in(Arg_0,Arg_1,Arg_0):|:1 <= Arg_1

  evalfbb4in(Arg_0,Arg_1,Arg_2) -> evalfreturnin(Arg_0,Arg_1,Arg_2):|:Arg_1 <= 0

  evalfentryin(Arg_0,Arg_1,Arg_2) -> evalfbb4in(Arg_1,Arg_0,Arg_2):|:

  evalfreturnin(Arg_0,Arg_1,Arg_2) -> evalfstop(Arg_0,Arg_1,Arg_2):|:Arg_1 <= 0

  evalfstart(Arg_0,Arg_1,Arg_2) -> evalfentryin(Arg_0,Arg_1,Arg_2):|:  



Timebounds: 

  Overall timebound: 4+2*max([0, Arg_0])+max([0, 1+Arg_0])+max([0, Arg_0*(1+Arg_0)])+max([0, 1+Arg_0]) {O(n^2)}

  6: evalfbb1in->evalfbb2in: max([0, Arg_0*(1+Arg_0)]) {O(n^2)}

  4: evalfbb2in->evalfbb1in: max([0, 1+Arg_0]) {O(n)}

  5: evalfbb2in->evalfbb3in: max([0, Arg_0]) {O(n)}

  7: evalfbb3in->evalfbb4in: max([0, Arg_0]) {O(n)}

  2: evalfbb4in->evalfbb2in: max([0, 1+Arg_0]) {O(n)}

  3: evalfbb4in->evalfreturnin: 1 {O(1)}

  1: evalfentryin->evalfbb4in: 1 {O(1)}

  8: evalfreturnin->evalfstop: 1 {O(1)}

  0: evalfstart->evalfentryin: 1 {O(1)}



Costbounds:

  Overall costbound: 4+2*max([0, Arg_0])+max([0, 1+Arg_0])+max([0, Arg_0*(1+Arg_0)])+max([0, 1+Arg_0]) {O(n^2)}

  6: evalfbb1in->evalfbb2in: max([0, Arg_0*(1+Arg_0)]) {O(n^2)}

  4: evalfbb2in->evalfbb1in: max([0, 1+Arg_0]) {O(n)}

  5: evalfbb2in->evalfbb3in: max([0, Arg_0]) {O(n)}

  7: evalfbb3in->evalfbb4in: max([0, Arg_0]) {O(n)}

  2: evalfbb4in->evalfbb2in: max([0, 1+Arg_0]) {O(n)}

  3: evalfbb4in->evalfreturnin: 1 {O(1)}

  1: evalfentryin->evalfbb4in: 1 {O(1)}

  8: evalfreturnin->evalfstop: 1 {O(1)}

  0: evalfstart->evalfentryin: 1 {O(1)}



Sizebounds:

`Lower:

  6: evalfbb1in->evalfbb2in, Arg_0: Arg_1 {O(n)}

  6: evalfbb1in->evalfbb2in, Arg_1: 1 {O(1)}

  6: evalfbb1in->evalfbb2in, Arg_2: -1+Arg_1 {O(n)}

  4: evalfbb2in->evalfbb1in, Arg_0: Arg_1 {O(n)}

  4: evalfbb2in->evalfbb1in, Arg_1: 1 {O(1)}

  4: evalfbb2in->evalfbb1in, Arg_2: Arg_1 {O(n)}

  5: evalfbb2in->evalfbb3in, Arg_0: Arg_1 {O(n)}

  5: evalfbb2in->evalfbb3in, Arg_1: 1 {O(1)}

  5: evalfbb2in->evalfbb3in, Arg_2: -1+Arg_1 {O(n)}

  7: evalfbb3in->evalfbb4in, Arg_0: Arg_1 {O(n)}

  7: evalfbb3in->evalfbb4in, Arg_1: 0 {O(1)}

  7: evalfbb3in->evalfbb4in, Arg_2: -1+Arg_1 {O(n)}

  2: evalfbb4in->evalfbb2in, Arg_0: Arg_1 {O(n)}

  2: evalfbb4in->evalfbb2in, Arg_1: 1 {O(1)}

  2: evalfbb4in->evalfbb2in, Arg_2: Arg_1 {O(n)}

  3: evalfbb4in->evalfreturnin, Arg_0: Arg_1 {O(n)}

  3: evalfbb4in->evalfreturnin, Arg_1: min([0, Arg_0]) {O(n)}

  3: evalfbb4in->evalfreturnin, Arg_2: min([Arg_2, -(1-Arg_1)]) {O(n)}

  1: evalfentryin->evalfbb4in, Arg_0: Arg_1 {O(n)}

  1: evalfentryin->evalfbb4in, Arg_1: Arg_0 {O(n)}

  1: evalfentryin->evalfbb4in, Arg_2: Arg_2 {O(n)}

  8: evalfreturnin->evalfstop, Arg_0: Arg_1 {O(n)}

  8: evalfreturnin->evalfstop, Arg_1: min([0, Arg_0]) {O(n)}

  8: evalfreturnin->evalfstop, Arg_2: min([Arg_2, -(1-Arg_1)]) {O(n)}

  0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)}

  0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)}

  0: evalfstart->evalfentryin, Arg_2: Arg_2 {O(n)}

`Upper:

  6: evalfbb1in->evalfbb2in, Arg_0: Arg_1 {O(n)}

  6: evalfbb1in->evalfbb2in, Arg_1: Arg_0 {O(n)}

  6: evalfbb1in->evalfbb2in, Arg_2: -1+Arg_1 {O(n)}

  4: evalfbb2in->evalfbb1in, Arg_0: Arg_1 {O(n)}

  4: evalfbb2in->evalfbb1in, Arg_1: Arg_0 {O(n)}

  4: evalfbb2in->evalfbb1in, Arg_2: Arg_1 {O(n)}

  5: evalfbb2in->evalfbb3in, Arg_0: Arg_1 {O(n)}

  5: evalfbb2in->evalfbb3in, Arg_1: Arg_0 {O(n)}

  5: evalfbb2in->evalfbb3in, Arg_2: -1+Arg_1 {O(n)}

  7: evalfbb3in->evalfbb4in, Arg_0: Arg_1 {O(n)}

  7: evalfbb3in->evalfbb4in, Arg_1: Arg_0 {O(n)}

  7: evalfbb3in->evalfbb4in, Arg_2: -1+Arg_1 {O(n)}

  2: evalfbb4in->evalfbb2in, Arg_0: Arg_1 {O(n)}

  2: evalfbb4in->evalfbb2in, Arg_1: Arg_0 {O(n)}

  2: evalfbb4in->evalfbb2in, Arg_2: Arg_1 {O(n)}

  3: evalfbb4in->evalfreturnin, Arg_0: Arg_1 {O(n)}

  3: evalfbb4in->evalfreturnin, Arg_1: 0 {O(1)}

  3: evalfbb4in->evalfreturnin, Arg_2: max([Arg_2, -1+Arg_1]) {O(n)}

  1: evalfentryin->evalfbb4in, Arg_0: Arg_1 {O(n)}

  1: evalfentryin->evalfbb4in, Arg_1: Arg_0 {O(n)}

  1: evalfentryin->evalfbb4in, Arg_2: Arg_2 {O(n)}

  8: evalfreturnin->evalfstop, Arg_0: Arg_1 {O(n)}

  8: evalfreturnin->evalfstop, Arg_1: 0 {O(1)}

  8: evalfreturnin->evalfstop, Arg_2: max([Arg_2, -1+Arg_1]) {O(n)}

  0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)}

  0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)}

  0: evalfstart->evalfentryin, Arg_2: Arg_2 {O(n)}


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

(2)
BOUNDS(1, max(4, 4 + 2 * Arg_0) + nat(2 + 2 * Arg_0) + nat(Arg_0 + Arg_0^2))

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

(3) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalfstart

      0: evalfstart -> evalfentryin : [], cost: 1

      1: evalfentryin -> evalfbb4in : A'=B, B'=A, [], cost: 1

      2: evalfbb4in -> evalfbb2in : C'=A, [ B>=1 ], cost: 1

      3: evalfbb4in -> evalfreturnin : [ 0>=B ], cost: 1

      4: evalfbb2in -> evalfbb1in : [ C>=A ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ A>=1+C ], cost: 1

      6: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1

      7: evalfbb3in -> evalfbb4in : B'=-1+B, [], cost: 1

      8: evalfreturnin -> evalfstop : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalfstart

      0: evalfstart -> evalfentryin : [], cost: 1

      1: evalfentryin -> evalfbb4in : A'=B, B'=A, [], cost: 1

      2: evalfbb4in -> evalfbb2in : C'=A, [ B>=1 ], cost: 1

      4: evalfbb2in -> evalfbb1in : [ C>=A ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ A>=1+C ], cost: 1

      6: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1

      7: evalfbb3in -> evalfbb4in : B'=-1+B, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

      2: evalfbb4in -> evalfbb2in : C'=A, [ B>=1 ], cost: 1

     10: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=A ], cost: 2

     11: evalfbb2in -> evalfbb4in : B'=-1+B, [ A>=1+C ], cost: 2



Accelerating simple loops of location 3.

   Accelerating the following rules:

     10: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=A ], cost: 2



   Accelerated rule 10 with metering function 1+C-A, yielding the new rule 12.

   Removing the simple loops: 10.



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

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

      2: evalfbb4in -> evalfbb2in : C'=A, [ B>=1 ], cost: 1

     11: evalfbb2in -> evalfbb4in : B'=-1+B, [ A>=1+C ], cost: 2

     12: evalfbb2in -> evalfbb2in : C'=-1+A, [ C>=A ], cost: 2+2*C-2*A



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

      2: evalfbb4in -> evalfbb2in : C'=A, [ B>=1 ], cost: 1

     13: evalfbb4in -> evalfbb2in : C'=-1+A, [ B>=1 ], cost: 3

     11: evalfbb2in -> evalfbb4in : B'=-1+B, [ A>=1+C ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

     14: evalfbb4in -> evalfbb4in : B'=-1+B, C'=-1+A, [ B>=1 ], cost: 5



Accelerating simple loops of location 2.

   Accelerating the following rules:

     14: evalfbb4in -> evalfbb4in : B'=-1+B, C'=-1+A, [ B>=1 ], cost: 5



   Accelerated rule 14 with metering function B, yielding the new rule 15.

   Removing the simple loops: 14.



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

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

     15: evalfbb4in -> evalfbb4in : B'=0, C'=-1+A, [ B>=1 ], cost: 5*B



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

      9: evalfstart -> evalfbb4in : A'=B, B'=A, [], cost: 2

     16: evalfstart -> evalfbb4in : A'=B, B'=0, C'=-1+B, [ A>=1 ], cost: 2+5*A



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

   Start location: evalfstart

     16: evalfstart -> evalfbb4in : A'=B, B'=0, C'=-1+B, [ A>=1 ], cost: 2+5*A



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalfstart

     16: evalfstart -> evalfbb4in : A'=B, B'=0, C'=-1+B, [ A>=1 ], cost: 2+5*A



Computing asymptotic complexity for rule 16

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      2+5*A (+), A (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {A==n}

      resulting limit problem:

      [solved]



   Solution:

      A / n

   Resulting cost 2+5*n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



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

   Complexity:  Poly(n^1)

   Cpx degree:  1

   Solved cost: 2+5*n

   Rule cost:   2+5*A

   Rule guard:  [ A>=1 ]



WORST_CASE(Omega(n^1),?)


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

(4)
BOUNDS(n^1, INF)