/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) 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(n^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 697 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 5241 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f16(1, X, Y, Z, A1, B1, C1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: A >= 1 && A <= 1 f16(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f18(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: H >= I f18(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f18(A, B, C, D, E, F, G, H, I, J, K + 1, L + 2, M, N, O, P, Q, R, S, T, U, V, W)) :|: J >= K f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f28(A, X, Y, Z, A1, B1, C1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= A f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f28(A, X, Y, Z, A1, B1, C1, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: A >= 2 f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f35(A, B, C, D, E, F, G, H, I, J, K, L, H - I + 2, 1, 0, P, Q, R, S, T, U, V, W)) :|: 0 >= I && H >= I f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f35(A, B, C, D, E, F, G, H, I, J, K, L, H - I + 2, 1, 0, P, Q, R, S, T, U, V, W)) :|: I >= 2 && H >= I f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f35(A, B, C, D, E, F, G, H, 1, J, K, L, 1, 1, 0, P, Q, R, S, T, U, V, W)) :|: H >= 1 && I >= 1 && I <= 1 f35(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: P >= 2 * X && 3 * X >= P + 1 && X + 1 >= Q f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= Q && J >= K f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: Q >= 2 && J >= K f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, K + 1, X, M, N, O, P, 1, Y, Z, A1, B1, V, W)) :|: 0 >= K && J >= K && Q >= 1 && Q <= 1 f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, K + 1, X, M, N, O, P, 1, Y, Z, A1, B1, V, W)) :|: J >= K && K >= 2 && Q >= 1 && Q <= 1 f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, 2, 1, M, N, O, P, 1, X, Y, Z, A1, V, W)) :|: J >= 1 && K >= 1 && K <= 1 && Q >= 1 && Q <= 1 f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, K + 1, J - K + 2, M, N, O, P, Q, X, Y, Z, A1, B1, W)) :|: 0 >= K f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, K + 1, J - K + 2, M, N, O, P, Q, X, Y, Z, A1, B1, W)) :|: K >= 2 f52(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f37(A, B, C, D, E, F, G, H, I, J, 2, 1, M, N, O, P, Q, X, Y, Z, A1, B1, W)) :|: K >= 1 && K <= 1 f37(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f35(A, B, C, D, N, F, G, H, I, J, K, L, M, X, Y, P, Q + 1, R, S, T, U, V, W + 2)) :|: K >= 1 + J f35(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f28(A, B, C, D, E, F, G, H, I + 1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: P >= 2 * X && 3 * X >= P + 1 && Q >= 2 + X f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f76(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: 0 >= 2 + A && I >= 1 + H f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f76(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: A >= 0 && I >= 1 + H f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f76(-(1), B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= 1 + H && A + 1 >= 0 && A + 1 <= 0 f18(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f16(A, B, C, D, E, F, G, H, I + 1, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: K >= 1 + J f16(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f28(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: I >= 1 + H The start-symbols are:[f0_23] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 8*Ar_7 + 8*Ar_8 + 13*Ar_9 + 25*Ar_10 + 3*Ar_15 + 3*Ar_16 + 59) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) f0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f16(1, Fresh_43, Fresh_44, Fresh_45, Fresh_46, Fresh_47, Fresh_48, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_0 = 1 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f18(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f18(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_11 + 2, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f28(Ar_0, Fresh_37, Fresh_38, Fresh_39, Fresh_40, Fresh_41, Fresh_42, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f28(Ar_0, Fresh_31, Fresh_32, Fresh_33, Fresh_34, Fresh_35, Fresh_36, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_7 - Ar_8 + 2, 1, 0, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_7 - Ar_8 + 2, 1, 0, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, 1, Ar_9, Ar_10, Ar_11, 1, 1, 0, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f52(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f52(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Fresh_26, Ar_12, Ar_13, Ar_14, Ar_15, 1, Fresh_27, Fresh_28, Fresh_29, Fresh_30, Ar_21, Ar_22)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Fresh_21, Ar_12, Ar_13, Ar_14, Ar_15, 1, Fresh_22, Fresh_23, Fresh_24, Fresh_25, Ar_21, Ar_22)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, 2, 1, Ar_12, Ar_13, Ar_14, Ar_15, 1, Fresh_17, Fresh_18, Fresh_19, Fresh_20, Ar_21, Ar_22)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_9 - Ar_10 + 2, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Fresh_12, Fresh_13, Fresh_14, Fresh_15, Fresh_16, Ar_22)) [ 0 >= Ar_10 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_9 - Ar_10 + 2, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Fresh_7, Fresh_8, Fresh_9, Fresh_10, Fresh_11, Ar_22)) [ Ar_10 >= 2 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, 2, 1, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Fresh_2, Fresh_3, Fresh_4, Fresh_5, Fresh_6, Ar_22)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_13, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Fresh_0, Fresh_1, Ar_15, Ar_16 + 1, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22 + 2)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f76(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f76(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f76(-1, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f16(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f28(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ Ar_8 >= Ar_7 + 1 ] (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22) -> Com_1(f0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7, Ar_8, Ar_9, Ar_10, Ar_11, Ar_12, Ar_13, Ar_14, Ar_15, Ar_16, Ar_17, Ar_18, Ar_19, Ar_20, Ar_21, Ar_22)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16]. We thus obtain the following problem: 2: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = 2 Pol(f0) = 2 Pol(f16) = 2 Pol(f28) = 1 Pol(f18) = 2 Pol(f76) = 0 Pol(f35) = 1 Pol(f37) = 1 Pol(f52) = 1 orients all transitions weakly and the transitions f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = -V_5 + 2 Pol(f0) = -V_5 + 2 Pol(f16) = -V_5 + 2 Pol(f28) = -V_5 + 2 Pol(f18) = -V_5 + 2 Pol(f76) = -V_5 Pol(f35) = -V_5 + 2 Pol(f37) = -V_5 + 2 Pol(f52) = -V_5 + 2 orients all transitions weakly and the transitions f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = V_4 - V_5 + 1 Pol(f0) = V_4 - V_5 + 1 Pol(f16) = V_4 - V_5 + 1 Pol(f28) = V_4 - V_5 + 1 Pol(f18) = V_4 - V_5 + 1 Pol(f76) = V_4 - V_5 Pol(f35) = V_4 - V_5 + 1 Pol(f37) = V_4 - V_5 + 1 Pol(f52) = V_4 - V_5 orients all transitions weakly and the transitions f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: ?, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 6 produces the following problem: 7: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: 2*Ar_9 + 2*Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = V_6 - V_7 + 1 Pol(f0) = V_6 - V_7 + 1 Pol(f16) = V_6 - V_7 + 1 Pol(f28) = V_6 - V_7 + 1 Pol(f18) = V_6 - V_7 + 1 Pol(f76) = V_6 - V_7 Pol(f35) = V_6 - V_7 + 1 Pol(f37) = V_6 - V_7 Pol(f52) = V_6 - V_7 orients all transitions weakly and the transition f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] strictly and produces the following problem: 8: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: ?, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: 2*Ar_9 + 2*Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: Ar_15 + Ar_16 + 1, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 8 produces the following problem: 9: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: Ar_15 + Ar_16 + 7*Ar_10 + 3*Ar_9 + 12, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: 2*Ar_9 + 2*Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: Ar_15 + Ar_16 + 1, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: ?, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: ?, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = V_2 - V_3 + 1 Pol(f0) = V_2 - V_3 + 1 Pol(f16) = V_2 - V_3 + 1 Pol(f28) = V_2 - V_3 + 1 Pol(f18) = V_2 - V_3 Pol(f76) = V_2 - V_3 Pol(f35) = V_2 - V_3 Pol(f37) = V_2 - V_3 Pol(f52) = V_2 - V_3 orients all transitions weakly and the transitions f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] strictly and produces the following problem: 10: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: ?, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: Ar_15 + Ar_16 + 7*Ar_10 + 3*Ar_9 + 12, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: 2*Ar_9 + 2*Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: Ar_15 + Ar_16 + 1, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 10 produces the following problem: 11: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 <= 0 ] (Comp: 2, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 ] (Comp: Ar_7 + Ar_8 + Ar_9 + Ar_10 + 2, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_10 >= Ar_9 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(-1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= Ar_7 + 1 /\ Ar_0 + 1 = 0 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 0 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 2, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f76(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 + 2 /\ Ar_8 >= Ar_7 + 1 ] (Comp: 3*Ar_7 + 3*Ar_8 + Ar_15 + Ar_16 + 7*Ar_10 + 3*Ar_9 + 15, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8 + 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ Ar_16 >= X' + 2 ] (Comp: Ar_15 + Ar_16 + 7*Ar_10 + 3*Ar_9 + 12, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16 + 1)) [ Ar_10 >= Ar_9 + 1 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, Ar_16)) [ Ar_10 = 1 ] (Comp: 2*Ar_9 + 2*Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_10 >= 2 ] (Comp: Ar_10 + 2, Cost: 1) f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ 0 >= Ar_10 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, 2, Ar_15, 1)) [ Ar_9 >= 1 /\ Ar_10 = 1 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ Ar_9 >= Ar_10 /\ Ar_10 >= 2 /\ Ar_16 = 1 ] (Comp: Ar_10 + 2, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, 1)) [ 0 >= Ar_10 /\ Ar_9 >= Ar_10 /\ Ar_16 = 1 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_16 >= 2 /\ Ar_9 >= Ar_10 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f52(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_16 /\ Ar_9 >= Ar_10 ] (Comp: Ar_15 + Ar_16 + 1, Cost: 1) f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f37(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_15 >= 2*X' /\ 3*X' >= Ar_15 + 1 /\ X' + 1 >= Ar_16 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, 1, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= 1 /\ Ar_8 = 1 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_8 >= 2 /\ Ar_7 >= Ar_8 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f35(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_8 /\ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 >= 2 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f28(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ 0 >= Ar_0 ] (Comp: Ar_9 + Ar_10 + 1, Cost: 1) f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10 + 1, Ar_15, Ar_16)) [ Ar_9 >= Ar_10 ] (Comp: Ar_7 + Ar_8 + 1, Cost: 1) f16(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f18(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_7 >= Ar_8 ] (Comp: 1, Cost: 1) f0(Ar_0, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16) -> Com_1(f16(1, Ar_7, Ar_8, Ar_9, Ar_10, Ar_15, Ar_16)) [ Ar_0 = 1 ] start location: koat_start leaf cost: 0 Complexity upper bound 8*Ar_7 + 8*Ar_8 + 13*Ar_9 + 25*Ar_10 + 3*Ar_15 + 3*Ar_16 + 59 Time: 0.665 sec (SMT: 0.362 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 1: f16 -> f18 : [ H>=Q ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 2: f18 -> f18 : K'=1+K, L'=2+L, [ J>=K ], cost: 1 22: f18 -> f16 : Q'=1+Q, [ K>=1+J ], cost: 1 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 19: f28 -> f76 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, E'=H, F'=Q, G'=J, H'=K, Q'=L, J'=M, K'=N, L'=O, M'=P, N'=Q_1, O'=R, P'=S, Q_1'=T, R'=U, S'=V, T'=W, [ 0>=2+A && Q>=1+H ], cost: 1 20: f28 -> f76 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, E'=H, F'=Q, G'=J, H'=K, Q'=L, J'=M, K'=N, L'=O, M'=P, N'=Q_1, O'=R, P'=S, Q_1'=T, R'=U, S'=V, T'=W, [ A>=0 && Q>=1+H ], cost: 1 21: f28 -> f76 : A'=-1, A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, E'=H, F'=Q, G'=J, H'=K, Q'=L, J'=M, K'=N, L'=O, M'=P, N'=Q_1, O'=R, P'=S, Q_1'=T, R'=U, S'=V, T'=W, [ Q>=1+H && 1+A==0 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 9: f37 -> f52 : [ 0>=Q_1 && J>=K ], cost: 1 10: f37 -> f52 : [ Q_1>=2 && J>=K ], cost: 1 11: f37 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ 0>=K && J>=K && Q_1==1 ], cost: 1 12: f37 -> f37 : K'=1+K, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ J>=K && K>=2 && Q_1==1 ], cost: 1 13: f37 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ J>=1 && K==1 && Q_1==1 ], cost: 1 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 14: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=K ], cost: 1 15: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ K>=2 ], cost: 1 16: f52 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ K==1 ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 1: f16 -> f18 : [ H>=Q ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 2: f18 -> f18 : K'=1+K, L'=2+L, [ J>=K ], cost: 1 22: f18 -> f16 : Q'=1+Q, [ K>=1+J ], cost: 1 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 9: f37 -> f52 : [ 0>=Q_1 && J>=K ], cost: 1 10: f37 -> f52 : [ Q_1>=2 && J>=K ], cost: 1 11: f37 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ 0>=K && J>=K && Q_1==1 ], cost: 1 12: f37 -> f37 : K'=1+K, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ J>=K && K>=2 && Q_1==1 ], cost: 1 13: f37 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ J>=1 && K==1 && Q_1==1 ], cost: 1 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 14: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=K ], cost: 1 15: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ K>=2 ], cost: 1 16: f52 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ K==1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 2. Accelerating the following rules: 2: f18 -> f18 : K'=1+K, L'=2+L, [ J>=K ], cost: 1 Accelerated rule 2 with metering function 1+J-K, yielding the new rule 24. Removing the simple loops: 2. Accelerating simple loops of location 5. Accelerating the following rules: 11: f37 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ 0>=K && J>=K && Q_1==1 ], cost: 1 12: f37 -> f37 : K'=1+K, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ J>=K && K>=2 && Q_1==1 ], cost: 1 13: f37 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ J>=1 && K==1 && Q_1==1 ], cost: 1 Found no metering function for rule 11. Accelerated rule 12 with metering function 1+J-K, yielding the new rule 25. Accelerated rule 13 with metering function 2-K, yielding the new rule 26. Removing the simple loops: 12 13. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 1: f16 -> f18 : [ H>=Q ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 22: f18 -> f16 : Q'=1+Q, [ K>=1+J ], cost: 1 24: f18 -> f18 : K'=1+J, L'=2+2*J-2*K+L, [ J>=K ], cost: 1+J-K 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 9: f37 -> f52 : [ 0>=Q_1 && J>=K ], cost: 1 10: f37 -> f52 : [ Q_1>=2 && J>=K ], cost: 1 11: f37 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ 0>=K && J>=K && Q_1==1 ], cost: 1 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 25: f37 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ J>=K && K>=2 && Q_1==1 ], cost: 1+J-K 26: f37 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ J>=1 && K==1 && Q_1==1 ], cost: 2-K 14: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=K ], cost: 1 15: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ K>=2 ], cost: 1 16: f52 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ K==1 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 1: f16 -> f18 : [ H>=Q ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 27: f16 -> f18 : K'=1+J, L'=2+2*J-2*K+L, [ H>=Q && J>=K ], cost: 2+J-K 22: f18 -> f16 : Q'=1+Q, [ K>=1+J ], cost: 1 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 28: f35 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 ], cost: 2 30: f35 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 2+J-K 33: f35 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 ], cost: 3-K 9: f37 -> f52 : [ 0>=Q_1 && J>=K ], cost: 1 10: f37 -> f52 : [ Q_1>=2 && J>=K ], cost: 1 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 14: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=K ], cost: 1 15: f52 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ K>=2 ], cost: 1 16: f52 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ K==1 ], cost: 1 29: f52 -> f37 : K'=2+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, V'=free_34, [ 0>=1+K && J>=1+K && Q_1==1 ], cost: 2 31: f52 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, V'=free_39, [ K>=2 && J>=1+K && Q_1==1 ], cost: 1+J-K 32: f52 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, V'=free_44, [ K==1 && J>=2 && Q_1==1 ], cost: J 34: f52 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, V'=free_34, [ J>=1 && 1+K==1 && Q_1==1 ], cost: 2-K Eliminated locations (on tree-shaped paths): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 35: f16 -> f16 : Q'=1+Q, [ H>=Q && K>=1+J ], cost: 2 36: f16 -> f16 : Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ H>=Q && J>=K ], cost: 3+J-K 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 28: f35 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 ], cost: 2 30: f35 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 2+J-K 33: f35 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 ], cost: 3-K 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 37: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=Q_1 && J>=K && 0>=K ], cost: 2 38: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ 0>=Q_1 && J>=K && K>=2 ], cost: 2 39: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ 0>=Q_1 && J>=K && K==1 ], cost: 2 40: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ Q_1>=2 && J>=K && 0>=K ], cost: 2 41: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ Q_1>=2 && J>=K && K>=2 ], cost: 2 42: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ Q_1>=2 && J>=K && K==1 ], cost: 2 Applied pruning (of leafs and parallel rules): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 35: f16 -> f16 : Q'=1+Q, [ H>=Q && K>=1+J ], cost: 2 36: f16 -> f16 : Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ H>=Q && J>=K ], cost: 3+J-K 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 28: f35 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 ], cost: 2 30: f35 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 2+J-K 33: f35 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 ], cost: 3-K 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 37: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=Q_1 && J>=K && 0>=K ], cost: 2 38: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ 0>=Q_1 && J>=K && K>=2 ], cost: 2 39: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ 0>=Q_1 && J>=K && K==1 ], cost: 2 40: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ Q_1>=2 && J>=K && 0>=K ], cost: 2 42: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ Q_1>=2 && J>=K && K==1 ], cost: 2 Accelerating simple loops of location 1. Accelerating the following rules: 35: f16 -> f16 : Q'=1+Q, [ H>=Q && K>=1+J ], cost: 2 36: f16 -> f16 : Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ H>=Q && J>=K ], cost: 3+J-K Accelerated rule 35 with metering function 1+H-Q, yielding the new rule 43. Found no metering function for rule 36. Removing the simple loops: 35. Accelerating simple loops of location 5. Accelerating the following rules: 37: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=Q_1 && J>=K && 0>=K ], cost: 2 38: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ 0>=Q_1 && J>=K && K>=2 ], cost: 2 39: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ 0>=Q_1 && J>=K && K==1 ], cost: 2 40: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ Q_1>=2 && J>=K && 0>=K ], cost: 2 42: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ Q_1>=2 && J>=K && K==1 ], cost: 2 Found no metering function for rule 37. Accelerated rule 38 with metering function 1+J-K, yielding the new rule 44. Accelerated rule 39 with metering function 1-K, yielding the new rule 45. Found no metering function for rule 40. Accelerated rule 42 with metering function 1-K, yielding the new rule 46. Removing the simple loops: 38 39 42. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 23: f16 -> f28 : [ Q>=1+H ], cost: 1 36: f16 -> f16 : Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ H>=Q && J>=K ], cost: 3+J-K 43: f16 -> f16 : Q'=1+H, [ H>=Q && K>=1+J ], cost: 2+2*H-2*Q 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 28: f35 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 ], cost: 2 30: f35 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 2+J-K 33: f35 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 ], cost: 3-K 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 37: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ 0>=Q_1 && J>=K && 0>=K ], cost: 2 40: f37 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ Q_1>=2 && J>=K && 0>=K ], cost: 2 44: f37 -> f37 : K'=1+J, L'=2, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ 0>=Q_1 && J>=K && K>=2 ], cost: 2+2*J-2*K 45: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ 0>=Q_1 && J>=K && K==1 && 1-K>=1 ], cost: 2-2*K 46: f37 -> f37 : K'=2, L'=1, R'=free_45, S'=free_47, T'=free_43, U'=free_46, V'=free_44, [ Q_1>=2 && J>=K && K==1 && 1-K>=1 ], cost: 2-2*K Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 ], cost: 1 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 47: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K ], cost: 4+J-K 48: f0 -> f16 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 3+2*H-2*Q 23: f16 -> f28 : [ Q>=1+H ], cost: 1 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 8: f35 -> f37 : [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 28: f35 -> f37 : K'=1+K, L'=free_21, Q_1'=1, R'=free_23, S'=free_19, T'=free_22, U'=free_20, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 ], cost: 2 30: f35 -> f37 : K'=1+J, L'=free_26, Q_1'=1, R'=free_28, S'=free_24, T'=free_27, U'=free_25, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 2+J-K 33: f35 -> f37 : K'=2, L'=1, Q_1'=1, R'=free_30, S'=free_32, T'=free_29, U'=free_31, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 ], cost: 3-K 49: f35 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && 0>=K ], cost: 3 50: f35 -> f37 : K'=1+K, L'=2+J-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && Q_1>=2 && J>=K && 0>=K ], cost: 3 51: f35 -> f37 : K'=1+J, L'=2, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 3+2*J-2*K 17: f37 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ K>=1+J ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 55: f35 -> f35 : E'=N, N'=free_48, O'=free_49, Q_1'=1+Q_1, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && K>=1+J ], cost: 2 56: f35 -> f35 : E'=N, K'=1+K, L'=free_21, N'=free_48, O'=free_49, Q_1'=2, R'=free_23, S'=free_19, T'=free_22, U'=free_20, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 && 1+K>=1+J ], cost: 3 57: f35 -> f35 : E'=N, K'=1+J, L'=free_26, N'=free_48, O'=free_49, Q_1'=2, R'=free_28, S'=free_24, T'=free_27, U'=free_25, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 3+J-K 58: f35 -> f35 : E'=N, K'=2, L'=1, N'=free_48, O'=free_49, Q_1'=2, R'=free_30, S'=free_32, T'=free_29, U'=free_31, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 && 2>=1+J ], cost: 4-K 59: f35 -> f35 : E'=N, K'=1+K, L'=2+J-K, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && 0>=K && 1+K>=1+J ], cost: 4 60: f35 -> f35 : E'=N, K'=1+K, L'=2+J-K, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && Q_1>=2 && J>=K && 0>=K && 1+K>=1+J ], cost: 4 61: f35 -> f35 : E'=N, K'=1+J, L'=2, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 4+2*J-2*K Applied pruning (of leafs and parallel rules): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 56: f35 -> f35 : E'=N, K'=1+K, L'=free_21, N'=free_48, O'=free_49, Q_1'=2, R'=free_23, S'=free_19, T'=free_22, U'=free_20, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && J>=K && Q_1==1 && 1+K>=1+J ], cost: 3 57: f35 -> f35 : E'=N, K'=1+J, L'=free_26, N'=free_48, O'=free_49, Q_1'=2, R'=free_28, S'=free_24, T'=free_27, U'=free_25, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 3+J-K 58: f35 -> f35 : E'=N, K'=2, L'=1, N'=free_48, O'=free_49, Q_1'=2, R'=free_30, S'=free_32, T'=free_29, U'=free_31, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=1 && K==1 && Q_1==1 && 2>=1+J ], cost: 4-K 59: f35 -> f35 : E'=N, K'=1+K, L'=2+J-K, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && 0>=K && 1+K>=1+J ], cost: 4 61: f35 -> f35 : E'=N, K'=1+J, L'=2, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 4+2*J-2*K Accelerating simple loops of location 4. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 56: f35 -> f35 : E'=N, K'=1+K, L'=free_21, N'=free_48, O'=free_49, Q_1'=2, R'=free_23, S'=free_19, T'=free_22, U'=free_20, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && -J+K==0 && Q_1==1 ], cost: 3 57: f35 -> f35 : E'=N, K'=1+J, L'=free_26, N'=free_48, O'=free_49, Q_1'=2, R'=free_28, S'=free_24, T'=free_27, U'=free_25, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 ], cost: 3+J-K 58: f35 -> f35 : E'=N, K'=2, L'=1, N'=free_48, O'=free_49, Q_1'=2, R'=free_30, S'=free_32, T'=free_29, U'=free_31, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 1-J==0 && K==1 && Q_1==1 ], cost: 4-K 59: f35 -> f35 : E'=N, K'=1+K, L'=2+J-K, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && -J+K==0 && 0>=K ], cost: 4 61: f35 -> f35 : E'=N, K'=1+J, L'=2, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 4+2*J-2*K Accelerated rule 56 with metering function meter_2 (where 2*meter_2==1+J-Q_1-K), yielding the new rule 62. Accelerated rule 57 with metering function 1-Q_1, yielding the new rule 63. Accelerated rule 58 with metering function meter_3 (where 2*meter_3==2-Q_1-K), yielding the new rule 64. Accelerated rule 59 with metering function J-K, yielding the new rule 65. Found no metering function for rule 61. Removing the simple loops: 56 57 58 59. Accelerated all simple loops using metering functions (where possible): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 61: f35 -> f35 : E'=N, K'=1+J, L'=2, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 4+2*J-2*K 62: f35 -> f35 : E'=free_48, K'=meter_2+K, L'=free_21, N'=free_48, O'=free_49, Q_1'=2, R'=free_23, S'=free_19, T'=free_22, U'=free_20, W'=W+2*meter_2, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=K && -J+K==0 && Q_1==1 && 2*meter_2==1+J-Q_1-K && meter_2>=1 ], cost: 3*meter_2 63: f35 -> f35 : E'=free_48, K'=1+J, L'=free_26, N'=free_48, O'=free_49, Q_1'=2, R'=free_28, S'=free_24, T'=free_27, U'=free_25, W'=2+W-2*Q_1, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && J>=K && K>=2 && Q_1==1 && 1-Q_1>=1 ], cost: 2-2*Q_1 64: f35 -> f35 : E'=free_48, K'=2, L'=1, N'=free_48, O'=free_49, Q_1'=2, R'=free_30, S'=free_32, T'=free_29, U'=free_31, W'=2*meter_3+W, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 1-J==0 && K==1 && Q_1==1 && 2*meter_3==2-Q_1-K && meter_3>=1 ], cost: 2*meter_3 65: f35 -> f35 : E'=free_48, K'=J, L'=3, N'=free_48, O'=free_49, Q_1'=J+Q_1-K, R'=free_35, S'=free_37, T'=free_33, U'=free_36, V'=free_34, W'=2*J+W-2*K, [ P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && -J+K==0 && 0>=K && J-K>=1 ], cost: 4*J-4*K Chained accelerated rules (with incoming rules): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 5: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q ], cost: 1 6: f28 -> f35 : M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q ], cost: 1 7: f28 -> f35 : Q'=1, M'=1, N'=1, O'=0, [ H>=1 && Q==1 ], cost: 1 66: f28 -> f35 : E'=1, K'=1+J, L'=2, M'=2+H-Q, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 67: f28 -> f35 : E'=1, K'=1+J, L'=2, M'=2+H-Q, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 68: f28 -> f35 : E'=1, Q'=1, K'=1+J, L'=2, M'=1, N'=free_48, O'=free_49, Q_1'=1+Q_1, R'=free_40, S'=free_42, T'=free_38, U'=free_41, V'=free_39, W'=2+W, [ H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 18: f35 -> f28 : Q'=1+Q, [ P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 69: f28 -> f28 : Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 70: f28 -> f28 : Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 71: f28 -> f28 : Q'=2, M'=1, N'=1, O'=0, [ H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 72: f28 -> [13] : [ 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 73: f28 -> [13] : [ Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 74: f28 -> [13] : [ H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K Accelerating simple loops of location 3. Accelerating the following rules: 69: f28 -> f28 : Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 70: f28 -> f28 : Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 71: f28 -> f28 : Q'=2, M'=1, N'=1, O'=0, [ H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 Found no metering function for rule 69. Accelerated rule 70 with metering function 1+H-Q, yielding the new rule 75. Accelerated rule 71 with metering function 2-Q, yielding the new rule 76. Removing the simple loops: 70 71. Accelerated all simple loops using metering functions (where possible): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 69: f28 -> f28 : Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ 0>=Q && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2 72: f28 -> [13] : [ 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 73: f28 -> [13] : [ Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 74: f28 -> [13] : [ H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 75: f28 -> f28 : Q'=1+H, M'=2, N'=1, O'=0, [ Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 2+2*H-2*Q 76: f28 -> f28 : Q'=2, M'=1, N'=1, O'=0, [ H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 4-2*Q Chained accelerated rules (with incoming rules): Start location: f0 3: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A ], cost: 1 4: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 ], cost: 1 52: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, [ A==1 && Q>=1+H ], cost: 2 53: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+Q, K'=1+J, L'=2+2*J-2*K+L, [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 54: f0 -> f28 : A'=1, B'=free_3, C'=free_5, D'=free_1, E'=free_4, F'=free_2, G'=free, Q'=1+H, [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 77: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ 0>=A && 0>=Q && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3 78: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, Q'=1+Q, M'=2+H-Q, N'=1, O'=0, [ A>=2 && 0>=Q && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3 79: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, Q'=1+H, M'=2, N'=1, O'=0, [ 0>=A && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 80: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, Q'=1+H, M'=2, N'=1, O'=0, [ A>=2 && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 81: f0 -> f28 : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, Q'=2, M'=1, N'=1, O'=0, [ 0>=A && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q 82: f0 -> f28 : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, Q'=2, M'=1, N'=1, O'=0, [ A>=2 && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q 72: f28 -> [13] : [ 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 73: f28 -> [13] : [ Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K 74: f28 -> [13] : [ H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 5+2*J-2*K Eliminated locations (on tree-shaped paths): Start location: f0 83: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 84: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 85: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 86: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 87: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 88: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 89: f0 -> [15] : [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 90: f0 -> [15] : [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 91: f0 -> [15] : [ 0>=A && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 92: f0 -> [15] : [ A>=2 && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 93: f0 -> [15] : [ 0>=A && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q 94: f0 -> [15] : [ A>=2 && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q Applied pruning (of leafs and parallel rules): Start location: f0 83: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 84: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 86: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 87: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 88: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 89: f0 -> [15] : [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 90: f0 -> [15] : [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 91: f0 -> [15] : [ 0>=A && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 92: f0 -> [15] : [ A>=2 && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 93: f0 -> [15] : [ 0>=A && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 83: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 84: f0 -> [13] : B'=free_9, C'=free_11, D'=free_7, E'=free_10, F'=free_8, G'=free_6, [ 0>=A && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 86: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 87: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && Q>=2 && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 88: f0 -> [13] : B'=free_15, C'=free_17, D'=free_13, E'=free_16, F'=free_14, G'=free_12, [ A>=2 && H>=1 && Q==1 && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ], cost: 6+2*J-2*K 89: f0 -> [15] : [ A==1 && H>=Q && J>=K && 1+Q>=1+H ], cost: 5+J-K 90: f0 -> [15] : [ A==1 && H>=Q && K>=1+J ], cost: 4+2*H-2*Q 91: f0 -> [15] : [ 0>=A && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 92: f0 -> [15] : [ A>=2 && Q>=2 && H>=Q && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 3+2*H-2*Q 93: f0 -> [15] : [ 0>=A && H>=1 && Q==1 && P>=2*free_50 && 3*free_50>=1+P && Q_1>=2+free_50 ], cost: 5-2*Q Computing asymptotic complexity for rule 83 Solved the limit problem by the following transformations: Created initial limit problem: 1-Q (+/+!), 2+free_18-Q_1 (+/+!), 1+J-K (+/+!), 1-A (+/+!), 1-2*free_18+P (+/+!), 3*free_18-P (+/+!), 1+H-Q (+/+!), 1-Q_1 (+/+!), 6+2*J-2*K (+), -1+K (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free_18==1,P==2,J==n,Q_1==0,A==-n,K==2,H==-n,Q==-n} resulting limit problem: [solved] Solution: free_18 / 1 P / 2 J / n Q_1 / 0 A / -n K / 2 H / -n Q / -n Resulting cost 2+2*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 2+2*n Rule cost: 6+2*J-2*K Rule guard: [ 0>=A && 0>=Q && H>=Q && P>=2*free_18 && 3*free_18>=1+P && 1+free_18>=Q_1 && 0>=Q_1 && J>=K && K>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)