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


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


WORST_CASE(?, O(n^2))
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(1, max(9, 9 + 2 * Arg_0) + nat(-1 + Arg_0) + nat(-1 * Arg_0 + Arg_0^2) + max(4, 4 + -1 * Arg_0 + Arg_0^2)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 5299 ms]
(2) BOUNDS(1, max(9, 9 + 2 * Arg_0) + nat(-1 + Arg_0) + nat(-1 * Arg_0 + Arg_0^2) + max(4, 4 + -1 * Arg_0 + Arg_0^2))


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 1 >= A && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A
start(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, H, C, 1, E, H - 1, G, H)) :|: A >= 2 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A
lbl16(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: A >= 2 && A >= B + 1 && F >= 0 && F <= 0 && H >= A && H <= A && D >= A && D <= A
lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, D - F, E, F, G, H)) :|: D >= F && A >= F + 1 && A >= F + D && A >= B && F >= 1 && D >= 0 && H >= A && H <= A
lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B, C, H, E, F - 1, G, H)) :|: F >= D + 1 && 0 >= D + 1 && A >= F + 1 && A >= F + D && A >= B && F >= 1 && D >= 0 && H >= A && H <= A
lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B, C, H, E, F - 1, G, H)) :|: F >= D + 1 && D >= 1 && A >= F + 1 && A >= F + D && A >= B && F >= 1 && D >= 0 && H >= A && H <= A
lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B - F, C, H, E, F - 1, G, H)) :|: F >= 1 && A >= F + 1 && A >= F && A >= B && D >= 0 && D <= 0 && H >= A && H <= A
lbl82(A, B, C, D, E, F, G, H) -> Com_1(lbl16(A, B, C, D, E, F, G, H)) :|: A >= 2 && A >= B && A >= B + 1 && F >= 0 && F <= 0 && H >= A && H <= A && D >= A && D <= A
lbl82(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, D - F, E, F, G, H)) :|: F >= 1 && A >= F && F >= 0 && A >= F + 2 && A >= B && A + F >= B + 1 && H >= A && H <= A && D >= A && D <= A
lbl82(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B, C, H, E, F - 1, G, H)) :|: F >= A + 1 && A >= 1 && F >= 0 && A >= F + 2 && A >= B && A + F >= B + 1 && H >= A && H <= A && D >= A && D <= A
lbl82(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B, C, H, E, F - 1, G, H)) :|: F >= 1 && 0 >= A + 1 && F >= 0 && A >= F + 2 && A >= B && A + F >= B + 1 && H >= A && H <= A && D >= A && D <= A
lbl82(A, B, C, D, E, F, G, H) -> Com_1(lbl82(A, B - F, C, H, E, F - 1, G, H)) :|: F >= 1 && F >= 0 && 0 >= F + 2 && 0 >= B && F >= B + 1 && D >= 0 && D <= 0 && H >= 0 && H <= 0 && A >= 0 && A <= 0
start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, E, E, G, G, A)) :|: TRUE

The start-symbols are:[start0_8]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 9+2*max([0, Arg_0])+max([0, -1+Arg_0])+max([0, Arg_0*(-1+Arg_0)])+max([4, 4+Arg_0*(-1+Arg_0)]) {O(n^2)})



Initial Complexity Problem:

  Start:  start0  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5, Arg_6, Arg_7  

  Temp_Vars:    

  Locations:  lbl111, lbl16, lbl82, start, start0, stop  

  Transitions:

  3: lbl111->lbl111

  4: lbl111->lbl82

  5: lbl111->lbl82

  6: lbl111->lbl82

  2: lbl16->stop

  8: lbl82->lbl111

  7: lbl82->lbl16

  9: lbl82->lbl82

  10: lbl82->lbl82

  11: lbl82->lbl82

  1: start->lbl111

  0: start->stop

  12: start0->start  



