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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f26(A, B) -> Com_1(f2(A, B)) :|: TRUE
f2(A, B) -> Com_1(f2(A, B)) :|: TRUE
f9(A, B) -> Com_1(f12(A, C)) :|: 5 >= A && 0 >= C + 1
f9(A, B) -> Com_1(f12(A, C)) :|: 5 >= A && C >= 1
f12(A, B) -> Com_1(f9(A + 1, B)) :|: A >= 6
f28(A, B) -> Com_1(f30(A, B)) :|: TRUE
f20(A, B) -> Com_1(f20(A - 1, B)) :|: A >= 3
f20(A, B) -> Com_1(f9(A, B)) :|: 2 >= A
f12(A, B) -> Com_1(f9(A + 1, B)) :|: 5 >= A
f9(A, B) -> Com_1(f20(A, 0)) :|: 5 >= A
f9(A, B) -> Com_1(f20(A, B)) :|: A >= 6
f0(A, B) -> Com_1(f9(C, B)) :|: TRUE

The start-symbols are:[f0_2]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f26 -> f2 : [], cost: 1

      1: f2 -> f2 : [], cost: 1

      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1

      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1

      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1

     10: f9 -> f20 : [ A>=6 ], cost: 1

      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1

      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1

      5: f28 -> f30 : [], cost: 1

      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1

      7: f20 -> f9 : [ 2>=A ], cost: 1

     11: f0 -> f9 : A'=free_2, [], cost: 1



Checking for constant complexity:

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

     11: f0 -> f9 : A'=free_2, [], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1

      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1

      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1

     10: f9 -> f20 : [ A>=6 ], cost: 1

      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1

      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1

      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1

      7: f20 -> f9 : [ 2>=A ], cost: 1

     11: f0 -> f9 : A'=free_2, [], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 5.

   Accelerating the following rules:

      6: f20 -> f20 : A'=-1+A, [ A>=3 ], cost: 1



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

   Removing the simple loops: 6.



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

   Start location: f0

      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1

      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1

      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1

     10: f9 -> f20 : [ A>=6 ], cost: 1

      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1

      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1

      7: f20 -> f9 : [ 2>=A ], cost: 1

     12: f20 -> f20 : A'=2, [ A>=3 ], cost: -2+A

     11: f0 -> f9 : A'=free_2, [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f0

      2: f9 -> f12 : B'=free, [ 5>=A && 0>=1+free ], cost: 1

      3: f9 -> f12 : B'=free_1, [ 5>=A && free_1>=1 ], cost: 1

      9: f9 -> f20 : B'=0, [ 5>=A ], cost: 1

     10: f9 -> f20 : [ A>=6 ], cost: 1

     13: f9 -> f20 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: -1+A

     14: f9 -> f20 : A'=2, [ A>=6 ], cost: -1+A

      4: f12 -> f9 : A'=1+A, [ A>=6 ], cost: 1

      8: f12 -> f9 : A'=1+A, [ 5>=A ], cost: 1

      7: f20 -> f9 : [ 2>=A ], cost: 1

     11: f0 -> f9 : A'=free_2, [], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

     15: f9 -> f9 : A'=1+A, B'=free, [ 5>=A && 0>=1+free ], cost: 2

     16: f9 -> f9 : A'=1+A, B'=free_1, [ 5>=A && free_1>=1 ], cost: 2

     17: f9 -> f9 : B'=0, [ 2>=A ], cost: 2

     18: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: A

     19: f9 -> f9 : A'=2, [ A>=6 ], cost: A

     11: f0 -> f9 : A'=free_2, [], cost: 1



