/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, 584 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 1775 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, H - 10, C, 1, E, H, G, H)) :|: A >= 101 && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A start(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, 2, E, 11 + H, G, H)) :|: 100 >= A && B >= C && B <= C && D >= E && D <= E && F >= G && F <= G && H >= A && H <= A lbl161(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 89 >= A && D >= 1 && D <= 1 && H >= A && H <= A && F >= 101 && F <= 101 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: 0 >= 10 && 89 >= A && 0 >= 1 && D >= 2 && D <= 2 && H >= A && H <= A && F >= 101 && F <= 101 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 0 >= 2 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 0 >= 1 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl161(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: 0 >= 10 && 0 >= 2 && 89 >= A && H >= A && H <= A && F >= 101 && F <= 101 && D >= 1 && D <= 1 && B >= 91 && B <= 91 lbl221(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 1 >= D && D >= 2 && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: 99 >= A && 89 >= A && F >= 111 && F <= 111 && D >= 2 && D <= 2 && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: D >= 2 && 110 >= F && F >= 102 && 111 >= F && F + 10 >= A + 11 * D && 89 >= A && H >= A && H <= A && B >= C && B <= C lbl221(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: D >= 3 && D >= 2 && 121 >= A + 11 * D && 89 >= A && F >= 111 && F <= 111 && H >= A && H <= A && B >= C && B <= C lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl111(A, B, C, 1 + D, E, 11 + F, G, H)) :|: 111 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E, F, G, H)) :|: 11 * D + A >= 112 && 1 >= D && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl161(A, F - 20, C, D - 1, E, F - 10, G, H)) :|: F >= 111 && F <= 111 && D >= 2 && D <= 2 && H >= 100 && H <= 100 && B >= C && B <= C && A >= 100 && A <= 100 lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 11 * D + A >= 112 && D >= 3 && 121 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D, E, 1 + F, G, H)) :|: 11 * D + A >= 112 && D >= 2 && 121 >= 11 * D + A && 122 >= 11 * D + A && 11 * D >= 22 && H >= A && H <= A && B >= C && B <= C && F + 11 >= 11 * D + A && F + 11 <= 11 * D + A lbl111(A, B, C, D, E, F, G, H) -> Com_1(lbl221(A, B, C, D - 1, E, F - 9, G, H)) :|: D >= 3 && 11 * D >= 22 && F >= 111 && F <= 111 && H + 11 * D >= 122 && H + 11 * D <= 122 && B >= C && B <= C && A + 11 * D >= 122 && A + 11 * D <= 122 start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, E, E, G, G, A)) :|: TRUE The start-symbols are:[start0_8] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 8*Ar_0 + 819) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_7 - 10, Ar_2, 1, Ar_4, Ar_7, Ar_6, Ar_7)) [ Ar_0 >= 101 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: ?, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, 2, Ar_4, Ar_7 + 11, Ar_6, Ar_7)) [ 100 >= Ar_0 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 0 >= 10 /\ 89 >= Ar_0 /\ 0 >= 1 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 0 >= 2 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 0 >= 1 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ 0 >= 10 /\ 0 >= 2 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 1 >= Ar_3 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ 1 >= Ar_3 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = 100 /\ Ar_1 = Ar_2 /\ Ar_0 = 100 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] (Comp: ?, Cost: 1) start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start(Ar_0, Ar_2, Ar_2, Ar_4, Ar_4, Ar_6, Ar_6, Ar_0)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Testing for reachability in the complexity graph removes the following transitions from problem 1: lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 0 >= 10 /\ 89 >= Ar_0 /\ 0 >= 1 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 0 >= 2 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 0 >= 1 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ 0 >= 10 /\ 0 >= 2 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_3 = 1 /\ Ar_1 = 91 ] lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 1 >= Ar_3 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ 1 >= Ar_3 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] We thus obtain the following problem: 2: T: (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = 100 /\ Ar_1 = Ar_2 /\ Ar_0 = 100 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, 2, Ar_4, Ar_7 + 11, Ar_6, Ar_7)) [ 100 >= Ar_0 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: ?, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_7 - 10, Ar_2, 1, Ar_4, Ar_7, Ar_6, Ar_7)) [ Ar_0 >= 101 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: ?, Cost: 1) start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start(Ar_0, Ar_2, Ar_2, Ar_4, Ar_4, Ar_6, Ar_6, Ar_0)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: ?, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = 100 /\ Ar_1 = Ar_2 /\ Ar_0 = 100 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, 2, Ar_4, Ar_7 + 11, Ar_6, Ar_7)) [ 100 >= Ar_0 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_7 - 10, Ar_2, 1, Ar_4, Ar_7, Ar_6, Ar_7)) [ Ar_0 >= 101 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start(Ar_0, Ar_2, Ar_2, Ar_4, Ar_4, Ar_6, Ar_6, Ar_0)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(lbl161) = 1 Pol(stop) = 0 Pol(lbl221) = 2 Pol(lbl111) = 3 Pol(start) = 3 Pol(start0) = 3 Pol(koat_start) = 3 orients all transitions weakly and the transitions lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] strictly and produces the following problem: 4: T: (Comp: 3, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: 3, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: ?, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = 100 /\ Ar_1 = Ar_2 /\ Ar_0 = 100 ] (Comp: ?, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, 2, Ar_4, Ar_7 + 11, Ar_6, Ar_7)) [ 100 >= Ar_0 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_7 - 10, Ar_2, 1, Ar_4, Ar_7, Ar_6, Ar_7)) [ Ar_0 >= 101 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start(Ar_0, Ar_2, Ar_2, Ar_4, Ar_4, Ar_6, Ar_6, Ar_0)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(lbl161) = V_1 + V_2 - 2*V_6 - V_8 + 111 Pol(stop) = -V_1 - 2*V_6 + V_8 + 200 Pol(lbl221) = 11*V_4 - V_6 + 90 Pol(lbl111) = -11*V_4 - 2*V_8 + 222 Pol(start) = -V_1 - V_8 + 200 Pol(start0) = -2*V_1 + 200 Pol(koat_start) = -2*V_1 + 200 orients all transitions weakly and the transitions lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] strictly and produces the following problem: 5: T: (Comp: 3, Cost: 1) lbl161(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 89 >= Ar_0 /\ Ar_3 = 1 /\ Ar_7 = Ar_0 /\ Ar_5 = 101 /\ Ar_1 = 91 ] (Comp: 3, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ 99 >= Ar_0 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: 2*Ar_0 + 200, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ Ar_3 >= 2 /\ 121 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_5 = 111 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: 2*Ar_0 + 200, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 2 /\ 110 >= Ar_5 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: 2*Ar_0 + 200, Cost: 1) lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 110 >= Ar_5 /\ Ar_3 >= 2 /\ Ar_5 >= 102 /\ 111 >= Ar_5 /\ Ar_5 + 10 >= Ar_0 + 11*Ar_3 /\ 89 >= Ar_0 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 9, Ar_6, Ar_7)) [ Ar_3 >= 3 /\ 11*Ar_3 >= 22 /\ Ar_5 = 111 /\ Ar_7 + 11*Ar_3 = 122 /\ Ar_1 = Ar_2 /\ Ar_0 + 11*Ar_3 = 122 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 3 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 3, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl221(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5 + 1, Ar_6, Ar_7)) [ 11*Ar_3 + Ar_0 >= 112 /\ Ar_3 >= 2 /\ 121 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl161(Ar_0, Ar_5 - 20, Ar_2, Ar_3 - 1, Ar_4, Ar_5 - 10, Ar_6, Ar_7)) [ Ar_5 = 111 /\ Ar_3 = 2 /\ Ar_7 = 100 /\ Ar_1 = Ar_2 /\ Ar_0 = 100 ] (Comp: 2*Ar_0 + 200, Cost: 1) lbl111(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, Ar_3 + 1, Ar_4, Ar_5 + 11, Ar_6, Ar_7)) [ 111 >= 11*Ar_3 + Ar_0 /\ 122 >= 11*Ar_3 + Ar_0 /\ 11*Ar_3 >= 22 /\ Ar_7 = Ar_0 /\ Ar_1 = Ar_2 /\ Ar_5 + 11 = 11*Ar_3 + Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(lbl111(Ar_0, Ar_1, Ar_2, 2, Ar_4, Ar_7 + 11, Ar_6, Ar_7)) [ 100 >= Ar_0 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(stop(Ar_0, Ar_7 - 10, Ar_2, 1, Ar_4, Ar_7, Ar_6, Ar_7)) [ Ar_0 >= 101 /\ Ar_1 = Ar_2 /\ Ar_3 = Ar_4 /\ Ar_5 = Ar_6 /\ Ar_7 = Ar_0 ] (Comp: 1, Cost: 1) start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start(Ar_0, Ar_2, Ar_2, Ar_4, Ar_4, Ar_6, Ar_6, Ar_0)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7) -> Com_1(start0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4, Ar_5, Ar_6, Ar_7)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 8*Ar_0 + 819 Time: 0.543 sec (SMT: 0.427 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: start0 0: start -> stop : B'=-10+H, D'=1, F'=H, [ A>=101 && B==C && D==E && F==G && H==A ], cost: 1 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 2: lbl161 -> stop : [ 89>=A && D==1 && H==A && F==101 && B==91 ], cost: 1 3: lbl161 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ 0>=10 && 89>=A && 0>=1 && D==2 && H==A && F==101 && B==91 ], cost: 1 4: lbl161 -> lbl221 : F'=1+F, [ 0>=2 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 5: lbl161 -> lbl221 : F'=1+F, [ 0>=1 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 6: lbl161 -> lbl221 : D'=-1+D, F'=-9+F, [ 0>=10 && 0>=2 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 7: lbl221 -> stop : [ 1>=D && D>=2 && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 8: lbl221 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ 99>=A && 89>=A && F==111 && D==2 && H==A && B==C ], cost: 1 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && D>=2 && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && D>=2 && 121>=11*D+A && 89>=A && F==111 && H==A && B==C ], cost: 1 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 13: lbl111 -> stop : [ 11*D+A>=112 && 1>=D && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 14: lbl111 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ F==111 && D==2 && H==100 && B==C && A==100 ], cost: 1 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 11*D>=22 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Removed unreachable and leaf rules: Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 3: lbl161 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ 0>=10 && 89>=A && 0>=1 && D==2 && H==A && F==101 && B==91 ], cost: 1 4: lbl161 -> lbl221 : F'=1+F, [ 0>=2 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 5: lbl161 -> lbl221 : F'=1+F, [ 0>=1 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 6: lbl161 -> lbl221 : D'=-1+D, F'=-9+F, [ 0>=10 && 0>=2 && 89>=A && H==A && F==101 && D==1 && B==91 ], cost: 1 8: lbl221 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ 99>=A && 89>=A && F==111 && D==2 && H==A && B==C ], cost: 1 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && D>=2 && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && D>=2 && 121>=11*D+A && 89>=A && F==111 && H==A && B==C ], cost: 1 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 14: lbl111 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ F==111 && D==2 && H==100 && B==C && A==100 ], cost: 1 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 11*D>=22 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Removed rules with unsatisfiable guard: Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 8: lbl221 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ 99>=A && 89>=A && F==111 && D==2 && H==A && B==C ], cost: 1 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && D>=2 && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && D>=2 && 121>=11*D+A && 89>=A && F==111 && H==A && B==C ], cost: 1 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 14: lbl111 -> lbl161 : B'=-20+F, D'=-1+D, F'=-10+F, [ F==111 && D==2 && H==100 && B==C && A==100 ], cost: 1 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 11*D>=22 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Removed unreachable and leaf rules: Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && D>=2 && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 111>=F && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && D>=2 && 121>=11*D+A && 89>=A && F==111 && H==A && B==C ], cost: 1 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && 122>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 11*D>=22 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Simplified all rules, resulting in: Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && F>=102 && 10+F>=11*D+A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 121>=11*D+A && F==111 && H==A && B==C ], cost: 1 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 2. Accelerating the following rules: 9: lbl221 -> lbl221 : F'=1+F, [ D>=3 && 110>=F && F>=102 && 10+F>=11*D+A && H==A && B==C ], cost: 1 10: lbl221 -> lbl221 : F'=1+F, [ D>=2 && 110>=F && F>=102 && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 1 11: lbl221 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && 121>=11*D+A && F==111 && H==A && B==C ], cost: 1 Accelerated rule 9 with metering function 111-F, yielding the new rule 19. Accelerated rule 10 with metering function 111-F, yielding the new rule 20. Accelerated rule 11 with metering function meter (where 9*meter==-111+F), yielding the new rule 21. Removing the simple loops: 9 10 11. Accelerating simple loops of location 3. Accelerating the following rules: 12: lbl111 -> lbl111 : D'=1+D, F'=11+F, [ 111>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A ], cost: 1 Accelerated rule 12 with metering function meter_3 (where 11*meter_3==112-11*D-A), yielding the new rule 22. Removing the simple loops: 12. Accelerated all simple loops using metering functions (where possible): Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 19: lbl221 -> lbl221 : F'=111, [ D>=3 && 110>=F && F>=102 && 10+F>=11*D+A && H==A && B==C ], cost: 111-F 20: lbl221 -> lbl221 : F'=111, [ D>=2 && 110>=F && F>=102 && 10+F>=11*D+A && 89>=A && H==A && B==C ], cost: 111-F 21: lbl221 -> lbl221 : D'=D-meter, F'=F-9*meter, [ D>=3 && 121>=11*D+A && F==111 && H==A && B==C && 9*meter==-111+F && meter>=1 ], cost: meter 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 22: lbl111 -> lbl111 : D'=D+meter_3, F'=F+11*meter_3, [ 111>=11*D+A && 11*D>=22 && H==A && B==C && 11+F==11*D+A && 11*meter_3==112-11*D-A && meter_3>=1 ], cost: meter_3 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Chained accelerated rules (with incoming rules): Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 29: start -> lbl111 : D'=2+meter_3, F'=11+11*meter_3+H, [ B==C && D==E && F==G && H==A && 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 1+meter_3 15: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 16: lbl111 -> lbl221 : F'=1+F, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A ], cost: 1 17: lbl111 -> lbl221 : D'=-1+D, F'=-9+F, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 ], cost: 1 23: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 ], cost: 111-F 24: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && D>=3 && 110>=1+F && 1+F>=102 ], cost: 111-F 25: lbl111 -> lbl221 : D'=-1+D, F'=111, [ F==111 && 11*D+H==122 && B==C && 11*D+A==122 && -1+D>=3 && 1+F>=-11+11*D+A && H==A ], cost: 121-F 26: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 27: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 28: lbl111 -> lbl221 : D'=-1+D, F'=111, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 && 1+F>=-11+11*D+A && 89>=A && H==A ], cost: 121-F 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Removed unreachable locations (and leaf rules with constant cost): Start location: start0 1: start -> lbl111 : D'=2, F'=11+H, [ 100>=A && B==C && D==E && F==G && H==A ], cost: 1 29: start -> lbl111 : D'=2+meter_3, F'=11+11*meter_3+H, [ B==C && D==E && F==G && H==A && 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 1+meter_3 23: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 ], cost: 111-F 24: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && D>=3 && 110>=1+F && 1+F>=102 ], cost: 111-F 25: lbl111 -> lbl221 : D'=-1+D, F'=111, [ F==111 && 11*D+H==122 && B==C && 11*D+A==122 && -1+D>=3 && 1+F>=-11+11*D+A && H==A ], cost: 121-F 26: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 27: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 28: lbl111 -> lbl221 : D'=-1+D, F'=111, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 && 1+F>=-11+11*D+A && 89>=A && H==A ], cost: 121-F 18: start0 -> start : B'=C, D'=E, F'=G, H'=A, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: start0 23: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 ], cost: 111-F 24: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && D>=3 && 110>=1+F && 1+F>=102 ], cost: 111-F 25: lbl111 -> lbl221 : D'=-1+D, F'=111, [ F==111 && 11*D+H==122 && B==C && 11*D+A==122 && -1+D>=3 && 1+F>=-11+11*D+A && H==A ], cost: 121-F 26: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 27: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=2 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 28: lbl111 -> lbl221 : D'=-1+D, F'=111, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 && 1+F>=-11+11*D+A && 89>=A && H==A ], cost: 121-F 30: start0 -> lbl111 : B'=C, D'=2, F'=11+A, H'=A, [ 100>=A ], cost: 2 31: start0 -> lbl111 : B'=C, D'=2+meter_3, F'=11+A+11*meter_3, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 2+meter_3 Applied pruning (of leafs and parallel rules): Start location: start0 23: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 ], cost: 111-F 24: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && D>=3 && 110>=1+F && 1+F>=102 ], cost: 111-F 25: lbl111 -> lbl221 : D'=-1+D, F'=111, [ F==111 && 11*D+H==122 && B==C && 11*D+A==122 && -1+D>=3 && 1+F>=-11+11*D+A && H==A ], cost: 121-F 26: lbl111 -> lbl221 : F'=111, [ 11*D+A>=112 && D>=3 && 121>=11*D+A && H==A && B==C && 11+F==11*D+A && 110>=1+F && 1+F>=102 && 89>=A ], cost: 111-F 28: lbl111 -> lbl221 : D'=-1+D, F'=111, [ D>=3 && F==111 && 11*D+H==122 && B==C && 11*D+A==122 && 1+F>=-11+11*D+A && 89>=A && H==A ], cost: 121-F 30: start0 -> lbl111 : B'=C, D'=2, F'=11+A, H'=A, [ 100>=A ], cost: 2 31: start0 -> lbl111 : B'=C, D'=2+meter_3, F'=11+A+11*meter_3, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 2+meter_3 Eliminated locations (on tree-shaped paths): Start location: start0 32: start0 -> lbl221 : B'=C, D'=2+meter_3, F'=111, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 102-A-10*meter_3 33: start0 -> lbl221 : B'=C, D'=2+meter_3, F'=111, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 102-A-10*meter_3 34: start0 -> lbl221 : B'=C, D'=2+meter_3, F'=111, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 102-A-10*meter_3 35: start0 -> [8] : [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 2+meter_3 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: start0 34: start0 -> lbl221 : B'=C, D'=2+meter_3, F'=111, H'=A, [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 102-A-10*meter_3 35: start0 -> [8] : [ 111>=22+A && 11*meter_3==90-A && meter_3>=1 ], cost: 2+meter_3 Computing asymptotic complexity for rule 34 Solved the limit problem by the following transformations: Created initial limit problem: 91-A-11*meter_3 (+/+!), 102-A-10*meter_3 (+), -89+A+11*meter_3 (+/+!), 90-A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==90-11*n,meter_3==n} resulting limit problem: [solved] Solution: A / 90-11*n meter_3 / n Resulting cost 12+n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 35 Solved the limit problem by the following transformations: Created initial limit problem: 91-A-11*meter_3 (+/+!), 2+meter_3 (+), -89+A+11*meter_3 (+/+!), 90-A (+/+!) [not solved] applying transformation rule (C) using substitution {A==90-11*meter_3} resulting limit problem: 1 (+/+!), 11*meter_3 (+/+!), 2+meter_3 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 11*meter_3 (+/+!), 2+meter_3 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_3==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 91-A-11*meter_3 (+/+!), 2+meter_3 (+), -89+A+11*meter_3 (+/+!), 90-A (+/+!) [not solved] applying transformation rule (C) using substitution {A==90-11*meter_3} resulting limit problem: 1 (+/+!), 11*meter_3 (+/+!), 2+meter_3 (+) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 11*meter_3 (+/+!), 2+meter_3 (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {meter_3==n} resulting limit problem: [solved] Solution: A / 90-11*n meter_3 / n Resulting cost 2+n has 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: 12+n Rule cost: 102-A-10*meter_3 Rule guard: [ 111>=22+A && 11*meter_3==90-A ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)