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


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


WORST_CASE(Omega(n^3), ?)
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(n^3, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 437 ms]
(2) BOUNDS(n^3, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
l0(A, B, C, D) -> Com_1(l1(0, B, C, D)) :|: TRUE
l1(A, B, C, D) -> Com_1(l2(A, B, 0, 0)) :|: B > 0
l2(A, B, C, D) -> Com_1(l2(A, B, C + 1, D + C)) :|: C < B
l2(A, B, C, D) -> Com_1(l1(A + D, B - 1, C, D)) :|: C >= B
l1(A, B, C, D) -> Com_1(l3(A, B, C, D)) :|: B <= 0
l3(A, B, C, D) -> Com_1(l3(A - 1, B, C, D)) :|: A > 0

The start-symbols are:[l0_4]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1

      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1



Checking for constant complexity:

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

      0: l0 -> l1 : A'=0, [], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 2.

   Accelerating the following rules:

      2: l2 -> l2 : C'=1+C, D'=C+D, [ B>=1+C ], cost: 1



   Accelerated rule 2 with metering function -C+B, yielding the new rule 6.

   Removing the simple loops: 2.



Accelerating simple loops of location 3.

   Accelerating the following rules:

      5: l3 -> l3 : A'=-1+A, [ A>=1 ], cost: 1



   Accelerated rule 5 with metering function A, yielding the new rule 7.

   Removing the simple loops: 5.



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

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1

      6: l2 -> l2 : C'=B, D'=1/2*C-(C-B)*C+D+1/2*(C-B)^2-1/2*B, [ B>=1+C ], cost: -C+B

      7: l3 -> l3 : A'=0, [ A>=1 ], cost: A



Chained accelerated rules (with incoming rules):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      4: l1 -> l3 : [ 0>=B ], cost: 1

      8: l1 -> l2 : C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 1+B

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1



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

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      1: l1 -> l2 : C'=0, D'=0, [ B>=1 ], cost: 1

      8: l1 -> l2 : C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 1+B

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

      3: l2 -> l1 : A'=D+A, B'=-1+B, [ C>=B ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

     10: l1 -> l1 : A'=A-1/2*B+1/2*B^2, B'=-1+B, C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 2+B



Accelerating simple loops of location 1.

   Accelerating the following rules:

     10: l1 -> l1 : A'=A-1/2*B+1/2*B^2, B'=-1+B, C'=B, D'=-1/2*B+1/2*B^2, [ B>=1 ], cost: 2+B



   Accelerated rule 10 with metering function B, yielding the new rule 11.

   Removing the simple loops: 10.



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

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A

     11: l1 -> l1 : A'=A+1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 5/2*B+1/2*B^2



Chained accelerated rules (with incoming rules):

   Start location: l0

      0: l0 -> l1 : A'=0, [], cost: 1

     12: l0 -> l1 : A'=1/6*B^3-1/6*B, B'=0, C'=1, D'=0, [ B>=1 ], cost: 1+5/2*B+1/2*B^2

      9: l1 -> l3 : A'=0, [ 0>=B && A>=1 ], cost: 1+A



Eliminated locations (on tree-shaped paths):

   Start location: l0

     13: l0 -> l3 : A'=0, B'=0, C'=1, D'=0, [ B>=1 && 1/6*B^3-1/6*B>=1 ], cost: 2+1/6*B^3+7/3*B+1/2*B^2



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: l0

     13: l0 -> l3 : A'=0, B'=0, C'=1, D'=0, [ B>=1 && 1/6*B^3-1/6*B>=1 ], cost: 2+1/6*B^3+7/3*B+1/2*B^2



Computing asymptotic complexity for rule 13

   Simplified the guard:

     13: l0 -> l3 : A'=0, B'=0, C'=1, D'=0, [ 1/6*B^3-1/6*B>=1 ], cost: 2+1/6*B^3+7/3*B+1/2*B^2

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      1/6*B^3-1/6*B (+/+!), 2+1/6*B^3+7/3*B+1/2*B^2 (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      B / n

   Resulting cost 2+1/2*n^2+1/6*n^3+7/3*n has complexity: Poly(n^3)



Found new complexity Poly(n^3).



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

   Complexity:  Poly(n^3)

   Cpx degree:  3

   Solved cost: 2+1/2*n^2+1/6*n^3+7/3*n

   Rule cost:   2+1/6*B^3+7/3*B+1/2*B^2

   Rule guard:  [ 1/6*B^3-1/6*B>=1 ]



WORST_CASE(Omega(n^3),?)


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

(2)
BOUNDS(n^3, INF)