6.56/2.86 WORST_CASE(NON_POLY, ?) 6.56/2.87 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.56/2.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.56/2.87 6.56/2.87 6.56/2.87 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 6.56/2.87 6.56/2.87 (0) CpxIntTrs 6.56/2.87 (1) Loat Proof [FINISHED, 1230 ms] 6.56/2.87 (2) BOUNDS(INF, INF) 6.56/2.87 6.56/2.87 6.56/2.87 ---------------------------------------- 6.56/2.87 6.56/2.87 (0) 6.56/2.87 Obligation: 6.56/2.87 Complexity Int TRS consisting of the following rules: 6.56/2.87 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, 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, B1, C1, D1, E1)) :|: A >= B + 1 6.56/2.87 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, 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, B1, C1, D1, E1)) :|: B >= A + 1 6.56/2.87 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, E, H1, 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 6.56/2.87 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, E, H1, 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 6.56/2.87 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, E, L1, 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)) :|: E >= I1 + 1 6.56/2.87 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, E, L1, 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 >= E + 1 6.56/2.87 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(f11(A, J1, J1, J1, F, F, 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)) :|: A >= J1 + 1 && G >= 0 && H >= 1 && F >= E && F <= E 6.56/2.87 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(f11(A, J1, J1, J1, F, F, 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 >= A + 1 && G >= 0 && H >= 1 && F >= E && F <= E 6.56/2.87 6.56/2.87 The start-symbols are:[f26_31] 6.56/2.87 6.56/2.87 6.56/2.87 ---------------------------------------- 6.56/2.87 6.56/2.87 (1) Loat Proof (FINISHED) 6.56/2.87 6.56/2.87 6.56/2.87 ### Pre-processing the ITS problem ### 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Initial linear ITS problem 6.56/2.87 6.56/2.87 Start location: f26 6.56/2.87 6.56/2.87 0: f11 -> f11 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.56/2.87 6.56/2.87 1: f11 -> f11 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.56/2.87 6.56/2.87 2: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 3: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 6: f6 -> f11 : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 7: f6 -> f11 : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 4: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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, [ E>=1+free_16 ], cost: 1 6.56/2.87 6.56/2.87 5: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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, [ free_27>=1+E ], cost: 1 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Simplified all rules, resulting in: 6.56/2.87 6.56/2.87 Start location: f26 6.56/2.87 6.56/2.87 0: f11 -> f11 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.56/2.87 6.56/2.87 1: f11 -> f11 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.56/2.87 6.56/2.87 2: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 3: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 6: f6 -> f11 : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 7: f6 -> f11 : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 4: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 5: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 ### Simplification by acceleration and chaining ### 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Accelerating simple loops of location 0. 6.56/2.87 6.56/2.87 Accelerating the following rules: 6.56/2.87 6.56/2.87 0: f11 -> f11 : C'=B, D'=B, [ A>=1+B ], cost: 1 6.56/2.87 6.56/2.87 1: f11 -> f11 : C'=B, D'=B, [ B>=1+A ], cost: 1 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Accelerated rule 0 with NONTERM, yielding the new rule 8. 6.56/2.87 6.56/2.87 Accelerated rule 1 with NONTERM, yielding the new rule 9. 6.56/2.87 6.56/2.87 Removing the simple loops: 0 1. 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Accelerating simple loops of location 1. 6.56/2.87 6.56/2.87 Accelerating the following rules: 6.56/2.87 6.56/2.87 2: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 3: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Accelerated rule 2 with metering function H (after strengthening guard), yielding the new rule 10. 6.56/2.87 6.56/2.87 Accelerated rule 3 with metering function H (after strengthening guard), yielding the new rule 11. 6.56/2.87 6.56/2.87 Removing the simple loops:. 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Accelerated all simple loops using metering functions (where possible): 6.56/2.87 6.56/2.87 Start location: f26 6.56/2.87 6.56/2.87 8: f11 -> [3] : [ A>=1+B ], cost: INF 6.56/2.87 6.56/2.87 9: f11 -> [3] : [ B>=1+A ], cost: INF 6.56/2.87 6.56/2.87 2: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 3: f6 -> f6 : F'=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 6.56/2.87 6.56/2.87 6: f6 -> f11 : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 7: f6 -> f11 : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 10: f6 -> f6 : F'=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 && E>=1+free ], cost: H 6.56/2.87 6.56/2.87 11: f6 -> f6 : F'=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 && free_3>=1+E ], cost: H 6.56/2.87 6.56/2.87 4: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 5: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Chained accelerated rules (with incoming rules): 6.56/2.87 6.56/2.87 Start location: f26 6.56/2.87 6.56/2.87 6: f6 -> f11 : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 7: f6 -> f11 : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: 1 6.56/2.87 6.56/2.87 12: f6 -> [3] : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: INF 6.56/2.87 6.56/2.87 13: f6 -> [3] : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: INF 6.56/2.87 6.56/2.87 4: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 5: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 14: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 15: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 16: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 17: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 18: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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, [ E>=1+free ], cost: 5 6.56/2.87 6.56/2.87 19: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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, [ E>=1+free ], cost: 5 6.56/2.87 6.56/2.87 20: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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, [ free_3>=1+E ], cost: 5 6.56/2.87 6.56/2.87 21: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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, [ free_3>=1+E ], cost: 5 6.56/2.87 6.56/2.87 6.56/2.87 6.56/2.87 Removed unreachable locations (and leaf rules with constant cost): 6.56/2.87 6.56/2.87 Start location: f26 6.56/2.87 6.56/2.87 12: f6 -> [3] : B'=free_28, C'=free_28, D'=free_28, E'=F, E1'=free_30, N'=free_31, Z'=free_29, [ A>=1+free_28 && G>=0 && H>=1 && F==E ], cost: INF 6.56/2.87 6.56/2.87 13: f6 -> [3] : B'=free_32, C'=free_32, D'=free_32, E'=F, E1'=free_34, N'=free_35, Z'=free_33, [ free_32>=1+A && G>=0 && H>=1 && F==E ], cost: INF 6.56/2.87 6.56/2.87 4: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 5: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 14: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 15: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 16: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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 6.56/2.87 6.56/2.87 17: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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 6.56/2.87 6.56/2.87 18: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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, [ E>=1+free ], cost: 5 6.56/2.88 6.56/2.88 19: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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, [ E>=1+free ], cost: 5 6.56/2.88 6.56/2.88 20: f26 -> f6 : A1'=free_6, B1'=free_15, C1'=free_11, D1'=4, F'=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, [ free_3>=1+E ], cost: 5 6.56/2.88 6.56/2.88 21: f26 -> f6 : A1'=free_17, B1'=free_26, C1'=free_22, D1'=4, F'=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, [ free_3>=1+E ], cost: 5 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Eliminated locations (on tree-shaped paths): 6.56/2.88 6.56/2.88 Start location: f26 6.56/2.88 6.56/2.88 22: f26 -> [3] : A1'=free_6, B'=free_28, 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, [ A>=1+free_28 && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 23: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 24: f26 -> [3] : A1'=free_17, B'=free_28, 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, [ A>=1+free_28 && free_18==E ], cost: INF 6.56/2.88 6.56/2.88 25: f26 -> [3] : A1'=free_17, B'=free_32, 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, [ free_32>=1+A && free_18==E ], cost: INF 6.56/2.88 6.56/2.88 26: f26 -> [3] : A1'=free_6, B'=free_28, 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, [ A>=1+free_28 && free==E ], cost: INF 6.56/2.88 6.56/2.88 27: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free==E ], cost: INF 6.56/2.88 6.56/2.88 28: f26 -> [3] : A1'=free_17, B'=free_28, 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, [ A>=1+free_28 && free==E ], cost: INF 6.56/2.88 6.56/2.88 29: f26 -> [3] : A1'=free_17, B'=free_32, 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, [ free_32>=1+A && free==E ], cost: INF 6.56/2.88 6.56/2.88 30: f26 -> [3] : A1'=free_6, B'=free_28, 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, [ A>=1+free_28 && free_3==E ], cost: INF 6.56/2.88 6.56/2.88 31: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free_3==E ], cost: INF 6.56/2.88 6.56/2.88 32: f26 -> [3] : A1'=free_17, B'=free_28, 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, [ A>=1+free_28 && free_3==E ], cost: INF 6.56/2.88 6.56/2.88 33: f26 -> [3] : A1'=free_17, B'=free_32, 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, [ free_32>=1+A && free_3==E ], cost: INF 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Applied pruning (of leafs and parallel rules): 6.56/2.88 6.56/2.88 Start location: f26 6.56/2.88 6.56/2.88 22: f26 -> [3] : A1'=free_6, B'=free_28, 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, [ A>=1+free_28 && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 23: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 25: f26 -> [3] : A1'=free_17, B'=free_32, 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, [ free_32>=1+A && free_18==E ], cost: INF 6.56/2.88 6.56/2.88 27: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free==E ], cost: INF 6.56/2.88 6.56/2.88 28: f26 -> [3] : A1'=free_17, B'=free_28, 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, [ A>=1+free_28 && free==E ], cost: INF 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 ### Computing asymptotic complexity ### 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Fully simplified ITS problem 6.56/2.88 6.56/2.88 Start location: f26 6.56/2.88 6.56/2.88 22: f26 -> [3] : A1'=free_6, B'=free_28, 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, [ A>=1+free_28 && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 23: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free_7==E ], cost: INF 6.56/2.88 6.56/2.88 25: f26 -> [3] : A1'=free_17, B'=free_32, 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, [ free_32>=1+A && free_18==E ], cost: INF 6.56/2.88 6.56/2.88 27: f26 -> [3] : A1'=free_6, B'=free_32, 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, [ free_32>=1+A && free==E ], cost: INF 6.56/2.88 6.56/2.88 28: f26 -> [3] : A1'=free_17, B'=free_28, 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, [ A>=1+free_28 && free==E ], cost: INF 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Computing asymptotic complexity for rule 22 6.56/2.88 6.56/2.88 Resulting cost INF has complexity: Nonterm 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Found new complexity Nonterm. 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 Obtained the following overall complexity (w.r.t. the length of the input n): 6.56/2.88 6.56/2.88 Complexity: Nonterm 6.56/2.88 6.56/2.88 Cpx degree: Nonterm 6.56/2.88 6.56/2.88 Solved cost: INF 6.56/2.88 6.56/2.88 Rule cost: INF 6.56/2.88 6.56/2.88 Rule guard: [ A>=1+free_28 && free_7==E ] 6.56/2.88 6.56/2.88 6.56/2.88 6.56/2.88 NO 6.56/2.88 6.56/2.88 6.56/2.88 ---------------------------------------- 6.56/2.88 6.56/2.88 (2) 6.56/2.88 BOUNDS(INF, INF) 6.78/2.91 EOF