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


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


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

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 3069 ms]
(2) BOUNDS(1, max(9 + -2 * Arg_2 + 2 * Arg_4, 9) + nat(-4 * Arg_2 + 4 * Arg_4) + nat(-2 * Arg_2 + 2 * Arg_4))


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

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

The start-symbols are:[start0_6]


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

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



Initial Complexity Problem:

  Start:  start0  

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

  Temp_Vars:    

  Locations:  lbl101, lbl91, start, start0, stop  

  Transitions:

  11: lbl101->lbl101

  10: lbl101->lbl91

  8: lbl101->stop

  9: lbl101->stop

  7: lbl91->lbl101

  6: lbl91->lbl91

  4: lbl91->stop

  5: lbl91->stop

  3: start->lbl101

  2: start->lbl91

  0: start->stop

  1: start->stop

  12: start0->start  



Timebounds: 

  Overall timebound: 9+2*max([0, Arg_4-Arg_2])+2*2*max([0, Arg_4-Arg_2])+2*max([0, Arg_4-Arg_2]) {O(n)}

  8: lbl101->stop: 1 {O(1)}

  9: lbl101->stop: 1 {O(1)}

  10: lbl101->lbl91: 2*max([0, Arg_4-Arg_2]) {O(n)}

  11: lbl101->lbl101: 2*max([0, Arg_4-Arg_2]) {O(n)}

  4: lbl91->stop: 1 {O(1)}

  5: lbl91->stop: 1 {O(1)}

  6: lbl91->lbl91: 2*max([0, Arg_4-Arg_2]) {O(n)}

  7: lbl91->lbl101: 2*max([0, Arg_4-Arg_2]) {O(n)}

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

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

  2: start->lbl91: 1 {O(1)}

  3: start->lbl101: 1 {O(1)}

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



Costbounds:

  Overall costbound: 9+2*max([0, Arg_4-Arg_2])+2*2*max([0, Arg_4-Arg_2])+2*max([0, Arg_4-Arg_2]) {O(n)}

  8: lbl101->stop: 1 {O(1)}

  9: lbl101->stop: 1 {O(1)}

  10: lbl101->lbl91: 2*max([0, Arg_4-Arg_2]) {O(n)}

  11: lbl101->lbl101: 2*max([0, Arg_4-Arg_2]) {O(n)}

  4: lbl91->stop: 1 {O(1)}

  5: lbl91->stop: 1 {O(1)}

  6: lbl91->lbl91: 2*max([0, Arg_4-Arg_2]) {O(n)}

  7: lbl91->lbl101: 2*max([0, Arg_4-Arg_2]) {O(n)}

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

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

  2: start->lbl91: 1 {O(1)}

  3: start->lbl101: 1 {O(1)}

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



Sizebounds:

