6.55/2.99 WORST_CASE(NON_POLY, ?) 6.81/3.00 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.81/3.00 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.81/3.00 6.81/3.00 6.81/3.00 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 6.81/3.00 6.81/3.00 (0) CpxIntTrs 6.81/3.00 (1) Loat Proof [FINISHED, 1204 ms] 6.81/3.00 (2) BOUNDS(INF, INF) 6.81/3.00 6.81/3.00 6.81/3.00 ---------------------------------------- 6.81/3.00 6.81/3.00 (0) 6.81/3.00 Obligation: 6.81/3.00 Complexity Int TRS consisting of the following rules: 6.81/3.00 f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, B, B, B, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: A >= B + 1 6.81/3.00 f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, B, B, B, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: B >= A + 1 6.81/3.00 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f2(A, B, C, D, E, B1, -(1) + G, 1 + H, 1 + H, -(1) + G, C1, D1, -(1) + G, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: E >= F + 1 && G >= 1 && H >= 0 6.81/3.00 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f2(A, B, C, D, E, B1, -(1) + G, 1 + H, 1 + H, -(1) + G, C1, D1, -(1) + G, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1)) :|: F >= E + 1 && G >= 1 && H >= 0 6.81/3.00 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f2(A, B, C, D, E, B1, 2, 1, 1, 2, K, L, M, 2, C1, D1, F1, G1, G1, G1, G1, H1, I1, 2, J1, 0, A1)) :|: E >= E1 + 1 6.81/3.00 f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f2(A, B, C, D, E, B1, 2, 1, 1, 2, K, L, M, 2, C1, D1, F1, G1, G1, G1, G1, H1, I1, 2, J1, 0, A1)) :|: E1 >= E + 1 6.81/3.00 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, C1, C1, C1, F, F, G, H, I, J, K, L, M, N, O, P, B1, R, S, T, D1, V, W, X, Y, Z, F1)) :|: A >= C1 + 1 && G >= 1 && H >= 0 && F >= E && F <= E 6.81/3.00 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1) -> Com_1(f8(A, C1, C1, C1, F, F, G, H, I, J, K, L, M, N, O, P, B1, R, S, T, D1, V, W, X, Y, Z, F1)) :|: C1 >= A + 1 && G >= 1 && H >= 0 && F >= E && F <= E 6.81/3.00 6.81/3.00 The start-symbols are:[f23_27] 6.81/3.00 6.81/3.00 6.81/3.00 ---------------------------------------- 6.81/3.00 6.81/3.00 (1) Loat Proof (FINISHED) 6.81/3.00 6.81/3.00 6.81/3.00 ### Pre-processing the ITS problem ### 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Initial linear ITS problem 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 0: f8 -> f8 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.81/3.00 6.81/3.00 1: f8 -> f8 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.81/3.00 6.81/3.00 2: f2 -> f2 : F'=free_1, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free, L'=free_2, M'=-1+G, [ E>=1+F && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 3: f2 -> f2 : F'=free_4, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free_3, L'=free_5, M'=-1+G, [ F>=1+E && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 6: f2 -> f8 : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 7: f2 -> f8 : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 4: f23 -> f2 : F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ E>=1+free_9 ], cost: 1 6.81/3.00 6.81/3.00 5: f23 -> f2 : F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_18>=1+E ], cost: 1 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Simplified all rules, resulting in: 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 0: f8 -> f8 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.81/3.00 6.81/3.00 1: f8 -> f8 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.81/3.00 6.81/3.00 2: f2 -> f2 : F'=free_1, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free, L'=free_2, M'=-1+G, [ E>=1+F && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 3: f2 -> f2 : F'=free_4, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free_3, L'=free_5, M'=-1+G, [ F>=1+E && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 6: f2 -> f8 : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 7: f2 -> f8 : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 4: f23 -> f2 : F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 5: f23 -> f2 : F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 ### Simplification by acceleration and chaining ### 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Accelerating simple loops of location 0. 6.81/3.00 6.81/3.00 Accelerating the following rules: 6.81/3.00 6.81/3.00 0: f8 -> f8 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.81/3.00 6.81/3.00 1: f8 -> f8 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Accelerated rule 0 with NONTERM, yielding the new rule 8. 6.81/3.00 6.81/3.00 Accelerated rule 1 with NONTERM, yielding the new rule 9. 6.81/3.00 6.81/3.00 Removing the simple loops: 0 1. 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Accelerating simple loops of location 1. 6.81/3.00 6.81/3.00 Accelerating the following rules: 6.81/3.00 6.81/3.00 2: f2 -> f2 : F'=free_1, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free, L'=free_2, M'=-1+G, [ E>=1+F && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 3: f2 -> f2 : F'=free_4, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free_3, L'=free_5, M'=-1+G, [ F>=1+E && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Accelerated rule 2 with metering function G (after strengthening guard), yielding the new rule 10. 6.81/3.00 6.81/3.00 Accelerated rule 3 with metering function G (after strengthening guard), yielding the new rule 11. 6.81/3.00 6.81/3.00 Removing the simple loops:. 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Accelerated all simple loops using metering functions (where possible): 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 8: f8 -> [3] : [ A>=1+B ], cost: INF 6.81/3.00 6.81/3.00 9: f8 -> [3] : [ B>=1+A ], cost: INF 6.81/3.00 6.81/3.00 2: f2 -> f2 : F'=free_1, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free, L'=free_2, M'=-1+G, [ E>=1+F && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 3: f2 -> f2 : F'=free_4, G'=-1+G, H'=1+H, Q'=1+H, J'=-1+G, K'=free_3, L'=free_5, M'=-1+G, [ F>=1+E && G>=1 && H>=0 ], cost: 1 6.81/3.00 6.81/3.00 6: f2 -> f8 : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 7: f2 -> f8 : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 10: f2 -> f2 : F'=free_1, G'=0, H'=G+H, Q'=G+H, J'=0, K'=free, L'=free_2, M'=0, [ E>=1+F && G>=1 && H>=0 && E>=1+free_1 ], cost: G 6.81/3.00 6.81/3.00 11: f2 -> f2 : F'=free_4, G'=0, H'=G+H, Q'=G+H, J'=0, K'=free_3, L'=free_5, M'=0, [ F>=1+E && G>=1 && H>=0 && free_4>=1+E ], cost: G 6.81/3.00 6.81/3.00 4: f23 -> f2 : F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 5: f23 -> f2 : F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Chained accelerated rules (with incoming rules): 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 6: f2 -> f8 : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 7: f2 -> f8 : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: 1 6.81/3.00 6.81/3.00 12: f2 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: INF 6.81/3.00 6.81/3.00 13: f2 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: INF 6.81/3.00 6.81/3.00 4: f23 -> f2 : F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 5: f23 -> f2 : F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 14: f23 -> f2 : F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 15: f23 -> f2 : F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 16: f23 -> f2 : F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 17: f23 -> f2 : F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 18: f23 -> f2 : F'=free_1, G'=0, H'=3, Q'=3, J'=0, K'=free, L'=free_2, M'=0, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ E>=1+free_1 ], cost: 3 6.81/3.00 6.81/3.00 19: f23 -> f2 : F'=free_1, G'=0, H'=3, Q'=3, J'=0, K'=free, L'=free_2, M'=0, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ E>=1+free_1 ], cost: 3 6.81/3.00 6.81/3.00 20: f23 -> f2 : F'=free_4, G'=0, H'=3, Q'=3, J'=0, K'=free_3, L'=free_5, M'=0, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_4>=1+E ], cost: 3 6.81/3.00 6.81/3.00 21: f23 -> f2 : F'=free_4, G'=0, H'=3, Q'=3, J'=0, K'=free_3, L'=free_5, M'=0, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_4>=1+E ], cost: 3 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Removed unreachable locations (and leaf rules with constant cost): 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 12: f2 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=F, Q_1'=free_25, U'=free_27, [ A>=1+free_26 && G>=1 && H>=0 && F==E ], cost: INF 6.81/3.00 6.81/3.00 13: f2 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=F, Q_1'=free_29, U'=free_31, [ free_30>=1+A && G>=1 && H>=0 && F==E ], cost: INF 6.81/3.00 6.81/3.00 4: f23 -> f2 : F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 5: f23 -> f2 : F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 1 6.81/3.00 6.81/3.00 14: f23 -> f2 : F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 15: f23 -> f2 : F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 16: f23 -> f2 : F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 17: f23 -> f2 : F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [], cost: 2 6.81/3.00 6.81/3.00 18: f23 -> f2 : F'=free_1, G'=0, H'=3, Q'=3, J'=0, K'=free, L'=free_2, M'=0, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ E>=1+free_1 ], cost: 3 6.81/3.00 6.81/3.00 19: f23 -> f2 : F'=free_1, G'=0, H'=3, Q'=3, J'=0, K'=free, L'=free_2, M'=0, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ E>=1+free_1 ], cost: 3 6.81/3.00 6.81/3.00 20: f23 -> f2 : F'=free_4, G'=0, H'=3, Q'=3, J'=0, K'=free_3, L'=free_5, M'=0, N'=2, O'=free_7, P'=free_13, Q_1'=free_6, R'=free_12, S'=free_12, T'=free_12, U'=free_12, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_4>=1+E ], cost: 3 6.81/3.00 6.81/3.00 21: f23 -> f2 : F'=free_4, G'=0, H'=3, Q'=3, J'=0, K'=free_3, L'=free_5, M'=0, N'=2, O'=free_16, P'=free_22, Q_1'=free_15, R'=free_21, S'=free_21, T'=free_21, U'=free_21, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_4>=1+E ], cost: 3 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Eliminated locations (on tree-shaped paths): 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 22: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_25, R'=free_12, S'=free_12, T'=free_12, U'=free_27, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ A>=1+free_26 && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 23: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 24: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_20, F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_25, R'=free_21, S'=free_21, T'=free_21, U'=free_27, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ A>=1+free_26 && free_20==E ], cost: INF 6.81/3.00 6.81/3.00 25: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_20, F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_29, R'=free_21, S'=free_21, T'=free_21, U'=free_31, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_30>=1+A && free_20==E ], cost: INF 6.81/3.00 6.81/3.00 26: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_25, R'=free_12, S'=free_12, T'=free_12, U'=free_27, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ A>=1+free_26 && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 27: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 28: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_25, R'=free_21, S'=free_21, T'=free_21, U'=free_27, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ A>=1+free_26 && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 29: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_29, R'=free_21, S'=free_21, T'=free_21, U'=free_31, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_30>=1+A && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 30: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_4, F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_25, R'=free_12, S'=free_12, T'=free_12, U'=free_27, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ A>=1+free_26 && free_4==E ], cost: INF 6.81/3.00 6.81/3.00 31: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_4, F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_4==E ], cost: INF 6.81/3.00 6.81/3.00 32: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_4, F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_25, R'=free_21, S'=free_21, T'=free_21, U'=free_27, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ A>=1+free_26 && free_4==E ], cost: INF 6.81/3.00 6.81/3.00 33: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_4, F'=free_4, G'=1, H'=2, Q'=2, J'=1, K'=free_3, L'=free_5, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_29, R'=free_21, S'=free_21, T'=free_21, U'=free_31, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_30>=1+A && free_4==E ], cost: INF 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Applied pruning (of leafs and parallel rules): 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 22: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_25, R'=free_12, S'=free_12, T'=free_12, U'=free_27, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ A>=1+free_26 && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 23: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 25: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_20, F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_29, R'=free_21, S'=free_21, T'=free_21, U'=free_31, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_30>=1+A && free_20==E ], cost: INF 6.81/3.00 6.81/3.00 27: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 28: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_25, R'=free_21, S'=free_21, T'=free_21, U'=free_27, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ A>=1+free_26 && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 ### Computing asymptotic complexity ### 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Fully simplified ITS problem 6.81/3.00 6.81/3.00 Start location: f23 6.81/3.00 6.81/3.00 22: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_25, R'=free_12, S'=free_12, T'=free_12, U'=free_27, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ A>=1+free_26 && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 23: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_11, F'=free_11, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_11==E ], cost: INF 6.81/3.00 6.81/3.00 25: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_20, F'=free_20, G'=2, H'=1, Q'=1, J'=2, N'=2, O'=free_16, P'=free_22, Q_1'=free_29, R'=free_21, S'=free_21, T'=free_21, U'=free_31, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ free_30>=1+A && free_20==E ], cost: INF 6.81/3.00 6.81/3.00 27: f23 -> [3] : A1'=free_28, B'=free_30, C'=free_30, D'=free_30, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_7, P'=free_13, Q_1'=free_29, R'=free_12, S'=free_12, T'=free_12, U'=free_31, V'=free_8, W'=free_14, X'=2, Y'=free_10, Z'=0, [ free_30>=1+A && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 28: f23 -> [3] : A1'=free_24, B'=free_26, C'=free_26, D'=free_26, E'=free_1, F'=free_1, G'=1, H'=2, Q'=2, J'=1, K'=free, L'=free_2, M'=1, N'=2, O'=free_16, P'=free_22, Q_1'=free_25, R'=free_21, S'=free_21, T'=free_21, U'=free_27, V'=free_17, W'=free_23, X'=2, Y'=free_19, Z'=0, [ A>=1+free_26 && free_1==E ], cost: INF 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Computing asymptotic complexity for rule 22 6.81/3.00 6.81/3.00 Resulting cost INF has complexity: Nonterm 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Found new complexity Nonterm. 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 Obtained the following overall complexity (w.r.t. the length of the input n): 6.81/3.00 6.81/3.00 Complexity: Nonterm 6.81/3.00 6.81/3.00 Cpx degree: Nonterm 6.81/3.00 6.81/3.00 Solved cost: INF 6.81/3.00 6.81/3.00 Rule cost: INF 6.81/3.00 6.81/3.00 Rule guard: [ A>=1+free_26 && free_11==E ] 6.81/3.00 6.81/3.00 6.81/3.00 6.81/3.00 NO 6.81/3.00 6.81/3.00 6.81/3.00 ---------------------------------------- 6.81/3.00 6.81/3.00 (2) 6.81/3.00 BOUNDS(INF, INF) 6.81/3.03 EOF