Timebounds: 

  Overall timebound: 9+2*max([0, Arg_0])+max([0, -1+Arg_0])+max([0, Arg_0*(-1+Arg_0)])+max([4, 4+Arg_0*(-1+Arg_0)]) {O(n^2)}

  3: lbl111->lbl111: max([4, 4+Arg_0*(-1+Arg_0)])+max([0, Arg_0*(-1+Arg_0)]) {O(n^2)}

  4: lbl111->lbl82: 1 {O(1)}

  5: lbl111->lbl82: max([0, Arg_0]) {O(n)}

  6: lbl111->lbl82: max([0, Arg_0]) {O(n)}

  2: lbl16->stop: 1 {O(1)}

  7: lbl82->lbl16: 1 {O(1)}

  8: lbl82->lbl111: max([0, -1+Arg_0]) {O(n)}

  9: lbl82->lbl82: 1 {O(1)}

  10: lbl82->lbl82: 1 {O(1)}

  11: lbl82->lbl82: 1 {O(1)}

  0: start->stop: 1 {O(1)}

  1: start->lbl111: 1 {O(1)}

  12: start0->start: 1 {O(1)}



Costbounds:

  Overall costbound: 9+2*max([0, Arg_0])+max([0, -1+Arg_0])+max([0, Arg_0*(-1+Arg_0)])+max([4, 4+Arg_0*(-1+Arg_0)]) {O(n^2)}

  3: lbl111->lbl111: max([4, 4+Arg_0*(-1+Arg_0)])+max([0, Arg_0*(-1+Arg_0)]) {O(n^2)}

  4: lbl111->lbl82: 1 {O(1)}

  5: lbl111->lbl82: max([0, Arg_0]) {O(n)}

  6: lbl111->lbl82: max([0, Arg_0]) {O(n)}

  2: lbl16->stop: 1 {O(1)}

  7: lbl82->lbl16: 1 {O(1)}

  8: lbl82->lbl111: max([0, -1+Arg_0]) {O(n)}

  9: lbl82->lbl82: 1 {O(1)}

  10: lbl82->lbl82: 1 {O(1)}

  11: lbl82->lbl82: 1 {O(1)}

  0: start->stop: 1 {O(1)}

  1: start->lbl111: 1 {O(1)}

  12: start0->start: 1 {O(1)}



Sizebounds:

