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