YES(?,O(n^1)) * Step 1: UnsatRules WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (?,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (?,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (?,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (?,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 5. lbl91(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 && 39 >= E && E >= 1 && 40 >= E && C = 100 && A = 0 && B = 0] (?,1) 6. lbl91(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 && 39 >= E && E >= 1 && 40 >= E && C = 100 && A = 0 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 8. lbl111(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 2 && 41 >= E && A = 0 && C = 100 && B = 0] (?,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{3,4,5,6},1->{7,8,9,10},2->{7,8,9,10},3->{},4->{3,4,5,6},5->{7,8,9,10},6->{7,8,9,10},7->{},8->{3,4,5 ,6},9->{7,8,9,10},10->{7,8,9,10},11->{0,1,2}] + Applied Processor: UnsatRules + Details: Following transitions have unsatisfiable constraints and are removed: [5,6] * Step 2: UnsatPaths WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (?,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (?,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (?,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (?,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 8. lbl111(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 2 && 41 >= E && A = 0 && C = 100 && B = 0] (?,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{3,4},1->{7,8,9,10},2->{7,8,9,10},3->{},4->{3,4},7->{},8->{3,4},9->{7,8,9,10},10->{7,8,9,10},11->{0,1 ,2}] + Applied Processor: UnsatPaths + Details: We remove following edges from the transition graph: [(0,3) ,(1,7) ,(1,8) ,(1,10) ,(2,7) ,(2,8) ,(2,9) ,(9,8) ,(9,10) ,(10,8) ,(10,9)] * Step 3: UnreachableRules WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (?,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (?,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (?,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (?,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 8. lbl111(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 2 && 41 >= E && A = 0 && C = 100 && B = 0] (?,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},8->{3,4},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: UnreachableRules + Details: Following transitions are not reachable from the starting states and are revomed: [8] * Step 4: TrivialSCCs WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (?,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (?,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (?,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (?,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: TrivialSCCs + Details: All trivial SCCs of the transition graph admit timebound 1. * Step 5: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (1,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (1,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (1,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (1,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (1,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 2 + 152*x2 + -1*x5 p(lbl91) = 152*x1 p(start) = 152*x1 p(start0) = 152*x2 p(stop) = -39 + 152*x2 Following rules are strictly oriented: [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + 152*B + -1*E > 152*B + -1*E = lbl111(A,B,C,D,2 + E,F) Following rules are weakly oriented: [A = 0 && B = 0 && C = D && E = F] ==> start(A,B,C,D,E,F) = 152*A >= 152*A = lbl91(A,B,100,D,1,F) [0 >= 1 + B && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = 152*A >= 152*B = lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = 152*A >= 152*B = lbl111(A,B,100,D,2,F) [E = 40 && C = 100 && A = 0 && B = 0] ==> lbl91(A,B,C,D,E,F) = 152*A >= -39 + 152*B = stop(A,B,C,D,E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] ==> lbl91(A,B,C,D,E,F) = 152*A >= 152*A = lbl91(A,B,C,D,1 + E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + 152*B + -1*E >= -39 + 152*B = stop(A,B,C,D,E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + 152*B + -1*E >= 152*B + -1*E = lbl111(A,B,C,D,2 + E,F) True ==> start0(A,B,C,D,E,F) = 152*B >= 152*B = start(B,B,D,D,F,F) * Step 6: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (1,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (1,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (1,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (1,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (1,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (?,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (152*B,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 2 + -38*x2 + -1*x5 p(lbl91) = -38*x1 p(start) = -38*x1 p(start0) = -38*x2 p(stop) = -39 + -38*x2 Following rules are strictly oriented: [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + -38*B + -1*E > -38*B + -1*E = lbl111(A,B,C,D,2 + E,F) Following rules are weakly oriented: [A = 0 && B = 0 && C = D && E = F] ==> start(A,B,C,D,E,F) = -38*A >= -38*A = lbl91(A,B,100,D,1,F) [0 >= 1 + B && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = -38*A >= -38*B = lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = -38*A >= -38*B = lbl111(A,B,100,D,2,F) [E = 40 && C = 100 && A = 0 && B = 0] ==> lbl91(A,B,C,D,E,F) = -38*A >= -39 + -38*B = stop(A,B,C,D,E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] ==> lbl91(A,B,C,D,E,F) = -38*A >= -38*A = lbl91(A,B,C,D,1 + E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + -38*B + -1*E >= -39 + -38*B = stop(A,B,C,D,E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 2 + -38*B + -1*E >= -38*B + -1*E = lbl111(A,B,C,D,2 + E,F) True ==> start0(A,B,C,D,E,F) = -38*B >= -38*B = start(B,B,D,D,F,F) * Step 7: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (1,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (1,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (1,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (1,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (?,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (1,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (38*B,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (152*B,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(lbl111) = 39 p(lbl91) = 41 + -1*x5 p(start) = 40 p(start0) = 40 p(stop) = 41 + -1*x5 Following rules are strictly oriented: [0 >= 1 + B && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = 40 > 39 = lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] ==> start(A,B,C,D,E,F) = 40 > 39 = lbl111(A,B,100,D,2,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] ==> lbl91(A,B,C,D,E,F) = 41 + -1*E > 40 + -1*E = lbl91(A,B,C,D,1 + E,F) Following rules are weakly oriented: [A = 0 && B = 0 && C = D && E = F] ==> start(A,B,C,D,E,F) = 40 >= 40 = lbl91(A,B,100,D,1,F) [E = 40 && C = 100 && A = 0 && B = 0] ==> lbl91(A,B,C,D,E,F) = 41 + -1*E >= 41 + -1*E = stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 39 >= 41 + -1*E = stop(A,B,C,D,E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 39 >= 39 = lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] ==> lbl111(A,B,C,D,E,F) = 39 >= 39 = lbl111(A,B,C,D,2 + E,F) True ==> start0(A,B,C,D,E,F) = 40 >= 40 = start(B,B,D,D,F,F) * Step 8: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. start(A,B,C,D,E,F) -> lbl91(A,B,100,D,1,F) [A = 0 && B = 0 && C = D && E = F] (1,1) 1. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [0 >= 1 + B && A = B && C = D && E = F] (1,1) 2. start(A,B,C,D,E,F) -> lbl111(A,B,100,D,2,F) [B >= 1 && A = B && C = D && E = F] (1,1) 3. lbl91(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E = 40 && C = 100 && A = 0 && B = 0] (1,1) 4. lbl91(A,B,C,D,E,F) -> lbl91(A,B,C,D,1 + E,F) [39 >= E && E >= 1 && 40 >= E && A = 0 && C = 100 && B = 0] (40,1) 7. lbl111(A,B,C,D,E,F) -> stop(A,B,C,D,E,F) [E >= 40 && E >= 2 && 41 >= E && C = 100 && A = B] (1,1) 9. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [0 >= 1 + B && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (38*B,1) 10. lbl111(A,B,C,D,E,F) -> lbl111(A,B,C,D,2 + E,F) [B >= 1 && 39 >= E && E >= 2 && 41 >= E && C = 100 && A = B] (152*B,1) 11. start0(A,B,C,D,E,F) -> start(B,B,D,D,F,F) True (1,1) Signature: {(lbl111,6);(lbl91,6);(start,6);(start0,6);(stop,6)} Flow Graph: [0->{4},1->{9},2->{10},3->{},4->{3,4},7->{},9->{7,9},10->{7,10},11->{0,1,2}] + Applied Processor: KnowledgePropagation + Details: The problem is already solved. YES(?,O(n^1))