/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) 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(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 10.7 s] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f135(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f136(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= A + 1 f135(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f136(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: A >= 1 f136(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f137(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= B + 1 f136(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f137(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: B >= 1 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f26(1, 1, 3, X, 1, 1, Y, 0, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE f26(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f29(A, B, C, D, E, F, G, H, 0, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= H + 1 f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f29(A, B, C, D, E, F, G, H, I + 1, X, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= I + 1 f38(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f41(A, B, C, D, E, F, G, H, 0, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= H + 1 f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= E + 1 && D >= I + 1 f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: E >= 1 && D >= I + 1 f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f41(A, B, C, D, 1, F, G, H, I + 1, J, 1, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE f44(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f41(A, B, C, D, 0, F, G, H, I + 1, J, 0, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f41(A, B, C, D, 0, F, G, H, I + 1, J, 0, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= I + 1 && E >= 0 && E <= 0 f56(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, 0, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= H + 1 f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f62(A, B, C, D, E, F, G, H, I, J, K, L, L + 1, N, O, P, Q, R, S, T, U, V, W)) :|: D >= 2 + L f62(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= M + 1 && 0 >= A + 1 f62(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= M + 1 && A >= 1 f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f62(1, B, C, D, E, F, G, H, I, J, K, L, M + 1, 1, O, P, Q, R, S, T, U, V, W)) :|: X >= Y + 1 f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f62(1, B, C, D, E, F, G, H, I, J, K, L, M + 1, 1, O, P, Q, R, S, T, U, V, W)) :|: TRUE f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f62(0, B, C, D, E, F, G, H, I, J, K, L, M + 1, 0, O, P, Q, R, S, T, U, V, W)) :|: TRUE f62(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f62(0, B, C, D, E, F, G, H, I, J, K, L, M + 1, 0, O, P, Q, R, S, T, U, V, W)) :|: D >= M + 1 && A >= 0 && A <= 0 f77(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, 0, P, Q, R, S, T, U, V, W)) :|: D >= I + 1 f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f83(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, O + 1, Q, R, S, T, U, V, W)) :|: D >= 2 + O f83(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f86(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= P + 1 && 0 >= B + 1 f83(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f86(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= P + 1 && B >= 1 f86(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f83(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P + 1, 1, R, S, T, U, V, W)) :|: X >= Y + 1 f86(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f83(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P + 1, 1, R, S, T, U, V, W)) :|: TRUE f86(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f83(A, 0, C, D, E, F, G, H, I, J, K, L, M, N, O, P + 1, 0, R, S, T, U, V, W)) :|: TRUE f83(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f83(A, 0, C, D, E, F, G, H, I, J, K, L, M, N, O, P + 1, 0, R, S, T, U, V, W)) :|: D >= P + 1 && B >= 0 && B <= 0 f98(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f101(A, B, C, D, E, F, G, H, 0, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: C >= H + 1 f101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f104(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, 0, S, T, U, V, W)) :|: C >= I + 1 f104(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f107(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, 0, T, U, V, W)) :|: C >= R + 1 f107(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, 0, U, V, W)) :|: C >= S + 1 f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, 0, V, W)) :|: C >= T + 1 f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f117(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= F + 1 && C * T + U >= C * R + S + 1 && C >= U + 1 f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f117(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: F >= 1 && C * T + U >= C * R + S + 1 && C >= U + 1 f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U + 1, V, W)) :|: C * R + S >= C * T + U && C >= U + 1 f117(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U + 1, 1, W)) :|: X >= Y + 1 f117(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U + 1, 1, W)) :|: TRUE f117(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U + 1, 0, W)) :|: TRUE f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f113(A, B, C, D, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U + 1, 0, W)) :|: C * T + U >= C * R + S + 1 && C >= U + 1 && F >= 0 && F <= 0 f137(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 0)) :|: 0 >= F + 1 f137(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 0)) :|: F >= 1 f137(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(A, B, C, D, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 1)) :|: F >= 0 && F <= 0 f136(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(A, 0, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 1)) :|: B >= 0 && B <= 0 f135(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(0, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 1)) :|: A >= 0 && A <= 0 f113(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T + 1, U, V, W)) :|: U >= C f110(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f107(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S + 1, T, U, V, W)) :|: T >= C f107(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f104(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R + 1, S, T, U, V, W)) :|: S >= C f104(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f101(A, B, C, D, E, F, G, H, I + 1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: R >= C f101(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f98(A, B, C, D, E, F, G, H + 1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= C f98(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f135(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= E + 1 && H >= C f98(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f135(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: E >= 1 && H >= C f98(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f146(A, B, C, D, 0, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 1)) :|: H >= C && E >= 0 && E <= 0 f83(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O + 1, P, Q, R, S, T, U, V, W)) :|: P >= D f80(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f77(A, B, C, D, E, F, G, H, I + 1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: O + 1 >= D f77(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f98(A, B, C, D, E, F, G, 0, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= D f62(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K, L + 1, M, N, O, P, Q, R, S, T, U, V, W)) :|: M >= D f59(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f56(A, B, C, D, E, F, G, H + 1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: L + 1 >= D f56(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f77(A, B, C, D, E, F, G, H, 0, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: H >= D f41(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f38(A, B, C, D, E, F, G, H + 1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= D f38(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f56(A, B, C, D, E, F, G, 0, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: H >= D f29(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f26(A, B, C, D, E, F, G, H + 1, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= D f26(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f38(A, B, C, D, E, F, G, 0, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: H >= D The start-symbols are:[f0_23] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f135 -> f136 : [ 0>=1+A ], cost: 1 1: f135 -> f136 : [ A>=1 ], cost: 1 45: f135 -> f146 : A'=0, W'=1, [ A==0 ], cost: 1 2: f136 -> f137 : [ 0>=1+B ], cost: 1 3: f136 -> f137 : [ B>=1 ], cost: 1 44: f136 -> f146 : B'=0, W'=1, [ B==0 ], cost: 1 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 6: f29 -> f29 : Q'=1+Q, J'=free_2, [ D>=1+Q ], cost: 1 62: f29 -> f26 : H'=1+H, [ Q>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 8: f41 -> f44 : [ 0>=1+E && D>=1+Q ], cost: 1 9: f41 -> f44 : [ E>=1 && D>=1+Q ], cost: 1 12: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ D>=1+Q && E==0 ], cost: 1 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 10: f44 -> f41 : E'=1, Q'=1+Q, K'=1, [], cost: 1 11: f44 -> f41 : E'=0, Q'=1+Q, K'=0, [], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 15: f62 -> f65 : [ D>=1+M && 0>=1+A ], cost: 1 16: f62 -> f65 : [ D>=1+M && A>=1 ], cost: 1 20: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A==0 ], cost: 1 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 17: f65 -> f62 : A'=1, M'=1+M, N'=1, [ free_3>=1+free_4 ], cost: 1 18: f65 -> f62 : A'=1, M'=1+M, N'=1, [], cost: 1 19: f65 -> f62 : A'=0, M'=1+M, N'=0, [], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 23: f83 -> f86 : [ D>=1+P && 0>=1+B ], cost: 1 24: f83 -> f86 : [ D>=1+P && B>=1 ], cost: 1 28: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B==0 ], cost: 1 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 25: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [ free_5>=1+free_6 ], cost: 1 26: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [], cost: 1 27: f86 -> f83 : B'=0, P'=1+P, Q_1'=0, [], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 51: f98 -> f135 : [ 0>=1+E && H>=C ], cost: 1 52: f98 -> f135 : [ E>=1 && H>=C ], cost: 1 53: f98 -> f146 : E'=0, W'=1, [ H>=C && E==0 ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 34: f113 -> f117 : [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 35: f113 -> f117 : [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 36: f113 -> f113 : U'=1+U, [ S+C*R>=C*T+U && C>=1+U ], cost: 1 40: f113 -> f113 : F'=0, U'=1+U, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 ], cost: 1 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 37: f117 -> f113 : F'=1, U'=1+U, V'=1, [ free_7>=1+free_8 ], cost: 1 38: f117 -> f113 : F'=1, U'=1+U, V'=1, [], cost: 1 39: f117 -> f113 : F'=0, U'=1+U, V'=0, [], cost: 1 41: f137 -> f146 : W'=0, [ 0>=1+F ], cost: 1 42: f137 -> f146 : W'=0, [ F>=1 ], cost: 1 43: f137 -> f146 : F'=0, W'=1, [ F==0 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 6: f29 -> f29 : Q'=1+Q, J'=free_2, [ D>=1+Q ], cost: 1 62: f29 -> f26 : H'=1+H, [ Q>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 8: f41 -> f44 : [ 0>=1+E && D>=1+Q ], cost: 1 9: f41 -> f44 : [ E>=1 && D>=1+Q ], cost: 1 12: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ D>=1+Q && E==0 ], cost: 1 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 10: f44 -> f41 : E'=1, Q'=1+Q, K'=1, [], cost: 1 11: f44 -> f41 : E'=0, Q'=1+Q, K'=0, [], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 15: f62 -> f65 : [ D>=1+M && 0>=1+A ], cost: 1 16: f62 -> f65 : [ D>=1+M && A>=1 ], cost: 1 20: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A==0 ], cost: 1 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 17: f65 -> f62 : A'=1, M'=1+M, N'=1, [ free_3>=1+free_4 ], cost: 1 18: f65 -> f62 : A'=1, M'=1+M, N'=1, [], cost: 1 19: f65 -> f62 : A'=0, M'=1+M, N'=0, [], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 23: f83 -> f86 : [ D>=1+P && 0>=1+B ], cost: 1 24: f83 -> f86 : [ D>=1+P && B>=1 ], cost: 1 28: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B==0 ], cost: 1 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 25: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [ free_5>=1+free_6 ], cost: 1 26: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [], cost: 1 27: f86 -> f83 : B'=0, P'=1+P, Q_1'=0, [], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 34: f113 -> f117 : [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 35: f113 -> f117 : [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 36: f113 -> f113 : U'=1+U, [ S+C*R>=C*T+U && C>=1+U ], cost: 1 40: f113 -> f113 : F'=0, U'=1+U, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 ], cost: 1 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 37: f117 -> f113 : F'=1, U'=1+U, V'=1, [ free_7>=1+free_8 ], cost: 1 38: f117 -> f113 : F'=1, U'=1+U, V'=1, [], cost: 1 39: f117 -> f113 : F'=0, U'=1+U, V'=0, [], cost: 1 Simplified all rules, resulting in: Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 6: f29 -> f29 : Q'=1+Q, J'=free_2, [ D>=1+Q ], cost: 1 62: f29 -> f26 : H'=1+H, [ Q>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 8: f41 -> f44 : [ 0>=1+E && D>=1+Q ], cost: 1 9: f41 -> f44 : [ E>=1 && D>=1+Q ], cost: 1 12: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ D>=1+Q && E==0 ], cost: 1 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 10: f44 -> f41 : E'=1, Q'=1+Q, K'=1, [], cost: 1 11: f44 -> f41 : E'=0, Q'=1+Q, K'=0, [], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 15: f62 -> f65 : [ D>=1+M && 0>=1+A ], cost: 1 16: f62 -> f65 : [ D>=1+M && A>=1 ], cost: 1 20: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A==0 ], cost: 1 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 18: f65 -> f62 : A'=1, M'=1+M, N'=1, [], cost: 1 19: f65 -> f62 : A'=0, M'=1+M, N'=0, [], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 23: f83 -> f86 : [ D>=1+P && 0>=1+B ], cost: 1 24: f83 -> f86 : [ D>=1+P && B>=1 ], cost: 1 28: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B==0 ], cost: 1 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 26: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [], cost: 1 27: f86 -> f83 : B'=0, P'=1+P, Q_1'=0, [], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 34: f113 -> f117 : [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 35: f113 -> f117 : [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 36: f113 -> f113 : U'=1+U, [ S+C*R>=C*T+U && C>=1+U ], cost: 1 40: f113 -> f113 : F'=0, U'=1+U, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 ], cost: 1 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 38: f117 -> f113 : F'=1, U'=1+U, V'=1, [], cost: 1 39: f117 -> f113 : F'=0, U'=1+U, V'=0, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 4. Accelerating the following rules: 6: f29 -> f29 : Q'=1+Q, J'=free_2, [ D>=1+Q ], cost: 1 Accelerated rule 6 with metering function D-Q, yielding the new rule 64. Removing the simple loops: 6. Accelerating simple loops of location 6. Accelerating the following rules: 12: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ D>=1+Q && E==0 ], cost: 1 Accelerated rule 12 with metering function D-Q, yielding the new rule 65. Removing the simple loops: 12. Accelerating simple loops of location 10. Accelerating the following rules: 20: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A==0 ], cost: 1 Accelerated rule 20 with metering function -M+D, yielding the new rule 66. Removing the simple loops: 20. Accelerating simple loops of location 14. Accelerating the following rules: 28: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B==0 ], cost: 1 Accelerated rule 28 with metering function -P+D, yielding the new rule 67. Removing the simple loops: 28. Accelerating simple loops of location 21. Accelerating the following rules: 36: f113 -> f113 : U'=1+U, [ S+C*R>=C*T+U && C>=1+U ], cost: 1 40: f113 -> f113 : F'=0, U'=1+U, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 ], cost: 1 Found no metering function for rule 36 (rule is too complicated). Found no metering function for rule 40 (rule is too complicated). Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 62: f29 -> f26 : H'=1+H, [ Q>=D ], cost: 1 64: f29 -> f29 : Q'=D, J'=free_2, [ D>=1+Q ], cost: D-Q 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 8: f41 -> f44 : [ 0>=1+E && D>=1+Q ], cost: 1 9: f41 -> f44 : [ E>=1 && D>=1+Q ], cost: 1 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 65: f41 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+Q && E==0 ], cost: D-Q 10: f44 -> f41 : E'=1, Q'=1+Q, K'=1, [], cost: 1 11: f44 -> f41 : E'=0, Q'=1+Q, K'=0, [], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 15: f62 -> f65 : [ D>=1+M && 0>=1+A ], cost: 1 16: f62 -> f65 : [ D>=1+M && A>=1 ], cost: 1 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 66: f62 -> f62 : A'=0, M'=D, N'=0, [ D>=1+M && A==0 ], cost: -M+D 18: f65 -> f62 : A'=1, M'=1+M, N'=1, [], cost: 1 19: f65 -> f62 : A'=0, M'=1+M, N'=0, [], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 23: f83 -> f86 : [ D>=1+P && 0>=1+B ], cost: 1 24: f83 -> f86 : [ D>=1+P && B>=1 ], cost: 1 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 67: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=1+P && B==0 ], cost: -P+D 26: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [], cost: 1 27: f86 -> f83 : B'=0, P'=1+P, Q_1'=0, [], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 34: f113 -> f117 : [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 35: f113 -> f117 : [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 36: f113 -> f113 : U'=1+U, [ S+C*R>=C*T+U && C>=1+U ], cost: 1 40: f113 -> f113 : F'=0, U'=1+U, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 ], cost: 1 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 38: f117 -> f113 : F'=1, U'=1+U, V'=1, [], cost: 1 39: f117 -> f113 : F'=0, U'=1+U, V'=0, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 68: f26 -> f29 : Q'=D, J'=free_2, [ D>=1+H && D>=1 ], cost: 1+D 62: f29 -> f26 : H'=1+H, [ Q>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 8: f41 -> f44 : [ 0>=1+E && D>=1+Q ], cost: 1 9: f41 -> f44 : [ E>=1 && D>=1+Q ], cost: 1 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 10: f44 -> f41 : E'=1, Q'=1+Q, K'=1, [], cost: 1 11: f44 -> f41 : E'=0, Q'=1+Q, K'=0, [], cost: 1 70: f44 -> f41 : E'=0, Q'=D, K'=0, [ D>=2+Q ], cost: D-Q 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 15: f62 -> f65 : [ D>=1+M && 0>=1+A ], cost: 1 16: f62 -> f65 : [ D>=1+M && A>=1 ], cost: 1 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 18: f65 -> f62 : A'=1, M'=1+M, N'=1, [], cost: 1 19: f65 -> f62 : A'=0, M'=1+M, N'=0, [], cost: 1 72: f65 -> f62 : A'=0, M'=D, N'=0, [ D>=2+M ], cost: -M+D 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 23: f83 -> f86 : [ D>=1+P && 0>=1+B ], cost: 1 24: f83 -> f86 : [ D>=1+P && B>=1 ], cost: 1 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 26: f86 -> f83 : B'=1, P'=1+P, Q_1'=1, [], cost: 1 27: f86 -> f83 : B'=0, P'=1+P, Q_1'=0, [], cost: 1 74: f86 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+P ], cost: -P+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 34: f113 -> f117 : [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 35: f113 -> f117 : [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 1 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 38: f117 -> f113 : F'=1, U'=1+U, V'=1, [], cost: 1 39: f117 -> f113 : F'=0, U'=1+U, V'=0, [], cost: 1 76: f117 -> f113 : F'=1, U'=2+U, V'=1, [ S+C*R>=1+C*T+U && C>=2+U ], cost: 2 77: f117 -> f113 : F'=0, U'=2+U, V'=0, [ S+C*R>=1+C*T+U && C>=2+U ], cost: 2 79: f117 -> f113 : F'=0, U'=2+U, V'=0, [ 1+C*T+U>=1+S+C*R && C>=2+U ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 80: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 81: f26 -> f26 : H'=1+H, Q'=D, J'=free_2, [ D>=1+H && D>=1 ], cost: 2+D 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 82: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 83: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 84: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1+D-Q 85: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 86: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ E>=1 && D>=1+Q ], cost: 2 87: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1+D-Q 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 88: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 89: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 90: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 91: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 92: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A>=1 ], cost: 2 93: f62 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=2+M ], cost: 1-M+D 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 94: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 95: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 96: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 97: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 98: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B>=1 ], cost: 2 99: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=2+P ], cost: 1-P+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 100: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 101: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 102: f113 -> f113 : F'=1, U'=2+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 103: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 104: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U ], cost: 3 105: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 106: f113 -> f113 : F'=0, U'=1+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 107: f113 -> f113 : F'=1, U'=2+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 108: f113 -> f113 : F'=0, U'=2+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 109: f113 -> f113 : F'=0, U'=2+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U ], cost: 3 Applied pruning (of leafs and parallel rules): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 80: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 81: f26 -> f26 : H'=1+H, Q'=D, J'=free_2, [ D>=1+H && D>=1 ], cost: 2+D 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 82: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 83: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 84: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1+D-Q 85: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 87: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1+D-Q 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 88: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 89: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 90: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 91: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 93: f62 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=2+M ], cost: 1-M+D 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 94: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 95: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 96: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 97: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 99: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=2+P ], cost: 1-P+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 100: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 101: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 103: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 104: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U ], cost: 3 105: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 Accelerating simple loops of location 3. Accelerating the following rules: 80: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 81: f26 -> f26 : H'=1+H, Q'=D, J'=free_2, [ D>=1+H && D>=1 ], cost: 2+D Accelerated rule 80 with metering function D-H, yielding the new rule 110. Accelerated rule 81 with metering function D-H, yielding the new rule 111. Removing the simple loops: 80 81. Accelerating simple loops of location 6. Accelerating the following rules: 82: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 83: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 84: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1+D-Q 85: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 87: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1+D-Q Found no metering function for rule 82. Found no metering function for rule 83. Found no metering function for rule 84. Accelerated rule 85 with metering function D-Q, yielding the new rule 112. Found no metering function for rule 87. Removing the simple loops: 85. Accelerating simple loops of location 10. Accelerating the following rules: 88: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 89: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 90: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 91: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 93: f62 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=2+M ], cost: 1-M+D Found no metering function for rule 88. Found no metering function for rule 89. Found no metering function for rule 90. Accelerated rule 91 with metering function -M+D, yielding the new rule 113. Found no metering function for rule 93. Removing the simple loops: 91. Accelerating simple loops of location 14. Accelerating the following rules: 94: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 95: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 96: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 97: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 99: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=2+P ], cost: 1-P+D Found no metering function for rule 94. Found no metering function for rule 95. Found no metering function for rule 96. Accelerated rule 97 with metering function -P+D, yielding the new rule 114. Found no metering function for rule 99. Removing the simple loops: 97. Accelerating simple loops of location 21. Accelerating the following rules: 100: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 101: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 103: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: 3 104: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U ], cost: 3 105: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 Found no metering function for rule 100 (rule is too complicated). Found no metering function for rule 101 (rule is too complicated). Accelerated rule 103 with NONTERM, yielding the new rule 115. Found no metering function for rule 104 (rule is too complicated). Found no metering function for rule 105 (rule is too complicated). Removing the simple loops: 103. Accelerated all simple loops using metering functions (where possible): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 110: f26 -> f26 : H'=D, Q'=0, [ D>=1+H && 0>=D ], cost: 2*D-2*H 111: f26 -> f26 : H'=D, Q'=D, J'=free_2, [ D>=1+H && D>=1 ], cost: 2*D-2*H+(D-H)*D 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 82: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 83: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 84: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1+D-Q 87: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1+D-Q 112: f41 -> f41 : E'=1, Q'=D, K'=1, [ E>=1 && D>=1+Q ], cost: 2*D-2*Q 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 88: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 89: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 90: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 93: f62 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=2+M ], cost: 1-M+D 113: f62 -> f62 : A'=1, M'=D, N'=1, [ D>=1+M && A>=1 ], cost: -2*M+2*D 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 94: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 95: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 96: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 99: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=2+P ], cost: 1-P+D 114: f83 -> f83 : B'=1, P'=D, Q_1'=1, [ D>=1+P && B>=1 ], cost: -2*P+2*D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 100: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 101: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 104: f113 -> f113 : F'=0, U'=2+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U ], cost: 3 105: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 115: f113 -> [34] : [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 116: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, [ free>=1 ], cost: 1+free^2+2*free 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 117: f38 -> f41 : E'=1, Q'=1, K'=1, [ D>=1+H && 0>=1+E && D>=1 ], cost: 3 118: f38 -> f41 : E'=0, Q'=1, K'=0, [ D>=1+H && 0>=1+E && D>=1 ], cost: 3 119: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 2+D 120: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 2+D 121: f38 -> f41 : E'=1, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 1+2*D 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 122: f59 -> f62 : A'=1, M'=2+L, N'=1, [ D>=2+L && 0>=1+A ], cost: 3 123: f59 -> f62 : A'=0, M'=2+L, N'=0, [ D>=2+L && 0>=1+A ], cost: 3 124: f59 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 1+D-L 125: f59 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 1+D-L 126: f59 -> f62 : A'=1, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: -1+2*D-2*L 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 127: f80 -> f83 : B'=1, P'=2+O, Q_1'=1, [ D>=2+O && 0>=1+B ], cost: 3 128: f80 -> f83 : B'=0, P'=2+O, Q_1'=0, [ D>=2+O && 0>=1+B ], cost: 3 129: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 1+D-O 130: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 1+D-O 131: f80 -> f83 : B'=1, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: -1+2*D-2*O 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 132: f110 -> f113 : F'=1, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 ], cost: 3 133: f110 -> f113 : F'=1, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 ], cost: 4 134: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 ], cost: 3 135: f110 -> f113 : F'=0, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 ], cost: 4 136: f110 -> f113 : F'=0, U'=2, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=2 ], cost: 4 137: f110 -> f113 : F'=0, U'=3, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=3 ], cost: 5 138: f110 -> f113 : F'=1, U'=1, V'=1, [ C>=1+T && F>=1 && C*T>=1+S+C*R && C>=1 ], cost: 3 139: f110 -> f113 : F'=1, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && F>=1 && C>=2 ], cost: 4 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 Removed unreachable locations (and leaf rules with constant cost): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [], cost: 1 116: f0 -> f26 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, [ free>=1 ], cost: 1+free^2+2*free 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 7: f38 -> f41 : Q'=0, [ D>=1+H ], cost: 1 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 69: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 117: f38 -> f41 : E'=1, Q'=1, K'=1, [ D>=1+H && 0>=1+E && D>=1 ], cost: 3 118: f38 -> f41 : E'=0, Q'=1, K'=0, [ D>=1+H && 0>=1+E && D>=1 ], cost: 3 119: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 2+D 120: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 2+D 121: f38 -> f41 : E'=1, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 1+2*D 60: f41 -> f38 : H'=1+H, [ Q>=D ], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 14: f59 -> f62 : M'=1+L, [ D>=2+L ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 71: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: D-L 122: f59 -> f62 : A'=1, M'=2+L, N'=1, [ D>=2+L && 0>=1+A ], cost: 3 123: f59 -> f62 : A'=0, M'=2+L, N'=0, [ D>=2+L && 0>=1+A ], cost: 3 124: f59 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 1+D-L 125: f59 -> f62 : A'=0, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 1+D-L 126: f59 -> f62 : A'=1, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: -1+2*D-2*L 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 22: f80 -> f83 : P'=1+O, [ D>=2+O ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 73: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 127: f80 -> f83 : B'=1, P'=2+O, Q_1'=1, [ D>=2+O && 0>=1+B ], cost: 3 128: f80 -> f83 : B'=0, P'=2+O, Q_1'=0, [ D>=2+O && 0>=1+B ], cost: 3 129: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 1+D-O 130: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 1+D-O 131: f80 -> f83 : B'=1, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: -1+2*D-2*O 54: f83 -> f80 : O'=1+O, [ P>=D ], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 75: f110 -> f113 : U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 ], cost: 2 78: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 ], cost: 2 132: f110 -> f113 : F'=1, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 ], cost: 3 133: f110 -> f113 : F'=1, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 ], cost: 4 134: f110 -> f113 : F'=0, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 ], cost: 3 135: f110 -> f113 : F'=0, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 ], cost: 4 136: f110 -> f113 : F'=0, U'=2, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=2 ], cost: 4 137: f110 -> f113 : F'=0, U'=3, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=3 ], cost: 5 138: f110 -> f113 : F'=1, U'=1, V'=1, [ C>=1+T && F>=1 && C*T>=1+S+C*R && C>=1 ], cost: 3 139: f110 -> f113 : F'=1, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && F>=1 && C>=2 ], cost: 4 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 140: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 2 141: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, [ free>=1 ], cost: 2+free^2+2*free 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 142: f38 -> f38 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 143: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 2+D 144: f38 -> f38 : E'=1, H'=1+H, Q'=1, K'=1, [ D>=1+H && 0>=1+E && D>=1 && 1>=D ], cost: 4 145: f38 -> f38 : E'=0, H'=1+H, Q'=1, K'=0, [ D>=1+H && 0>=1+E && D>=1 && 1>=D ], cost: 4 146: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 3+D 147: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 3+D 148: f38 -> f38 : E'=1, H'=1+H, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 2+2*D 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 149: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ D>=2+L && A==0 ], cost: 1+D-L 150: f59 -> f59 : A'=1, L'=1+L, M'=2+L, N'=1, [ D>=2+L && 0>=1+A && 2+L>=D ], cost: 4 151: f59 -> f59 : A'=0, L'=1+L, M'=2+L, N'=0, [ D>=2+L && 0>=1+A && 2+L>=D ], cost: 4 152: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 2+D-L 153: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 2+D-L 154: f59 -> f59 : A'=1, L'=1+L, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: 2*D-2*L 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 155: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: 1+D-O 156: f80 -> f80 : B'=1, O'=1+O, P'=2+O, Q_1'=1, [ D>=2+O && 0>=1+B && 2+O>=D ], cost: 4 157: f80 -> f80 : B'=0, O'=1+O, P'=2+O, Q_1'=0, [ D>=2+O && 0>=1+B && 2+O>=D ], cost: 4 158: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 2+D-O 159: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 2+D-O 160: f80 -> f80 : B'=1, O'=1+O, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: 2*D-2*O 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 161: f110 -> f110 : T'=1+T, U'=0, [ C>=1+T && 0>=C ], cost: 2 162: f110 -> f110 : T'=1+T, U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 && 1>=C ], cost: 3 163: f110 -> f110 : F'=0, T'=1+T, U'=1, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && 1>=C ], cost: 3 164: f110 -> f110 : F'=1, T'=1+T, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 && 1>=C ], cost: 4 165: f110 -> f110 : F'=1, T'=1+T, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 && 2>=C ], cost: 5 166: f110 -> f110 : F'=0, T'=1+T, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 && 1>=C ], cost: 4 167: f110 -> f110 : F'=0, T'=1+T, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 && 2>=C ], cost: 5 168: f110 -> f110 : F'=0, T'=1+T, U'=2, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=2 && 2>=C ], cost: 5 169: f110 -> f110 : F'=0, T'=1+T, U'=3, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=3 && 3>=C ], cost: 6 170: f110 -> f110 : F'=1, T'=1+T, U'=1, V'=1, [ C>=1+T && F>=1 && C*T>=1+S+C*R && C>=1 && 1>=C ], cost: 4 171: f110 -> f110 : F'=1, T'=1+T, U'=2, V'=1, [ C>=1+T && -S-C*R+C*T==0 && F>=1 && C>=2 && 2>=C ], cost: 5 Applied pruning (of leafs and parallel rules): Start location: f0 140: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 2 141: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, [ free>=1 ], cost: 2+free^2+2*free 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 143: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 2+D 145: f38 -> f38 : E'=0, H'=1+H, Q'=1, K'=0, [ D>=1+H && 0>=1+E && D>=1 && 1>=D ], cost: 4 146: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 3+D 147: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 3+D 148: f38 -> f38 : E'=1, H'=1+H, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 2+2*D 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 149: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ D>=2+L && A==0 ], cost: 1+D-L 151: f59 -> f59 : A'=0, L'=1+L, M'=2+L, N'=0, [ D>=2+L && 0>=1+A && 2+L>=D ], cost: 4 152: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 2+D-L 153: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 2+D-L 154: f59 -> f59 : A'=1, L'=1+L, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: 2*D-2*L 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 155: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: 1+D-O 157: f80 -> f80 : B'=0, O'=1+O, P'=2+O, Q_1'=0, [ D>=2+O && 0>=1+B && 2+O>=D ], cost: 4 158: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 2+D-O 159: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 2+D-O 160: f80 -> f80 : B'=1, O'=1+O, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: 2*D-2*O 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 161: f110 -> f110 : T'=1+T, U'=0, [ C>=1+T && 0>=C ], cost: 2 162: f110 -> f110 : T'=1+T, U'=1, [ C>=1+T && S+C*R>=C*T && C>=1 && 1>=C ], cost: 3 164: f110 -> f110 : F'=1, T'=1+T, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 && 1>=C ], cost: 4 166: f110 -> f110 : F'=0, T'=1+T, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && C>=1 && 1>=C ], cost: 4 167: f110 -> f110 : F'=0, T'=1+T, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && C>=2 && 2>=C ], cost: 5 Accelerating simple loops of location 5. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 143: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 2+D 145: f38 -> f38 : E'=0, H'=1+H, Q'=1, K'=0, [ D>=1+H && 0>=1+E && 1-D==0 ], cost: 4 146: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 3+D 147: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 3+D 148: f38 -> f38 : E'=1, H'=1+H, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 2+2*D Accelerated rule 143 with metering function D-H, yielding the new rule 172. Accelerated rule 145 with metering function 1-D, yielding the new rule 173. Found no metering function for rule 146. Found no metering function for rule 147. Accelerated rule 148 with metering function D-H, yielding the new rule 174. Removing the simple loops: 143 145 148. Accelerating simple loops of location 9. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 149: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ D>=2+L && A==0 ], cost: 1+D-L 151: f59 -> f59 : A'=0, L'=1+L, M'=2+L, N'=0, [ 2-D+L==0 && 0>=1+A ], cost: 4 152: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 2+D-L 153: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 2+D-L 154: f59 -> f59 : A'=1, L'=1+L, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: 2*D-2*L Accelerated rule 149 with metering function -1+D-L, yielding the new rule 175. Accelerated rule 151 with metering function -2+D-L, yielding the new rule 176. Found no metering function for rule 152. Found no metering function for rule 153. Accelerated rule 154 with metering function -1+D-L, yielding the new rule 177. Removing the simple loops: 149 151 154. Accelerating simple loops of location 13. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 155: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: 1+D-O 157: f80 -> f80 : B'=0, O'=1+O, P'=2+O, Q_1'=0, [ 2-D+O==0 && 0>=1+B ], cost: 4 158: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 2+D-O 159: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 2+D-O 160: f80 -> f80 : B'=1, O'=1+O, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: 2*D-2*O Accelerated rule 155 with metering function -1+D-O, yielding the new rule 178. Accelerated rule 157 with metering function -2+D-O, yielding the new rule 179. Found no metering function for rule 158. Found no metering function for rule 159. Accelerated rule 160 with metering function -1+D-O, yielding the new rule 180. Removing the simple loops: 155 157 160. Accelerating simple loops of location 20. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 161: f110 -> f110 : T'=1+T, U'=0, [ C>=1+T && 0>=C ], cost: 2 162: f110 -> f110 : T'=1+T, U'=1, [ C>=1+T && S+C*R>=C*T && 1-C==0 ], cost: 3 164: f110 -> f110 : F'=1, T'=1+T, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && 1-C==0 ], cost: 4 166: f110 -> f110 : F'=0, T'=1+T, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && 1-C==0 ], cost: 4 167: f110 -> f110 : F'=0, T'=1+T, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && 2-C==0 ], cost: 5 Accelerated rule 161 with metering function C-T, yielding the new rule 181. Found no metering function for rule 162 (rule is too complicated). Found no metering function for rule 164 (rule is too complicated). Found no metering function for rule 166 (rule is too complicated). Found no metering function for rule 167 (rule is too complicated). Removing the simple loops: 161. Accelerated all simple loops using metering functions (where possible): Start location: f0 140: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 2 141: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, [ free>=1 ], cost: 2+free^2+2*free 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 146: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && 0>=1+E && D>=2 ], cost: 3+D 147: f38 -> f38 : E'=0, H'=1+H, Q'=D, K'=0, [ D>=1+H && E>=1 && D>=2 ], cost: 3+D 172: f38 -> f38 : E'=0, H'=D, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 2*D-2*H+(D-H)*D 173: f38 -> f38 : E'=0, H'=1-D+H, Q'=1, K'=0, [ D>=1+H && 0>=1+E && 1-D==0 && 1-D>=1 ], cost: 4-4*D 174: f38 -> f38 : E'=1, H'=D, Q'=D, K'=1, [ D>=1+H && E>=1 && D>=1 ], cost: 2*D-2*H+2*(D-H)*D 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 152: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ 0>=1+A && D>=3+L ], cost: 2+D-L 153: f59 -> f59 : A'=0, L'=1+L, M'=D, N'=0, [ A>=1 && D>=3+L ], cost: 2+D-L 175: f59 -> f59 : A'=0, L'=-1+D, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -3/2+3/2*D-(-1+D-L)*L+(-1+D-L)*D-3/2*L-1/2*(-1+D-L)^2 176: f59 -> f59 : A'=0, L'=-2+D, M'=-1+D, N'=0, [ 2-D+L==0 && 0>=1+A && -2+D-L>=1 ], cost: -8+4*D-4*L 177: f59 -> f59 : A'=1, L'=-1+D, M'=D, N'=1, [ D>=2+L && A>=1 ], cost: -1+D-2*(-1+D-L)*L+2*(-1+D-L)*D-L-(-1+D-L)^2 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 158: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ 0>=1+B && D>=3+O ], cost: 2+D-O 159: f80 -> f80 : B'=0, O'=1+O, P'=D, Q_1'=0, [ B>=1 && D>=3+O ], cost: 2+D-O 178: f80 -> f80 : B'=0, O'=-1+D, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: -3/2+(-1+D-O)*D-1/2*(-1+D-O)^2-(-1+D-O)*O+3/2*D-3/2*O 179: f80 -> f80 : B'=0, O'=-2+D, P'=-1+D, Q_1'=0, [ 2-D+O==0 && 0>=1+B && -2+D-O>=1 ], cost: -8+4*D-4*O 180: f80 -> f80 : B'=1, O'=-1+D, P'=D, Q_1'=1, [ D>=2+O && B>=1 ], cost: -1+2*(-1+D-O)*D-(-1+D-O)^2-2*(-1+D-O)*O+D-O 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 162: f110 -> f110 : T'=1+T, U'=1, [ C>=1+T && S+C*R>=C*T && 1-C==0 ], cost: 3 164: f110 -> f110 : F'=1, T'=1+T, U'=1, V'=1, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && 1-C==0 ], cost: 4 166: f110 -> f110 : F'=0, T'=1+T, U'=1, V'=0, [ C>=1+T && 0>=1+F && C*T>=1+S+C*R && 1-C==0 ], cost: 4 167: f110 -> f110 : F'=0, T'=1+T, U'=2, V'=0, [ C>=1+T && -S-C*R+C*T==0 && 0>=1+F && 2-C==0 ], cost: 5 181: f110 -> f110 : T'=C, U'=0, [ C>=1+T && 0>=C ], cost: 2*C-2*T Chained accelerated rules (with incoming rules): Start location: f0 140: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 2 141: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, [ free>=1 ], cost: 2+free^2+2*free 182: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=0, F'=1, G'=free_1, H'=1, Q'=free, J'=free_2, K'=0, [ free>=2 ], cost: 5+free^2+3*free 183: f0 -> f38 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, K'=1, [ free>=1 ], cost: 2+3*free^2+4*free 61: f38 -> f56 : H'=0, [ H>=D ], cost: 1 13: f56 -> f59 : L'=0, [ D>=1+H ], cost: 1 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 184: f56 -> f59 : A'=0, L'=1, M'=D, N'=0, [ D>=1+H && 0>=1+A && D>=3 ], cost: 3+D 185: f56 -> f59 : A'=0, L'=1, M'=D, N'=0, [ D>=1+H && A>=1 && D>=3 ], cost: 3+D 186: f56 -> f59 : A'=0, L'=-1+D, M'=D, N'=0, [ D>=1+H && D>=2 && A==0 ], cost: -1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 187: f56 -> f59 : A'=1, L'=-1+D, M'=D, N'=1, [ D>=1+H && D>=2 && A>=1 ], cost: -(-1+D)^2+D+2*(-1+D)*D 58: f59 -> f56 : H'=1+H, [ 1+L>=D ], cost: 1 21: f77 -> f80 : O'=0, [ D>=1+Q ], cost: 1 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 188: f77 -> f80 : B'=0, O'=1, P'=D, Q_1'=0, [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 189: f77 -> f80 : B'=0, O'=1, P'=D, Q_1'=0, [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 190: f77 -> f80 : B'=0, O'=-1+D, P'=D, Q_1'=0, [ D>=1+Q && D>=2 && B==0 ], cost: -1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 191: f77 -> f80 : B'=1, O'=-1+D, P'=D, Q_1'=1, [ D>=1+Q && D>=2 && B>=1 ], cost: -(-1+D)^2+D+2*(-1+D)*D 55: f80 -> f77 : Q'=1+Q, [ 1+O>=D ], cost: 1 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 192: f107 -> f110 : T'=1, U'=1, [ C>=1+S && S+C*R>=0 && 1-C==0 ], cost: 4 193: f107 -> f110 : F'=1, T'=1, U'=1, V'=1, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 5 194: f107 -> f110 : F'=0, T'=1, U'=1, V'=0, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 5 195: f107 -> f110 : F'=0, T'=1, U'=2, V'=0, [ C>=1+S && -S-C*R==0 && 0>=1+F && 2-C==0 ], cost: 6 47: f110 -> f107 : S'=1+S, [ T>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 196: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 3 197: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=1 ], cost: 3+3*free^2+4*free 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 200: f56 -> f56 : H'=1+H, L'=0, [ D>=1+H && 1>=D ], cost: 2 201: f56 -> f56 : A'=0, H'=1+H, L'=-1+D, M'=D, N'=0, [ D>=1+H && D>=2 && A==0 ], cost: 1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 202: f56 -> f56 : A'=1, H'=1+H, L'=-1+D, M'=D, N'=1, [ D>=1+H && D>=2 && A>=1 ], cost: 1-(-1+D)^2+D+2*(-1+D)*D 203: f56 -> [40] : [ D>=1+H && 0>=1+A && D>=3 ], cost: 3+D 204: f56 -> [40] : [ D>=1+H && A>=1 && D>=3 ], cost: 3+D 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 205: f77 -> f77 : Q'=1+Q, O'=0, [ D>=1+Q && 1>=D ], cost: 2 206: f77 -> f77 : B'=0, Q'=1+Q, O'=-1+D, P'=D, Q_1'=0, [ D>=1+Q && D>=2 && B==0 ], cost: 1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 207: f77 -> f77 : B'=1, Q'=1+Q, O'=-1+D, P'=D, Q_1'=1, [ D>=1+Q && D>=2 && B>=1 ], cost: 1-(-1+D)^2+D+2*(-1+D)*D 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 210: f107 -> f107 : S'=1+S, T'=0, [ C>=1+S && 0>=C ], cost: 2 211: f107 -> f107 : S'=1+S, T'=1, U'=1, [ C>=1+S && S+C*R>=0 && 1-C==0 ], cost: 5 212: f107 -> f107 : F'=1, S'=1+S, T'=1, U'=1, V'=1, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 213: f107 -> f107 : F'=0, S'=1+S, T'=1, U'=1, V'=0, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 Accelerating simple loops of location 8. Accelerating the following rules: 200: f56 -> f56 : H'=1+H, L'=0, [ D>=1+H && 1>=D ], cost: 2 201: f56 -> f56 : A'=0, H'=1+H, L'=-1+D, M'=D, N'=0, [ D>=1+H && D>=2 && A==0 ], cost: 1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 202: f56 -> f56 : A'=1, H'=1+H, L'=-1+D, M'=D, N'=1, [ D>=1+H && D>=2 && A>=1 ], cost: 1-(-1+D)^2+D+2*(-1+D)*D Accelerated rule 200 with metering function D-H, yielding the new rule 214. Accelerated rule 201 with metering function D-H, yielding the new rule 215. Accelerated rule 202 with metering function D-H, yielding the new rule 216. Removing the simple loops: 200 201 202. Accelerating simple loops of location 12. Accelerating the following rules: 205: f77 -> f77 : Q'=1+Q, O'=0, [ D>=1+Q && 1>=D ], cost: 2 206: f77 -> f77 : B'=0, Q'=1+Q, O'=-1+D, P'=D, Q_1'=0, [ D>=1+Q && D>=2 && B==0 ], cost: 1/2-1/2*(-1+D)^2+3/2*D+(-1+D)*D 207: f77 -> f77 : B'=1, Q'=1+Q, O'=-1+D, P'=D, Q_1'=1, [ D>=1+Q && D>=2 && B>=1 ], cost: 1-(-1+D)^2+D+2*(-1+D)*D Accelerated rule 205 with metering function D-Q, yielding the new rule 217. Accelerated rule 206 with metering function D-Q, yielding the new rule 218. Accelerated rule 207 with metering function D-Q, yielding the new rule 219. Removing the simple loops: 205 206 207. Accelerating simple loops of location 19. Accelerating the following rules: 210: f107 -> f107 : S'=1+S, T'=0, [ C>=1+S && 0>=C ], cost: 2 211: f107 -> f107 : S'=1+S, T'=1, U'=1, [ C>=1+S && S+C*R>=0 && 1-C==0 ], cost: 5 212: f107 -> f107 : F'=1, S'=1+S, T'=1, U'=1, V'=1, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 213: f107 -> f107 : F'=0, S'=1+S, T'=1, U'=1, V'=0, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 Accelerated rule 210 with metering function -S+C, yielding the new rule 220. Found no metering function for rule 211 (rule is too complicated). Found no metering function for rule 212 (rule is too complicated). Found no metering function for rule 213 (rule is too complicated). Removing the simple loops: 210. Accelerated all simple loops using metering functions (where possible): Start location: f0 196: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 3 197: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=1 ], cost: 3+3*free^2+4*free 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 203: f56 -> [40] : [ D>=1+H && 0>=1+A && D>=3 ], cost: 3+D 204: f56 -> [40] : [ D>=1+H && A>=1 && D>=3 ], cost: 3+D 214: f56 -> f56 : H'=D, L'=0, [ D>=1+H && 1>=D ], cost: 2*D-2*H 215: f56 -> f56 : A'=0, H'=D, L'=-1+D, M'=D, N'=0, [ D>=1+H && D>=2 && A==0 ], cost: 3/2*(D-H)*D+1/2*(D-H)*D^2 216: f56 -> f56 : A'=1, H'=D, L'=-1+D, M'=D, N'=1, [ D>=1+H && D>=2 && A>=1 ], cost: (D-H)*D+(D-H)*D^2 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 217: f77 -> f77 : Q'=D, O'=0, [ D>=1+Q && 1>=D ], cost: 2*D-2*Q 218: f77 -> f77 : B'=0, Q'=D, O'=-1+D, P'=D, Q_1'=0, [ D>=1+Q && D>=2 && B==0 ], cost: 1/2*D^2*(D-Q)+3/2*D*(D-Q) 219: f77 -> f77 : B'=1, Q'=D, O'=-1+D, P'=D, Q_1'=1, [ D>=1+Q && D>=2 && B>=1 ], cost: D^2*(D-Q)+D*(D-Q) 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 211: f107 -> f107 : S'=1+S, T'=1, U'=1, [ C>=1+S && S+C*R>=0 && 1-C==0 ], cost: 5 212: f107 -> f107 : F'=1, S'=1+S, T'=1, U'=1, V'=1, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 213: f107 -> f107 : F'=0, S'=1+S, T'=1, U'=1, V'=0, [ C>=1+S && 0>=1+F && 0>=1+S+C*R && 1-C==0 ], cost: 6 220: f107 -> f107 : S'=C, T'=0, [ C>=1+S && 0>=C ], cost: -2*S+2*C Chained accelerated rules (with incoming rules): Start location: f0 196: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, [ 0>=free ], cost: 3 197: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=1 ], cost: 3+3*free^2+4*free 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 221: f0 -> f56 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=1, J'=free_2, K'=1, L'=0, [], cost: 12 222: f0 -> f56 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=2 ], cost: 3+4*free^2+free^3+4*free 59: f56 -> f77 : Q'=0, [ H>=D ], cost: 1 203: f56 -> [40] : [ D>=1+H && 0>=1+A && D>=3 ], cost: 3+D 204: f56 -> [40] : [ D>=1+H && A>=1 && D>=3 ], cost: 3+D 223: f56 -> f77 : Q'=D, O'=0, [ H>=D && 1-D==0 ], cost: 1+2*D 224: f56 -> f77 : B'=0, Q'=D, O'=-1+D, P'=D, Q_1'=0, [ H>=D && D>=2 && B==0 ], cost: 1+1/2*D^3+3/2*D^2 225: f56 -> f77 : B'=1, Q'=D, O'=-1+D, P'=D, Q_1'=1, [ H>=D && D>=2 && B>=1 ], cost: 1+D^3+D^2 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 226: f104 -> f107 : S'=1, T'=1, U'=1, [ C>=1+R && C*R>=0 && 1-C==0 ], cost: 6 227: f104 -> f107 : F'=1, S'=1, T'=1, U'=1, V'=1, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 7 228: f104 -> f107 : F'=0, S'=1, T'=1, U'=1, V'=0, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 7 48: f107 -> f104 : R'=1+R, [ S>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 229: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 4 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 231: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=0, J'=free_2, K'=1, L'=0, [], cost: 13 232: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 15 233: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=2 ], cost: 4+4*free^2+free^3+4*free 234: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 237: f104 -> f104 : R'=1+R, S'=0, [ C>=1+R && 0>=C ], cost: 2 238: f104 -> f104 : R'=1+R, S'=1, T'=1, U'=1, [ C>=1+R && C*R>=0 && 1-C==0 ], cost: 7 239: f104 -> f104 : F'=1, R'=1+R, S'=1, T'=1, U'=1, V'=1, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 240: f104 -> f104 : F'=0, R'=1+R, S'=1, T'=1, U'=1, V'=0, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 Accelerating simple loops of location 18. Accelerating the following rules: 237: f104 -> f104 : R'=1+R, S'=0, [ C>=1+R && 0>=C ], cost: 2 238: f104 -> f104 : R'=1+R, S'=1, T'=1, U'=1, [ C>=1+R && C*R>=0 && 1-C==0 ], cost: 7 239: f104 -> f104 : F'=1, R'=1+R, S'=1, T'=1, U'=1, V'=1, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 240: f104 -> f104 : F'=0, R'=1+R, S'=1, T'=1, U'=1, V'=0, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 Accelerated rule 237 with metering function C-R, yielding the new rule 241. Found no metering function for rule 238 (rule is too complicated). Found no metering function for rule 239 (rule is too complicated). Found no metering function for rule 240 (rule is too complicated). Removing the simple loops: 237. Accelerated all simple loops using metering functions (where possible): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 229: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 4 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 231: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=0, J'=free_2, K'=1, L'=0, [], cost: 13 232: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 15 233: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=2 ], cost: 4+4*free^2+free^3+4*free 234: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 238: f104 -> f104 : R'=1+R, S'=1, T'=1, U'=1, [ C>=1+R && C*R>=0 && 1-C==0 ], cost: 7 239: f104 -> f104 : F'=1, R'=1+R, S'=1, T'=1, U'=1, V'=1, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 240: f104 -> f104 : F'=0, R'=1+R, S'=1, T'=1, U'=1, V'=0, [ C>=1+R && 0>=1+F && 0>=1+C*R && 1-C==0 ], cost: 8 241: f104 -> f104 : R'=C, S'=0, [ C>=1+R && 0>=C ], cost: 2*C-2*R Chained accelerated rules (with incoming rules): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 229: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 4 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 231: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=0, J'=free_2, K'=1, L'=0, [], cost: 13 232: f0 -> f77 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=1, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 15 233: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=2 ], cost: 4+4*free^2+free^3+4*free 234: f0 -> f77 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 56: f77 -> f98 : H'=0, [ Q>=D ], cost: 1 208: f77 -> [41] : [ D>=1+Q && 0>=1+B && D>=3 ], cost: 3+D 209: f77 -> [41] : [ D>=1+Q && B>=1 && D>=3 ], cost: 3+D 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 30: f101 -> f104 : R'=0, [ C>=1+Q ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 242: f101 -> f104 : R'=1, S'=1, T'=1, U'=1, [ C>=1+Q && 1-C==0 ], cost: 8 49: f104 -> f101 : Q'=1+Q, [ R>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 249: f101 -> f101 : Q'=1+Q, R'=0, [ C>=1+Q && 0>=C ], cost: 2 250: f101 -> f101 : Q'=1+Q, R'=1, S'=1, T'=1, U'=1, [ C>=1+Q && 1-C==0 ], cost: 9 Accelerating simple loops of location 17. Accelerating the following rules: 249: f101 -> f101 : Q'=1+Q, R'=0, [ C>=1+Q && 0>=C ], cost: 2 250: f101 -> f101 : Q'=1+Q, R'=1, S'=1, T'=1, U'=1, [ C>=1+Q && 1-C==0 ], cost: 9 Accelerated rule 249 with metering function C-Q, yielding the new rule 251. Accelerated rule 250 with metering function 2-C-Q, yielding the new rule 252. Removing the simple loops: 249 250. Accelerated all simple loops using metering functions (where possible): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 251: f101 -> f101 : Q'=C, R'=0, [ C>=1+Q && 0>=C ], cost: 2*C-2*Q 252: f101 -> f101 : Q'=2-C, R'=1, S'=1, T'=1, U'=1, [ C>=1+Q && 1-C==0 && 2-C-Q>=1 ], cost: 18-9*C-9*Q Chained accelerated rules (with incoming rules): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 29: f98 -> f101 : Q'=0, [ C>=1+H ], cost: 1 253: f98 -> f101 : Q'=2-C, R'=1, S'=1, T'=1, U'=1, [ C>=1+H && 1-C==0 ], cost: 19-9*C 50: f101 -> f98 : H'=1+H, [ Q>=C ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 254: f98 -> f98 : H'=1+H, Q'=0, [ C>=1+H && 0>=C ], cost: 2 255: f98 -> f98 : H'=1+H, Q'=2-C, R'=1, S'=1, T'=1, U'=1, [ C>=1+H && 1-C==0 && 2-C>=C ], cost: 20-9*C Accelerating simple loops of location 16. Accelerating the following rules: 254: f98 -> f98 : H'=1+H, Q'=0, [ C>=1+H && 0>=C ], cost: 2 255: f98 -> f98 : H'=1+H, Q'=2-C, R'=1, S'=1, T'=1, U'=1, [ C>=1+H && 1-C==0 && 2-C>=C ], cost: 20-9*C Accelerated rule 254 with metering function C-H, yielding the new rule 256. Accelerated rule 255 with metering function 2-C-H, yielding the new rule 257. Removing the simple loops: 254 255. Accelerated all simple loops using metering functions (where possible): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free 256: f98 -> f98 : H'=C, Q'=0, [ C>=1+H && 0>=C ], cost: 2*C-2*H 257: f98 -> f98 : H'=2-C, Q'=2-C, R'=1, S'=1, T'=1, U'=1, [ C>=1+H && 1-C==0 && 2-C>=C && 2-C-H>=1 ], cost: 40-20*C+9*C*(-2+C+H)-20*H Chained accelerated rules (with incoming rules): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 243: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=0, [ 0>=free ], cost: 5 244: f0 -> f98 : A'=1, B'=1, C'=3, D'=1, E'=1, F'=1, G'=free_1, H'=0, Q'=1, J'=free_2, K'=1, L'=0, O'=0, [], cost: 16 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free Removed unreachable locations (and leaf rules with constant cost): Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 236: f0 -> [45] : [ free>=2 ], cost: 3+4*free^2+free^3+4*free 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free 248: f0 -> [47] : [ free>=2 ], cost: 4+5*free^2+2*free^3+4*free ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 198: f0 -> [39] : [ free>=1 ], cost: 2+free^2+2*free 199: f0 -> [39] : [ free>=2 ], cost: 5+free^2+3*free 230: f0 -> [40] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, [ free>=3 ], cost: 6+3*free^2+5*free 235: f0 -> [45] : [ free>=1 ], cost: 3+3*free^2+4*free 245: f0 -> [41] : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=free, Q'=0, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, [ free>=3 ], cost: 7+4*free^2+free^3+5*free 246: f0 -> f98 : A'=1, B'=1, C'=3, D'=free, E'=1, F'=1, G'=free_1, H'=0, Q'=free, J'=free_2, K'=1, L'=-1+free, M'=free, N'=1, O'=-1+free, P'=free, Q_1'=1, [ free>=2 ], cost: 5+5*free^2+2*free^3+4*free 247: f0 -> [47] : [ free>=2 ], cost: 4+4*free^2+free^3+4*free Computing asymptotic complexity for rule 198 Solved the limit problem by the following transformations: Created initial limit problem: free (+/+!), 2+free^2+2*free (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free==n} resulting limit problem: [solved] Solution: free / n Resulting cost 2+n^2+2*n has complexity: Unbounded Found new complexity Unbounded. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Unbounded Cpx degree: Unbounded Solved cost: 2+n^2+2*n Rule cost: 2+free^2+2*free Rule guard: [ free>=1 ] WORST_CASE(INF,?) ---------------------------------------- (2) BOUNDS(INF, INF)