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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f9(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f9(A, 1 + B, 1 + C, S, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 + B && C >= 0
f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f0(A, B, C, D, E, F, S, G, V, W, X, L, M, N, O, P, Q, R)) :|: U >= T + 1 && E >= 1 && F >= 0
f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f5(A, B, C, D, 1 + E, -(1) + F, M, 0, W, X, K, M, N, V, S, E, Q, R)) :|: T >= U && E >= 0 && F >= 0 && H >= 0 && H <= 0
f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f12(A, B, C, D, E, F, G, 0, V, W, K, M, M, 0, O, E, S, R)) :|: X >= T && E >= 0 && F >= 0 && N >= 0 && N <= 0 && H >= 0 && H <= 0
f9(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f5(A, B, C, D, 1, T - 3 + C, S, 0, U, A1, K, S, V, X, W, P, D, -(2) + C)) :|: C >= 2 && B >= A && Y >= Z
f6(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f9(17, 1, 0, S, E, F, G, H, I, J, K, V, M, N, O, P, Q, R)) :|: TRUE

The start-symbols are:[f6_18]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f6

      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1

      4: f9 -> f5 : E'=1, F'=-3+free_20+C, G'=free_19, H'=0, Q'=free_22, J'=free_25, L'=free_23, M'=free_19, N'=free_26, O'=free_24, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && free_18>=free_21 ], cost: 1

      1: f5 -> f0 : A1'=B, B'=C, C'=D, D'=E, E'=F, F'=free_2, H'=free_1, Q'=free_3, J'=free_5, K'=L, L'=M, M'=N, N'=O, O'=P, P'=Q_1, Q_1'=R, [ free_4>=1+free_6 && E>=1 && F>=0 ], cost: 1

      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_8, J'=free_7, L'=N, M'=L, N'=free_9, O'=free_11, P'=E, [ free_10>=free_12 && E>=0 && F>=0 && H==0 ], cost: 1

      3: f5 -> f12 : A1'=B, B'=C, C'=D, D'=E, E'=F, F'=G, G'=0, H'=free_14, Q'=free_13, J'=K, K'=L, M'=0, N'=O, O'=E, P'=free_15, Q_1'=R, [ free_17>=free_16 && E>=0 && F>=0 && N==0 && H==0 ], cost: 1

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1



Checking for constant complexity:

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

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1



Removed unreachable and leaf rules:

   Start location: f6

      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1

      4: f9 -> f5 : E'=1, F'=-3+free_20+C, G'=free_19, H'=0, Q'=free_22, J'=free_25, L'=free_23, M'=free_19, N'=free_26, O'=free_24, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && free_18>=free_21 ], cost: 1

      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_8, J'=free_7, L'=N, M'=L, N'=free_9, O'=free_11, P'=E, [ free_10>=free_12 && E>=0 && F>=0 && H==0 ], cost: 1

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1



Simplified all rules, resulting in:

   Start location: f6

      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1

      4: f9 -> f5 : E'=1, F'=-3+free_20+C, G'=free_19, H'=0, Q'=free_22, J'=free_25, L'=free_23, M'=free_19, N'=free_26, O'=free_24, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1

      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_8, J'=free_7, L'=N, M'=L, N'=free_9, O'=free_11, P'=E, [ E>=0 && F>=0 && H==0 ], cost: 1

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 0.

   Accelerating the following rules:

      0: f9 -> f9 : B'=1+B, C'=1+C, D'=free, [ A>=1+B && C>=0 ], cost: 1



   Accelerated rule 0 with metering function -B+A, yielding the new rule 6.

   Removing the simple loops: 0.



Accelerating simple loops of location 1.

   Accelerating the following rules:

      2: f5 -> f5 : E'=1+E, F'=-1+F, G'=L, H'=0, Q'=free_8, J'=free_7, L'=N, M'=L, N'=free_9, O'=free_11, P'=E, [ E>=0 && F>=0 && H==0 ], cost: 1



   Accelerated rule 2 with metering function 1+F, yielding the new rule 7.

   Removing the simple loops: 2.



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

   Start location: f6

      4: f9 -> f5 : E'=1, F'=-3+free_20+C, G'=free_19, H'=0, Q'=free_22, J'=free_25, L'=free_23, M'=free_19, N'=free_26, O'=free_24, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1

      6: f9 -> f9 : B'=A, C'=-B+C+A, D'=free, [ A>=1+B && C>=0 ], cost: -B+A

      7: f5 -> f5 : E'=1+E+F, F'=-1, G'=free_9, H'=0, Q'=free_8, J'=free_7, L'=free_9, M'=free_9, N'=free_9, O'=free_11, P'=E+F, [ E>=0 && F>=0 && H==0 ], cost: 1+F

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f6

      4: f9 -> f5 : E'=1, F'=-3+free_20+C, G'=free_19, H'=0, Q'=free_22, J'=free_25, L'=free_23, M'=free_19, N'=free_26, O'=free_24, Q_1'=D, R'=-2+C, [ C>=2 && B>=A ], cost: 1

      9: f9 -> f5 : E'=-1+free_20+C, F'=-1, G'=free_9, H'=0, Q'=free_8, J'=free_7, L'=free_9, M'=free_9, N'=free_9, O'=free_11, P'=-2+free_20+C, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && -3+free_20+C>=0 ], cost: -1+free_20+C

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1

      8: f6 -> f9 : A'=17, B'=17, C'=16, D'=free, M'=free_27, [], cost: 17



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

   Start location: f6

      9: f9 -> f5 : E'=-1+free_20+C, F'=-1, G'=free_9, H'=0, Q'=free_8, J'=free_7, L'=free_9, M'=free_9, N'=free_9, O'=free_11, P'=-2+free_20+C, Q_1'=D, R'=-2+C, [ C>=2 && B>=A && -3+free_20+C>=0 ], cost: -1+free_20+C

      5: f6 -> f9 : A'=17, B'=1, C'=0, D'=free_28, M'=free_27, [], cost: 1

      8: f6 -> f9 : A'=17, B'=17, C'=16, D'=free, M'=free_27, [], cost: 17



Eliminated locations (on tree-shaped paths):

   Start location: f6

     10: f6 -> f5 : A'=17, B'=17, C'=16, D'=free, E'=15+free_20, F'=-1, G'=free_9, H'=0, Q'=free_8, J'=free_7, L'=free_9, M'=free_9, N'=free_9, O'=free_11, P'=14+free_20, Q_1'=free, R'=14, [ 13+free_20>=0 ], cost: 32+free_20



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f6

     10: f6 -> f5 : A'=17, B'=17, C'=16, D'=free, E'=15+free_20, F'=-1, G'=free_9, H'=0, Q'=free_8, J'=free_7, L'=free_9, M'=free_9, N'=free_9, O'=free_11, P'=14+free_20, Q_1'=free, R'=14, [ 13+free_20>=0 ], cost: 32+free_20



Computing asymptotic complexity for rule 10

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      32+free_20 (+), 14+free_20 (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free_20 / n

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

   Rule cost:   32+free_20

   Rule guard:  [ 13+free_20>=0 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)