/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 827 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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1

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

      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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1

      3: f0 -> f0 : A'=-1+A, C'=free_7, D'=free_8, E'=free_6, [ free_6>=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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1

      3: f0 -> f0 : A'=-1+A, C'=free_7, D'=free_8, E'=free_6, [ free_6>=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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: A

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

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

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

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

     11: f0 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: -1+C+(-1+A)*free_7-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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=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_4>=3 ], cost: 2+(-1+A)*free_4-A

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

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

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=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_4>=3 ], cost: 2+(-1+A)*free_4-A

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

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

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-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_4, D'=free_5, E'=free_3, [ 0>=1+free_3 && A>=1 ], cost: 1+A

     14: f1 -> f0 : A'=0, C'=free_7, D'=free_8, E'=free_6, [ free_6>=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_4>=3 ], cost: 2+(-1+A)*free_4-A

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

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

     18: f1 -> f0 : A'=1, C'=2, D'=free_1, E'=0, F'=free_2, [ C>=3 && -1+A>=1 && free_7>=3 ], cost: C+(-1+A)*free_7-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:

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



      applying transformation rule (C) using substitution {free_4==3}

      resulting limit problem:

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



      applying transformation rule (B), deleting 1 (+/+!)

      resulting limit problem:

      -1+A (+/+!), -1+2*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]



   Solved the limit problem by the following transformations:

      Created initial limit problem:

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



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {A==2,free_4==3+n}

      resulting limit problem:

      [solved]



   Solution:

      A / 2

      free_4 / 3+n

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

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

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



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)