/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 280.8 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_1, E'=1, F'=1, G'=free, 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_4>=1+free_3 ], 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_6>=1+free_5 ], 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_8>=1+free_7 ], 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 Removed unreachable and leaf rules: Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, 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_4>=1+free_3 ], 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_6>=1+free_5 ], 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_8>=1+free_7 ], 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_1, E'=1, F'=1, G'=free, 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 -Q+D, 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 -Q+D, 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 Accelerated rule 36 with backward acceleration, yielding the new rule 68. Accelerated rule 36 with backward acceleration, yielding the new rule 69. Accelerated rule 40 with backward acceleration, yielding the new rule 70. Nested simple loops 40 (outer loop) and 68 (inner loop) with NONTERM, resulting in the new rules: 71. Nested simple loops 40 (outer loop) and 69 (inner loop) with NONTERM, resulting in the new rules: 72. Removing the simple loops: 36 40. Accelerated all simple loops using metering functions (where possible): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, 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: -Q+D 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: -Q+D 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 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 68: f113 -> f113 : U'=1+S+C*R-C*T, [ S+C*R>=C*T+U && C>=1+U && C>=1+S+C*R-C*T ], cost: 1+S+C*R-C*T-U 69: f113 -> f113 : U'=C, [ S+C*R>=C*T+U && C>=1+U && S+C*R>=-1+C+C*T ], cost: C-U 70: f113 -> f113 : F'=0, U'=C, V'=0, [ C*T+U>=1+S+C*R && C>=1+U && F==0 && -1+C+C*T>=1+S+C*R ], cost: C-U 71: f113 -> [29] : [ C*T+U>=1+S+C*R && F==0 && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: INF 72: f113 -> [29] : [ C*T+U>=1+S+C*R && F==0 && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: INF 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_1, E'=1, F'=1, G'=free, H'=0, [], cost: 1 5: f26 -> f29 : Q'=0, [ D>=1+H ], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 73: 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 74: 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 75: f44 -> f41 : E'=0, Q'=D, K'=0, [ D>=2+Q ], cost: -Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 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 77: 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 78: 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 79: 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 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 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 81: f117 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 1+S+C*R-C*T-U 82: f117 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 1+S+C*R-C*T-U 84: f117 -> f113 : F'=1, U'=C, V'=1, [ S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: C-U 85: f117 -> f113 : F'=0, U'=C, V'=0, [ S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: C-U 87: f117 -> f113 : F'=0, U'=C, V'=0, [ 1+C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: C-U Eliminated locations (on tree-shaped paths): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 90: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 91: 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 74: 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 92: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 93: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 94: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1-Q+D 95: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 96: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ E>=1 && D>=1+Q ], cost: 2 97: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1-Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 98: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 99: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 100: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 101: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 102: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && A>=1 ], cost: 2 103: 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 78: 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 104: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 105: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 106: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 107: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 108: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && B>=1 ], cost: 2 109: 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 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 110: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 111: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 112: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 113: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 114: f113 -> f113 : F'=1, U'=C, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 115: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 116: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U 117: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 118: f113 -> f113 : F'=0, U'=1+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 119: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 120: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 121: f113 -> f113 : F'=1, U'=C, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 122: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 123: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U Applied pruning (of leafs and parallel rules): Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 90: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 91: 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 74: 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 92: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 93: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 94: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1-Q+D 95: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 97: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1-Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 98: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 99: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 100: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 101: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 103: 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 78: 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 104: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 105: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 106: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 107: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 109: 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 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 110: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 111: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 112: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 113: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 114: f113 -> f113 : F'=1, U'=C, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 115: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 116: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U 117: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 118: f113 -> f113 : F'=0, U'=1+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 119: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 120: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 121: f113 -> f113 : F'=1, U'=C, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 122: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 123: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U Aborted due to lack of remaining time ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 90: f26 -> f26 : H'=1+H, Q'=0, [ D>=1+H && 0>=D ], cost: 2 91: 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 74: 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 92: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ 0>=1+E && D>=1+Q ], cost: 2 93: f41 -> f41 : E'=0, Q'=1+Q, K'=0, [ 0>=1+E && D>=1+Q ], cost: 2 94: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1-Q+D 95: f41 -> f41 : E'=1, Q'=1+Q, K'=1, [ E>=1 && D>=1+Q ], cost: 2 97: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1-Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 57: f62 -> f59 : L'=1+L, [ M>=D ], cost: 1 98: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && 0>=1+A ], cost: 2 99: f62 -> f62 : A'=0, M'=1+M, N'=0, [ D>=1+M && 0>=1+A ], cost: 2 100: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 101: f62 -> f62 : A'=1, M'=1+M, N'=1, [ D>=1+M && A>=1 ], cost: 2 103: 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 78: 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 104: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && 0>=1+B ], cost: 2 105: f83 -> f83 : B'=0, P'=1+P, Q_1'=0, [ D>=1+P && 0>=1+B ], cost: 2 106: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 107: f83 -> f83 : B'=1, P'=1+P, Q_1'=1, [ D>=1+P && B>=1 ], cost: 2 109: 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 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 46: f113 -> f110 : T'=1+T, [ U>=C ], cost: 1 110: f113 -> f113 : F'=1, U'=1+U, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 111: f113 -> f113 : F'=0, U'=1+U, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 112: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 113: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 114: f113 -> f113 : F'=1, U'=C, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 115: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 116: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U 117: f113 -> f113 : F'=1, U'=1+U, V'=1, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 118: f113 -> f113 : F'=0, U'=1+U, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=1+U ], cost: 2 119: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 120: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 121: f113 -> f113 : F'=1, U'=C, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 122: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 123: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U This is only a partial result (probably due to a timeout). Trying to find the maximal complexity that has already been derived. Removed rules with constant/unknown complexity: Start location: f0 4: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=0, [], cost: 1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 91: 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 74: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 94: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1-Q+D 97: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1-Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 100: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 103: 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 78: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 106: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 109: 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 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 112: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 113: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 114: f113 -> f113 : F'=1, U'=C, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 115: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 116: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U 119: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 120: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 121: f113 -> f113 : F'=1, U'=C, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 122: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 123: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U Performed chaining from the start location: Start location: f0 124: f0 -> f38 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=0, [ 0>=free_1 ], cost: 2 125: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=1, Q'=free_1, J'=free_2, [ free_1>=1 && free_1>=1 ], cost: 3+free_1 63: f26 -> f38 : H'=0, [ H>=D ], cost: 1 91: 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 74: f38 -> f41 : E'=0, Q'=D, K'=0, [ D>=1+H && D>=1 && E==0 ], cost: 1+D 94: f41 -> f41 : E'=0, Q'=D, K'=0, [ 0>=1+E && D>=2+Q ], cost: 1-Q+D 97: f41 -> f41 : E'=0, Q'=D, K'=0, [ E>=1 && D>=2+Q ], cost: 1-Q+D 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 76: f59 -> f62 : A'=0, M'=D, N'=0, [ D>=2+L && A==0 ], cost: -L+D 100: f62 -> f62 : A'=0, M'=D, N'=0, [ 0>=1+A && D>=2+M ], cost: 1-M+D 103: 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 78: f80 -> f83 : B'=0, P'=D, Q_1'=0, [ D>=2+O && B==0 ], cost: D-O 106: f83 -> f83 : B'=0, P'=D, Q_1'=0, [ 0>=1+B && D>=2+P ], cost: 1-P+D 109: 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 31: f104 -> f107 : S'=0, [ C>=1+R ], cost: 1 32: f107 -> f110 : T'=0, [ C>=1+S ], cost: 1 33: f110 -> f113 : U'=0, [ C>=1+T ], cost: 1 80: f110 -> f113 : U'=1+S+C*R-C*T, [ C>=1+T && S+C*R>=C*T && C>=1 && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T 83: f110 -> f113 : U'=C, [ C>=1+T && S+C*R>=C*T && C>=1 && S+C*R>=-1+C+C*T ], cost: 1+C 86: f110 -> f113 : F'=0, U'=C, V'=0, [ C>=1+T && C*T>=1+S+C*R && C>=1 && F==0 && -1+C+C*T>=1+S+C*R ], cost: 1+C 88: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && C>=1+S+C*R-C*T ], cost: INF 89: f110 -> [29] : U'=0, [ C>=1+T && C*T>=1+S+C*R && F==0 && S+C*R>=1+C*T && C>=2 && S+C*R>=-1+C+C*T ], cost: INF 112: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 113: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 114: f113 -> f113 : F'=1, U'=C, V'=1, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 115: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 116: f113 -> f113 : F'=0, U'=C, V'=0, [ 0>=1+F && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U 119: f113 -> f113 : F'=1, U'=1+S+C*R-C*T, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 120: f113 -> f113 : F'=0, U'=1+S+C*R-C*T, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && C>=1+S+C*R-C*T ], cost: 2+S+C*R-C*T-U 121: f113 -> f113 : F'=1, U'=C, V'=1, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 122: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && S+C*R>=1+C*T+U && C>=2+U && S+C*R>=-1+C+C*T ], cost: 1+C-U 123: f113 -> f113 : F'=0, U'=C, V'=0, [ F>=1 && C*T+U>=1+S+C*R && C>=2+U && -1+C+C*T>=1+S+C*R ], cost: 1+C-U Computing asymptotic complexity for rule 125 Simplified the guard: 125: f0 -> f26 : A'=1, B'=1, C'=3, D'=free_1, E'=1, F'=1, G'=free, H'=1, Q'=free_1, J'=free_2, [ free_1>=1 ], cost: 3+free_1 Solved the limit problem by the following transformations: Created initial limit problem: 3+free_1 (+), free_1 (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free_1==n} resulting limit problem: [solved] Solution: free_1 / n Resulting cost 3+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: 3+n Rule cost: 3+free_1 Rule guard: [ free_1>=1 ] WORST_CASE(INF,?) ---------------------------------------- (2) BOUNDS(INF, INF)