MAYBE
Input TRS:
      1: app(app(add(),0()),y) -> y
      2: app(app(add(),app(s(),x)),y) -> app(s(),app(app(add(),x),y))
      3: app(app(mult(),0()),y) -> 0()
      4: app(app(mult(),app(s(),x)),y) -> app(app(add(),app(app(mult(),x),y)),y)
      5: app(app(app(rec(),f),x),0()) -> x
      6: app(app(app(rec(),f),x),app(s(),y)) -> app(app(f,app(s(),y)),app(app(app(rec(),f),x),y))
      7: fact() -> app(app(rec(),mult()),app(s(),0()))
Number of strict rules: 7
Direct POLO(bPol) ... failed.
Uncurrying app
      1: app^2_add(0(),y) -> y
      2: app^2_add(app^1_s(x),y) -> app^1_s(app^2_add(x,y))
      3: app^2_mult(0(),y) -> 0()
      4: app^2_mult(app^1_s(x),y) -> app^2_add(app^2_mult(x,y),y)
      5: app^3_rec(f,x,0()) -> x
      6: app^3_rec(f,x,app^1_s(y)) -> app(app(f,app^1_s(y)),app^3_rec(f,x,y))
      7: fact() -> app^2_rec(mult(),app^1_s(0()))
      8: app(rec(),_1) ->= app^1_rec(_1)
      9: app(app^1_rec(_1),_2) ->= app^2_rec(_1,_2)
      10: app(app^2_rec(_1,_2),_3) ->= app^3_rec(_1,_2,_3)
      11: app(s(),_1) ->= app^1_s(_1)
      12: app(add(),_1) ->= app^1_add(_1)
      13: app(app^1_add(_1),_2) ->= app^2_add(_1,_2)
      14: app(mult(),_1) ->= app^1_mult(_1)
      15: app(app^1_mult(_1),_2) ->= app^2_mult(_1,_2)
Number of strict rules: 7
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #app^2_add(app^1_s(x),y) -> #app^2_add(x,y)
     #2: #app^3_rec(f,x,app^1_s(y)) -> #app(app(f,app^1_s(y)),app^3_rec(f,x,y))
     #3: #app^3_rec(f,x,app^1_s(y)) -> #app(f,app^1_s(y))
     #4: #app^3_rec(f,x,app^1_s(y)) -> #app^3_rec(f,x,y)
     #5: #app(app^1_add(_1),_2) ->? #app^2_add(_1,_2)
     #6: #app(app^2_rec(_1,_2),_3) ->? #app^3_rec(_1,_2,_3)
     #7: #app(app^1_mult(_1),_2) ->? #app^2_mult(_1,_2)
     #8: #app^2_mult(app^1_s(x),y) -> #app^2_add(app^2_mult(x,y),y)
     #9: #app^2_mult(app^1_s(x),y) -> #app^2_mult(x,y)
Number of SCCs: 3, DPs: 6
  SCC { #9 }
POLO(Sum)... succeeded.
      #app^2_mult	w: x1
      s 	w: 0
      #app^3_rec	w: 0
      app^3_rec	w: 0
      app^1_rec	w: 0
      app^2_rec	w: 0
      #fact	w: 0
      mult	w: 0
      app^2_add	w: 0
      0 	w: 0
      app^1_add	w: 0
      rec	w: 0
      fact	w: 0
      #app	w: 0
      app^1_mult	w: 0
      app^2_mult	w: 0
      add	w: 0
      #app^2_add	w: 0
      app^1_s	w: x1 + 1
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #9
Number of SCCs: 2, DPs: 5
  SCC { #1 }
POLO(Sum)... succeeded.
      #app^2_mult	w: 0
      s 	w: 0
      #app^3_rec	w: 0
      app^3_rec	w: 0
      app^1_rec	w: 0
      app^2_rec	w: 0
      #fact	w: 0
      mult	w: 0
      app^2_add	w: 0
      0 	w: 0
      app^1_add	w: 0
      rec	w: 0
      fact	w: 0
      #app	w: 0
      app^1_mult	w: 0
      app^2_mult	w: 0
      add	w: 0
      #app^2_add	w: x1
      app^1_s	w: x1 + 1
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #1
Number of SCCs: 1, DPs: 4
  SCC { #2..4 #6 }
POLO(Sum)... POLO(max)... succeeded.
      #app^2_mult	w: 0
      s 	w: 20818
      #app^3_rec	w: max(x1 + 48208)
      app^3_rec	w: max(x1 + 2, x2 + 1)
      app^1_rec	w: x1
      app^2_rec	w: max(x1 + 1, x2)
      #fact	w: 0
      mult	w: 33953
      app^2_add	w: max(x1, x2)
      0 	w: 0
      app^1_add	w: x1
      rec	w: 41062
      fact	w: 0
      #app	w: max(x1 + 48207)
      app^1_mult	w: 1
      app^2_mult	w: max(x2)
      add	w: 1142
      #app^2_add	w: 0
      app^1_s	w: 1
      app	w: max(x1 + 1, x2)
    USABLE RULES: { 1..6 8..15 }
    Removed DPs: #3
Number of SCCs: 1, DPs: 3
  SCC { #2 #4 #6 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.