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


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


WORST_CASE(NON_POLY, ?)
proof of /export/starexec/sandbox2/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, 753 ms]
(2) BOUNDS(INF, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f0(A, B, C, D, E, F) -> Com_1(f2(A, G, C, D, E, F)) :|: 0 >= A
f0(A, B, C, D, E, F) -> Com_1(f0(A, B, -(1) + C, G, 0, H)) :|: A >= 1 && C >= 3
f0(A, B, C, D, E, F) -> Com_1(f0(-(1) + A, B, I, G, H, F)) :|: 0 >= H + 1 && A >= 1
f0(A, B, C, D, E, F) -> Com_1(f0(-(1) + A, B, I, G, H, F)) :|: H >= 1 && A >= 1
f1(A, B, C, D, E, F) -> Com_1(f0(A, B, C, D, E, F)) :|: TRUE

The start-symbols are:[f1_6]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f1

      0: f0 -> f2 : B'=free, [ 0>=A ], cost: 1

      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1

      2: f0 -> f0 : A'=-1+A, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1

      3: f0 -> f0 : A'=-1+A, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1

      4: f1 -> f0 : [], cost: 1



Checking for constant complexity:

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

      4: f1 -> f0 : [], cost: 1



Removed unreachable and leaf rules:

   Start location: f1

      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1

      2: f0 -> f0 : A'=-1+A, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1

      3: f0 -> f0 : A'=-1+A, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1

      4: f1 -> f0 : [], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 0.

   Accelerating the following rules:

      1: f0 -> f0 : C'=-1+C, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: 1

      2: f0 -> f0 : A'=-1+A, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1

      3: f0 -> f0 : A'=-1+A, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1



   Accelerated rule 1 with metering function -2+C, yielding the new rule 5.

   Accelerated rule 2 with metering function A, yielding the new rule 6.

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

   Nested simple loops 2 (outer loop) and 5 (inner loop) with metering function -1+A, resulting in the new rules: 8, 9.

   Nested simple loops 3 (outer loop) and 5 (inner loop) with metering function -1+A, resulting in the new rules: 10, 11.

   Removing the simple loops: 1 2 3.



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

   Start location: f1

      5: f0 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -2+C

      6: f0 -> f0 : A'=0, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: A

      7: f0 -> f0 : A'=0, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: A

      8: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_3>=3 ], cost: 1-A+free_3*(-1+A)

      9: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_3>=3 ], cost: -1+C-A+free_3*(-1+A)

     10: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_6>=3 ], cost: 1-A+free_6*(-1+A)

     11: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_6>=3 ], cost: -1+C-A+free_6*(-1+A)

      4: f1 -> f0 : [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f1

      4: f1 -> f0 : [], cost: 1

     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C

     13: f1 -> f0 : A'=0, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1+A

     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_3>=3 ], cost: 2-A+free_3*(-1+A)

     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_3>=3 ], cost: C-A+free_3*(-1+A)

     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_6>=3 ], cost: 2-A+free_6*(-1+A)

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_6>=3 ], cost: C-A+free_6*(-1+A)



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

   Start location: f1

     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C

     13: f1 -> f0 : A'=0, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1+A

     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_3>=3 ], cost: 2-A+free_3*(-1+A)

     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_3>=3 ], cost: C-A+free_3*(-1+A)

     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_6>=3 ], cost: 2-A+free_6*(-1+A)

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_6>=3 ], cost: C-A+free_6*(-1+A)



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f1

     12: f1 -> f0 : C'=2, D'=free_1, E'=0, F'=free_2, [ A>=1 && C>=3 ], cost: -1+C

     13: f1 -> f0 : A'=0, C'=free_3, D'=free_4, E'=free_5, [ 0>=1+free_5 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_6, D'=free_7, E'=free_8, [ free_8>=1 && A>=1 ], cost: 1+A

     15: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_3>=3 ], cost: 2-A+free_3*(-1+A)

     16: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_3>=3 ], cost: C-A+free_3*(-1+A)

     17: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ -1+A>=1 && free_6>=3 ], cost: 2-A+free_6*(-1+A)

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_6>=3 ], cost: C-A+free_6*(-1+A)



Computing asymptotic complexity for rule 12

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -2+C (+/+!), A (+/+!), -1+C (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      C / n

      A / 1

   Resulting cost -1+n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Computing asymptotic complexity for rule 15

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -1+A (+/+!), -2+free_3 (+/+!), 2-free_3+free_3*A-A (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free_3 / n

      A / 2

   Resulting cost 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: n

   Rule cost:   2-A+free_3*(-1+A)

   Rule guard:  [ -1+A>=1 && free_3>=3 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)