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


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


WORST_CASE(?, O(n^1))
proof of /export/starexec/sandbox2/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(2, 2 + Arg_2) + max(3, 1 + 2 * Arg_0) + nat(Arg_0) + max(9 + Arg_0, 8) + nat(2 + 2 * Arg_2) + nat(Arg_2) + max(1 + 2 * Arg_2, 3)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 1758 ms]
(2) BOUNDS(1, max(2, 2 + Arg_2) + max(3, 1 + 2 * Arg_0) + nat(Arg_0) + max(9 + Arg_0, 8) + nat(2 + 2 * Arg_2) + nat(Arg_2) + max(1 + 2 * Arg_2, 3))


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

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

The start-symbols are:[start0_4]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 8+max([0, 1+Arg_0])+max([0, 1+Arg_2])+max([0, Arg_2])+max([3, 1+2*Arg_2])+max([2, 2+Arg_2])+max([0, 1+Arg_2])+max([3, 1+2*Arg_0])+max([0, Arg_0]) {O(n)})



Initial Complexity Problem:

  Start:  start0  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3  

  Temp_Vars:    

  Locations:  cut, lbl101, lbl111, lbl6, start, start0, stop  

  Transitions:

  12: cut->stop

  6: lbl101->cut

  7: lbl101->lbl101

  8: lbl101->lbl111

  9: lbl111->cut

  10: lbl111->lbl101

  11: lbl111->lbl111

  5: lbl6->stop

  2: start->cut

  3: start->lbl101

  4: start->lbl111

  1: start->lbl6

  0: start->stop

  13: start0->start  



Timebounds: 

  Overall timebound: 8+max([0, 1+Arg_0])+max([0, 1+Arg_2])+max([0, Arg_2])+max([3, 1+2*Arg_2])+max([2, 2+Arg_2])+max([0, 1+Arg_2])+max([3, 1+2*Arg_0])+max([0, Arg_0]) {O(n)}

  12: cut->stop: 1 {O(1)}

  6: lbl101->cut: 1 {O(1)}

  7: lbl101->lbl101: max([0, Arg_2])+max([0, 1+Arg_2]) {O(n)}

  8: lbl101->lbl111: max([3, 1+2*Arg_0])+max([3, 1+2*Arg_2]) {O(n)}

  9: lbl111->cut: 1 {O(1)}

  10: lbl111->lbl101: max([0, Arg_2])+max([0, 1+Arg_2]) {O(n)}

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

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

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

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

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

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

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

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



Costbounds:

  Overall costbound: 8+max([0, 1+Arg_0])+max([0, 1+Arg_2])+max([0, Arg_2])+max([3, 1+2*Arg_2])+max([2, 2+Arg_2])+max([0, 1+Arg_2])+max([3, 1+2*Arg_0])+max([0, Arg_0]) {O(n)}

  12: cut->stop: 1 {O(1)}

  6: lbl101->cut: 1 {O(1)}

  7: lbl101->lbl101: max([0, Arg_2])+max([0, 1+Arg_2]) {O(n)}

  8: lbl101->lbl111: max([3, 1+2*Arg_0])+max([3, 1+2*Arg_2]) {O(n)}

  9: lbl111->cut: 1 {O(1)}

  10: lbl111->lbl101: max([0, Arg_2])+max([0, 1+Arg_2]) {O(n)}

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

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

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

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

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

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

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

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



Sizebounds:

`Lower:

  12: cut->stop, Arg_0: 1 {O(1)}

  12: cut->stop, Arg_1: 1 {O(1)}

  12: cut->stop, Arg_2: 1 {O(1)}

  12: cut->stop, Arg_3: 1 {O(1)}

  6: lbl101->cut, Arg_0: 1 {O(1)}

  6: lbl101->cut, Arg_1: 1 {O(1)}

  6: lbl101->cut, Arg_2: 2 {O(1)}

  6: lbl101->cut, Arg_3: 1 {O(1)}

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

  7: lbl101->lbl101, Arg_1: 1 {O(1)}

  7: lbl101->lbl101, Arg_2: 3 {O(1)}

  7: lbl101->lbl101, Arg_3: 1 {O(1)}

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

  8: lbl101->lbl111, Arg_1: 1 {O(1)}

  8: lbl101->lbl111, Arg_2: 3 {O(1)}

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

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

  9: lbl111->cut, Arg_1: 1 {O(1)}

  9: lbl111->cut, Arg_2: 1 {O(1)}

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

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

  10: lbl111->lbl101, Arg_1: 1 {O(1)}

  10: lbl111->lbl101, Arg_2: 2 {O(1)}

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

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

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

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

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

  5: lbl6->stop, Arg_0: 1 {O(1)}

  5: lbl6->stop, Arg_1: Arg_2 {O(n)}

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

  5: lbl6->stop, Arg_3: 1 {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_0 {O(n)}

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

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

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

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

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

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

  2: start->cut, Arg_2: 1 {O(1)}

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

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

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

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

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

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

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

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

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

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

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

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

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

`Upper:

  12: cut->stop, Arg_0: Arg_0 {O(n)}

  12: cut->stop, Arg_1: max([Arg_2, max([Arg_2, max([Arg_2, -1+Arg_2])])]) {O(n)}

  12: cut->stop, Arg_2: Arg_2 {O(n)}

  12: cut->stop, Arg_3: max([Arg_0, max([Arg_0, -1+Arg_0])]) {O(n)}

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

  6: lbl101->cut, Arg_1: max([Arg_2, -1+Arg_2]) {O(n)}

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

  6: lbl101->cut, Arg_3: max([Arg_0, max([Arg_0, -1+Arg_0])]) {O(n)}

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

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

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

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

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

  8: lbl101->lbl111, Arg_1: max([Arg_2, -1+Arg_2]) {O(n)}

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

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

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

  9: lbl111->cut, Arg_1: max([Arg_2, max([Arg_2, -1+Arg_2])]) {O(n)}

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

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

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

  10: lbl111->lbl101, Arg_1: max([Arg_2, -1+Arg_2]) {O(n)}

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

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

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

  11: lbl111->lbl111, Arg_1: max([Arg_2, -1+Arg_2]) {O(n)}

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

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

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

  5: lbl6->stop, Arg_1: 0 {O(1)}

  5: lbl6->stop, Arg_2: 0 {O(1)}

  5: lbl6->stop, Arg_3: Arg_0 {O(n)}

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

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

  1: start->lbl6, Arg_1: 0 {O(1)}

  1: start->lbl6, Arg_2: 0 {O(1)}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

(2)
BOUNDS(1, max(2, 2 + Arg_2) + max(3, 1 + 2 * Arg_0) + nat(Arg_0) + max(9 + Arg_0, 8) + nat(2 + 2 * Arg_2) + nat(Arg_2) + max(1 + 2 * Arg_2, 3))