`Lower:

  3: lbl111->lbl111, Arg_0: 2 {O(1)}

  3: lbl111->lbl111, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  3: lbl111->lbl111, Arg_2: Arg_2 {O(n)}

  3: lbl111->lbl111, Arg_3: 0 {O(1)}

  3: lbl111->lbl111, Arg_4: Arg_4 {O(n)}

  3: lbl111->lbl111, Arg_5: 1 {O(1)}

  3: lbl111->lbl111, Arg_6: Arg_6 {O(n)}

  3: lbl111->lbl111, Arg_7: 2 {O(1)}

  4: lbl111->lbl82, Arg_0: inf {Infinity}

  4: lbl111->lbl82, Arg_1: inf {Infinity}

  4: lbl111->lbl82, Arg_2: inf {Infinity}

  4: lbl111->lbl82, Arg_3: inf {Infinity}

  4: lbl111->lbl82, Arg_4: inf {Infinity}

  4: lbl111->lbl82, Arg_5: inf {Infinity}

  4: lbl111->lbl82, Arg_6: inf {Infinity}

  4: lbl111->lbl82, Arg_7: inf {Infinity}

  5: lbl111->lbl82, Arg_0: 3 {O(1)}

  5: lbl111->lbl82, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  5: lbl111->lbl82, Arg_2: Arg_2 {O(n)}

  5: lbl111->lbl82, Arg_3: 3 {O(1)}

  5: lbl111->lbl82, Arg_4: Arg_4 {O(n)}

  5: lbl111->lbl82, Arg_5: 1 {O(1)}

  5: lbl111->lbl82, Arg_6: Arg_6 {O(n)}

  5: lbl111->lbl82, Arg_7: 3 {O(1)}

  6: lbl111->lbl82, Arg_0: 2 {O(1)}

  6: lbl111->lbl82, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  6: lbl111->lbl82, Arg_2: Arg_2 {O(n)}

  6: lbl111->lbl82, Arg_3: 2 {O(1)}

  6: lbl111->lbl82, Arg_4: Arg_4 {O(n)}

  6: lbl111->lbl82, Arg_5: 0 {O(1)}

  6: lbl111->lbl82, Arg_6: Arg_6 {O(n)}

  6: lbl111->lbl82, Arg_7: 2 {O(1)}

  2: lbl16->stop, Arg_0: 2 {O(1)}

  2: lbl16->stop, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  2: lbl16->stop, Arg_2: Arg_2 {O(n)}

  2: lbl16->stop, Arg_3: 2 {O(1)}

  2: lbl16->stop, Arg_4: Arg_4 {O(n)}

  2: lbl16->stop, Arg_5: 0 {O(1)}

  2: lbl16->stop, Arg_6: Arg_6 {O(n)}

  2: lbl16->stop, Arg_7: 2 {O(1)}

  7: lbl82->lbl16, Arg_0: 2 {O(1)}

  7: lbl82->lbl16, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  7: lbl82->lbl16, Arg_2: Arg_2 {O(n)}

  7: lbl82->lbl16, Arg_3: 2 {O(1)}

  7: lbl82->lbl16, Arg_4: Arg_4 {O(n)}

  7: lbl82->lbl16, Arg_5: 0 {O(1)}

  7: lbl82->lbl16, Arg_6: Arg_6 {O(n)}

  7: lbl82->lbl16, Arg_7: 2 {O(1)}

  8: lbl82->lbl111, Arg_0: 3 {O(1)}

  8: lbl82->lbl111, Arg_1: min([1, -(-1+Arg_0*(-1+Arg_0))]) {O(n^2)}

  8: lbl82->lbl111, Arg_2: Arg_2 {O(n)}

  8: lbl82->lbl111, Arg_3: 2 {O(1)}

  8: lbl82->lbl111, Arg_4: Arg_4 {O(n)}

  8: lbl82->lbl111, Arg_5: 1 {O(1)}

  8: lbl82->lbl111, Arg_6: Arg_6 {O(n)}

  8: lbl82->lbl111, Arg_7: 3 {O(1)}

  9: lbl82->lbl82, Arg_0: inf {Infinity}

  9: lbl82->lbl82, Arg_1: inf {Infinity}

  9: lbl82->lbl82, Arg_2: inf {Infinity}

  9: lbl82->lbl82, Arg_3: inf {Infinity}

  9: lbl82->lbl82, Arg_4: inf {Infinity}

  9: lbl82->lbl82, Arg_5: inf {Infinity}

  9: lbl82->lbl82, Arg_6: inf {Infinity}

  9: lbl82->lbl82, Arg_7: inf {Infinity}

  10: lbl82->lbl82, Arg_0: inf {Infinity}

  10: lbl82->lbl82, Arg_1: inf {Infinity}

  10: lbl82->lbl82, Arg_2: inf {Infinity}

  10: lbl82->lbl82, Arg_3: inf {Infinity}

  10: lbl82->lbl82, Arg_4: inf {Infinity}

  10: lbl82->lbl82, Arg_5: inf {Infinity}

  10: lbl82->lbl82, Arg_6: inf {Infinity}

  10: lbl82->lbl82, Arg_7: inf {Infinity}

  11: lbl82->lbl82, Arg_0: inf {Infinity}

  11: lbl82->lbl82, Arg_1: inf {Infinity}

  11: lbl82->lbl82, Arg_2: inf {Infinity}

  11: lbl82->lbl82, Arg_3: inf {Infinity}

  11: lbl82->lbl82, Arg_4: inf {Infinity}

  11: lbl82->lbl82, Arg_5: inf {Infinity}

  11: lbl82->lbl82, Arg_6: inf {Infinity}

  11: lbl82->lbl82, Arg_7: inf {Infinity}

  0: start->stop, Arg_0: Arg_0 {O(n)}

  0: start->stop, Arg_1: Arg_2 {O(n)}

  0: start->stop, Arg_2: Arg_2 {O(n)}

  0: start->stop, Arg_3: Arg_4 {O(n)}

  0: start->stop, Arg_4: Arg_4 {O(n)}

  0: start->stop, Arg_5: Arg_6 {O(n)}

  0: start->stop, Arg_6: Arg_6 {O(n)}

  0: start->stop, Arg_7: Arg_0 {O(n)}

  1: start->lbl111, Arg_0: 2 {O(1)}

  1: start->lbl111, Arg_1: 2 {O(1)}

  1: start->lbl111, Arg_2: Arg_2 {O(n)}

  1: start->lbl111, Arg_3: 1 {O(1)}

  1: start->lbl111, Arg_4: Arg_4 {O(n)}

  1: start->lbl111, Arg_5: 1 {O(1)}

  1: start->lbl111, Arg_6: Arg_6 {O(n)}

  1: start->lbl111, Arg_7: 2 {O(1)}

  12: start0->start, Arg_0: Arg_0 {O(n)}

  12: start0->start, Arg_1: Arg_2 {O(n)}

  12: start0->start, Arg_2: Arg_2 {O(n)}

  12: start0->start, Arg_3: Arg_4 {O(n)}

  12: start0->start, Arg_4: Arg_4 {O(n)}

  12: start0->start, Arg_5: Arg_6 {O(n)}

  12: start0->start, Arg_6: Arg_6 {O(n)}

  12: start0->start, Arg_7: Arg_0 {O(n)}

`Upper:

  3: lbl111->lbl111, Arg_0: Arg_0 {O(n)}

  3: lbl111->lbl111, Arg_1: Arg_0 {O(n)}

  3: lbl111->lbl111, Arg_2: Arg_2 {O(n)}

  3: lbl111->lbl111, Arg_3: max([1, -1+Arg_0]) {O(n)}

  3: lbl111->lbl111, Arg_4: Arg_4 {O(n)}

  3: lbl111->lbl111, Arg_5: -1+Arg_0 {O(n)}

  3: lbl111->lbl111, Arg_6: Arg_6 {O(n)}

  3: lbl111->lbl111, Arg_7: Arg_0 {O(n)}

  4: lbl111->lbl82, Arg_0: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_1: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_2: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_3: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_4: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_5: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_6: -(inf) {Infinity}

  4: lbl111->lbl82, Arg_7: -(inf) {Infinity}

  5: lbl111->lbl82, Arg_0: Arg_0 {O(n)}

  5: lbl111->lbl82, Arg_1: Arg_0 {O(n)}

  5: lbl111->lbl82, Arg_2: Arg_2 {O(n)}

  5: lbl111->lbl82, Arg_3: Arg_0 {O(n)}

  5: lbl111->lbl82, Arg_4: Arg_4 {O(n)}

  5: lbl111->lbl82, Arg_5: -1+Arg_0 {O(n)}

  5: lbl111->lbl82, Arg_6: Arg_6 {O(n)}

  5: lbl111->lbl82, Arg_7: Arg_0 {O(n)}

  6: lbl111->lbl82, Arg_0: Arg_0 {O(n)}

  6: lbl111->lbl82, Arg_1: Arg_0 {O(n)}

  6: lbl111->lbl82, Arg_2: Arg_2 {O(n)}

  6: lbl111->lbl82, Arg_3: Arg_0 {O(n)}

  6: lbl111->lbl82, Arg_4: Arg_4 {O(n)}

  6: lbl111->lbl82, Arg_5: -1+Arg_0 {O(n)}

  6: lbl111->lbl82, Arg_6: Arg_6 {O(n)}

  6: lbl111->lbl82, Arg_7: Arg_0 {O(n)}

  2: lbl16->stop, Arg_0: Arg_0 {O(n)}

  2: lbl16->stop, Arg_1: Arg_0 {O(n)}

  2: lbl16->stop, Arg_2: Arg_2 {O(n)}

  2: lbl16->stop, Arg_3: Arg_0 {O(n)}

  2: lbl16->stop, Arg_4: Arg_4 {O(n)}

  2: lbl16->stop, Arg_5: 0 {O(1)}

  2: lbl16->stop, Arg_6: Arg_6 {O(n)}

  2: lbl16->stop, Arg_7: Arg_0 {O(n)}

  7: lbl82->lbl16, Arg_0: Arg_0 {O(n)}

  7: lbl82->lbl16, Arg_1: Arg_0 {O(n)}

  7: lbl82->lbl16, Arg_2: Arg_2 {O(n)}

  7: lbl82->lbl16, Arg_3: Arg_0 {O(n)}

  7: lbl82->lbl16, Arg_4: Arg_4 {O(n)}

  7: lbl82->lbl16, Arg_5: 0 {O(1)}

  7: lbl82->lbl16, Arg_6: Arg_6 {O(n)}

  7: lbl82->lbl16, Arg_7: Arg_0 {O(n)}

  8: lbl82->lbl111, Arg_0: Arg_0 {O(n)}

  8: lbl82->lbl111, Arg_1: Arg_0 {O(n)}

  8: lbl82->lbl111, Arg_2: Arg_2 {O(n)}

  8: lbl82->lbl111, Arg_3: -1+Arg_0 {O(n)}

  8: lbl82->lbl111, Arg_4: Arg_4 {O(n)}

  8: lbl82->lbl111, Arg_5: -1+Arg_0 {O(n)}

  8: lbl82->lbl111, Arg_6: Arg_6 {O(n)}

  8: lbl82->lbl111, Arg_7: Arg_0 {O(n)}

  9: lbl82->lbl82, Arg_0: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_1: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_2: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_3: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_4: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_5: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_6: -(inf) {Infinity}

  9: lbl82->lbl82, Arg_7: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_0: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_1: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_2: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_3: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_4: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_5: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_6: -(inf) {Infinity}

  10: lbl82->lbl82, Arg_7: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_0: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_1: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_2: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_3: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_4: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_5: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_6: -(inf) {Infinity}

  11: lbl82->lbl82, Arg_7: -(inf) {Infinity}

  0: start->stop, Arg_0: 1 {O(1)}

  0: start->stop, Arg_1: Arg_2 {O(n)}

  0: start->stop, Arg_2: Arg_2 {O(n)}

  0: start->stop, Arg_3: Arg_4 {O(n)}

  0: start->stop, Arg_4: Arg_4 {O(n)}

  0: start->stop, Arg_5: Arg_6 {O(n)}

  0: start->stop, Arg_6: Arg_6 {O(n)}

  0: start->stop, Arg_7: 1 {O(1)}

  1: start->lbl111, Arg_0: Arg_0 {O(n)}

  1: start->lbl111, Arg_1: Arg_0 {O(n)}

  1: start->lbl111, Arg_2: Arg_2 {O(n)}

  1: start->lbl111, Arg_3: 1 {O(1)}

  1: start->lbl111, Arg_4: Arg_4 {O(n)}

  1: start->lbl111, Arg_5: -1+Arg_0 {O(n)}

  1: start->lbl111, Arg_6: Arg_6 {O(n)}

  1: start->lbl111, Arg_7: Arg_0 {O(n)}

  12: start0->start, Arg_0: Arg_0 {O(n)}

  12: start0->start, Arg_1: Arg_2 {O(n)}

  12: start0->start, Arg_2: Arg_2 {O(n)}

  12: start0->start, Arg_3: Arg_4 {O(n)}

  12: start0->start, Arg_4: Arg_4 {O(n)}

  12: start0->start, Arg_5: Arg_6 {O(n)}

  12: start0->start, Arg_6: Arg_6 {O(n)}

  12: start0->start, Arg_7: Arg_0 {O(n)}


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

(2)
BOUNDS(1, max(9, 9 + 2 * Arg_0) + nat(-1 + Arg_0) + nat(-1 * Arg_0 + Arg_0^2) + max(4, 4 + -1 * Arg_0 + Arg_0^2))