`Lower:

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

  8: lbl101->stop, Arg_1: min([Arg_2, -(-1-Arg_2)]) {O(n)}

  8: lbl101->stop, Arg_2: Arg_2 {O(n)}

  8: lbl101->stop, Arg_3: min([Arg_4, -(2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([0, max([-(Arg_4), max([-(Arg_4), 1+Arg_0-Arg_4])])]))]) {O(n^2)}

  8: lbl101->stop, Arg_4: Arg_4 {O(n)}

  8: lbl101->stop, Arg_5: 0 {O(1)}

  9: lbl101->stop, Arg_0: inf {Infinity}

  9: lbl101->stop, Arg_1: inf {Infinity}

  9: lbl101->stop, Arg_2: inf {Infinity}

  9: lbl101->stop, Arg_3: inf {Infinity}

  9: lbl101->stop, Arg_4: inf {Infinity}

  9: lbl101->stop, Arg_5: inf {Infinity}

  10: lbl101->lbl91, Arg_0: 0 {O(1)}

  10: lbl101->lbl91, Arg_1: min([Arg_2, -(-1-Arg_2)]) {O(n)}

  10: lbl101->lbl91, Arg_2: Arg_2 {O(n)}

  10: lbl101->lbl91, Arg_3: min([0, min([Arg_4, min([Arg_4, -(1+Arg_0-Arg_4)])])])+-2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0]) {O(n^2)}

  10: lbl101->lbl91, Arg_4: Arg_4 {O(n)}

  10: lbl101->lbl91, Arg_5: 0 {O(1)}

  11: lbl101->lbl101, Arg_0: 0 {O(1)}

  11: lbl101->lbl101, Arg_1: min([Arg_2, -(-1-Arg_2)]) {O(n)}

  11: lbl101->lbl101, Arg_2: Arg_2 {O(n)}

  11: lbl101->lbl101, Arg_3: min([0, min([Arg_4, min([Arg_4, -(1+Arg_0-Arg_4)])])])+-2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0]) {O(n^2)}

  11: lbl101->lbl101, Arg_4: Arg_4 {O(n)}

  11: lbl101->lbl101, Arg_5: 0 {O(1)}

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

  4: lbl91->stop, Arg_1: min([Arg_2, min([Arg_2, -(-1-Arg_2)])]) {O(n)}

  4: lbl91->stop, Arg_2: Arg_2 {O(n)}

  4: lbl91->stop, Arg_3: min([-(2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([0, max([-(Arg_4), max([-(Arg_4), 1+Arg_0-Arg_4])])])), min([-(1+Arg_0-Arg_4), -(2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([0, max([-(Arg_4), max([-(Arg_4), 1+Arg_0-Arg_4])])]))])]) {O(n^2)}

  4: lbl91->stop, Arg_4: Arg_4 {O(n)}

  4: lbl91->stop, Arg_5: 0 {O(1)}

  5: lbl91->stop, Arg_0: inf {Infinity}

  5: lbl91->stop, Arg_1: inf {Infinity}

  5: lbl91->stop, Arg_2: inf {Infinity}

  5: lbl91->stop, Arg_3: inf {Infinity}

  5: lbl91->stop, Arg_4: inf {Infinity}

  5: lbl91->stop, Arg_5: inf {Infinity}

  6: lbl91->lbl91, Arg_0: 0 {O(1)}

  6: lbl91->lbl91, Arg_1: min([Arg_2, -(-1-Arg_2)]) {O(n)}

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

  6: lbl91->lbl91, Arg_3: min([0, min([Arg_4, min([Arg_4, -(1+Arg_0-Arg_4)])])])+-2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0]) {O(n^2)}

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

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

  7: lbl91->lbl101, Arg_0: 0 {O(1)}

  7: lbl91->lbl101, Arg_1: min([Arg_2, -(-1-Arg_2)]) {O(n)}

  7: lbl91->lbl101, Arg_2: Arg_2 {O(n)}

  7: lbl91->lbl101, Arg_3: min([0, min([Arg_4, min([Arg_4, -(1+Arg_0-Arg_4)])])])+-2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0]) {O(n^2)}

  7: lbl91->lbl101, Arg_4: Arg_4 {O(n)}

  7: lbl91->lbl101, Arg_5: 0 {O(1)}

  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_0 {O(n)}

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

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

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

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

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

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

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

  2: start->lbl91, Arg_1: Arg_2 {O(n)}

  2: start->lbl91, Arg_2: Arg_2 {O(n)}

  2: start->lbl91, Arg_3: -1+Arg_4-Arg_0 {O(n)}

  2: start->lbl91, Arg_4: Arg_4 {O(n)}

  2: start->lbl91, Arg_5: 0 {O(1)}

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

  3: start->lbl101, Arg_1: 1+Arg_2 {O(n)}

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

  3: start->lbl101, Arg_3: Arg_4 {O(n)}

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

  3: start->lbl101, Arg_5: 0 {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_0 {O(n)}

`Upper:

  8: lbl101->stop, Arg_0: Arg_0 {O(n)}

  8: lbl101->stop, Arg_1: max([2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])]), max([1+Arg_2+Arg_0, 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])])])]) {O(n^2)}

  8: lbl101->stop, Arg_2: Arg_2 {O(n)}

  8: lbl101->stop, Arg_3: max([Arg_4, max([Arg_4, -1+Arg_4])]) {O(n)}

  8: lbl101->stop, Arg_4: Arg_4 {O(n)}

  8: lbl101->stop, Arg_5: Arg_0 {O(n)}

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

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

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

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

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

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

  10: lbl101->lbl91, Arg_0: Arg_0 {O(n)}

  10: lbl101->lbl91, Arg_1: 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])]) {O(n^2)}

  10: lbl101->lbl91, Arg_2: Arg_2 {O(n)}

  10: lbl101->lbl91, Arg_3: max([Arg_4, -1+Arg_4]) {O(n)}

  10: lbl101->lbl91, Arg_4: Arg_4 {O(n)}

  10: lbl101->lbl91, Arg_5: Arg_0 {O(n)}

  11: lbl101->lbl101, Arg_0: Arg_0 {O(n)}

  11: lbl101->lbl101, Arg_1: 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])]) {O(n^2)}

  11: lbl101->lbl101, Arg_2: Arg_2 {O(n)}

  11: lbl101->lbl101, Arg_3: max([Arg_4, -1+Arg_4]) {O(n)}

  11: lbl101->lbl101, Arg_4: Arg_4 {O(n)}

  11: lbl101->lbl101, Arg_5: Arg_0 {O(n)}

  4: lbl91->stop, Arg_0: Arg_0 {O(n)}

  4: lbl91->stop, Arg_1: max([Arg_2, 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])])]) {O(n^2)}

  4: lbl91->stop, Arg_2: Arg_2 {O(n)}

  4: lbl91->stop, Arg_3: max([Arg_4, -1+Arg_4]) {O(n)}

  4: lbl91->stop, Arg_4: Arg_4 {O(n)}

  4: lbl91->stop, Arg_5: Arg_0 {O(n)}

  5: lbl91->stop, Arg_0: -(inf) {Infinity}

  5: lbl91->stop, Arg_1: -(inf) {Infinity}

  5: lbl91->stop, Arg_2: -(inf) {Infinity}

  5: lbl91->stop, Arg_3: -(inf) {Infinity}

  5: lbl91->stop, Arg_4: -(inf) {Infinity}

  5: lbl91->stop, Arg_5: -(inf) {Infinity}

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

  6: lbl91->lbl91, Arg_1: 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])]) {O(n^2)}

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

  6: lbl91->lbl91, Arg_3: max([Arg_4, -1+Arg_4]) {O(n)}

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

  6: lbl91->lbl91, Arg_5: Arg_0 {O(n)}

  7: lbl91->lbl101, Arg_0: Arg_0 {O(n)}

  7: lbl91->lbl101, Arg_1: 2*2*max([0, Arg_4-Arg_2])*max([1, 1+Arg_0])+max([Arg_0, max([Arg_2, max([Arg_0, 1+Arg_2+Arg_0])])]) {O(n^2)}

  7: lbl91->lbl101, Arg_2: Arg_2 {O(n)}

  7: lbl91->lbl101, Arg_3: max([Arg_4, -1+Arg_4]) {O(n)}

  7: lbl91->lbl101, Arg_4: Arg_4 {O(n)}

  7: lbl91->lbl101, Arg_5: Arg_0 {O(n)}

  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: -1 {O(1)}

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

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

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

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

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

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

  2: start->lbl91, Arg_0: Arg_0 {O(n)}

  2: start->lbl91, Arg_1: Arg_2 {O(n)}

  2: start->lbl91, Arg_2: Arg_2 {O(n)}

  2: start->lbl91, Arg_3: -1+Arg_4 {O(n)}

  2: start->lbl91, Arg_4: Arg_4 {O(n)}

  2: start->lbl91, Arg_5: Arg_0 {O(n)}

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

  3: start->lbl101, Arg_1: 1+Arg_2+Arg_0 {O(n)}

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

  3: start->lbl101, Arg_3: Arg_4 {O(n)}

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

  3: start->lbl101, Arg_5: 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_0 {O(n)}


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

(2)
BOUNDS(1, max(9 + -2 * Arg_2 + 2 * Arg_4, 9) + nat(-4 * Arg_2 + 4 * Arg_4) + nat(-2 * Arg_2 + 2 * Arg_4))