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,S,T,U,V,W) -> f16(1,X,Y,Z,A1,B1,C1,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [A = 1] (1,1) 1. f16(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f18(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (?,1) 2. f18(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f18(A,B,C,D,E,F,G,H,I,J,1 + K,2 + L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f28(A,X,Y,Z,A1,B1,C1,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [0 >= A] (1,1) 4. f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f28(A,X,Y,Z,A1,B1,C1,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [A >= 2] (1,1) 5. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f35(A,B,C,D,E,F,G,H,I,J,K,L,2 + H + -1*I,1,0,P,Q,R,S,T,U,V,W) [0 >= I && H >= I] (?,1) 6. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f35(A,B,C,D,E,F,G,H,I,J,K,L,2 + H + -1*I,1,0,P,Q,R,S,T,U,V,W) [I >= 2 && H >= I] (?,1) 7. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f35(A,B,C,D,E,F,G,H,1,J,K,L,1,1,0,P,Q,R,S,T,U,V,W) [H >= 1 && I = 1] (?,1) 8. f35(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f52(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f52(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,1 + K,X,M,N,O,P,1,Y,Z,A1,B1,V,W) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,1 + K,X,M,N,O,P,1,Y,Z,A1,B1,V,W) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,2,1,M,N,O,P,1,X,Y,Z,A1,V,W) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,1 + K,2 + J + -1*K,M,N,O,P,Q,X,Y,Z,A1,B1,W) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,1 + K,2 + J + -1*K,M,N,O,P,Q,X,Y,Z,A1,B1,W) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f37(A,B,C,D,E,F,G,H,I,J,2,1,M,N,O,P,Q,X,Y,Z,A1,B1,W) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f35(A,B,C,D,N,F,G,H,I,J,K,L,M,X,Y,P,1 + Q,R,S,T,U,V,2 + W) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f28(A,B,C,D,E,F,G,H,1 + I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f76(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [0 >= 2 + A && I >= 1 + H] (?,1) 20. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f76(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [A >= 0 && I >= 1 + H] (?,1) 21. f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f76(-1,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [I >= 1 + H && 1 + A = 0] (?,1) 22. f18(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f16(A,B,C,D,E,F,G,H,1 + I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (?,1) 23. f16(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) -> f28(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (?,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,19,20,21},5->{8,18},6->{8,18},7->{8,18},8->{9 ,10,11,12,13,17},9->{14,15,16},10->{14,15,16},11->{9,10,11,12,13,17},12->{9,10,11,12,13,17},13->{9,10,11,12 ,13,17},14->{9,10,11,12,13,17},15->{9,10,11,12,13,17},16->{9,10,11,12,13,17},17->{8,18},18->{5,6,7,19,20,21} ,19->{},20->{},21->{},22->{1,23},23->{5,6,7,19,20,21}] + Applied Processor: ArgumentFilter [1,2,3,4,5,6,11,12,13,14,17,18,19,20,21,22] + Details: We remove following argument positions: [1,2,3,4,5,6,11,12,13,14,17,18,19,20,21,22]. * Step 2: TrivialSCCs WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (?,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (?,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (?,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (?,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (?,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (?,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,19,20,21},5->{8,18},6->{8,18},7->{8,18},8->{9 ,10,11,12,13,17},9->{14,15,16},10->{14,15,16},11->{9,10,11,12,13,17},12->{9,10,11,12,13,17},13->{9,10,11,12 ,13,17},14->{9,10,11,12,13,17},15->{9,10,11,12,13,17},16->{9,10,11,12,13,17},17->{8,18},18->{5,6,7,19,20,21} ,19->{},20->{},21->{},22->{1,23},23->{5,6,7,19,20,21}] + 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,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (?,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (?,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,19,20,21},5->{8,18},6->{8,18},7->{8,18},8->{9 ,10,11,12,13,17},9->{14,15,16},10->{14,15,16},11->{9,10,11,12,13,17},12->{9,10,11,12,13,17},13->{9,10,11,12 ,13,17},14->{9,10,11,12,13,17},15->{9,10,11,12,13,17},16->{9,10,11,12,13,17},17->{8,18},18->{5,6,7,19,20,21} ,19->{},20->{},21->{},22->{1,23},23->{5,6,7,19,20,21}] + Applied Processor: UnsatPaths + Details: We remove following edges from the transition graph: [(4,19) ,(4,21) ,(11,9) ,(11,10) ,(11,12) ,(12,9) ,(12,10) ,(12,11) ,(12,13) ,(13,9) ,(13,10) ,(13,11) ,(13,13) ,(14,12) ,(15,11) ,(15,13) ,(16,11) ,(16,13) ,(23,5) ,(23,6) ,(23,7) ,(23,19) ,(23,21)] * Step 4: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (?,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (?,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x2 + -1*x3 + x23 p(f16) = x2 + -1*x3 + x23 p(f18) = x2 + -1*x3 + x23 p(f28) = x2 + -1*x3 + x23 p(f35) = x2 + -1*x3 p(f37) = x2 + -1*x3 p(f52) = x2 + -1*x3 p(f76) = x2 + -1*x3 + x23 Following rules are strictly oriented: [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + H + -1*I > H + -1*I = f16(A,H,1 + I,J,K,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= H + -1*I = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= H + -1*I = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= -1 + H = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(-1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) * Step 5: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (?,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 6: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (?,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x2 + -1*x3 + x23 p(f16) = x2 + -1*x3 + x23 p(f18) = x2 + -1*x3 p(f28) = x2 + -1*x3 + x23 p(f35) = x2 + -1*x3 + x23 p(f37) = x2 + -1*x3 + x23 p(f52) = x2 + -1*x3 + x23 p(f76) = x2 + -1*x3 + x23 Following rules are strictly oriented: [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + H + -1*I > H + -1*I = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 1 + H + -1*I > H + -1*I = f28(A,H,1 + I,J,K,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f16(1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= H = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f35(A,H,I,J,K,P,1 + Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = H + -1*I >= H + -1*I = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + H + -1*I >= 1 + H + -1*I = f28(A,H,I,J,K,P,Q) * Step 7: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (?,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (?,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (?,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 8: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (?,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x6 + -1*x7 + x23 p(f16) = x6 + -1*x7 + x23 p(f18) = x6 + -1*x7 + x23 p(f28) = x6 + -1*x7 + x23 p(f35) = x6 + -1*x7 + x23 p(f37) = x6 + -1*x7 p(f52) = x6 + -1*x7 p(f76) = x6 + -1*x7 + x23 Following rules are strictly oriented: [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 1 + P + -1*Q > P + -1*Q = f37(A,H,I,J,K,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= -1 + P = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= -1 + P = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= -1 + P = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = P + -1*Q >= P + -1*Q = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + P + -1*Q >= 1 + P + -1*Q = f28(A,H,I,J,K,P,Q) * Step 9: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (?,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x4 + -1*x5 + x23 p(f16) = x4 + -1*x5 + x23 p(f18) = x4 + -1*x5 + x23 p(f28) = x4 + -1*x5 + x23 p(f35) = x4 + -1*x5 + x23 p(f37) = x4 + -1*x5 + x23 p(f52) = x4 + -1*x5 p(f76) = x4 + -1*x5 + x23 Following rules are strictly oriented: [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f52(A,H,I,J,K,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= -1 + J = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= -1 + J = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) * Step 10: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (?,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = -1*x5 + 2*x23 p(f16) = -1*x5 + 2*x23 p(f18) = -1*x5 + 2*x23 p(f28) = -1*x5 + 2*x23 p(f35) = -1*x5 + 2*x23 p(f37) = -1*x5 + 2*x23 p(f52) = -1*x5 + 2*x23 p(f76) = -1*x5 + 2*x23 Following rules are strictly oriented: [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K > 0 = f37(A,H,I,J,2,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 0 = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) * Step 11: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (?,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (?,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x4 + -1*x5 + x23 p(f16) = x4 + -1*x5 + x23 p(f18) = x4 + -1*x5 + x23 p(f28) = x4 + -1*x5 + x23 p(f35) = x4 + -1*x5 + x23 p(f37) = x4 + -1*x5 + x23 p(f52) = x4 + -1*x5 p(f76) = x4 + -1*x5 + x23 Following rules are strictly oriented: [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > -1 + J = f37(A,H,I,J,2,P,1) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= -1 + J = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) * Step 12: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (?,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (?,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 13: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (?,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (2 + 2*J + 2*K,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (2 + 2*J + 2*K,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x1 + x4 + -1*x5 p(f16) = x4 + -1*x5 + x23 p(f18) = x4 + -1*x5 + x23 p(f28) = x1 + x4 + -1*x5 p(f35) = x1 + x4 + -1*x5 p(f37) = x1 + x4 + -1*x5 p(f52) = x1 + x4 + -1*x5 p(f76) = x1 + x4 + -1*x5 Following rules are strictly oriented: [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f18(A,H,I,J,1 + K,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = A + J + -1*K >= 1 + J + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f18(A,H,I,J,K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= -1 + A + J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= -1 + A + J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= -2 + A + J = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = A + J + -1*K >= -1 + A + J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = A + J + -1*K >= -1 + A + J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = A + J + -1*K >= -2 + A + J = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= A + J + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = A + J + -1*K >= -1 + J + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= A + J + -1*K = f28(A,H,I,J,K,P,Q) * Step 14: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (A + J + K,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (?,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (2 + 2*J + 2*K,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (2 + 2*J + 2*K,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = -1*x5 + 2*x23 p(f16) = -1*x5 + 2*x23 p(f18) = -1*x5 + 2*x23 p(f28) = -1*x5 + 2*x23 p(f35) = -1*x5 + 2*x23 p(f37) = -1*x5 + 2*x23 p(f52) = -1*x5 + 2*x23 p(f76) = -1*x5 + 2*x23 Following rules are strictly oriented: [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K > 1 + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K > 0 = f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K > 1 + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K > 0 = f37(A,H,I,J,2,P,Q) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f18(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f18(A,H,I,J,1 + K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = 2 + -1*K >= 1 + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 2 + -1*K >= 2 + -1*K = f28(A,H,I,J,K,P,Q) * Step 15: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (A + J + K,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (2 + K,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (?,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (2 + 2*J + 2*K,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (2 + 2*J + 2*K,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: We apply a polynomial interpretation of shape linear: p(f0) = x4 + -1*x5 + x23 p(f16) = x4 + -1*x5 + x23 p(f18) = x4 + -1*x5 + x23 p(f28) = x4 + -1*x5 + x23 p(f35) = x4 + -1*x5 + x23 p(f37) = x4 + -1*x5 + x23 p(f52) = x4 + -1*x5 p(f76) = x4 + -1*x5 + x23 Following rules are strictly oriented: [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > J + -1*K = f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K > -1 + J = f37(A,H,I,J,2,P,1) Following rules are weakly oriented: [A = 1] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(1,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f18(A,H,I,J,K,P,Q) [0 >= A] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [A >= 2] ==> f0(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) [0 >= I && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,Q) [H >= 1 && I = 1] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,1,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= J + -1*K = f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] ==> f52(A,H,I,J,K,P,Q) = J + -1*K >= -1 + J = f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && K >= 1 + J] ==> f37(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] ==> f35(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,1 + I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(A,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] ==> f28(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f76(-1,H,I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] ==> f18(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f16(A,H,1 + I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] ==> f16(A,H,I,J,K,P,Q) = 1 + J + -1*K >= 1 + J + -1*K = f28(A,H,I,J,K,P,Q) * Step 16: KnowledgePropagation WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (A + J + K,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (2 + K,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (1 + J + K,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (2 + 2*J + 2*K,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (2 + 2*J + 2*K,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (?,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: KnowledgePropagation + Details: We propagate bounds from predecessors. * Step 17: PolyRank WORST_CASE(?,O(n^1)) + Considered Problem: Rules: 0. f0(A,H,I,J,K,P,Q) -> f16(1,H,I,J,K,P,Q) [A = 1] (1,1) 1. f16(A,H,I,J,K,P,Q) -> f18(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && H >= I] (2 + H + I,1) 2. f18(A,H,I,J,K,P,Q) -> f18(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && J >= K] (A + J + K,1) 3. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [0 >= A] (1,1) 4. f0(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [A >= 2] (1,1) 5. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [0 >= I && H >= I] (3 + H + I,1) 6. f28(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,Q) [I >= 2 && H >= I] (3 + H + I,1) 7. f28(A,H,I,J,K,P,Q) -> f35(A,H,1,J,K,P,Q) [H >= 1 && I = 1] (3 + H + I,1) 8. f35(A,H,I,J,K,P,Q) -> f37(A,H,I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && 1 + X >= Q] (1 + P + Q,1) 9. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && 0 >= Q && J >= K] (1 + J + K,1) 10. f37(A,H,I,J,K,P,Q) -> f52(A,H,I,J,K,P,Q) [H + -1*I >= 0 && Q >= 2 && J >= K] (1 + J + K,1) 11. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && 0 >= K && J >= K && Q = 1] (2 + K,1) 12. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,1) [H + -1*I >= 0 && J >= K && K >= 2 && Q = 1] (1 + J + K,1) 13. f37(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,1) [H + -1*I >= 0 && J >= 1 && K = 1 && Q = 1] (1 + J + K,1) 14. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && 0 >= K] (2 + 2*J + 2*K,1) 15. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,1 + K,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K >= 2] (2 + 2*J + 2*K,1) 16. f52(A,H,I,J,K,P,Q) -> f37(A,H,I,J,2,P,Q) [H + -1*I >= 0 && J + -1*K >= 0 && K = 1] (2 + K,1) 17. f37(A,H,I,J,K,P,Q) -> f35(A,H,I,J,K,P,1 + Q) [H + -1*I >= 0 && K >= 1 + J] (11 + 6*J + 8*K + P + Q,1) 18. f35(A,H,I,J,K,P,Q) -> f28(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && P >= 2*X && 3*X >= 1 + P && Q >= 2 + X] (1 + H + I,1) 19. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [0 >= 2 + A && I >= 1 + H] (1,1) 20. f28(A,H,I,J,K,P,Q) -> f76(A,H,I,J,K,P,Q) [A >= 0 && I >= 1 + H] (1,1) 21. f28(A,H,I,J,K,P,Q) -> f76(-1,H,I,J,K,P,Q) [I >= 1 + H && 1 + A = 0] (1,1) 22. f18(A,H,I,J,K,P,Q) -> f16(A,H,1 + I,J,K,P,Q) [H + -1*I >= 0 && 1 + -1*A >= 0 && -1 + A >= 0 && K >= 1 + J] (1 + H + I,1) 23. f16(A,H,I,J,K,P,Q) -> f28(A,H,I,J,K,P,Q) [1 + -1*A >= 0 && -1 + A >= 0 && I >= 1 + H] (1,1) Signature: {(f0,23);(f16,23);(f18,23);(f28,23);(f35,23);(f37,23);(f52,23);(f76,23)} Flow Graph: [0->{1,23},1->{2,22},2->{2,22},3->{5,6,7,19,20,21},4->{5,6,7,20},5->{8,18},6->{8,18},7->{8,18},8->{9,10,11 ,12,13,17},9->{14,15,16},10->{14,15,16},11->{11,13,17},12->{12,17},13->{12,17},14->{9,10,11,13,17},15->{9,10 ,12,17},16->{9,10,12,17},17->{8,18},18->{5,6,7,19,20,21},19->{},20->{},21->{},22->{1,23},23->{20}] + Applied Processor: PolyRank {useFarkas = True, withSizebounds = [], shape = Linear} + Details: The problem is already solved. YES(?,O(n^1))