/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(6, 5 + -1 * Arg_0 + 2 * Arg_2 + -1 * Arg_4)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 1959 ms]
(2) BOUNDS(1, max(6, 5 + -1 * Arg_0 + 2 * Arg_2 + -1 * Arg_4))


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

(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)) :|: A >= 101 && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A && G >= H && G <= H
start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: E >= C + 1 && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A && G >= H && G <= H
start(A, B, C, D, E, F, G, H) -> Com_1(lbl72(A, B - 1, C, 1 + F, E, D, F, H)) :|: C >= E && 100 >= A && B >= C && B <= C && D >= E && D <= E && F >= A && F <= A && G >= H && G <= H
lbl72(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: F >= 101 && 100 >= A && 101 + F + B >= A + E + C && B + 1 >= F && C >= 1 + B && C >= E && G + 1 + F + B >= A + E + C && G + 1 + F + B <= A + E + C && D + F + B >= A + E + C && D + F + B <= A + E + C
lbl72(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: A + E + C >= F + 2 * B + 1 && 100 >= A && 101 + F + B >= A + E + C && B + 1 >= F && C >= 1 + B && C >= E && G + 1 + F + B >= A + E + C && G + 1 + F + B <= A + E + C && D + F + B >= A + E + C && D + F + B <= A + E + C
lbl72(A, B, C, D, E, F, G, H) -> Com_1(lbl72(A, B - 1, C, 1 + F, E, D, F, H)) :|: 2 * B + F >= A + E + C && 100 >= F && 100 >= A && 101 + F + B >= A + E + C && B + 1 >= F && C >= 1 + B && C >= E && G + 1 + F + B >= A + E + C && G + 1 + F + B <= A + E + C && D + F + B >= A + E + C && D + F + B <= A + E + C
start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, E, E, A, H, H)) :|: TRUE

The start-symbols are:[start0_8]


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

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



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:  lbl72, start, start0, stop  

  Transitions:

  5: lbl72->lbl72

  3: lbl72->stop

  4: lbl72->stop

  2: start->lbl72

  0: start->stop

  1: start->stop

  6: start0->start  



Timebounds: 

  Overall timebound: max([6, 7+-(Arg_0)-Arg_4+2*(-1+Arg_2)]) {O(n)}

  3: lbl72->stop: 1 {O(1)}

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

  5: lbl72->lbl72: max([0, 1+-(Arg_0)-Arg_4+2*(-1+Arg_2)]) {O(n)}

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

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

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

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



Costbounds:

  Overall costbound: max([6, 7+-(Arg_0)-Arg_4+2*(-1+Arg_2)]) {O(n)}

  3: lbl72->stop: 1 {O(1)}

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

  5: lbl72->lbl72: max([0, 1+-(Arg_0)-Arg_4+2*(-1+Arg_2)]) {O(n)}

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

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

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

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



Sizebounds:

`Lower:

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

  3: lbl72->stop, Arg_1: 100 {O(1)}

  3: lbl72->stop, Arg_2: 101 {O(1)}

  3: lbl72->stop, Arg_3: min([Arg_4, -(-1-Arg_0)]) {O(n)}

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

  3: lbl72->stop, Arg_5: 101 {O(1)}

  3: lbl72->stop, Arg_6: min([Arg_0, min([Arg_4, min([Arg_4, -(-1-Arg_0)])])]) {O(n)}

  3: lbl72->stop, Arg_7: Arg_7 {O(n)}

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

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

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

  4: lbl72->stop, Arg_3: min([Arg_4, -(-1-Arg_0)]) {O(n)}

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

  4: lbl72->stop, Arg_5: min([Arg_4, min([Arg_4, -(-1-Arg_0)])]) {O(n)}

  4: lbl72->stop, Arg_6: min([Arg_0, min([Arg_4, min([Arg_4, -(-1-Arg_0)])])]) {O(n)}

  4: lbl72->stop, Arg_7: Arg_7 {O(n)}

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

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

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

  5: lbl72->lbl72, Arg_3: min([Arg_4, -(-1-Arg_0)]) {O(n)}

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

  5: lbl72->lbl72, Arg_5: min([Arg_4, -(-1-Arg_0)]) {O(n)}

  5: lbl72->lbl72, Arg_6: min([Arg_4, min([Arg_4, -(-1-Arg_0)])]) {O(n)}

  5: lbl72->lbl72, Arg_7: Arg_7 {O(n)}

  0: start->stop, Arg_0: 101 {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: 101 {O(1)}

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

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

  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)}

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

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

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

  2: start->lbl72, Arg_1: -1+Arg_2 {O(n)}

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

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

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

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

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

  2: start->lbl72, Arg_7: Arg_7 {O(n)}

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

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

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

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

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

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

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

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

`Upper:

  3: lbl72->stop, Arg_0: 100 {O(1)}

  3: lbl72->stop, Arg_1: -1+Arg_2 {O(n)}

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

  3: lbl72->stop, Arg_3: 101 {O(1)}

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

  3: lbl72->stop, Arg_5: max([101, Arg_4]) {O(n)}

  3: lbl72->stop, Arg_6: 100 {O(1)}

  3: lbl72->stop, Arg_7: Arg_7 {O(n)}

  4: lbl72->stop, Arg_0: 100 {O(1)}

  4: lbl72->stop, Arg_1: 100 {O(1)}

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

  4: lbl72->stop, Arg_3: 101 {O(1)}

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

  4: lbl72->stop, Arg_5: 101 {O(1)}

  4: lbl72->stop, Arg_6: 100 {O(1)}

  4: lbl72->stop, Arg_7: Arg_7 {O(n)}

  5: lbl72->lbl72, Arg_0: 100 {O(1)}

  5: lbl72->lbl72, Arg_1: -1+Arg_2 {O(n)}

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

  5: lbl72->lbl72, Arg_3: 101 {O(1)}

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

  5: lbl72->lbl72, Arg_5: 101 {O(1)}

  5: lbl72->lbl72, Arg_6: 100 {O(1)}

  5: lbl72->lbl72, Arg_7: Arg_7 {O(n)}

  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)}

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

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

  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)}

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

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

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

  2: start->lbl72, Arg_1: -1+Arg_2 {O(n)}

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

  2: start->lbl72, Arg_3: 101 {O(1)}

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

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

  2: start->lbl72, Arg_6: 100 {O(1)}

  2: start->lbl72, Arg_7: Arg_7 {O(n)}

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

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

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

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

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

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

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

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


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

(2)
BOUNDS(1, max(6, 5 + -1 * Arg_0 + 2 * Arg_2 + -1 * Arg_4))