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


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


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

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 2866 ms]
(2) BOUNDS(1, max(2 + 4 * Arg_0, 2) + max(12 + 12 * Arg_0, 6) + 4 * nat(1 + 2 * Arg_0) * max(3, 1 + 2 * Arg_0) + nat(2 + 2 * Arg_0))
(3) Loat Proof [FINISHED, 986 ms]
(4) BOUNDS(n^1, INF)


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

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

The start-symbols are:[start0_8]


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

(1) Koat2 Proof (FINISHED)
YES( ?, 6+2*2*max([0, 1+2*Arg_0])*max([3, 1+2*Arg_0])+2*2*max([0, 1+2*Arg_0])+max([0, 2+2*Arg_0])+max([0, 1+2*Arg_0])+max([1, 1+2*Arg_0])+max([1, 1+2*Arg_0])+max([0, 1+2*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:  lbl121, lbl82, start, start0, stop  

  Transitions:

  8: lbl121->lbl121

  7: lbl121->lbl82

  6: lbl121->stop

  5: lbl82->lbl121

  4: lbl82->lbl82

  3: lbl82->stop

  2: start->lbl121

  1: start->lbl82

  0: start->stop

  9: start0->start  



Timebounds: 

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

  6: lbl121->stop: 1 {O(1)}

  7: lbl121->lbl82: max([0, 2+2*Arg_0])+max([0, 1+2*Arg_0]) {O(n)}

  8: lbl121->lbl121: 2*max([0, 1+2*Arg_0]) {O(n)}

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

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

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

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

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

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

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



Costbounds:

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

  6: lbl121->stop: 1 {O(1)}

  7: lbl121->lbl82: max([0, 2+2*Arg_0])+max([0, 1+2*Arg_0]) {O(n)}

  8: lbl121->lbl121: 2*max([0, 1+2*Arg_0]) {O(n)}

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

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

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

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

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

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

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



Sizebounds:

`Lower:

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

  6: lbl121->stop, Arg_1: 0 {O(1)}

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

  6: lbl121->stop, Arg_3: 0 {O(1)}

  6: lbl121->stop, Arg_4: -1 {O(1)}

  6: lbl121->stop, Arg_5: Arg_5 {O(n)}

  6: lbl121->stop, Arg_6: -1 {O(1)}

  6: lbl121->stop, Arg_7: Arg_7 {O(n)}

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

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

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

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

  7: lbl121->lbl82, Arg_4: 1 {O(1)}

  7: lbl121->lbl82, Arg_5: Arg_5 {O(n)}

  7: lbl121->lbl82, Arg_6: 0 {O(1)}

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

  8: lbl121->lbl121, Arg_0: 1 {O(1)}

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

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

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

  8: lbl121->lbl121, Arg_4: 0 {O(1)}

  8: lbl121->lbl121, Arg_5: Arg_5 {O(n)}

  8: lbl121->lbl121, Arg_6: 0 {O(1)}

  8: lbl121->lbl121, Arg_7: Arg_7 {O(n)}

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

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

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

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

  3: lbl82->stop, Arg_4: 0 {O(1)}

  3: lbl82->stop, Arg_5: Arg_5 {O(n)}

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

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

  4: lbl82->lbl82, Arg_0: 1 {O(1)}

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

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

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

  4: lbl82->lbl82, Arg_4: 2 {O(1)}

  4: lbl82->lbl82, Arg_5: Arg_5 {O(n)}

  4: lbl82->lbl82, Arg_6: 0 {O(1)}

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

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

  5: lbl82->lbl121, Arg_1: 1 {O(1)}

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

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

  5: lbl82->lbl121, Arg_4: 1 {O(1)}

  5: lbl82->lbl121, Arg_5: Arg_5 {O(n)}

  5: lbl82->lbl121, Arg_6: 1 {O(1)}

  5: lbl82->lbl121, 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_0 {O(n)}

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

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

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

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

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

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

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

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

  1: start->lbl82, Arg_4: 0 {O(1)}

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

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

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

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

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

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

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

  2: start->lbl121, Arg_4: -1 {O(1)}

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

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

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

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

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

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

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

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

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

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

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

`Upper:

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

  6: lbl121->stop, Arg_1: max([-1+2*Arg_0, 2*Arg_0]) {O(n)}

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

  6: lbl121->stop, Arg_3: Arg_0 {O(n)}

  6: lbl121->stop, Arg_4: 2*Arg_0 {O(n)}

  6: lbl121->stop, Arg_5: Arg_5 {O(n)}

  6: lbl121->stop, Arg_6: max([-1+2*Arg_0, 2*Arg_0]) {O(n)}

  6: lbl121->stop, Arg_7: Arg_7 {O(n)}

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

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

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

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

  7: lbl121->lbl82, Arg_4: 2*Arg_0 {O(n)}

  7: lbl121->lbl82, Arg_5: Arg_5 {O(n)}

  7: lbl121->lbl82, Arg_6: max([-2+2*Arg_0, max([-1+2*Arg_0, -2+2*Arg_0])]) {O(n)}

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

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

  8: lbl121->lbl121, Arg_1: max([-1+2*Arg_0, 2*Arg_0]) {O(n)}

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

  8: lbl121->lbl121, Arg_3: Arg_0 {O(n)}

  8: lbl121->lbl121, Arg_4: 2*Arg_0 {O(n)}

  8: lbl121->lbl121, Arg_5: Arg_5 {O(n)}

  8: lbl121->lbl121, Arg_6: -1+2*Arg_0 {O(n)}

  8: lbl121->lbl121, Arg_7: Arg_7 {O(n)}

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

  3: lbl82->stop, Arg_1: max([Arg_2, max([Arg_2, max([-1+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, 2*Arg_0])])])])])])])])])])])]) {O(n)}

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

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

  3: lbl82->stop, Arg_4: 2*Arg_0 {O(n)}

  3: lbl82->stop, Arg_5: Arg_5 {O(n)}

  3: lbl82->stop, Arg_6: max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, 2*Arg_0])])])])]) {O(n)}

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

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

  4: lbl82->lbl82, Arg_1: max([Arg_2, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, max([-2+2*Arg_0, max([-1+2*Arg_0, 2*Arg_0])])])])])]) {O(n)}

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

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

  4: lbl82->lbl82, Arg_4: 2*Arg_0 {O(n)}

  4: lbl82->lbl82, Arg_5: Arg_5 {O(n)}

  4: lbl82->lbl82, Arg_6: max([-1+2*Arg_0, max([-2+2*Arg_0, 2*Arg_0])]) {O(n)}

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

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

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

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

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

  5: lbl82->lbl121, Arg_4: 2*Arg_0 {O(n)}

  5: lbl82->lbl121, Arg_5: Arg_5 {O(n)}

  5: lbl82->lbl121, Arg_6: -1+2*Arg_0 {O(n)}

  5: lbl82->lbl121, Arg_7: Arg_7 {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: -1 {O(1)}

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

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

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

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

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

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

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

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

  1: start->lbl82, Arg_4: 2*Arg_0 {O(n)}

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

  1: start->lbl82, Arg_6: 2*Arg_0 {O(n)}

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

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

  2: start->lbl121, Arg_1: 2*Arg_0 {O(n)}

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

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

  2: start->lbl121, Arg_4: 2*Arg_0 {O(n)}

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

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

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

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

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

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

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

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

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

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

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


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

(2)
BOUNDS(1, max(2 + 4 * Arg_0, 2) + max(12 + 12 * Arg_0, 6) + 4 * nat(1 + 2 * Arg_0) * max(3, 1 + 2 * Arg_0) + nat(2 + 2 * Arg_0))

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

(3) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: start0

      0: start -> stop : [ 0>=1+A && B==C && D==A && E==F && G==H ], cost: 1

      1: start -> lbl82 : E'=2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      2: start -> lbl121 : B'=2*D, E'=-1+2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      3: lbl82 -> stop : [ E>=A && 2*A>=E && D==A && 1+G==A ], cost: 1

      4: lbl82 -> lbl82 : G'=-1+G, [ G>=A && E>=1+G && 2*A>=E && 1+G>=A && D==A ], cost: 1

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && 1+G>=A && D==A ], cost: 1

      6: lbl121 -> stop : [ A>=1+E && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      8: lbl121 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



Checking for constant complexity:

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

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



Removed unreachable and leaf rules:

   Start location: start0

      1: start -> lbl82 : E'=2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      2: start -> lbl121 : B'=2*D, E'=-1+2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      4: lbl82 -> lbl82 : G'=-1+G, [ G>=A && E>=1+G && 2*A>=E && 1+G>=A && D==A ], cost: 1

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && 1+G>=A && D==A ], cost: 1

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      8: lbl121 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



