YES(?,O(n^1)) * Step 1: TrivialSCCs WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (?,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (?,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (?,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (?,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,17,18,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11} ,8->{10},9->{6,16},10->{6,16},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20} ,18->{3,20},19->{3,20},20->{6,16}] + Applied Processor: TrivialSCCs + Details: All trivial SCCs of the transition graph admit timebound 1. * Step 2: UnsatPaths WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (?,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (?,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,17,18,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11} ,8->{10},9->{6,16},10->{6,16},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20} ,18->{3,20},19->{3,20},20->{6,16}] + Applied Processor: UnsatPaths + Details: We remove following edges from the transition graph: [(3,17),(3,18),(9,6),(10,16)] * Step 3: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (?,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (?,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x2 p(f12) = 1 + x1 + -1*x2 p(f15) = 1 + x1 + -1*x2 p(f28) = x1 + -1*x2 p(f30) = x1 + -1*x2 p(f42) = x1 + -1*x2 p(f59) = x1 + -1*x2 p(f69) = x1 + -1*x2 p(f71) = x1 + -1*x2 p(f73) = x1 + -1*x2 p(f82) = x1 + -1*x2 Following rules are strictly oriented: [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,0,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 4: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (?,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x2 p(f12) = 1 + x1 + -1*x2 p(f15) = 1 + x1 + -1*x2 p(f28) = x1 + -1*x2 p(f30) = x1 + -1*x2 p(f42) = x1 + -1*x2 p(f59) = x1 + -1*x2 p(f69) = x1 + -1*x2 p(f71) = x1 + -1*x2 p(f73) = x1 + -1*x2 p(f82) = x1 + -1*x2 Following rules are strictly oriented: [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,0,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 5: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x2 p(f12) = 1 + x1 + -1*x2 p(f15) = 1 + x1 + -1*x2 p(f28) = x1 + -1*x2 p(f30) = x1 + -1*x2 p(f42) = x1 + -1*x2 p(f59) = x1 + -1*x2 p(f69) = x1 + -1*x2 p(f71) = x1 + -1*x2 p(f73) = x1 + -1*x2 p(f82) = x1 + -1*x2 Following rules are strictly oriented: [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B > A + -1*B = f12(A,1 + B,0,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= 1 + A + -1*B = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*B >= A + -1*B = f82(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*B >= A + -1*B = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 6: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (?,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 7: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (?,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x4 p(f12) = 1 + x1 + -1*x4 p(f15) = 1 + x1 + -1*x4 p(f28) = 1 + x1 + -1*x4 p(f30) = 1 + x1 + -1*x4 p(f42) = x1 + -1*x4 p(f59) = x1 + -1*x4 p(f69) = x1 + -1*x4 p(f71) = x1 + -1*x4 p(f73) = x1 + -1*x4 p(f82) = 1 + x1 + -1*x4 Following rules are strictly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f42(A,B,0,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= A + -1*D = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= A + -1*D = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= 0 = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,0,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 8: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (?,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (?,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 9: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (?,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x8 p(f12) = 1 + x1 + -1*x8 p(f15) = 1 + x1 + -1*x8 p(f28) = 1 + x1 + -1*x8 p(f30) = 1 + x1 + -1*x8 p(f42) = 1 + x1 + -1*x8 p(f59) = 1 + x1 + -1*x8 p(f69) = 1 + x1 + -1*x8 p(f71) = 1 + x1 + -1*x8 p(f73) = 1 + x1 + -1*x8 p(f82) = 1 + x1 + -1*x8 Following rules are strictly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H > A + -1*H = f59(A,B,C,D,E,F,G,1 + H,L,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f12(A,1 + B,0,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*H >= 1 + A + -1*H = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 10: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (?,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (?,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 11: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (4 + 4*A + 3*D + H,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (?,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (3 + 3*A + 2*D + H,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x1 + -1*x4 p(f12) = x1 + -1*x4 p(f15) = x1 + -1*x4 p(f28) = x1 + -1*x4 p(f30) = x1 + -1*x4 p(f42) = x1 + -1*x4 p(f59) = x1 + -1*x4 p(f69) = x1 + -1*x4 p(f71) = x1 + -1*x4 p(f73) = x1 + -1*x4 p(f82) = x1 + -1*x4 Following rules are strictly oriented: [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D > -1 + A + -1*D = f28(A,B,C,1 + D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= -1 + A + -1*D = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= -1 + A + -1*D = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= -1 = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f12(A,1 + B,0,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 12: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (?,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (4 + 4*A + 3*D + H,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (?,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (?,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (?,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (A + D,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (3 + 3*A + 2*D + H,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 13: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (4 + 4*A + 3*D + H,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (4 + 4*A + 3*D + H,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (1 + A + D,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (8 + 8*A + 6*D + 2*H,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (8 + 8*A + 6*D + 2*H,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (A + D,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (3 + 3*A + 2*D + H,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x4 p(f12) = 1 + x1 + -1*x4 p(f15) = 1 + x1 + -1*x4 p(f28) = 1 + x1 + -1*x4 p(f30) = x1 + -1*x4 p(f42) = x1 + -1*x4 p(f59) = x1 + -1*x4 p(f69) = x1 + -1*x4 p(f71) = x1 + -1*x4 p(f73) = x1 + -1*x4 p(f82) = 1 + x1 + -1*x4 Following rules are strictly oriented: [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f30(A,B,C,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f15(A,B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= A + -1*D = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= 0 = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,0,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 14: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (4 + 4*A + 3*D + H,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (4 + 4*A + 3*D + H,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (?,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (1 + A + D,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (1 + A + D,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (8 + 8*A + 6*D + 2*H,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (8 + 8*A + 6*D + 2*H,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (A + D,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (3 + 3*A + 2*D + H,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 1 + x1 + -1*x4 p(f12) = 1 + x1 + -1*x4 p(f15) = 1 + x1 + -1*x4 p(f28) = 1 + x1 + -1*x4 p(f30) = x1 + -1*x4 p(f42) = x1 + -1*x4 p(f59) = x1 + -1*x4 p(f69) = x1 + -1*x4 p(f71) = x1 + -1*x4 p(f73) = x1 + -1*x4 p(f82) = 1 + x1 + -1*x4 Following rules are strictly oriented: [A + -1*B >= 0 && C >= L && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f15(A,B,L,1 + D,L,L,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D > A + -1*D = f30(A,B,C,D,E,F,G,H,I,J,K) Following rules are weakly oriented: [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] ==> f69(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f71(A,B,C,D,E,F,G,H,I,J,K) True ==> f0(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,B,C,D,E,F,G,H,I,J,K) [A >= B] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f15(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] ==> f71(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= 0 = f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] ==> f73(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] ==> f59(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 ==> && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] ==> f42(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] ==> f30(A,B,C,D,E,F,G,H,I,J,K) = A + -1*D >= A + -1*D = f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] ==> f28(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f82(A,B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] ==> f15(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f12(A,1 + B,0,D,E,F,G,H,I,J,K) [B >= 1 + A] ==> f12(A,B,C,D,E,F,G,H,I,J,K) = 1 + A + -1*D >= 1 + A + -1*D = f28(A,B,C,D,E,F,G,H,I,J,K) * Step 15: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && 0 >= 1 + L] (4 + 4*A + 3*D + H,1) 1. f69(A,B,C,D,E,F,G,H,I,J,K) -> f71(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0] (4 + 4*A + 3*D + H,1) 2. f0(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,B,C,D,E,F,G,H,I,J,K) True (1,1) 3. f12(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,0,D,E,F,G,H,I,J,K) [A >= B] (4 + 3*A + 3*B,1) 4. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,C,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && C >= L && A >= D] (1 + A + D,1) 5. f15(A,B,C,D,E,F,G,H,I,J,K) -> f15(A,B,L,1 + D,L,L,G,H,I,J,K) [A + -1*B >= 0 && L >= 1 + C && A >= D] (1 + A + D,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K) -> f30(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && A >= D] (1 + A + D,1) 7. f59(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,1 + H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= H] (1 + A + H,1) 8. f71(A,B,C,D,E,F,G,H,I,J,K) -> f73(A,B,C,D,E,F,G,H,L,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A >= 1 + D] (8 + 8*A + 6*D + 2*H,1) 9. f71(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + A,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && A = D] (8 + 8*A + 6*D + 2*H,1) 10. f73(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,1 + D,E,F,G,H,I,J,K) [-2 + B + -1*D >= 0 && -1 + A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A] (A + D,1) 11. f59(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && H >= 1 + A] (3 + 3*A + 2*D + H,1) 12. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && K >= 1 + D] 13. f42(A,B,C,D,E,F,G,H,I,J,K) -> f59(A,B,C,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 (1 + A + D,1) && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D >= 1 + K] 14. f42(A,B,C,D,E,F,G,H,I,J,K) -> f69(A,B,C,D,E,F,G,H,I,J,D) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1*C >= 0 && C >= 0 && -1 + -1*A + B >= 0 && B >= 1 + A && D = K] (1 + A + D,1) 15. f30(A,B,C,D,E,F,G,H,I,J,K) -> f42(A,B,0,D,E,F,G,H,I,J,K) [-1 + B + -1*D >= 0 && A + -1*D >= 0 && -1 + -1*A + B >= 0 && B >= D] (1 + A + D,1) 16. f28(A,B,C,D,E,F,G,H,I,J,K) -> f82(A,B,C,D,E,F,G,H,I,J,K) [-1 + -1*A + B >= 0 && D >= 1 + A] (1,1) 17. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && 0 >= 1 + C && D >= 1 + A] (1 + A + B,1) 18. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,C,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && C >= 1 && D >= 1 + A] (1 + A + B,1) 19. f15(A,B,C,D,E,F,G,H,I,J,K) -> f12(A,1 + B,0,D,E,F,G,H,I,J,K) [A + -1*B >= 0 && D >= 1 + A && C = 0] (1 + A + B,1) 20. f12(A,B,C,D,E,F,G,H,I,J,K) -> f28(A,B,C,D,E,F,G,H,I,J,K) [B >= 1 + A] (1,1) Signature: {(f0,11);(f12,11);(f15,11);(f28,11);(f30,11);(f42,11);(f59,11);(f69,11);(f71,11);(f73,11);(f82,11)} Flow Graph: [0->{8,9},1->{8,9},2->{3,20},3->{4,5,19},4->{4,5,17,18,19},5->{4,5,17,18,19},6->{15},7->{7,11},8->{10} ,9->{16},10->{6},11->{0,1},12->{7,11},13->{7,11},14->{0,1},15->{12,13,14},16->{},17->{3,20},18->{3,20} ,19->{3,20},20->{6,16}] + Applied Processor: KnowledgePropagation + Details: The problem is already solved. YES(?,O(n^1))