Accelerating simple loops of location 2.

   Accelerating the following rules:

     15: f9 -> f9 : A'=1+A, B'=free, [ 5>=A && 0>=1+free ], cost: 2

     16: f9 -> f9 : A'=1+A, B'=free_1, [ 5>=A && free_1>=1 ], cost: 2

     17: f9 -> f9 : B'=0, [ 2>=A ], cost: 2

     18: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 ], cost: A

     19: f9 -> f9 : A'=2, [ A>=6 ], cost: A



   Accelerated rule 15 with metering function 6-A, yielding the new rule 20.

   Accelerated rule 16 with metering function 6-A, yielding the new rule 21.

   Accelerated rule 17 with NONTERM, yielding the new rule 22.

   Accelerated rule 18 with metering function meter (where 3*meter==-2+A), yielding the new rule 23.

   Found no metering function for rule 19.

   Nested simple loops 19 (outer loop) and 20 (inner loop) with NONTERM, resulting in the new rules: 24, 25.

   Nested simple loops 19 (outer loop) and 21 (inner loop) with NONTERM, resulting in the new rules: 26, 27.

   Nested simple loops 15 (outer loop) and 23 (inner loop) with metering function meter_3 (where 2*meter_3==-4-meter+A), resulting in the new rules: 28.

   Nested simple loops 16 (outer loop) and 23 (inner loop) with metering function meter_4 (where 2*meter_4==-4-meter+A), resulting in the new rules: 29.

   Removing the simple loops: 15 16 17 18 19.



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

   Start location: f0

     20: f9 -> f9 : A'=6, B'=free, [ 5>=A && 0>=1+free ], cost: 12-2*A

     21: f9 -> f9 : A'=6, B'=free_1, [ 5>=A && free_1>=1 ], cost: 12-2*A

     22: f9 -> [9] : [ 2>=A ], cost: NONTERM

     23: f9 -> f9 : A'=2, B'=0, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 ], cost: 2*meter

     24: f9 -> [9] : [ 5>=A && 0>=1+free && 18-2*A>=1 ], cost: NONTERM

     25: f9 -> [9] : A'=2, [ A>=6 && 0>=1+free ], cost: NONTERM

     26: f9 -> [9] : [ 5>=A && free_1>=1 && 18-2*A>=1 ], cost: NONTERM

     27: f9 -> [9] : A'=2, [ A>=6 && free_1>=1 ], cost: NONTERM

     28: f9 -> f9 : A'=3, B'=free, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 && 0>=1+free && 2*meter_3==-4-meter+A && meter_3>=1 ], cost: 2*meter_3+2*meter_3*meter

     29: f9 -> f9 : A'=3, B'=free_1, [ 5>=A && A>=3 && 3*meter==-2+A && meter>=1 && free_1>=1 && 2*meter_4==-4-meter+A && meter_4>=1 ], cost: 2*meter_4+2*meter*meter_4

     11: f0 -> f9 : A'=free_2, [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f0

     11: f0 -> f9 : A'=free_2, [], cost: 1

     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2

     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2

     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: NONTERM

     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter

     34: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: NONTERM

     35: f0 -> [9] : A'=2, [], cost: NONTERM

     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: NONTERM

     37: f0 -> [9] : A'=2, [], cost: NONTERM



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

   Start location: f0

     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2

     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2

     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: NONTERM

     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter

     34: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: NONTERM

     35: f0 -> [9] : A'=2, [], cost: NONTERM

     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: NONTERM

     37: f0 -> [9] : A'=2, [], cost: NONTERM



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     30: f0 -> f9 : A'=6, B'=free, [ 5>=free_2 && 0>=1+free ], cost: 13-2*free_2

     31: f0 -> f9 : A'=6, B'=free_1, [ 5>=free_2 && free_1>=1 ], cost: 13-2*free_2

     32: f0 -> [9] : A'=free_2, [ 2>=free_2 ], cost: NONTERM

     33: f0 -> f9 : A'=2, B'=0, [ 5>=2+3*meter && 2+3*meter>=3 && meter>=1 ], cost: 1+2*meter

     36: f0 -> [9] : A'=free_2, [ 5>=free_2 && 18-2*free_2>=1 ], cost: NONTERM

     37: f0 -> [9] : A'=2, [], cost: NONTERM



Computing asymptotic complexity for rule 30

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -free (+/+!), 6-free_2 (+/+!), 13-2*free_2 (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free_2 / -n

      free / -1

   Resulting cost 13+2*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: 13+2*n

   Rule cost:   13-2*free_2

   Rule guard:  [ 5>=free_2 && 0>=1+free ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)