14.58/5.21 WORST_CASE(NON_POLY, ?) 14.58/5.22 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 14.58/5.22 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.58/5.22 14.58/5.22 14.58/5.22 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 14.58/5.22 14.58/5.22 (0) CpxIntTrs 14.58/5.22 (1) Loat Proof [FINISHED, 3517 ms] 14.58/5.22 (2) BOUNDS(INF, INF) 14.58/5.22 14.58/5.22 14.58/5.22 ---------------------------------------- 14.58/5.22 14.58/5.22 (0) 14.58/5.22 Obligation: 14.58/5.22 Complexity Int TRS consisting of the following rules: 14.58/5.22 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f13(1, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 && A <= 1 14.58/5.22 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= A 14.58/5.22 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 2 14.58/5.22 f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f23(A, B, B + 1, S, T, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= B 14.58/5.22 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f23(A, B, C, S, T, F + 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= F 14.58/5.22 f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, F + 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= F 14.58/5.22 f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, F + 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: B >= F 14.58/5.22 f60(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f60(A, B, C, D, E, F + 1, G, H, I, J, K - 1, S, T, U, V, K, Q, R)) :|: J >= F 14.58/5.22 f60(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + J 14.58/5.22 f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f60(A, B, C, D, E, 1, G, H, I, S, B, L, M, N, O, P, T, U)) :|: F >= 1 + B 14.58/5.22 f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f13(A, B, A, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + B && A >= C && A <= C 14.58/5.22 f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: A >= C + 1 && F >= 1 + B 14.58/5.22 f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: C >= 1 + A && F >= 1 + B 14.58/5.22 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= E + 1 && F >= 1 + B 14.58/5.22 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: E >= 1 && F >= 1 + B 14.58/5.22 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, 0, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + B && E >= 0 && E <= 0 14.58/5.22 f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f13(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= 1 + A 14.58/5.22 14.58/5.22 The start-symbols are:[f0_18] 14.58/5.22 14.58/5.22 14.58/5.22 ---------------------------------------- 14.58/5.22 14.58/5.22 (1) Loat Proof (FINISHED) 14.58/5.22 14.58/5.22 14.58/5.22 ### Pre-processing the ITS problem ### 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Initial linear ITS problem 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 0: f0 -> f13 : A'=1, [ A==1 ], cost: 1 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1 14.58/5.22 14.58/5.22 16: f17 -> f13 : [ B>=1+A ], cost: 1 14.58/5.22 14.58/5.22 4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1 14.58/5.22 14.58/5.22 5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 10: f33 -> f13 : C'=A, [ F>=1+B && A==C ], cost: 1 14.58/5.22 14.58/5.22 11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Removed unreachable and leaf rules: 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1 14.58/5.22 14.58/5.22 4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1 14.58/5.22 14.58/5.22 5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 ### Simplification by acceleration and chaining ### 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerating simple loops of location 2. 14.58/5.22 14.58/5.22 Accelerating the following rules: 14.58/5.22 14.58/5.22 4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated rule 4 with metering function 1-F+B, yielding the new rule 17. 14.58/5.22 14.58/5.22 Removing the simple loops: 4. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerating simple loops of location 3. 14.58/5.22 14.58/5.22 Accelerating the following rules: 14.58/5.22 14.58/5.22 5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated rule 5 with metering function 1-F+B, yielding the new rule 18. 14.58/5.22 14.58/5.22 Removing the simple loops: 5. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerating simple loops of location 4. 14.58/5.22 14.58/5.22 Accelerating the following rules: 14.58/5.22 14.58/5.22 6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated rule 6 with metering function 1-F+B, yielding the new rule 19. 14.58/5.22 14.58/5.22 Removing the simple loops: 6. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerating simple loops of location 5. 14.58/5.22 14.58/5.22 Accelerating the following rules: 14.58/5.22 14.58/5.22 7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated rule 7 with metering function 1-F+J, yielding the new rule 20. 14.58/5.22 14.58/5.22 Removing the simple loops: 7. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated all simple loops using metering functions (where possible): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1 14.58/5.22 14.58/5.22 13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1 14.58/5.22 14.58/5.22 17: f23 -> f23 : D'=free_2, E'=free_3, F'=1+B, [ B>=F ], cost: 1-F+B 14.58/5.22 14.58/5.22 11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 18: f33 -> f33 : F'=1+B, [ B>=F ], cost: 1-F+B 14.58/5.22 14.58/5.22 9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 19: f46 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1-F+B 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 20: f60 -> f60 : F'=1+J, K'=-1+F-J+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=F-J+K, [ J>=F ], cost: 1-F+J 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Chained accelerated rules (with incoming rules): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1 14.58/5.22 14.58/5.22 21: f17 -> f23 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1 14.58/5.22 14.58/5.22 22: f23 -> f33 : F'=1+B, [ 0>=1+E && F>=1+B && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 23: f23 -> f33 : F'=1+B, [ E>=1 && F>=1+B && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 24: f23 -> f33 : E'=0, F'=1+B, [ F>=1+B && E==0 && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 25: f33 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ A>=1+C && F>=1+B && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 26: f33 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ C>=1+A && F>=1+B && B>=1 ], cost: 1+B 14.58/5.22 14.58/5.22 9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1 14.58/5.22 14.58/5.22 27: f46 -> f60 : F'=1+free_11, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ F>=1+B && free_11>=1 ], cost: 1+free_11 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Eliminated locations (on tree-shaped paths): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 28: f17 -> f33 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B && 0>=1+free_1 && 1>=1+B ], cost: 2 14.58/5.22 14.58/5.22 29: f17 -> f33 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B && free_1>=1 && 1>=1+B ], cost: 2 14.58/5.22 14.58/5.22 30: f17 -> f33 : C'=1+B, D'=free, E'=0, F'=1, [ A>=B && 1>=1+B && free_1==0 ], cost: 2 14.58/5.22 14.58/5.22 31: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 32: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 33: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1, [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 34: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 35: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 36: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1+B, [ A>=B && B>=1 && free_3==0 ], cost: 2+2*B 14.58/5.22 14.58/5.22 37: f33 -> f60 : F'=1, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B ], cost: 2 14.58/5.22 14.58/5.22 38: f33 -> f60 : F'=1+free_11, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11 14.58/5.22 14.58/5.22 39: f33 -> f60 : F'=1, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B ], cost: 2 14.58/5.22 14.58/5.22 40: f33 -> f60 : F'=1+free_11, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11 14.58/5.22 14.58/5.22 41: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 42: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B 14.58/5.22 14.58/5.22 43: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 44: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Applied pruning (of leafs and parallel rules): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 31: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 32: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 33: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1, [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 34: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 35: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 38: f33 -> f60 : F'=1+free_11, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11 14.58/5.22 14.58/5.22 40: f33 -> f60 : F'=1+free_11, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11 14.58/5.22 14.58/5.22 42: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B 14.58/5.22 14.58/5.22 43: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 44: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Eliminated locations (on tree-shaped paths): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 45: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 46: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A ], cost: 4+3*B 14.58/5.22 14.58/5.22 47: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 48: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 49: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A ], cost: 4+3*B 14.58/5.22 14.58/5.22 50: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Applied pruning (of leafs and parallel rules): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 45: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 47: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 48: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 49: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A ], cost: 4+3*B 14.58/5.22 14.58/5.22 50: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B 14.58/5.22 14.58/5.22 51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Eliminated locations (on tree-shaped paths): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 56: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 57: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 58: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 59: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && 1>=1+free_11 ], cost: 5+3*B 14.58/5.22 14.58/5.22 60: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerating simple loops of location 1. 14.58/5.22 14.58/5.22 Simplified some of the simple loops (and removed duplicate rules). 14.58/5.22 14.58/5.22 Accelerating the following rules: 14.58/5.22 14.58/5.22 56: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 57: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && 0>=1+free_3 && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 58: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 59: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && 1>=1+free_11 ], cost: 5+3*B 14.58/5.22 14.58/5.22 60: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && free_11>=1 ], cost: 5+free_11+3*B 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated rule 56 with metering function -1+A-B, yielding the new rule 61. 14.58/5.22 14.58/5.22 Accelerated rule 57 with metering function 1+A-B, yielding the new rule 62. 14.58/5.22 14.58/5.22 Accelerated rule 58 with metering function -1+A-B, yielding the new rule 63. 14.58/5.22 14.58/5.22 Accelerated rule 59 with metering function 1+A-B, yielding the new rule 64. 14.58/5.22 14.58/5.22 Accelerated rule 60 with metering function 1+A-B, yielding the new rule 65. 14.58/5.22 14.58/5.22 Removing the simple loops: 56 57 58 59 60. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Accelerated all simple loops using metering functions (where possible): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 61: f17 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: -7/2+free_11*(-1+A-B)+7/2*A+3*(-1+A-B)*B+3/2*(-1+A-B)^2-7/2*B 14.58/5.22 14.58/5.22 62: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && 0>=1+free_3 && free_11>=1 ], cost: 7/2+free_11*(1+A-B)+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B 14.58/5.22 14.58/5.22 63: f17 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: -7/2+free_11*(-1+A-B)+7/2*A+3*(-1+A-B)*B+3/2*(-1+A-B)^2-7/2*B 14.58/5.22 14.58/5.22 64: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && 1>=1+free_11 ], cost: 7/2+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B 14.58/5.22 14.58/5.22 65: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && free_11>=1 ], cost: 7/2+free_11*(1+A-B)+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Chained accelerated rules (with incoming rules): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1 14.58/5.22 14.58/5.22 2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1 14.58/5.22 14.58/5.22 66: f0 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 67: f0 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B 14.58/5.22 14.58/5.22 52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B 14.58/5.22 14.58/5.22 53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B 14.58/5.22 14.58/5.22 54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B 14.58/5.22 14.58/5.22 55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Eliminated locations (on tree-shaped paths): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 68: f0 -> [11] : B'=1, [ A>=2 && 0>=1+free_3 ], cost: 4 14.58/5.22 14.58/5.22 69: f0 -> [11] : B'=1, [ A>=2 && free_3>=1 ], cost: 4 14.58/5.22 14.58/5.22 70: f0 -> [11] : B'=1, [ A>=2 && free_3==0 ], cost: 4 14.58/5.22 14.58/5.22 71: f0 -> [11] : B'=1, [ A>=2 && 0>=1+free_3 ], cost: 5 14.58/5.22 14.58/5.22 72: f0 -> [11] : B'=1, [ A>=2 && free_3>=1 ], cost: 5 14.58/5.22 14.58/5.22 73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Applied pruning (of leafs and parallel rules): 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 ### Computing asymptotic complexity ### 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Fully simplified ITS problem 14.58/5.22 14.58/5.22 Start location: f0 14.58/5.22 14.58/5.22 73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A 14.58/5.22 14.58/5.22 77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Computing asymptotic complexity for rule 73 14.58/5.22 14.58/5.22 Solved the limit problem by the following transformations: 14.58/5.22 14.58/5.22 Created initial limit problem: 14.58/5.22 14.58/5.22 -5-2*free_11+free_11*A+3/2*A+3/2*A^2 (+), free_11 (+/+!), -free_3 (+/+!), -2+A (+/+!) [not solved] 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 removing all constraints (solved by SMT) 14.58/5.22 14.58/5.22 resulting limit problem: [solved] 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 applying transformation rule (C) using substitution {free_11==1+n,free_3==-1,A==3} 14.58/5.22 14.58/5.22 resulting limit problem: 14.58/5.22 14.58/5.22 [solved] 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Solution: 14.58/5.22 14.58/5.22 free_11 / 1+n 14.58/5.22 14.58/5.22 free_3 / -1 14.58/5.22 14.58/5.22 A / 3 14.58/5.22 14.58/5.22 Resulting cost 14+n has complexity: Unbounded 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Found new complexity Unbounded. 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 Obtained the following overall complexity (w.r.t. the length of the input n): 14.58/5.22 14.58/5.22 Complexity: Unbounded 14.58/5.22 14.58/5.22 Cpx degree: Unbounded 14.58/5.22 14.58/5.22 Solved cost: 14+n 14.58/5.22 14.58/5.22 Rule cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A 14.58/5.22 14.58/5.22 Rule guard: [ 0>=1+free_3 && A>=3 && free_11>=1 ] 14.58/5.22 14.58/5.22 14.58/5.22 14.58/5.22 WORST_CASE(INF,?) 14.58/5.22 14.58/5.22 14.58/5.22 ---------------------------------------- 14.58/5.22 14.58/5.22 (2) 14.58/5.22 BOUNDS(INF, INF) 14.65/5.25 EOF