18.51/8.36 WORST_CASE(Omega(n^1), O(n^1)) 18.71/8.37 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 18.71/8.37 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.71/8.37 18.71/8.37 18.71/8.37 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 18.71/8.37 18.71/8.37 (0) CpxIntTrs 18.71/8.37 (1) Koat Proof [FINISHED, 1074 ms] 18.71/8.37 (2) BOUNDS(1, n^1) 18.71/8.37 (3) Loat Proof [FINISHED, 6616 ms] 18.71/8.37 (4) BOUNDS(n^1, INF) 18.71/8.37 18.71/8.37 18.71/8.37 ---------------------------------------- 18.71/8.37 18.71/8.37 (0) 18.71/8.37 Obligation: 18.71/8.37 Complexity Int TRS consisting of the following rules: 18.71/8.37 start(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, 0, C, 0, E, F, G, 0, I, J)) :|: 0 >= A && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= A && J <= A 18.71/8.37 start(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, 0, C, 0, E, K, G, 1, I, J)) :|: A >= 1 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= I && H <= I && J >= A && J <= A 18.71/8.37 lbl21(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 1 && A + D >= B + 1 && A + B >= D + 1 && A >= D + B + 1 && H >= A && H <= A && J >= A && J <= A 18.71/8.37 lbl21(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 1 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && J >= A && J <= A 18.71/8.37 lbl121(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 2 && A + D >= B + 2 && A + B >= D && A >= D + B && H >= A && H <= A && F >= 0 && F <= 0 && J >= A && J <= A 18.71/8.37 lbl121(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 2 && H + D >= B + 2 && H + B >= D && H >= D + B && F >= 0 && F <= 0 && J >= A && J <= A 18.71/8.37 lbl141(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 0 && A + D >= B && A + B >= D + 2 && A >= D + B + 2 && H >= A && H <= A && F >= 1 && F <= 1 && J >= A && J <= A 18.71/8.37 lbl141(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 0 && H + D >= B && H + B >= D + 2 && H >= D + B + 2 && F >= 1 && F <= 1 && J >= A && J <= A 18.71/8.37 lbl171(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 2 && A + D >= B && A + B >= D + 2 && A >= D + B && H >= A && H <= A && F >= 2 && F <= 2 && J >= A && J <= A 18.71/8.37 lbl171(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 2 && H + D >= B && H + B >= D + 2 && H >= D + B && F >= 2 && F <= 2 && J >= A && J <= A 18.71/8.37 lbl191(A, B, C, D, E, F, G, H, I, J) -> Com_1(stop(A, B, C, D, E, F, G, H, I, J)) :|: A + D + B >= 0 && A + D >= B + 2 && A + B >= D && A >= D + B + 2 && H >= A && H <= A && F >= 3 && F <= 3 && J >= A && J <= A 18.71/8.37 lbl191(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl81(A, B, C, D, E, K, G, 1 + H, I, J)) :|: A >= H + 1 && A >= H && H + D + B >= 0 && H + D >= B + 2 && H + B >= D && H >= D + B + 2 && F >= 3 && F <= 3 && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl21(A, B, C, D, E, F, G, H, I, J)) :|: 0 >= F + 1 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl21(A, B, C, D, E, F, G, H, I, J)) :|: F >= 4 && H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl121(A, B, C, 1 + D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 0 && F <= 0 && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl141(A, B, C, D - 1, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 1 && F <= 1 && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl171(A, 1 + B, C, D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 2 && F <= 2 && J >= A && J <= A 18.71/8.37 lbl81(A, B, C, D, E, F, G, H, I, J) -> Com_1(lbl191(A, B - 1, C, D, E, F, G, H, I, J)) :|: H + D >= B + 1 && H + B >= D + 1 && H >= D + B + 1 && H + D + B >= 1 && A >= H && F >= 3 && F <= 3 && J >= A && J <= A 18.71/8.37 start0(A, B, C, D, E, F, G, H, I, J) -> Com_1(start(A, C, C, E, E, G, G, I, I, A)) :|: TRUE 18.71/8.37 18.71/8.37 The start-symbols are:[start0_10] 18.71/8.37 18.71/8.37 18.71/8.37 ---------------------------------------- 18.71/8.37 18.71/8.37 (1) Koat Proof (FINISHED) 18.71/8.37 YES(?, 110*ar_0 + 8) 18.71/8.37 18.71/8.37 18.71/8.37 18.71/8.37 Initial complexity problem: 18.71/8.37 18.71/8.37 1: T: 18.71/8.37 18.71/8.37 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, 0, ar_2, 0, ar_4, ar_5, ar_6, 0, ar_8, ar_9)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.37 18.71/8.37 (Comp: ?, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, 0, ar_2, 0, ar_4, k, ar_6, 1, ar_8, ar_9)) [ ar_0 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.37 18.71/8.37 (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, ar_0)) 18.71/8.38 18.71/8.38 (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) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 <= 0 ] 18.71/8.38 18.71/8.38 start location: koat_start 18.71/8.38 18.71/8.38 leaf cost: 0 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Repeatedly propagating knowledge in problem 1 produces the following problem: 18.71/8.38 18.71/8.38 2: T: 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, 0, ar_2, 0, ar_4, ar_5, ar_6, 0, ar_8, ar_9)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, 0, ar_2, 0, ar_4, k, ar_6, 1, ar_8, ar_9)) [ ar_0 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, ar_0)) 18.71/8.38 18.71/8.38 (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) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 <= 0 ] 18.71/8.38 18.71/8.38 start location: koat_start 18.71/8.38 18.71/8.38 leaf cost: 0 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 A polynomial rank function with 18.71/8.38 18.71/8.38 Pol(start) = 1 18.71/8.38 18.71/8.38 Pol(stop) = 0 18.71/8.38 18.71/8.38 Pol(lbl81) = 1 18.71/8.38 18.71/8.38 Pol(lbl21) = 1 18.71/8.38 18.71/8.38 Pol(lbl121) = 1 18.71/8.38 18.71/8.38 Pol(lbl141) = 1 18.71/8.38 18.71/8.38 Pol(lbl171) = 1 18.71/8.38 18.71/8.38 Pol(lbl191) = 1 18.71/8.38 18.71/8.38 Pol(start0) = 1 18.71/8.38 18.71/8.38 Pol(koat_start) = 1 18.71/8.38 18.71/8.38 orients all transitions weakly and the transitions 18.71/8.38 18.71/8.38 lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 strictly and produces the following problem: 18.71/8.38 18.71/8.38 3: T: 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, 0, ar_2, 0, ar_4, ar_5, ar_6, 0, ar_8, ar_9)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, 0, ar_2, 0, ar_4, k, ar_6, 1, ar_8, ar_9)) [ ar_0 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: ?, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, ar_0)) 18.71/8.38 18.71/8.38 (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) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 <= 0 ] 18.71/8.38 18.71/8.38 start location: koat_start 18.71/8.38 18.71/8.38 leaf cost: 0 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 A polynomial rank function with 18.71/8.38 18.71/8.38 Pol(start) = 10*V_1 18.71/8.38 18.71/8.38 Pol(stop) = 10*V_1 - 2*V_8 - 7 18.71/8.38 18.71/8.38 Pol(lbl81) = -2*V_8 + 10*V_10 - 6 18.71/8.38 18.71/8.38 Pol(lbl21) = -2*V_8 + 10*V_10 - 7 18.71/8.38 18.71/8.38 Pol(lbl121) = -2*V_8 + 10*V_10 - 7 18.71/8.38 18.71/8.38 Pol(lbl141) = -2*V_8 + 10*V_10 - 7 18.71/8.38 18.71/8.38 Pol(lbl171) = -2*V_8 + 10*V_10 - 7 18.71/8.38 18.71/8.38 Pol(lbl191) = -2*V_8 + 10*V_10 - 7 18.71/8.38 18.71/8.38 Pol(start0) = 10*V_1 18.71/8.38 18.71/8.38 Pol(koat_start) = 10*V_1 18.71/8.38 18.71/8.38 orients all transitions weakly and the transitions 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 strictly and produces the following problem: 18.71/8.38 18.71/8.38 4: T: 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, 0, ar_2, 0, ar_4, ar_5, ar_6, 0, ar_8, ar_9)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, 0, ar_2, 0, ar_4, k, ar_6, 1, ar_8, ar_9)) [ ar_0 >= 1 /\ ar_1 = ar_2 /\ ar_3 = ar_4 /\ ar_5 = ar_6 /\ ar_7 = ar_8 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 1 /\ ar_0 + ar_3 >= ar_1 + 1 /\ ar_0 + ar_1 >= ar_3 + 1 /\ ar_0 >= ar_3 + ar_1 + 1 /\ ar_7 = ar_0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl121(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl141(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 2 /\ ar_0 + ar_3 >= ar_1 /\ ar_0 + ar_1 >= ar_3 + 2 /\ ar_0 >= ar_3 + ar_1 /\ ar_7 = ar_0 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl171(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 2 /\ ar_7 + ar_3 >= ar_1 /\ ar_7 + ar_1 >= ar_3 + 2 /\ ar_7 >= ar_3 + ar_1 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_0 + ar_3 + ar_1 >= 0 /\ ar_0 + ar_3 >= ar_1 + 2 /\ ar_0 + ar_1 >= ar_3 /\ ar_0 >= ar_3 + ar_1 + 2 /\ ar_7 = ar_0 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl191(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, k, ar_6, ar_7 + 1, ar_8, ar_9)) [ ar_0 >= ar_7 + 1 /\ ar_0 >= ar_7 /\ ar_7 + ar_3 + ar_1 >= 0 /\ ar_7 + ar_3 >= ar_1 + 2 /\ ar_7 + ar_1 >= ar_3 /\ ar_7 >= ar_3 + ar_1 + 2 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 >= ar_5 + 1 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl21(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_5 >= 4 /\ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl121(ar_0, ar_1, ar_2, ar_3 + 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 0 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl141(ar_0, ar_1, ar_2, ar_3 - 1, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 1 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl171(ar_0, ar_1 + 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 2 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 10*ar_0, Cost: 1) lbl81(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(lbl191(ar_0, ar_1 - 1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ ar_7 + ar_3 >= ar_1 + 1 /\ ar_7 + ar_1 >= ar_3 + 1 /\ ar_7 >= ar_3 + ar_1 + 1 /\ ar_7 + ar_3 + ar_1 >= 1 /\ ar_0 >= ar_7 /\ ar_5 = 3 /\ ar_9 = ar_0 ] 18.71/8.38 18.71/8.38 (Comp: 1, Cost: 1) start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9) -> Com_1(start(ar_0, ar_2, ar_2, ar_4, ar_4, ar_6, ar_6, ar_8, ar_8, ar_0)) 18.71/8.38 18.71/8.38 (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) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7, ar_8, ar_9)) [ 0 <= 0 ] 18.71/8.38 18.71/8.38 start location: koat_start 18.71/8.38 18.71/8.38 leaf cost: 0 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Complexity upper bound 110*ar_0 + 8 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Time: 1.041 sec (SMT: 0.749 sec) 18.71/8.38 18.71/8.38 18.71/8.38 ---------------------------------------- 18.71/8.38 18.71/8.38 (2) 18.71/8.38 BOUNDS(1, n^1) 18.71/8.38 18.71/8.38 ---------------------------------------- 18.71/8.38 18.71/8.38 (3) Loat Proof (FINISHED) 18.71/8.38 18.71/8.38 18.71/8.38 ### Pre-processing the ITS problem ### 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Initial linear ITS problem 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 0: start -> stop : B'=0, D'=0, H'=0, [ 0>=A && B==C && D==E && F==G && H==Q && J==A ], cost: 1 18.71/8.38 18.71/8.38 1: start -> lbl81 : B'=0, D'=0, F'=free, H'=1, [ A>=1 && B==C && D==E && F==G && H==Q && J==A ], cost: 1 18.71/8.38 18.71/8.38 2: lbl21 -> stop : [ D+A+B>=1 && D+A>=1+B && A+B>=1+D && A>=1+D+B && H==A && J==A ], cost: 1 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && A>=H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 4: lbl121 -> stop : [ D+A+B>=2 && D+A>=2+B && A+B>=D && A>=D+B && H==A && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 5: lbl121 -> lbl81 : F'=free_2, H'=1+H, [ A>=1+H && A>=H && D+H+B>=2 && D+H>=2+B && H+B>=D && H>=D+B && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 6: lbl141 -> stop : [ D+A+B>=0 && D+A>=B && A+B>=2+D && A>=2+D+B && H==A && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 7: lbl141 -> lbl81 : F'=free_3, H'=1+H, [ A>=1+H && A>=H && D+H+B>=0 && D+H>=B && H+B>=2+D && H>=2+D+B && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 8: lbl171 -> stop : [ D+A+B>=2 && D+A>=B && A+B>=2+D && A>=D+B && H==A && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 9: lbl171 -> lbl81 : F'=free_4, H'=1+H, [ A>=1+H && A>=H && D+H+B>=2 && D+H>=B && H+B>=2+D && H>=D+B && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 10: lbl191 -> stop : [ D+A+B>=0 && D+A>=2+B && A+B>=D && A>=2+D+B && H==A && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 11: lbl191 -> lbl81 : F'=free_5, H'=1+H, [ A>=1+H && A>=H && D+H+B>=0 && D+H>=2+B && H+B>=D && H>=2+D+B && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 14: lbl81 -> lbl121 : D'=1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 15: lbl81 -> lbl141 : D'=-1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 16: lbl81 -> lbl171 : B'=1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 17: lbl81 -> lbl191 : B'=-1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 18: start0 -> start : B'=C, D'=E, F'=G, H'=Q, J'=A, [], cost: 1 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Removed unreachable and leaf rules: 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 1: start -> lbl81 : B'=0, D'=0, F'=free, H'=1, [ A>=1 && B==C && D==E && F==G && H==Q && J==A ], cost: 1 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && A>=H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 5: lbl121 -> lbl81 : F'=free_2, H'=1+H, [ A>=1+H && A>=H && D+H+B>=2 && D+H>=2+B && H+B>=D && H>=D+B && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 7: lbl141 -> lbl81 : F'=free_3, H'=1+H, [ A>=1+H && A>=H && D+H+B>=0 && D+H>=B && H+B>=2+D && H>=2+D+B && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 9: lbl171 -> lbl81 : F'=free_4, H'=1+H, [ A>=1+H && A>=H && D+H+B>=2 && D+H>=B && H+B>=2+D && H>=D+B && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 11: lbl191 -> lbl81 : F'=free_5, H'=1+H, [ A>=1+H && A>=H && D+H+B>=0 && D+H>=2+B && H+B>=D && H>=2+D+B && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 14: lbl81 -> lbl121 : D'=1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 15: lbl81 -> lbl141 : D'=-1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 16: lbl81 -> lbl171 : B'=1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 17: lbl81 -> lbl191 : B'=-1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 18: start0 -> start : B'=C, D'=E, F'=G, H'=Q, J'=A, [], cost: 1 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Simplified all rules, resulting in: 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 1: start -> lbl81 : B'=0, D'=0, F'=free, H'=1, [ A>=1 && B==C && D==E && F==G && H==Q && J==A ], cost: 1 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 5: lbl121 -> lbl81 : F'=free_2, H'=1+H, [ A>=1+H && D+H+B>=2 && D+H>=2+B && H+B>=D && H>=D+B && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 7: lbl141 -> lbl81 : F'=free_3, H'=1+H, [ A>=1+H && D+H+B>=0 && D+H>=B && H+B>=2+D && H>=2+D+B && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 9: lbl171 -> lbl81 : F'=free_4, H'=1+H, [ A>=1+H && D+H+B>=2 && D+H>=B && H+B>=2+D && H>=D+B && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 11: lbl191 -> lbl81 : F'=free_5, H'=1+H, [ A>=1+H && D+H+B>=0 && D+H>=2+B && H+B>=D && H>=2+D+B && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 14: lbl81 -> lbl121 : D'=1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==0 && J==A ], cost: 1 18.71/8.38 18.71/8.38 15: lbl81 -> lbl141 : D'=-1+D, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==1 && J==A ], cost: 1 18.71/8.38 18.71/8.38 16: lbl81 -> lbl171 : B'=1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==2 && J==A ], cost: 1 18.71/8.38 18.71/8.38 17: lbl81 -> lbl191 : B'=-1+B, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && F==3 && J==A ], cost: 1 18.71/8.38 18.71/8.38 18: start0 -> start : B'=C, D'=E, F'=G, H'=Q, J'=A, [], cost: 1 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 ### Simplification by acceleration and chaining ### 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Eliminated locations (on linear paths): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 20: lbl81 -> lbl81 : D'=1+D, F'=free_2, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==0 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 21: lbl81 -> lbl81 : D'=-1+D, F'=free_3, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==1 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 22: lbl81 -> lbl81 : B'=1+B, F'=free_4, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==2 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 23: lbl81 -> lbl81 : B'=-1+B, F'=free_5, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==3 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 19: start0 -> lbl81 : B'=0, D'=0, F'=free, H'=1, J'=A, [ A>=1 ], cost: 2 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Accelerating simple loops of location 6. 18.71/8.38 18.71/8.38 Accelerating the following rules: 18.71/8.38 18.71/8.38 20: lbl81 -> lbl81 : D'=1+D, F'=free_2, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==0 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 21: lbl81 -> lbl81 : D'=-1+D, F'=free_3, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==1 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 22: lbl81 -> lbl81 : B'=1+B, F'=free_4, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==2 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 23: lbl81 -> lbl81 : B'=-1+B, F'=free_5, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==3 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Accelerated rule 20 with metering function A-H (after strengthening guard), yielding the new rule 24. 18.71/8.38 18.71/8.38 Accelerated rule 21 with metering function A-H (after strengthening guard), yielding the new rule 25. 18.71/8.38 18.71/8.38 Accelerated rule 22 with metering function A-H (after strengthening guard), yielding the new rule 26. 18.71/8.38 18.71/8.38 Accelerated rule 23 with metering function A-H (after strengthening guard), yielding the new rule 27. 18.71/8.38 18.71/8.38 Removing the simple loops:. 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Accelerated all simple loops using metering functions (where possible): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 20: lbl81 -> lbl81 : D'=1+D, F'=free_2, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==0 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 21: lbl81 -> lbl81 : D'=-1+D, F'=free_3, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==1 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 22: lbl81 -> lbl81 : B'=1+B, F'=free_4, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==2 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 23: lbl81 -> lbl81 : B'=-1+B, F'=free_5, H'=1+H, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==3 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 24: lbl81 -> lbl81 : D'=D+A-H, F'=free_2, H'=A, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==0 && J==A && A>=1+H && free_2==0 ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 25: lbl81 -> lbl81 : D'=D-A+H, F'=free_3, H'=A, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==1 && J==A && A>=1+H && free_3==1 ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 26: lbl81 -> lbl81 : B'=A-H+B, F'=free_4, H'=A, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==2 && J==A && A>=1+H && free_4==2 ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 27: lbl81 -> lbl81 : B'=-A+H+B, F'=free_5, H'=A, [ D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && F==3 && J==A && A>=1+H && free_5==3 ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 19: start0 -> lbl81 : B'=0, D'=0, F'=free, H'=1, J'=A, [ A>=1 ], cost: 2 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Chained accelerated rules (with incoming rules): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 3: lbl21 -> lbl81 : F'=free_1, H'=1+H, [ A>=1+H && D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A ], cost: 1 18.71/8.38 18.71/8.38 28: lbl21 -> lbl81 : D'=1+D, F'=free_2, H'=2+H, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: 3 18.71/8.38 18.71/8.38 30: lbl21 -> lbl81 : D'=-1+D, F'=free_3, H'=2+H, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: 3 18.71/8.38 18.71/8.38 32: lbl21 -> lbl81 : B'=1+B, F'=free_4, H'=2+H, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: 3 18.71/8.38 18.71/8.38 34: lbl21 -> lbl81 : B'=-1+B, F'=free_5, H'=2+H, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: 3 18.71/8.38 18.71/8.38 36: lbl21 -> lbl81 : D'=-1+D+A-H, F'=0, H'=A, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: -1+2*A-2*H 18.71/8.38 18.71/8.38 38: lbl21 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: -1+2*A-2*H 18.71/8.38 18.71/8.38 40: lbl21 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: -1+2*A-2*H 18.71/8.38 18.71/8.38 42: lbl21 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ D+H+B>=1 && D+H>=1+B && H+B>=1+D && H>=1+D+B && J==A && A>=2+H ], cost: -1+2*A-2*H 18.71/8.38 18.71/8.38 12: lbl81 -> lbl21 : [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 13: lbl81 -> lbl21 : [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && A>=H && J==A ], cost: 1 18.71/8.38 18.71/8.38 19: start0 -> lbl81 : B'=0, D'=0, F'=free, H'=1, J'=A, [ A>=1 ], cost: 2 18.71/8.38 18.71/8.38 29: start0 -> lbl81 : B'=0, D'=1, F'=free_2, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 31: start0 -> lbl81 : B'=0, D'=-1, F'=free_3, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 33: start0 -> lbl81 : B'=1, D'=0, F'=free_4, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 35: start0 -> lbl81 : B'=-1, D'=0, F'=free_5, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Eliminated locations (on tree-shaped paths): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 44: lbl81 -> lbl81 : F'=free_1, H'=1+H, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 45: lbl81 -> lbl81 : D'=1+D, F'=free_2, H'=2+H, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 46: lbl81 -> lbl81 : D'=-1+D, F'=free_3, H'=2+H, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 47: lbl81 -> lbl81 : B'=1+B, F'=free_4, H'=2+H, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 48: lbl81 -> lbl81 : B'=-1+B, F'=free_5, H'=2+H, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 49: lbl81 -> lbl81 : D'=-1+D+A-H, F'=0, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 50: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 51: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 52: lbl81 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 53: lbl81 -> lbl81 : F'=free_1, H'=1+H, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=1+H ], cost: 2 18.71/8.38 18.71/8.38 54: lbl81 -> lbl81 : D'=1+D, F'=free_2, H'=2+H, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 55: lbl81 -> lbl81 : D'=-1+D, F'=free_3, H'=2+H, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 56: lbl81 -> lbl81 : B'=1+B, F'=free_4, H'=2+H, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 57: lbl81 -> lbl81 : B'=-1+B, F'=free_5, H'=2+H, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 4 18.71/8.38 18.71/8.38 58: lbl81 -> lbl81 : D'=-1+D+A-H, F'=0, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 59: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 60: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 61: lbl81 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 19: start0 -> lbl81 : B'=0, D'=0, F'=free, H'=1, J'=A, [ A>=1 ], cost: 2 18.71/8.38 18.71/8.38 29: start0 -> lbl81 : B'=0, D'=1, F'=free_2, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 31: start0 -> lbl81 : B'=0, D'=-1, F'=free_3, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 33: start0 -> lbl81 : B'=1, D'=0, F'=free_4, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 35: start0 -> lbl81 : B'=-1, D'=0, F'=free_5, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Applied pruning (of leafs and parallel rules): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 50: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 51: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 59: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 60: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 61: lbl81 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 33: start0 -> lbl81 : B'=1, D'=0, F'=free_4, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Accelerating simple loops of location 6. 18.71/8.38 18.71/8.38 Accelerating the following rules: 18.71/8.38 18.71/8.38 50: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 51: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 59: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 60: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 61: lbl81 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Found no metering function for rule 50. 18.71/8.38 18.71/8.38 Found no metering function for rule 51. 18.71/8.38 18.71/8.38 Found no metering function for rule 59. 18.71/8.38 18.71/8.38 Found no metering function for rule 60. 18.71/8.38 18.71/8.38 Found no metering function for rule 61. 18.71/8.38 18.71/8.38 Removing the simple loops:. 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Accelerated all simple loops using metering functions (where possible): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 50: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 51: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ 0>=1+F && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 59: lbl81 -> lbl81 : D'=1+D-A+H, F'=1, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 60: lbl81 -> lbl81 : B'=-1+A-H+B, F'=2, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 61: lbl81 -> lbl81 : B'=1-A+H+B, F'=3, H'=A, [ F>=4 && D+H>=1+B && H+B>=1+D && H>=1+D+B && D+H+B>=1 && J==A && A>=2+H ], cost: 2*A-2*H 18.71/8.38 18.71/8.38 33: start0 -> lbl81 : B'=1, D'=0, F'=free_4, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Chained accelerated rules (with incoming rules): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 33: start0 -> lbl81 : B'=1, D'=0, F'=free_4, H'=2, J'=A, [ A>=2 ], cost: 4 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 62: start0 -> lbl81 : B'=1, D'=3-A, F'=1, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 63: start0 -> lbl81 : B'=-2+A, D'=0, F'=2, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 64: start0 -> lbl81 : B'=1, D'=3-A, F'=1, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 65: start0 -> lbl81 : B'=-2+A, D'=0, F'=2, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 66: start0 -> lbl81 : B'=4-A, D'=0, F'=3, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Removed unreachable locations (and leaf rules with constant cost): 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 37: start0 -> lbl81 : B'=0, D'=-1+A, F'=0, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 39: start0 -> lbl81 : B'=0, D'=1-A, F'=1, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 41: start0 -> lbl81 : B'=-1+A, D'=0, F'=2, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 62: start0 -> lbl81 : B'=1, D'=3-A, F'=1, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 63: start0 -> lbl81 : B'=-2+A, D'=0, F'=2, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 64: start0 -> lbl81 : B'=1, D'=3-A, F'=1, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 65: start0 -> lbl81 : B'=-2+A, D'=0, F'=2, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 66: start0 -> lbl81 : B'=4-A, D'=0, F'=3, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 ### Computing asymptotic complexity ### 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Fully simplified ITS problem 18.71/8.38 18.71/8.38 Start location: start0 18.71/8.38 18.71/8.38 43: start0 -> lbl81 : B'=1-A, D'=0, F'=3, H'=A, J'=A, [ A>=2 ], cost: 2*A 18.71/8.38 18.71/8.38 66: start0 -> lbl81 : B'=4-A, D'=0, F'=3, H'=A, J'=A, [ A>=4 ], cost: 2*A 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Computing asymptotic complexity for rule 43 18.71/8.38 18.71/8.38 Solved the limit problem by the following transformations: 18.71/8.38 18.71/8.38 Created initial limit problem: 18.71/8.38 18.71/8.38 -1+A (+/+!), 2*A (+) [not solved] 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 removing all constraints (solved by SMT) 18.71/8.38 18.71/8.38 resulting limit problem: [solved] 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 applying transformation rule (C) using substitution {A==n} 18.71/8.38 18.71/8.38 resulting limit problem: 18.71/8.38 18.71/8.38 [solved] 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Solution: 18.71/8.38 18.71/8.38 A / n 18.71/8.38 18.71/8.38 Resulting cost 2*n has complexity: Poly(n^1) 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Found new complexity Poly(n^1). 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 Obtained the following overall complexity (w.r.t. the length of the input n): 18.71/8.38 18.71/8.38 Complexity: Poly(n^1) 18.71/8.38 18.71/8.38 Cpx degree: 1 18.71/8.38 18.71/8.38 Solved cost: 2*n 18.71/8.38 18.71/8.38 Rule cost: 2*A 18.71/8.38 18.71/8.38 Rule guard: [ A>=2 ] 18.71/8.38 18.71/8.38 18.71/8.38 18.71/8.38 WORST_CASE(Omega(n^1),?) 18.71/8.38 18.71/8.38 18.71/8.38 ---------------------------------------- 18.71/8.38 18.71/8.38 (4) 18.71/8.38 BOUNDS(n^1, INF) 18.77/9.46 EOF