Simplified all rules, resulting in:

   Start location: start0

      1: start -> lbl82 : E'=2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      2: start -> lbl121 : B'=2*D, E'=-1+2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      4: lbl82 -> lbl82 : G'=-1+G, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      8: lbl121 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 1.

   Accelerating the following rules:

      4: lbl82 -> lbl82 : G'=-1+G, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1



   Accelerated rule 4 with metering function 1+G-A, yielding the new rule 10.

   Removing the simple loops: 4.



Accelerating simple loops of location 2.

   Accelerating the following rules:

      8: lbl121 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1



   Accelerated rule 8 with metering function 1-A+E, yielding the new rule 11.

   Removing the simple loops: 8.



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

   Start location: start0

      1: start -> lbl82 : E'=2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      2: start -> lbl121 : B'=2*D, E'=-1+2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1

     10: lbl82 -> lbl82 : G'=-1+A, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1+G-A

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

     11: lbl121 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1-A+E

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: start0

      1: start -> lbl82 : E'=2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

      2: start -> lbl121 : B'=2*D, E'=-1+2*D, G'=-1+2*D, [ A>=0 && B==C && D==A && E==F && G==H ], cost: 1

     12: start -> lbl82 : E'=2*D, G'=-1+A, [ A>=0 && B==C && D==A && E==F && G==H && -1+2*D>=A && 2*A>=2*D ], cost: 1+2*D-A

     14: start -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ A>=0 && B==C && D==A && E==F && G==H && -1+2*D>=A && 2*A>=2*D ], cost: 1+2*D-A

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1

     15: lbl82 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ G>=A && E>=1+G && 2*A>=E && D==A && -1+E>=A ], cost: 1-A+E

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

     13: lbl121 -> lbl82 : G'=-1+A, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 1+G-A

      9: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: start0

      5: lbl82 -> lbl121 : B'=G, E'=-1+E, G'=-1+E, [ G>=A && E>=1+G && 2*A>=E && D==A ], cost: 1

     15: lbl82 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ G>=A && E>=1+G && 2*A>=E && D==A && -1+E>=A ], cost: 1-A+E

      7: lbl121 -> lbl82 : G'=-1+G, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A ], cost: 1

     13: lbl121 -> lbl82 : G'=-1+A, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 1+G-A

     16: start0 -> lbl82 : B'=C, D'=A, E'=2*A, G'=-1+2*A, [ A>=0 ], cost: 2

     17: start0 -> lbl121 : B'=2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ A>=0 ], cost: 2

     18: start0 -> lbl82 : B'=C, D'=A, E'=2*A, G'=-1+A, [ -1+2*A>=A ], cost: 2+A

     19: start0 -> lbl121 : B'=A, D'=A, E'=-1+A, G'=-1+A, [ -1+2*A>=A ], cost: 2+A



