YES(?,O(n^1)) * Step 1: ArgumentFilter WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f10(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [A >= 2] (1,1) 1. f10(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f73(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-2 + A >= 0 && B >= A] (?,1) 2. f10(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f73(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (?,1) 3. f10(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f13(A,B,0,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f10(A,1 + B,0,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,0) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f13(A,B,S,1 + D,C,S,S,H,I,J,K,L,M,N,O,P,Q,R) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f13(A,B,C,1 + D,C,S,S,H,I,J,K,L,M,N,O,P,Q,R) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f29(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f29(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f34(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f53(A,B,C,D,E,F,G,H,I,J,K,L,M,N,-1*S,T,S,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f53(A,B,C,D,E,F,G,H,I,J,K,L,S,T,T,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f10(A,1 + B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f55(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f61(A,B,C,D,E,F,G,H,I,J,K,S,M,N,O,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R) -> f53(A,B,C,D,E,F,G,H,I,J,1 + K,L,M,N,O,P,Q,R) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6,7,8},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: ArgumentFilter [4,5,6,7,8,9,11,12,13,14,15,16,17] + Details: We remove following argument positions: [4,5,6,7,8,9,11,12,13,14,15,16,17]. * Step 2: TrivialSCCs WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (?,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (?,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6,7,8},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: TrivialSCCs + Details: All trivial SCCs of the transition graph admit timebound 1. * Step 3: UnsatPaths WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6,7,8},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: UnsatPaths + Details: We remove following edges from the transition graph: [(3,7),(3,8)] * Step 4: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x1 + -1*x5 + x18 p(f10) = x1 + -1*x5 + x18 p(f13) = x1 + -1*x5 + x18 p(f29) = x1 + -1*x5 + x18 p(f34) = x1 + -1*x5 + x18 p(f53) = x1 + -1*x5 + x18 p(f55) = x1 + -1*x5 + x18 p(f61) = x1 + -1*x5 + x18 p(f73) = x1 + -1*x5 + x18 Following rules are strictly oriented: [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = 1 + A + -1*K > A + -1*K = f53(A,B,C,D,1 + K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f34(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,1 + B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f61(A,B,C,D,K) * Step 5: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x1 + -1*x5 + x18 p(f10) = x1 + -1*x5 + x18 p(f13) = x1 + -1*x5 + x18 p(f29) = x1 + -1*x5 + x18 p(f34) = x1 + -1*x5 + x18 p(f53) = x1 + -1*x5 + x18 p(f55) = x1 + -1*x5 + x18 p(f61) = x1 + -1*x5 p(f73) = x1 + -1*x5 + x18 Following rules are strictly oriented: [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = 1 + A + -1*K > A + -1*K = f61(A,B,C,D,K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f34(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f10(A,1 + B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = 1 + A + -1*K >= 1 + A + -1*K = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = A + -1*K >= A + -1*K = f53(A,B,C,D,1 + K) * Step 6: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 3*x1 + -2*x2 + -2*x18 p(f10) = 3*x1 + -2*x2 + -3*x18 p(f13) = 3*x1 + -2*x2 + -3*x18 p(f29) = 3*x1 + -2*x2 + -3*x18 p(f34) = 3*x1 + -2*x2 + -3*x18 p(f53) = 3*x1 + -2*x2 + -3*x18 p(f55) = 3*x1 + -2*x2 + -3*x18 p(f61) = 3*x1 + -2*x2 + -3*x18 p(f73) = 3*x1 + -2*x2 + -3*x18 Following rules are strictly oriented: [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = -3 + 3*A + -2*B > -5 + 3*A + -2*B = f10(A,1 + B,C,D,K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = -2 + 3*A + -2*B >= -3 + 3*A + -2*B = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = -3 + 3*A + -2*B >= -5 + 3*A + -2*B = f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f34(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f61(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = -3 + 3*A + -2*B >= -3 + 3*A + -2*B = f53(A,B,C,D,1 + K) * Step 7: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (?,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 2*x1 + -1*x4 p(f10) = 2*x1 + -1*x4 p(f13) = 2*x1 + -1*x4 p(f29) = 2*x1 + -1*x4 p(f34) = 2*x1 + -1*x4 p(f53) = 2*x1 + -1*x4 p(f55) = 2*x1 + -1*x4 p(f61) = 2*x1 + -1*x4 p(f73) = 2*x1 + -1*x4 Following rules are strictly oriented: [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = 2*A + -1*D > -1 + 2*A + -1*D = f13(A,B,C,1 + D,K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = 2*A + -1*D >= -1 + 2*A + -1*D = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f34(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,1 + B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f61(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,1 + K) * Step 8: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (?,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (2*A + D,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = 2*x1 + -1*x4 p(f10) = 2*x1 + -1*x4 p(f13) = 2*x1 + -1*x4 p(f29) = 2*x1 + -1*x4 p(f34) = 2*x1 + -1*x4 p(f53) = 2*x1 + -1*x4 p(f55) = 2*x1 + -1*x4 p(f61) = 2*x1 + -1*x4 p(f73) = 2*x1 + -1*x4 Following rules are strictly oriented: [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = 2*A + -1*D > -1 + 2*A + -1*D = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = 2*A + -1*D > -1 + 2*A + -1*D = f13(A,B,C,1 + D,K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f34(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f10(A,1 + B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f61(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = 2*A + -1*D >= 2*A + -1*D = f53(A,B,C,D,1 + K) * Step 9: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (2*A + D,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (2*A + D,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (?,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (?,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (?,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 10: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (?,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (2*A + D,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (2*A + D,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (4*A + 2*D,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (4*A + 2*D,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (1 + 17*A + 8*D + K,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x1 + -1*x2 p(f10) = x1 + -1*x2 p(f13) = x1 + -1*x2 p(f29) = x1 + -1*x2 p(f34) = x1 + -1*x2 + -1*x18 p(f53) = x1 + -1*x2 + -1*x18 p(f55) = x1 + -1*x2 + -1*x18 p(f61) = x1 + -1*x2 + -1*x18 p(f73) = x1 + -1*x2 Following rules are strictly oriented: [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] ==> f13(A,B,C,D,K) = A + -1*B > -1 + A + -1*B = f10(A,1 + B,0,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f29(A,B,C,D,K) = A + -1*B > -1 + A + -1*B = f34(A,B,C,D,K) Following rules are weakly oriented: [A >= 2] ==> f0(A,B,C,D,K) = A + -1*B >= A + -1*B = f10(A,B,C,D,K) [-2 + A >= 0 && B >= A] ==> f10(A,B,C,D,K) = A + -1*B >= A + -1*B = f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] ==> f10(A,B,C,D,K) = A + -1*B >= A + -1*B = f73(A,B,C,D,K) [-2 + A >= 0 && A >= 1 + B] ==> f10(A,B,C,D,K) = A + -1*B >= A + -1*B = f13(A,B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] ==> f13(A,B,C,D,K) = A + -1*B >= A + -1*B = f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] ==> f13(A,B,C,D,K) = A + -1*B >= A + -1*B = f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] ==> f13(A,B,C,D,K) = A + -1*B >= A + -1*B = f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] ==> f13(A,B,C,D,K) = A + -1*B >= A + -1*B = f29(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] f34(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] f34(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f53(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] f53(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f10(A,1 + B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] f53(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f55(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f55(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f61(A,B,C,D,K) [-3 + D >= 0 ==> && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] f61(A,B,C,D,K) = -1 + A + -1*B >= -1 + A + -1*B = f53(A,B,C,D,1 + K) * Step 11: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (?,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (A + B,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (2*A + D,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (2*A + D,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (4*A + 2*D,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (4*A + 2*D,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (1 + 17*A + 8*D + K,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 12: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,B,C,D,K) -> f10(A,B,C,D,K) [A >= 2] (1,1) 1. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A] (1,1) 2. f10(A,B,C,D,K) -> f73(A,B,C,D,K) [-2 + A >= 0 && B >= A && 0 >= 1 + S] (1,1) 3. f10(A,B,C,D,K) -> f13(A,B,0,D,K) [-2 + A >= 0 && A >= 1 + B] (3 + 4*A + 3*B,1) 4. f13(A,B,C,D,K) -> f10(A,1 + B,0,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A && C = 0] (A + B,1) 5. f13(A,B,C,D,K) -> f13(A,B,S,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && S >= C && A >= D] (2*A + D,1) 6. f13(A,B,C,D,K) -> f13(A,B,C,1 + D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 + S && A >= D] (2*A + D,1) 7. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && C >= 1 && D >= 1 + A] (4*A + 2*D,1) 8. f13(A,B,C,D,K) -> f29(A,B,C,D,K) [-1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + C && D >= 1 + A] (4*A + 2*D,1) 9. f29(A,B,C,D,K) -> f34(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 10. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && 0 >= 1 + U && D >= 1 + A] 11. f34(A,B,C,D,K) -> f53(A,B,C,D,K) [-3 + D >= 0 (8*A + 4*D,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && D >= 1 + A] 12. f53(A,B,C,D,K) -> f10(A,1 + B,C,D,K) [-3 + D >= 0 (2 + 3*A + 2*B,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && K >= 1 + A] 13. f53(A,B,C,D,K) -> f55(A,B,C,D,K) [-3 + D >= 0 (1 + 17*A + 8*D + K,1) && -2 + -1*B + D >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && -2 + A >= 0 && A >= K] 14. f55(A,B,C,D,K) -> f61(A,B,C,D,K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] 15. f61(A,B,C,D,K) -> f53(A,B,C,D,1 + K) [-3 + D >= 0 (1 + A + K,1) && -2 + -1*B + D >= 0 && -1 + D + -1*K >= 0 && -5 + A + D >= 0 && -1 + -1*A + D >= 0 && -1 + A + -1*B >= 0 && A + -1*K >= 0 && -2 + A >= 0 && D >= 1 + A] Signature: {(f0,18);(f10,18);(f13,18);(f29,18);(f34,18);(f53,18);(f55,18);(f61,18);(f73,18)} Flow Graph: [0->{1,2,3},1->{},2->{},3->{4,5,6},4->{1,2,3},5->{4,5,6,7,8},6->{4,5,6,7,8},7->{9},8->{9},9->{10,11} ,10->{12,13},11->{12,13},12->{1,2,3},13->{14},14->{15},15->{12,13}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: The problem is already solved. YES(?,O(n^1))