/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 4046 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f15(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: A >= B + 1 f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f15(A, B, C + 1, Y, 0, 1, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: B >= A f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: TRUE f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, 1, D, E, F, 0, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: TRUE f36(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f45(A, B, C, D, E, F, G, H, Y, Z, A1, B1, B1, N, O, P, Q, R, S, T, U, V, W, X)) :|: H >= C f45(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, M, O, P, Q, R, S, T, U, V, W, X)) :|: 0 >= M + 1 f45(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f46(A, B, C, D, E, F, G, H, I, J, K, L, M, M, O, P, Q, R, S, T, U, V, W, X)) :|: M >= 1 f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: A >= B + 1 f45(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, C + 1, D, E, F, G, H, I, J, K, L, 0, 0, O, P, Q, R, S, T, U, V, W, X)) :|: M >= 0 && M <= 0 f61(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f61(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: TRUE f63(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f65(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: TRUE f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, C + 1, Y, 0, F, G, H, I, J, K, L, M, N, Z, P, Q, R, S, T, U, V, W, X)) :|: B >= A f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f45(A, B, C, D, E, F, G, H, I, Y, Z, A1, A1, N, O, B1, Q, R, S, T, U, V, W, X)) :|: B >= A f36(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f61(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, 0, R, S, T, U, V, W, X)) :|: C >= 1 + H f15(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, Y, Z, A1, A1, A1, X)) :|: 0 >= A1 + 1 && R >= C + 1 f15(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f25(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, Y, Z, A1, A1, A1, X)) :|: A1 >= 1 && R >= C + 1 f15(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f15(A, B, C + 1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, Y, Z, 0, 0, 0, X)) :|: R >= C + 1 f15(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f31(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X)) :|: C >= R f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f15(A, B, 0, D, E, F, 0, Z, I, J, K, L, M, N, O, P, 0, Y, S, T, U, V, W, 1)) :|: TRUE f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, 1, D, E, F, 0, A1, I, J, K, L, M, N, O, P, 0, Z, S, T, U, V, W, Y)) :|: 0 >= Y f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X) -> Com_1(f36(A, B, 1, D, E, F, 0, A1, I, J, K, L, M, N, O, P, 0, Z, S, T, U, V, W, Y)) :|: Y >= 2 The start-symbols are:[f0_24] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f25 -> f15 : C'=1+C, [ A>=1+B ], cost: 1 1: f25 -> f15 : C'=1+C, D'=free, E'=0, F'=1, [ B>=A ], cost: 1 2: f31 -> f31 : [], cost: 1 3: f33 -> f36 : C'=1, G'=0, [], cost: 1 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 13: f36 -> f61 : Q_1'=0, [ C>=1+H ], cost: 1 5: f45 -> f46 : N'=M, [ 0>=1+M ], cost: 1 6: f45 -> f46 : N'=M, [ M>=1 ], cost: 1 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 7: f46 -> f36 : C'=1+C, [ A>=1+B ], cost: 1 11: f46 -> f36 : C'=1+C, D'=free_5, E'=0, O'=free_6, [ B>=A ], cost: 1 12: f46 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, P'=free_7, [ B>=A ], cost: 1 9: f61 -> f61 : [], cost: 1 10: f63 -> f65 : 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, V'=X, [], cost: 1 14: f15 -> f25 : S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C ], cost: 1 15: f15 -> f25 : S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C ], cost: 1 16: f15 -> f15 : C'=1+C, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ R>=1+C ], cost: 1 17: f15 -> f31 : [ C>=R ], cost: 1 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f25 -> f15 : C'=1+C, [ A>=1+B ], cost: 1 1: f25 -> f15 : C'=1+C, D'=free, E'=0, F'=1, [ B>=A ], cost: 1 2: f31 -> f31 : [], cost: 1 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 13: f36 -> f61 : Q_1'=0, [ C>=1+H ], cost: 1 5: f45 -> f46 : N'=M, [ 0>=1+M ], cost: 1 6: f45 -> f46 : N'=M, [ M>=1 ], cost: 1 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 7: f46 -> f36 : C'=1+C, [ A>=1+B ], cost: 1 11: f46 -> f36 : C'=1+C, D'=free_5, E'=0, O'=free_6, [ B>=A ], cost: 1 12: f46 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, P'=free_7, [ B>=A ], cost: 1 9: f61 -> f61 : [], cost: 1 14: f15 -> f25 : S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C ], cost: 1 15: f15 -> f25 : S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C ], cost: 1 16: f15 -> f15 : C'=1+C, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ R>=1+C ], cost: 1 17: f15 -> f31 : [ C>=R ], cost: 1 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 2: f31 -> f31 : [], cost: 1 Accelerated rule 2 with NONTERM, yielding the new rule 21. Removing the simple loops: 2. Accelerating simple loops of location 6. Accelerating the following rules: 9: f61 -> f61 : [], cost: 1 Accelerated rule 9 with NONTERM, yielding the new rule 22. Removing the simple loops: 9. Accelerating simple loops of location 8. Accelerating the following rules: 16: f15 -> f15 : C'=1+C, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ R>=1+C ], cost: 1 Accelerated rule 16 with metering function R-C, yielding the new rule 23. Removing the simple loops: 16. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f25 -> f15 : C'=1+C, [ A>=1+B ], cost: 1 1: f25 -> f15 : C'=1+C, D'=free, E'=0, F'=1, [ B>=A ], cost: 1 21: f31 -> [11] : [], cost: NONTERM 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 13: f36 -> f61 : Q_1'=0, [ C>=1+H ], cost: 1 5: f45 -> f46 : N'=M, [ 0>=1+M ], cost: 1 6: f45 -> f46 : N'=M, [ M>=1 ], cost: 1 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 7: f46 -> f36 : C'=1+C, [ A>=1+B ], cost: 1 11: f46 -> f36 : C'=1+C, D'=free_5, E'=0, O'=free_6, [ B>=A ], cost: 1 12: f46 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, P'=free_7, [ B>=A ], cost: 1 22: f61 -> [12] : [], cost: NONTERM 14: f15 -> f25 : S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C ], cost: 1 15: f15 -> f25 : S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C ], cost: 1 17: f15 -> f31 : [ C>=R ], cost: 1 23: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ R>=1+C ], cost: R-C 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 0: f25 -> f15 : C'=1+C, [ A>=1+B ], cost: 1 1: f25 -> f15 : C'=1+C, D'=free, E'=0, F'=1, [ B>=A ], cost: 1 26: f25 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ A>=1+B && R>=2+C ], cost: R-C 27: f25 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ B>=A && R>=2+C ], cost: R-C 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 13: f36 -> f61 : Q_1'=0, [ C>=1+H ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 5: f45 -> f46 : N'=M, [ 0>=1+M ], cost: 1 6: f45 -> f46 : N'=M, [ M>=1 ], cost: 1 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 7: f46 -> f36 : C'=1+C, [ A>=1+B ], cost: 1 11: f46 -> f36 : C'=1+C, D'=free_5, E'=0, O'=free_6, [ B>=A ], cost: 1 12: f46 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, P'=free_7, [ B>=A ], cost: 1 14: f15 -> f25 : S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C ], cost: 1 15: f15 -> f25 : S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C ], cost: 1 17: f15 -> f31 : [ C>=R ], cost: 1 24: f15 -> [11] : [ C>=R ], cost: NONTERM 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 Removed unreachable locations (and leaf rules with constant cost): Start location: f0 0: f25 -> f15 : C'=1+C, [ A>=1+B ], cost: 1 1: f25 -> f15 : C'=1+C, D'=free, E'=0, F'=1, [ B>=A ], cost: 1 26: f25 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ A>=1+B && R>=2+C ], cost: R-C 27: f25 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ B>=A && R>=2+C ], cost: R-C 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 5: f45 -> f46 : N'=M, [ 0>=1+M ], cost: 1 6: f45 -> f46 : N'=M, [ M>=1 ], cost: 1 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 7: f46 -> f36 : C'=1+C, [ A>=1+B ], cost: 1 11: f46 -> f36 : C'=1+C, D'=free_5, E'=0, O'=free_6, [ B>=A ], cost: 1 12: f46 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, P'=free_7, [ B>=A ], cost: 1 14: f15 -> f25 : S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C ], cost: 1 15: f15 -> f25 : S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C ], cost: 1 24: f15 -> [11] : [ C>=R ], cost: NONTERM 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 Eliminated locations (on tree-shaped paths): Start location: f0 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 29: f45 -> f36 : C'=1+C, N'=M, [ 0>=1+M && A>=1+B ], cost: 2 30: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ 0>=1+M && B>=A ], cost: 2 31: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ 0>=1+M && B>=A ], cost: 2 32: f45 -> f36 : C'=1+C, N'=M, [ M>=1 && A>=1+B ], cost: 2 33: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ M>=1 && B>=A ], cost: 2 34: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ M>=1 && B>=A ], cost: 2 24: f15 -> [11] : [ C>=R ], cost: NONTERM 35: f15 -> f15 : C'=1+C, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C && A>=1+B ], cost: 2 36: f15 -> f15 : C'=1+C, D'=free, E'=0, F'=1, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C && B>=A ], cost: 2 37: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ 0>=1+free_12 && A>=1+B && R>=2+C ], cost: 1+R-C 38: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ 0>=1+free_12 && B>=A && R>=2+C ], cost: 1+R-C 39: f15 -> f15 : C'=1+C, S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C && A>=1+B ], cost: 2 40: f15 -> f15 : C'=1+C, D'=free, E'=0, F'=1, S'=free_14, T'=free_16, U'=free_15, V'=free_15, W'=free_15, [ free_15>=1 && R>=1+C && B>=A ], cost: 2 41: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ free_15>=1 && A>=1+B && R>=2+C ], cost: 1+R-C 42: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ free_15>=1 && B>=A && R>=2+C ], cost: 1+R-C 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 Applied pruning (of leafs and parallel rules): Start location: f0 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 29: f45 -> f36 : C'=1+C, N'=M, [ 0>=1+M && A>=1+B ], cost: 2 30: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ 0>=1+M && B>=A ], cost: 2 31: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ 0>=1+M && B>=A ], cost: 2 32: f45 -> f36 : C'=1+C, N'=M, [ M>=1 && A>=1+B ], cost: 2 33: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ M>=1 && B>=A ], cost: 2 34: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ M>=1 && B>=A ], cost: 2 24: f15 -> [11] : [ C>=R ], cost: NONTERM 36: f15 -> f15 : C'=1+C, D'=free, E'=0, F'=1, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C && B>=A ], cost: 2 37: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ 0>=1+free_12 && A>=1+B && R>=2+C ], cost: 1+R-C 38: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ 0>=1+free_12 && B>=A && R>=2+C ], cost: 1+R-C 41: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ free_15>=1 && A>=1+B && R>=2+C ], cost: 1+R-C 42: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ free_15>=1 && B>=A && R>=2+C ], cost: 1+R-C 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 Accelerating simple loops of location 4. Accelerating the following rules: 31: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ 0>=1+M && B>=A ], cost: 2 34: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ M>=1 && B>=A ], cost: 2 Accelerated rule 31 with NONTERM (after strengthening guard), yielding the new rule 43. Accelerated rule 34 with NONTERM (after strengthening guard), yielding the new rule 44. Removing the simple loops:. Accelerating simple loops of location 8. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 36: f15 -> f15 : C'=1+C, D'=free, E'=0, F'=1, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C && B>=A ], cost: 2 41: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ A>=1+B && R>=2+C ], cost: 1+R-C 42: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ B>=A && R>=2+C ], cost: 1+R-C Accelerated rule 36 with metering function R-C, yielding the new rule 45. Found no metering function for rule 41. Found no metering function for rule 42. Removing the simple loops: 36. Accelerated all simple loops using metering functions (where possible): Start location: f0 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 29: f45 -> f36 : C'=1+C, N'=M, [ 0>=1+M && A>=1+B ], cost: 2 30: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ 0>=1+M && B>=A ], cost: 2 31: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ 0>=1+M && B>=A ], cost: 2 32: f45 -> f36 : C'=1+C, N'=M, [ M>=1 && A>=1+B ], cost: 2 33: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ M>=1 && B>=A ], cost: 2 34: f45 -> f45 : J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=M, P'=free_7, [ M>=1 && B>=A ], cost: 2 43: f45 -> [14] : [ 0>=1+M && B>=A && 0>=1+free_9 ], cost: NONTERM 44: f45 -> [14] : [ M>=1 && B>=A && free_9>=1 ], cost: NONTERM 24: f15 -> [11] : [ C>=R ], cost: NONTERM 41: f15 -> f15 : C'=R, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ A>=1+B && R>=2+C ], cost: 1+R-C 42: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, [ B>=A && R>=2+C ], cost: 1+R-C 45: f15 -> f15 : C'=R, D'=free, E'=0, F'=1, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, [ 0>=1+free_12 && R>=1+C && B>=A ], cost: 2*R-2*C 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 Chained accelerated rules (with incoming rules): Start location: f0 4: f36 -> f45 : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C ], cost: 1 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 46: f36 -> f45 : Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_1, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A ], cost: 3 47: f36 -> f45 : Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_1, P'=free_7, [ H>=C && free_1>=1 && B>=A ], cost: 3 48: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && 0>=1+free_1 && B>=A ], cost: NONTERM 49: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && free_1>=1 && B>=A ], cost: NONTERM 8: f45 -> f36 : C'=1+C, M'=0, N'=0, [ M==0 ], cost: 1 29: f45 -> f36 : C'=1+C, N'=M, [ 0>=1+M && A>=1+B ], cost: 2 30: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ 0>=1+M && B>=A ], cost: 2 32: f45 -> f36 : C'=1+C, N'=M, [ M>=1 && A>=1+B ], cost: 2 33: f45 -> f36 : C'=1+C, D'=free_5, E'=0, N'=M, O'=free_6, [ M>=1 && B>=A ], cost: 2 24: f15 -> [11] : [ C>=R ], cost: NONTERM 18: f0 -> f15 : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [], cost: 1 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 28: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: 1+free_20 50: f0 -> f15 : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: 2+free_20 51: f0 -> f15 : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: 2+free_20 52: f0 -> f15 : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: 1+2*free_20 Eliminated locations (on tree-shaped paths): Start location: f0 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 48: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && 0>=1+free_1 && B>=A ], cost: NONTERM 49: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && free_1>=1 && B>=A ], cost: NONTERM 58: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=0, N'=0, [ H>=C && free_1==0 ], cost: 2 59: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && 0>=1+free_1 && A>=1+B ], cost: 3 60: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, O'=free_6, [ H>=C && 0>=1+free_1 && B>=A ], cost: 3 61: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && free_1>=1 && A>=1+B ], cost: 3 62: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, O'=free_6, [ H>=C && free_1>=1 && B>=A ], cost: 3 63: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=0, N'=0, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A && free_9==0 ], cost: 4 64: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A && 0>=1+free_9 ], cost: 5 65: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A && free_9>=1 ], cost: 5 66: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=0, N'=0, P'=free_7, [ H>=C && free_1>=1 && B>=A && free_9==0 ], cost: 4 67: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && free_1>=1 && B>=A && 0>=1+free_9 ], cost: 5 68: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && free_1>=1 && B>=A && free_9>=1 ], cost: 5 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM Applied pruning (of leafs and parallel rules): Start location: f0 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 48: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && 0>=1+free_1 && B>=A ], cost: NONTERM 49: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && free_1>=1 && B>=A ], cost: NONTERM 58: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=0, N'=0, [ H>=C && free_1==0 ], cost: 2 59: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && 0>=1+free_1 && A>=1+B ], cost: 3 61: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && free_1>=1 && A>=1+B ], cost: 3 63: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=0, N'=0, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A && free_9==0 ], cost: 4 64: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && 0>=1+free_1 && B>=A && 0>=1+free_9 ], cost: 5 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM Accelerating simple loops of location 3. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 58: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, [ H>=C ], cost: 2 59: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && 0>=1+free_1 && A>=1+B ], cost: 3 61: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && free_1>=1 && A>=1+B ], cost: 3 63: f36 -> f36 : C'=1+C, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, [ H>=C && B>=A ], cost: 4 64: f36 -> f36 : C'=1+C, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && B>=A && 0>=1+free_9 ], cost: 5 Accelerated rule 58 with metering function 1+H-C, yielding the new rule 69. Accelerated rule 59 with metering function 1+H-C, yielding the new rule 70. Accelerated rule 61 with metering function 1+H-C, yielding the new rule 71. Accelerated rule 63 with metering function 1+H-C, yielding the new rule 72. Accelerated rule 64 with metering function 1+H-C, yielding the new rule 73. Removing the simple loops: 58 59 61 63 64. Accelerated all simple loops using metering functions (where possible): Start location: f0 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 48: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && 0>=1+free_1 && B>=A ], cost: NONTERM 49: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && free_1>=1 && B>=A ], cost: NONTERM 69: f36 -> f36 : C'=1+H, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, [ H>=C ], cost: 2+2*H-2*C 70: f36 -> f36 : C'=1+H, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && 0>=1+free_1 && A>=1+B ], cost: 3+3*H-3*C 71: f36 -> f36 : C'=1+H, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, [ H>=C && free_1>=1 && A>=1+B ], cost: 3+3*H-3*C 72: f36 -> f36 : C'=1+H, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, [ H>=C && B>=A ], cost: 4+4*H-4*C 73: f36 -> f36 : C'=1+H, D'=free_5, E'=0, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, [ H>=C && B>=A && 0>=1+free_9 ], cost: 5+5*H-5*C 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 25: f36 -> [12] : Q_1'=0, [ C>=1+H ], cost: NONTERM 48: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && 0>=1+free_1 && B>=A ], cost: NONTERM 49: f36 -> [14] : Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, [ H>=C && free_1>=1 && B>=A ], cost: NONTERM 19: f0 -> f36 : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 ], cost: 1 20: f0 -> f36 : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 ], cost: 1 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM 74: f0 -> f36 : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 ], cost: 1+2*free_21 75: f0 -> f36 : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 ], cost: 1+2*free_24 76: f0 -> f36 : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_21 77: f0 -> f36 : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_24 78: f0 -> f36 : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_21 79: f0 -> f36 : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_24 80: f0 -> f36 : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && B>=A ], cost: 1+4*free_21 81: f0 -> f36 : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && B>=A ], cost: 1+4*free_24 82: f0 -> f36 : C'=1+free_21, D'=free_5, E'=0, G'=0, H'=free_21, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_21 83: f0 -> f36 : C'=1+free_24, D'=free_5, E'=0, G'=0, H'=free_24, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_24 Eliminated locations (on tree-shaped paths): Start location: f0 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM 84: f0 -> [12] : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && 1>=1+free_21 ], cost: NONTERM 85: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 86: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && B>=A ], cost: NONTERM 87: f0 -> [12] : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && 1>=1+free_24 ], cost: NONTERM 88: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 89: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && free_1>=1 && B>=A ], cost: NONTERM 90: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 ], cost: NONTERM 91: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 ], cost: NONTERM 92: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && A>=1+B ], cost: NONTERM 93: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: NONTERM 94: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: NONTERM 95: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && free_1>=1 && A>=1+B ], cost: NONTERM 96: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && B>=A ], cost: NONTERM 97: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_8, K'=free_10, L'=0, M'=0, N'=0, P'=free_7, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && B>=A ], cost: NONTERM 98: f0 -> [12] : C'=1+free_21, D'=free_5, E'=0, G'=0, H'=free_21, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && B>=A && 0>=1+free_9 ], cost: NONTERM 99: f0 -> [12] : C'=1+free_24, D'=free_5, E'=0, G'=0, H'=free_24, Q'=free_2, J'=free_8, K'=free_10, L'=free_9, M'=free_9, N'=free_9, O'=free_6, P'=free_7, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && B>=A && 0>=1+free_9 ], cost: NONTERM 100: f0 -> [17] : [ 0>=free_22 && free_21>=1 ], cost: 1+2*free_21 101: f0 -> [17] : [ free_25>=2 && free_24>=1 ], cost: 1+2*free_24 102: f0 -> [17] : [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_21 103: f0 -> [17] : [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_24 104: f0 -> [17] : [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_21 105: f0 -> [17] : [ free_25>=2 && free_24>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_24 106: f0 -> [17] : [ 0>=free_22 && free_21>=1 && B>=A ], cost: 1+4*free_21 107: f0 -> [17] : [ free_25>=2 && free_24>=1 && B>=A ], cost: 1+4*free_24 108: f0 -> [17] : [ 0>=free_22 && free_21>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_21 109: f0 -> [17] : [ free_25>=2 && free_24>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_24 Applied pruning (of leafs and parallel rules): Start location: f0 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM 84: f0 -> [12] : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && 1>=1+free_21 ], cost: NONTERM 85: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 86: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && B>=A ], cost: NONTERM 87: f0 -> [12] : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && 1>=1+free_24 ], cost: NONTERM 88: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 89: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && free_1>=1 && B>=A ], cost: NONTERM 91: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 ], cost: NONTERM 93: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: NONTERM 94: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: NONTERM 102: f0 -> [17] : [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_21 103: f0 -> [17] : [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_24 104: f0 -> [17] : [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_21 105: f0 -> [17] : [ free_25>=2 && free_24>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_24 108: f0 -> [17] : [ 0>=free_22 && free_21>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_21 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 53: f0 -> [11] : C'=0, G'=0, H'=free_19, Q_1'=0, R'=free_20, X'=1, [ 0>=free_20 ], cost: NONTERM 54: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ free_20>=1 ], cost: NONTERM 55: f0 -> [11] : C'=free_20, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ A>=1+B && free_20>=2 ], cost: NONTERM 56: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_17, T'=free_18, U'=0, V'=0, W'=0, X'=1, [ B>=A && free_20>=2 ], cost: NONTERM 57: f0 -> [11] : C'=free_20, D'=free, E'=0, F'=1, G'=0, H'=free_19, Q_1'=0, R'=free_20, S'=free_11, T'=free_13, U'=free_12, V'=free_12, W'=free_12, X'=1, [ 0>=1+free_12 && free_20>=1 && B>=A ], cost: NONTERM 84: f0 -> [12] : C'=1, G'=0, H'=free_21, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && 1>=1+free_21 ], cost: NONTERM 85: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 86: f0 -> [14] : C'=1, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && B>=A ], cost: NONTERM 87: f0 -> [12] : C'=1, G'=0, H'=free_24, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && 1>=1+free_24 ], cost: NONTERM 88: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && B>=A ], cost: NONTERM 89: f0 -> [14] : C'=1, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && free_1>=1 && B>=A ], cost: NONTERM 91: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=0, M'=0, N'=0, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 ], cost: NONTERM 93: f0 -> [12] : C'=1+free_24, G'=0, H'=free_24, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_26, X'=free_25, [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: NONTERM 94: f0 -> [12] : C'=1+free_21, G'=0, H'=free_21, Q'=free_2, J'=free_4, K'=free_3, L'=free_1, M'=free_1, N'=free_1, Q_1'=0, R'=free_23, X'=free_22, [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: NONTERM 102: f0 -> [17] : [ 0>=free_22 && free_21>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_21 103: f0 -> [17] : [ free_25>=2 && free_24>=1 && 0>=1+free_1 && A>=1+B ], cost: 1+3*free_24 104: f0 -> [17] : [ 0>=free_22 && free_21>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_21 105: f0 -> [17] : [ free_25>=2 && free_24>=1 && free_1>=1 && A>=1+B ], cost: 1+3*free_24 108: f0 -> [17] : [ 0>=free_22 && free_21>=1 && B>=A && 0>=1+free_9 ], cost: 1+5*free_21 Computing asymptotic complexity for rule 53 Guard is satisfiable, yielding nontermination Resulting cost NONTERM has complexity: Nonterm Found new complexity Nonterm. Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Nonterm Cpx degree: Nonterm Solved cost: NONTERM Rule cost: NONTERM Rule guard: [ 0>=free_20 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)