Eliminated location lbl82 (as a last resort):

   Start location: start0

     20: lbl121 -> lbl121 : B'=-1+G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 2

     21: lbl121 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A && -1+E>=A ], cost: 2-A+E

     24: lbl121 -> [7] : [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 1+G-A

     17: start0 -> lbl121 : B'=2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ A>=0 ], cost: 2

     19: start0 -> lbl121 : B'=A, D'=A, E'=-1+A, G'=-1+A, [ -1+2*A>=A ], cost: 2+A

     22: start0 -> lbl121 : B'=-1+2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -1+2*A>=A ], cost: 3

     23: start0 -> lbl121 : B'=A, D'=A, E'=-1+A, G'=-1+A, [ -1+2*A>=A ], cost: 3+A

     25: start0 -> [7] : [ -1+2*A>=A ], cost: 2+A



Accelerating simple loops of location 2.

   Accelerating the following rules:

     20: lbl121 -> lbl121 : B'=-1+G, E'=-1+E, G'=-1+E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 2

     21: lbl121 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A && -1+E>=A ], cost: 2-A+E



   Accelerated rule 20 with metering function -G-A+2*E, yielding the new rule 26.

   Accelerated rule 21 with metering function -G+E, yielding the new rule 27.

   Removing the simple loops: 20 21.



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

   Start location: start0

     24: lbl121 -> [7] : [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 1+G-A

     26: lbl121 -> lbl121 : B'=G+A-E, E'=G+A-E, G'=G+A-E, [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A && -G-A+2*E>=1 ], cost: -2*G-2*A+4*E

     27: lbl121 -> lbl121 : B'=A, E'=-1+A, G'=-1+A, [ 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A && -1+E>=A && -G+E>=1 ], cost: -G+E

     17: start0 -> lbl121 : B'=2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ A>=0 ], cost: 2

     22: start0 -> lbl121 : B'=-1+2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -1+2*A>=A ], cost: 3

     23: start0 -> lbl121 : B'=A, D'=A, E'=-1+A, G'=-1+A, [ -1+2*A>=A ], cost: 3+A

     25: start0 -> [7] : [ -1+2*A>=A ], cost: 2+A



Chained accelerated rules (with incoming rules):

   Start location: start0

     24: lbl121 -> [7] : [ E>=A && 2*A>=1+E && B>=A && 1+E>=B && G==E && D==A && -1+G>=A ], cost: 1+G-A

     17: start0 -> lbl121 : B'=2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ A>=0 ], cost: 2

     22: start0 -> lbl121 : B'=-1+2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -1+2*A>=A ], cost: 3

     23: start0 -> lbl121 : B'=A, D'=A, E'=-1+A, G'=-1+A, [ -1+2*A>=A ], cost: 3+A

     25: start0 -> [7] : [ -1+2*A>=A ], cost: 2+A

     28: start0 -> lbl121 : B'=A, D'=A, E'=A, G'=A, [ -2+2*A>=A ], cost: 2*A

     29: start0 -> lbl121 : B'=A, D'=A, E'=A, G'=A, [ -2+2*A>=A ], cost: 1+2*A



Eliminated locations (on tree-shaped paths):

   Start location: start0

     25: start0 -> [7] : [ -1+2*A>=A ], cost: 2+A

     30: start0 -> [7] : B'=2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -2+2*A>=A ], cost: 2+A

     31: start0 -> [7] : B'=-1+2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -2+2*A>=A ], cost: 3+A

     32: start0 -> [9] : [ -1+2*A>=A ], cost: 3+A

     33: start0 -> [9] : [ -2+2*A>=A ], cost: 2*A

     34: start0 -> [9] : [ -2+2*A>=A ], cost: 1+2*A



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: start0

     31: start0 -> [7] : B'=-1+2*A, D'=A, E'=-1+2*A, G'=-1+2*A, [ -2+2*A>=A ], cost: 3+A

     32: start0 -> [9] : [ -1+2*A>=A ], cost: 3+A

     34: start0 -> [9] : [ -2+2*A>=A ], cost: 1+2*A



Computing asymptotic complexity for rule 31

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -1+A (+/+!), 3+A (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      A / n

   Resulting cost 3+n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^1)

   Cpx degree:  1

   Solved cost: 3+n

   Rule cost:   3+A

   Rule guard:  [ -2+2*A>=A ]



WORST_CASE(Omega(n^1),?)


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

(4)
BOUNDS(n^1, INF)