6.84/3.12 WORST_CASE(NON_POLY, ?) 7.08/3.13 proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat 7.08/3.13 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.08/3.13 7.08/3.13 7.08/3.13 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 7.08/3.13 7.08/3.13 (0) CpxIntTrs 7.08/3.13 (1) Loat Proof [FINISHED, 1410 ms] 7.08/3.13 (2) BOUNDS(INF, INF) 7.08/3.13 7.08/3.13 7.08/3.13 ---------------------------------------- 7.08/3.13 7.08/3.13 (0) 7.08/3.13 Obligation: 7.08/3.13 Complexity Int TRS consisting of the following rules: 7.08/3.13 f13(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(f47(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: A >= B 7.08/3.13 f39(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(f47(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: C >= 3 7.08/3.13 f39(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(f47(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 1 >= C 7.08/3.13 f54(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(f54(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE 7.08/3.13 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, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE 7.08/3.13 f47(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(f54(A, B, C, D, 0, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: D >= 1 7.08/3.13 f47(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(f54(A, B, C, D, 0, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= D 7.08/3.13 f39(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(f47(A, B, 2, D, E + 1, F, H, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: C >= 2 && C <= 2 7.08/3.13 f13(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(f47(A, B, C, D, E, F, G, X, Y, Z, A1, E, X, X, X, P, Q, R, S, T, U, V, W)) :|: X >= 1 && B >= A + 1 7.08/3.13 f13(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(f39(A, B, B1, D, E, F, G, X, Y, Z, A1, E, X, X, X, X, R, 0, B1, B1, B1, 0, W)) :|: B >= A + 1 && 0 >= X && B1 >= 2 7.08/3.13 f13(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(f39(A, B, B1, D, E, F, G, X, Y, Z, A1, E, X, X, X, X, R, 0, B1, B1, B1, 0, W)) :|: B >= A + 1 && 0 >= X && 0 >= B1 7.08/3.13 f13(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(f13(A + 1, B, 1, D, E, F, G, X, Y, Z, A1, E, X, X, X, X, R, R, 1, 1, 1, 0, W)) :|: 0 >= X && B >= A + 1 7.08/3.13 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(f13(A, B, C, Y, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 0)) :|: 0 >= Y 7.08/3.13 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(f13(A, B, C, Y, E, 0, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, 0)) :|: Y >= 1 7.08/3.13 7.08/3.13 The start-symbols are:[f0_23] 7.08/3.13 7.08/3.13 7.08/3.13 ---------------------------------------- 7.08/3.13 7.08/3.13 (1) Loat Proof (FINISHED) 7.08/3.13 7.08/3.13 7.08/3.13 ### Pre-processing the ITS problem ### 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Initial linear ITS problem 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 0: f13 -> f47 : [ A>=B ], cost: 1 7.08/3.13 7.08/3.13 8: f13 -> f47 : H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, [ free_1>=1 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 9: f13 -> f39 : C'=free_5, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, [ B>=1+A && 0>=free_7 && free_5>=2 ], cost: 1 7.08/3.13 7.08/3.13 10: f13 -> f39 : C'=free_10, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, [ B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 1 7.08/3.13 7.08/3.13 11: f13 -> f13 : A'=1+A, C'=1, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, [ 0>=free_15 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 3: f54 -> f54 : [], cost: 1 7.08/3.13 7.08/3.13 4: f56 -> f59 : A1'=B, B'=C, B1'=D, C'=E, D'=F, E'=G, F'=H, G'=Q, H'=J, Q'=K, J'=L, K'=M, L'=N, M'=O, N'=P, O'=Q_1, P'=R, Q_1'=S, R'=T, S'=U, T'=V, U'=W, [], cost: 1 7.08/3.13 7.08/3.13 5: f47 -> f54 : E'=0, [ D>=1 ], cost: 1 7.08/3.13 7.08/3.13 6: f47 -> f54 : E'=0, F'=0, [ 0>=D ], cost: 1 7.08/3.13 7.08/3.13 12: f0 -> f13 : D'=free_18, F'=0, W'=0, [ 0>=free_18 ], cost: 1 7.08/3.13 7.08/3.13 13: f0 -> f13 : D'=free_19, F'=0, W'=0, [ free_19>=1 ], cost: 1 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Removed unreachable and leaf rules: 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 0: f13 -> f47 : [ A>=B ], cost: 1 7.08/3.13 7.08/3.13 8: f13 -> f47 : H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, [ free_1>=1 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 9: f13 -> f39 : C'=free_5, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, [ B>=1+A && 0>=free_7 && free_5>=2 ], cost: 1 7.08/3.13 7.08/3.13 10: f13 -> f39 : C'=free_10, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, [ B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 1 7.08/3.13 7.08/3.13 11: f13 -> f13 : A'=1+A, C'=1, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, [ 0>=free_15 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 3: f54 -> f54 : [], cost: 1 7.08/3.13 7.08/3.13 5: f47 -> f54 : E'=0, [ D>=1 ], cost: 1 7.08/3.13 7.08/3.13 6: f47 -> f54 : E'=0, F'=0, [ 0>=D ], cost: 1 7.08/3.13 7.08/3.13 12: f0 -> f13 : D'=free_18, F'=0, W'=0, [ 0>=free_18 ], cost: 1 7.08/3.13 7.08/3.13 13: f0 -> f13 : D'=free_19, F'=0, W'=0, [ free_19>=1 ], cost: 1 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 ### Simplification by acceleration and chaining ### 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Accelerating simple loops of location 0. 7.08/3.13 7.08/3.13 Accelerating the following rules: 7.08/3.13 7.08/3.13 11: f13 -> f13 : A'=1+A, C'=1, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, [ 0>=free_15 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Accelerated rule 11 with metering function B-A, yielding the new rule 14. 7.08/3.13 7.08/3.13 Removing the simple loops: 11. 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Accelerating simple loops of location 2. 7.08/3.13 7.08/3.13 Accelerating the following rules: 7.08/3.13 7.08/3.13 3: f54 -> f54 : [], cost: 1 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Accelerated rule 3 with NONTERM, yielding the new rule 15. 7.08/3.13 7.08/3.13 Removing the simple loops: 3. 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Accelerated all simple loops using metering functions (where possible): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 0: f13 -> f47 : [ A>=B ], cost: 1 7.08/3.13 7.08/3.13 8: f13 -> f47 : H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, [ free_1>=1 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 9: f13 -> f39 : C'=free_5, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, [ B>=1+A && 0>=free_7 && free_5>=2 ], cost: 1 7.08/3.13 7.08/3.13 10: f13 -> f39 : C'=free_10, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, [ B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 1 7.08/3.13 7.08/3.13 14: f13 -> f13 : A'=B, C'=1, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, [ 0>=free_15 && B>=1+A ], cost: B-A 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 15: f54 -> [8] : [], cost: INF 7.08/3.13 7.08/3.13 5: f47 -> f54 : E'=0, [ D>=1 ], cost: 1 7.08/3.13 7.08/3.13 6: f47 -> f54 : E'=0, F'=0, [ 0>=D ], cost: 1 7.08/3.13 7.08/3.13 12: f0 -> f13 : D'=free_18, F'=0, W'=0, [ 0>=free_18 ], cost: 1 7.08/3.13 7.08/3.13 13: f0 -> f13 : D'=free_19, F'=0, W'=0, [ free_19>=1 ], cost: 1 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Chained accelerated rules (with incoming rules): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 0: f13 -> f47 : [ A>=B ], cost: 1 7.08/3.13 7.08/3.13 8: f13 -> f47 : H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, [ free_1>=1 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 9: f13 -> f39 : C'=free_5, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, [ B>=1+A && 0>=free_7 && free_5>=2 ], cost: 1 7.08/3.13 7.08/3.13 10: f13 -> f39 : C'=free_10, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, [ B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 1 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 5: f47 -> f54 : E'=0, [ D>=1 ], cost: 1 7.08/3.13 7.08/3.13 6: f47 -> f54 : E'=0, F'=0, [ 0>=D ], cost: 1 7.08/3.13 7.08/3.13 18: f47 -> [8] : E'=0, [ D>=1 ], cost: INF 7.08/3.13 7.08/3.13 19: f47 -> [8] : E'=0, F'=0, [ 0>=D ], cost: INF 7.08/3.13 7.08/3.13 12: f0 -> f13 : D'=free_18, F'=0, W'=0, [ 0>=free_18 ], cost: 1 7.08/3.13 7.08/3.13 13: f0 -> f13 : D'=free_19, F'=0, W'=0, [ free_19>=1 ], cost: 1 7.08/3.13 7.08/3.13 16: f0 -> f13 : A'=B, C'=1, D'=free_18, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 17: f0 -> f13 : A'=B, C'=1, D'=free_19, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Removed unreachable locations (and leaf rules with constant cost): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 0: f13 -> f47 : [ A>=B ], cost: 1 7.08/3.13 7.08/3.13 8: f13 -> f47 : H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, [ free_1>=1 && B>=1+A ], cost: 1 7.08/3.13 7.08/3.13 9: f13 -> f39 : C'=free_5, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, [ B>=1+A && 0>=free_7 && free_5>=2 ], cost: 1 7.08/3.13 7.08/3.13 10: f13 -> f39 : C'=free_10, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, [ B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 1 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 18: f47 -> [8] : E'=0, [ D>=1 ], cost: INF 7.08/3.13 7.08/3.13 19: f47 -> [8] : E'=0, F'=0, [ 0>=D ], cost: INF 7.08/3.13 7.08/3.13 12: f0 -> f13 : D'=free_18, F'=0, W'=0, [ 0>=free_18 ], cost: 1 7.08/3.13 7.08/3.13 13: f0 -> f13 : D'=free_19, F'=0, W'=0, [ free_19>=1 ], cost: 1 7.08/3.13 7.08/3.13 16: f0 -> f13 : A'=B, C'=1, D'=free_18, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 17: f0 -> f13 : A'=B, C'=1, D'=free_19, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Eliminated locations (on tree-shaped paths): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 18: f47 -> [8] : E'=0, [ D>=1 ], cost: INF 7.08/3.13 7.08/3.13 19: f47 -> [8] : E'=0, F'=0, [ 0>=D ], cost: INF 7.08/3.13 7.08/3.13 20: f0 -> f47 : D'=free_18, F'=0, W'=0, [ 0>=free_18 && A>=B ], cost: 2 7.08/3.13 7.08/3.13 21: f0 -> f47 : D'=free_18, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ 0>=free_18 && free_1>=1 && B>=1+A ], cost: 2 7.08/3.13 7.08/3.13 22: f0 -> f39 : C'=free_5, D'=free_18, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5>=2 ], cost: 2 7.08/3.13 7.08/3.13 23: f0 -> f39 : C'=free_10, D'=free_18, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 2 7.08/3.13 7.08/3.13 24: f0 -> f47 : D'=free_19, F'=0, W'=0, [ free_19>=1 && A>=B ], cost: 2 7.08/3.13 7.08/3.13 25: f0 -> f47 : D'=free_19, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ free_19>=1 && free_1>=1 && B>=1+A ], cost: 2 7.08/3.13 7.08/3.13 26: f0 -> f39 : C'=free_5, D'=free_19, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_7 && free_5>=2 ], cost: 2 7.08/3.13 7.08/3.13 27: f0 -> f39 : C'=free_10, D'=free_19, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 2 7.08/3.13 7.08/3.13 28: f0 -> f47 : A'=B, C'=1, D'=free_18, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 29: f0 -> f47 : A'=B, C'=1, D'=free_19, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 30: f0 -> [9] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 31: f0 -> [9] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Applied pruning (of leafs and parallel rules): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 1: f39 -> f47 : [ C>=3 ], cost: 1 7.08/3.13 7.08/3.13 2: f39 -> f47 : [ 1>=C ], cost: 1 7.08/3.13 7.08/3.13 7: f39 -> f47 : C'=2, E'=1+E, G'=H, [ C==2 ], cost: 1 7.08/3.13 7.08/3.13 18: f47 -> [8] : E'=0, [ D>=1 ], cost: INF 7.08/3.13 7.08/3.13 19: f47 -> [8] : E'=0, F'=0, [ 0>=D ], cost: INF 7.08/3.13 7.08/3.13 21: f0 -> f47 : D'=free_18, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ 0>=free_18 && free_1>=1 && B>=1+A ], cost: 2 7.08/3.13 7.08/3.13 22: f0 -> f39 : C'=free_5, D'=free_18, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5>=2 ], cost: 2 7.08/3.13 7.08/3.13 23: f0 -> f39 : C'=free_10, D'=free_18, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 2 7.08/3.13 7.08/3.13 24: f0 -> f47 : D'=free_19, F'=0, W'=0, [ free_19>=1 && A>=B ], cost: 2 7.08/3.13 7.08/3.13 25: f0 -> f47 : D'=free_19, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ free_19>=1 && free_1>=1 && B>=1+A ], cost: 2 7.08/3.13 7.08/3.13 26: f0 -> f39 : C'=free_5, D'=free_19, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_7 && free_5>=2 ], cost: 2 7.08/3.13 7.08/3.13 27: f0 -> f39 : C'=free_10, D'=free_19, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: 2 7.08/3.13 7.08/3.13 28: f0 -> f47 : A'=B, C'=1, D'=free_18, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 29: f0 -> f47 : A'=B, C'=1, D'=free_19, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 30: f0 -> [9] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 31: f0 -> [9] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Eliminated locations (on tree-shaped paths): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 30: f0 -> [9] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 31: f0 -> [9] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 38: f0 -> [8] : D'=free_18, E'=0, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ 0>=free_18 && free_1>=1 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 39: f0 -> [8] : D'=free_19, E'=0, F'=0, W'=0, [ free_19>=1 && A>=B ], cost: INF 7.08/3.13 7.08/3.13 40: f0 -> [8] : D'=free_19, E'=0, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ free_19>=1 && free_1>=1 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 41: f0 -> [8] : A'=B, C'=1, D'=free_18, E'=0, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 42: f0 -> [8] : A'=B, C'=1, D'=free_19, E'=0, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 43: f0 -> [8] : C'=free_5, D'=free_18, E'=0, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5>=3 ], cost: INF 7.08/3.13 7.08/3.13 44: f0 -> [8] : C'=2, D'=free_18, E'=0, F'=0, G'=free_7, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5==2 ], cost: INF 7.08/3.13 7.08/3.13 45: f0 -> [8] : C'=free_10, D'=free_18, E'=0, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: INF 7.08/3.13 7.08/3.13 46: f0 -> [8] : C'=free_5, D'=free_19, E'=0, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_7 && free_5>=3 ], cost: INF 7.08/3.13 7.08/3.13 47: f0 -> [8] : C'=2, D'=free_19, E'=0, F'=0, G'=free_7, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_7 && free_5==2 ], cost: INF 7.08/3.13 7.08/3.13 48: f0 -> [8] : C'=free_10, D'=free_19, E'=0, F'=0, H'=free_12, Q'=free_9, J'=free_13, K'=free_11, L'=E, M'=free_12, N'=free_12, O'=free_12, P'=free_12, Q_1'=R, R'=0, S'=free_10, T'=free_10, U'=free_10, V'=0, W'=0, [ free_19>=1 && B>=1+A && 0>=free_12 && 0>=free_10 ], cost: INF 7.08/3.13 7.08/3.13 49: f0 -> [10] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 50: f0 -> [10] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Applied pruning (of leafs and parallel rules): 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 30: f0 -> [9] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 31: f0 -> [9] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 1+B-A 7.08/3.13 7.08/3.13 38: f0 -> [8] : D'=free_18, E'=0, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ 0>=free_18 && free_1>=1 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 39: f0 -> [8] : D'=free_19, E'=0, F'=0, W'=0, [ free_19>=1 && A>=B ], cost: INF 7.08/3.13 7.08/3.13 41: f0 -> [8] : A'=B, C'=1, D'=free_18, E'=0, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 43: f0 -> [8] : C'=free_5, D'=free_18, E'=0, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5>=3 ], cost: INF 7.08/3.13 7.08/3.13 44: f0 -> [8] : C'=2, D'=free_18, E'=0, F'=0, G'=free_7, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5==2 ], cost: INF 7.08/3.13 7.08/3.13 49: f0 -> [10] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 50: f0 -> [10] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 ### Computing asymptotic complexity ### 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Fully simplified ITS problem 7.08/3.13 7.08/3.13 Start location: f0 7.08/3.13 7.08/3.13 38: f0 -> [8] : D'=free_18, E'=0, F'=0, H'=free_1, Q'=free_2, J'=free, K'=free_3, L'=E, M'=free_1, N'=free_1, O'=free_1, W'=0, [ 0>=free_18 && free_1>=1 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 39: f0 -> [8] : D'=free_19, E'=0, F'=0, W'=0, [ free_19>=1 && A>=B ], cost: INF 7.08/3.13 7.08/3.13 41: f0 -> [8] : A'=B, C'=1, D'=free_18, E'=0, F'=0, H'=free_15, Q'=free_16, J'=free_14, K'=free_17, L'=E, M'=free_15, N'=free_15, O'=free_15, P'=free_15, Q_1'=R, S'=1, T'=1, U'=1, V'=0, W'=0, [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: INF 7.08/3.13 7.08/3.13 43: f0 -> [8] : C'=free_5, D'=free_18, E'=0, F'=0, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5>=3 ], cost: INF 7.08/3.13 7.08/3.13 44: f0 -> [8] : C'=2, D'=free_18, E'=0, F'=0, G'=free_7, H'=free_7, Q'=free_4, J'=free_8, K'=free_6, L'=E, M'=free_7, N'=free_7, O'=free_7, P'=free_7, Q_1'=R, R'=0, S'=free_5, T'=free_5, U'=free_5, V'=0, W'=0, [ 0>=free_18 && B>=1+A && 0>=free_7 && free_5==2 ], cost: INF 7.08/3.13 7.08/3.13 49: f0 -> [10] : [ 0>=free_18 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 50: f0 -> [10] : [ free_19>=1 && 0>=free_15 && B>=1+A ], cost: 2+B-A 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Computing asymptotic complexity for rule 38 7.08/3.13 7.08/3.13 Resulting cost INF has complexity: Nonterm 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Found new complexity Nonterm. 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 Obtained the following overall complexity (w.r.t. the length of the input n): 7.08/3.13 7.08/3.13 Complexity: Nonterm 7.08/3.13 7.08/3.13 Cpx degree: Nonterm 7.08/3.13 7.08/3.13 Solved cost: INF 7.08/3.13 7.08/3.13 Rule cost: INF 7.08/3.13 7.08/3.13 Rule guard: [ 0>=free_18 && free_1>=1 && B>=1+A ] 7.08/3.13 7.08/3.13 7.08/3.13 7.08/3.13 NO 7.08/3.13 7.08/3.13 7.08/3.13 ---------------------------------------- 7.08/3.13 7.08/3.13 (2) 7.08/3.13 BOUNDS(INF, INF) 7.08/3.15 EOF