YES(?,O(n^1)) * Step 1: UnsatRules WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (?,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (?,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (?,1) 3. lbl161(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [0 >= 10 && 89 >= A && 0 >= 1 && D = 2 && H = A && F = 101 && B = 91] (?,1) 4. lbl161(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [0 >= 2 && 89 >= A && H = A && F = 101 && D = 1 && B = 91] (?,1) 5. lbl161(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [0 >= 1 && 89 >= A && H = A && F = 101 && D = 1 && B = 91] (?,1) 6. lbl161(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [0 >= 10 && 0 >= 2 && 89 >= A && H = A && F = 101 && D = 1 && B = 91] (?,1) 7. lbl221(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [1 >= D && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (?,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (?,1) 13. lbl111(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [A + 11*D >= 112 && 1 >= D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (?,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (?,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (?,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,13,14,15,16,17},2->{},3->{2,3,4,5,6},4->{7,8,9,10,11},5->{7,8,9,10,11},6->{7,8,9,10,11} ,7->{},8->{2,3,4,5,6},9->{7,8,9,10,11},10->{7,8,9,10,11},11->{7,8,9,10,11},12->{12,13,14,15,16,17},13->{} ,14->{2,3,4,5,6},15->{7,8,9,10,11},16->{7,8,9,10,11},17->{7,8,9,10,11},18->{0,1}] + Applied Processor: UnsatRules + Details: Following transitions have unsatisfiable constraints and are removed: [3,4,5,6,7,13] * Step 2: UnsatPaths WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (?,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (?,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (?,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (?,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (?,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (?,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (?,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,15,16,17},2->{},8->{2},9->{8,9,10,11},10->{8,9,10,11},11->{8,9,10,11},12->{12,14,15,16 ,17},14->{2},15->{8,9,10,11},16->{8,9,10,11},17->{8,9,10,11},18->{0,1}] + Applied Processor: UnsatPaths + Details: We remove following edges from the transition graph: [(1,15) ,(1,17) ,(9,8) ,(11,8) ,(11,11) ,(12,14) ,(14,2) ,(15,8) ,(16,8) ,(17,8) ,(17,11)] * Step 3: TrivialSCCs WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (?,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (?,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (?,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (?,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (?,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (?,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (?,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (?,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: TrivialSCCs + Details: All trivial SCCs of the transition graph admit timebound 1. * Step 4: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (1,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (1,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (1,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (1,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (?,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (1,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (1,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 112 + -11*x4 + -1*x8 p(lbl161) = -11 p(lbl221) = -11 + x1 + -1*x8 p(start) = 90 + -1*x1 p(start0) = 90 + -1*x1 p(stop) = 80 + -1*x2 Following rules are strictly oriented: [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] ==> lbl111(A,B,C,D,E,F,G,H) = 112 + -11*D + -1*H > 101 + -11*D + -1*H = lbl111(A,B,C,1 + D,E,11 + F,G,H) Following rules are weakly oriented: [A >= 101 && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 90 + -1*A >= 90 + -1*H = stop(A,-10 + H,C,1,E,H,G,H) [100 >= A && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 90 + -1*A >= 90 + -1*H = lbl111(A,B,C,2,E,11 + H,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] ==> lbl161(A,B,C,D,E,F,G,H) = -11 >= 80 + -1*B = stop(A,B,C,D,E,F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = -11 + A + -1*H >= -11 = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = -11 + A + -1*H >= -11 + A + -1*H = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = -11 + A + -1*H >= -11 + A + -1*H = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = -11 + A + -1*H >= -11 + A + -1*H = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] ==> lbl111(A,B,C,D,E,F,G,H) = 112 + -11*D + -1*H >= -11 = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [A + 11*D >= 112 ==> && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 112 + -11*D + -1*H >= -11 + A + -1*H = lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 ==> && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 112 + -11*D + -1*H >= -11 + A + -1*H = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] ==> lbl111(A,B,C,D,E,F,G,H) = 112 + -11*D + -1*H >= -11 + A + -1*H = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) True ==> start0(A,B,C,D,E,F,G,H) = 90 + -1*A >= 90 + -1*A = start(A,C,C,E,E,G,G,A) * Step 5: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (1,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (1,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (1,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (1,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (90 + A,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (1,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (1,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 934 + -2*x1 + -17*x4 + -1*x6 + -6*x8 p(lbl161) = 268 + -2*x1 + -1*x8 p(lbl221) = 361 + -3*x1 + 9*x4 + -1*x6 p(start) = 889 + x1 + -10*x8 p(start0) = 889 + -9*x1 p(stop) = 814 + x1 + -6*x2 + -4*x8 Following rules are strictly oriented: [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 361 + -3*A + 9*D + -1*F > 360 + -3*A + 9*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) Following rules are weakly oriented: [A >= 101 && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 889 + A + -10*H >= 874 + A + -10*H = stop(A,-10 + H,C,1,E,H,G,H) [100 >= A && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 889 + A + -10*H >= 889 + -2*A + -7*H = lbl111(A,B,C,2,E,11 + H,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] ==> lbl161(A,B,C,D,E,F,G,H) = 268 + -2*A + -1*H >= 814 + A + -6*B + -4*H = stop(A,B,C,D,E,F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 361 + -3*A + 9*D + -1*F >= 268 + -2*A + -1*H = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 361 + -3*A + 9*D + -1*F >= 360 + -3*A + 9*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 361 + -3*A + 9*D + -1*F >= 361 + -3*A + 9*D + -1*F = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] ==> lbl111(A,B,C,D,E,F,G,H) = 934 + -2*A + -17*D + -1*F + -6*H >= 906 + -2*A + -17*D + -1*F + -6*H = lbl111(A,B,C,1 + D,E,11 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] ==> lbl111(A,B,C,D,E,F,G,H) = 934 + -2*A + -17*D + -1*F + -6*H >= 268 + -2*A + -1*H = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [A + 11*D >= 112 ==> && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 934 + -2*A + -17*D + -1*F + -6*H >= 360 + -3*A + 9*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 ==> && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 934 + -2*A + -17*D + -1*F + -6*H >= 360 + -3*A + 9*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] ==> lbl111(A,B,C,D,E,F,G,H) = 934 + -2*A + -17*D + -1*F + -6*H >= 361 + -3*A + 9*D + -1*F = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) True ==> start0(A,B,C,D,E,F,G,H) = 889 + -9*A >= 889 + -9*A = start(A,C,C,E,E,G,G,A) * Step 6: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (1,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (1,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (1,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (1,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (889 + 9*A,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (?,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (90 + A,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (1,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (1,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 1701 + -9*x1 + 88*x4 + -8*x6 p(lbl161) = 801 + -9*x1 p(lbl221) = 800 + -9*x1 + x4 p(start) = 1789 + x1 + -18*x8 p(start0) = 1789 + -17*x1 p(stop) = 1449 + x1 + -16*x2 + 8*x6 + -10*x8 Following rules are strictly oriented: [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 800 + -9*A + D > 801 + -9*A = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 800 + -9*A + D > 799 + -9*A + D = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) Following rules are weakly oriented: [A >= 101 && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 1789 + A + -18*H >= 1609 + A + -18*H = stop(A,-10 + H,C,1,E,H,G,H) [100 >= A && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 1789 + A + -18*H >= 1789 + -9*A + -8*H = lbl111(A,B,C,2,E,11 + H,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] ==> lbl161(A,B,C,D,E,F,G,H) = 801 + -9*A >= 1449 + A + -16*B + 8*F + -10*H = stop(A,B,C,D,E,F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 800 + -9*A + D >= 800 + -9*A + D = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 800 + -9*A + D >= 800 + -9*A + D = lbl221(A,B,C,D,E,1 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] ==> lbl111(A,B,C,D,E,F,G,H) = 1701 + -9*A + 88*D + -8*F >= 1701 + -9*A + 88*D + -8*F = lbl111(A,B,C,1 + D,E,11 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] ==> lbl111(A,B,C,D,E,F,G,H) = 1701 + -9*A + 88*D + -8*F >= 801 + -9*A = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [A + 11*D >= 112 ==> && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 1701 + -9*A + 88*D + -8*F >= 800 + -9*A + D = lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 ==> && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 1701 + -9*A + 88*D + -8*F >= 800 + -9*A + D = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] ==> lbl111(A,B,C,D,E,F,G,H) = 1701 + -9*A + 88*D + -8*F >= 799 + -9*A + D = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) True ==> start0(A,B,C,D,E,F,G,H) = 1789 + -17*A >= 1789 + -17*A = start(A,C,C,E,E,G,G,A) * Step 7: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (1,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (1,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (1,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (1,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (?,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (889 + 9*A,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (1789 + 17*A,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (90 + A,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (1,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (1,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 90 + 11*x4 + -1*x6 p(lbl161) = -1*x1 + x8 p(lbl221) = 90 + 11*x4 + -1*x6 p(start) = 101 + -1*x8 p(start0) = 101 + -1*x1 p(stop) = 91 + -1*x1 + -1*x2 + x8 Following rules are strictly oriented: [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > -1*A + H = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > 89 + 11*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > 89 + 11*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] ==> lbl111(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > -1*A + H = lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [A + 11*D >= 112 ==> && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > 89 + 11*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] ==> lbl111(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F > 88 + 11*D + -1*F = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) Following rules are weakly oriented: [A >= 101 && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 101 + -1*H >= 101 + -1*A = stop(A,-10 + H,C,1,E,H,G,H) [100 >= A && B = C && D = E && F = G && H = A] ==> start(A,B,C,D,E,F,G,H) = 101 + -1*H >= 101 + -1*H = lbl111(A,B,C,2,E,11 + H,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] ==> lbl161(A,B,C,D,E,F,G,H) = -1*A + H >= 91 + -1*A + -1*B + H = stop(A,B,C,D,E,F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] ==> lbl221(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F >= 88 + 11*D + -1*F = lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] ==> lbl111(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F >= 90 + 11*D + -1*F = lbl111(A,B,C,1 + D,E,11 + F,G,H) [A + 11*D >= 112 ==> && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] lbl111(A,B,C,D,E,F,G,H) = 90 + 11*D + -1*F >= 89 + 11*D + -1*F = lbl221(A,B,C,D,E,1 + F,G,H) True ==> start0(A,B,C,D,E,F,G,H) = 101 + -1*A >= 101 + -1*A = start(A,C,C,E,E,G,G,A) * Step 8: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F,G,H) -> stop(A,-10 + H,C,1,E,H,G,H) [A >= 101 && B = C && D = E && F = G && H = A] (1,1) 1. start(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,2,E,11 + H,G,H) [100 >= A && B = C && D = E && F = G && H = A] (1,1) 2. lbl161(A,B,C,D,E,F,G,H) -> stop(A,B,C,D,E,F,G,H) [89 >= A && D = 1 && H = A && F = 101 && B = 91] (1,1) 8. lbl221(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [99 >= A && 89 >= A && F = 111 && D = 2 && H = A && B = C] (1,1) 9. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 3 && 110 >= F && D >= 2 && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (101 + A,1) 10. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [D >= 2 && 110 >= F && F >= 102 && 111 >= F && 10 + F >= A + 11*D && 89 >= A && H = A && B = C] (889 + 9*A,1) 11. lbl221(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && D >= 2 && 121 >= A + 11*D && 89 >= A && F = 111 && H = A && B = C] (1789 + 17*A,1) 12. lbl111(A,B,C,D,E,F,G,H) -> lbl111(A,B,C,1 + D,E,11 + F,G,H) [111 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] (90 + A,1) 14. lbl111(A,B,C,D,E,F,G,H) -> lbl161(A,-20 + F,C,-1 + D,E,-10 + F,G,H) [F = 111 && D = 2 && H = 100 && B = C && A = 100] (1,1) 15. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 3 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 16. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,D,E,1 + F,G,H) [A + 11*D >= 112 (1,1) && D >= 2 && 121 >= A + 11*D && 122 >= A + 11*D && 11*D >= 22 && H = A && B = C && 11 + F = A + 11*D] 17. lbl111(A,B,C,D,E,F,G,H) -> lbl221(A,B,C,-1 + D,E,-9 + F,G,H) [D >= 3 && 11*D >= 22 && F = 111 && 11*D + H = 122 && B = C && A + 11*D = 122] (1,1) 18. start0(A,B,C,D,E,F,G,H) -> start(A,C,C,E,E,G,G,A) True (1,1) Signature: {(lbl111,8);(lbl161,8);(lbl221,8);(start,8);(start0,8);(stop,8)} Flow Graph: [0->{},1->{12,14,16},2->{},8->{2},9->{9,10,11},10->{8,9,10,11},11->{9,10},12->{12,15,16,17},14->{},15->{9 ,10,11},16->{9,10,11},17->{9,10},18->{0,1}] + Applied Processor: KnowledgePropagation + Details: The problem is already solved. YES(?,O(n^1))