MAYBE
Input TRS:
AC symbols: virg *
      1: substt(ef(x),y) -> ef(substt(x,y))
      2: substf(Pe(x),y) -> Pe(substt(x,y))
      3: substf(neg(f),s) -> neg(substf(f,s))
      4: substf(and(f,g),s) -> and(substf(f,s),substf(g,s))
      5: substf(or(f,g),s) -> or(substf(f,s),substf(g,s))
      6: substf(imp(f,g),s) -> imp(substf(f,s),substf(g,s))
      7: substf(forall(f),s) -> forall(substf(f,.(1(),ron(s,shift()))))
      8: substf(exists(f),s) -> exists(substf(f,.(1(),ron(s,shift()))))
      9: substt(x,id()) -> x
      10: substf(f,id()) -> f
      11: substt(substt(x,s),t) -> substt(x,ron(s,t))
      12: substf(substf(f,s),t) -> substf(f,ron(s,t))
      13: substt(1(),.(x,s)) -> x
      14: ron(id(),s) -> s
      15: ron(shift(),.(x,s)) -> s
      16: ron(ron(s,t),u) -> ron(s,ron(t,u))
      17: ron(.(x,s),t) -> .(substt(x,t),ron(s,t))
      18: ron(s,id()) -> s
      19: .(1(),shift()) -> id()
      20: .(substt(1(),s),ron(shift(),s)) -> s
      21: virg(emptyfset(),a) -> a
      22: virg(a,a) -> a
      23: *(emptysset(),a) -> a
      24: *(a,a) -> a
      25: neg(neg(f)) -> f
      26: and(f,f) -> f
      27: or(f,f) -> f
      28: imp(f,g) -> or(neg(f),g)
      29: exists(f) -> neg(forall(neg(f)))
      30: sequent(virg(convf(neg(f)),a),b) -> sequent(a,virg(convf(f),b))
      31: sequent(convf(neg(f)),b) -> sequent(emptyfset(),virg(convf(f),b))
      32: sequent(a,virg(convf(neg(f)),b)) -> sequent(virg(convf(f),a),b)
      33: sequent(a,convf(neg(f))) -> sequent(virg(convf(f),a),emptyfset())
      34: sequent(virg(convf(and(f,g)),a),b) -> sequent(virg(convf(g),virg(convf(f),a)),b)
      35: sequent(convf(and(f,g)),b) -> sequent(virg(convf(f),convf(g)),b)
      36: sequent(a,virg(convf(or(f,g)),b)) -> sequent(a,virg(virg(convf(f),convf(g)),b))
      37: sequent(a,convf(or(f,g))) -> sequent(a,virg(convf(f),convf(g)))
      38: convs(sequent(a,virg(convf(and(f,g)),b))) -> *(convs(sequent(a,virg(convf(f),b))),convs(sequent(a,virg(convf(g),b))))
      39: convs(sequent(a,convf(and(f,g)))) -> *(convs(sequent(a,convf(f))),convs(sequent(a,convf(g))))
      40: convs(sequent(virg(convf(or(f,g)),a),b)) -> *(convs(sequent(virg(convf(f),a),b)),convs(sequent(virg(convf(g),a),b)))
      41: convs(sequent(convf(or(f,g)),b)) -> *(convs(sequent(convf(f),b)),convs(sequent(convf(g),b)))
      42: convs(sequent(virg(convf(f),a),virg(convf(f),b))) -> emptysset()
      43: convs(sequent(virg(convf(f),a),convf(f))) -> emptysset()
      44: convs(sequent(convf(f),virg(convf(f),b))) -> emptysset()
      45: convs(sequent(convf(f),convf(f))) -> emptysset()
      46: *(convs(sequent(virg(f,a),virg(g,b))),convs(sequent(a,b))) -> convs(sequent(a,b))
      47: *(convs(sequent(virg(f,a),b)),convs(sequent(a,b))) -> convs(sequent(a,b))
      48: *(convs(sequent(a,virg(f,b))),convs(sequent(a,b))) -> convs(sequent(a,b))
      49: *(convs(sequent(virg(f,a),b)),convs(sequent(a,emptyfset()))) -> convs(sequent(a,emptyfset()))
      50: *(convs(sequent(emptyfset(),b)),convs(sequent(a,virg(f,b)))) -> convs(sequent(emptyfset(),b))
      51: *(convs(sequent(emptyfset(),b)),convs(sequent(a,b))) -> convs(sequent(emptyfset(),b))
      52: *(convs(sequent(a,emptyfset())),convs(sequent(a,b))) -> convs(sequent(a,emptyfset()))
      53: *(convs(sequent(emptyfset(),emptyfset())),convs(sequent(a,b))) -> convs(sequent(emptyfset(),emptyfset()))
Number of strict rules: 53
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #substf(Pe(x),y) -> #substt(x,y)
     #2: #exists(f) -> #neg(forall(neg(f)))
     #3: #exists(f) -> #neg(f)
     #4: #sequent(convf(and(f,g)),b) -> #sequent(virg(convf(f),convf(g)),b)
     #5: #sequent(convf(and(f,g)),b) -> #virg(convf(f),convf(g))
     #6: #convs(sequent(convf(or(f,g)),b)) -> #*(convs(sequent(convf(f),b)),convs(sequent(convf(g),b)))
     #7: #convs(sequent(convf(or(f,g)),b)) -> #convs(sequent(convf(f),b))
     #8: #convs(sequent(convf(or(f,g)),b)) -> #sequent(convf(f),b)
     #9: #convs(sequent(convf(or(f,g)),b)) -> #convs(sequent(convf(g),b))
     #10: #convs(sequent(convf(or(f,g)),b)) -> #sequent(convf(g),b)
     #11: #sequent(a,convf(or(f,g))) -> #sequent(a,virg(convf(f),convf(g)))
     #12: #sequent(a,convf(or(f,g))) -> #virg(convf(f),convf(g))
     #13: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #*(convs(sequent(a,virg(convf(f),b))),convs(sequent(a,virg(convf(g),b))))
     #14: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #convs(sequent(a,virg(convf(f),b)))
     #15: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #sequent(a,virg(convf(f),b))
     #16: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #virg(convf(f),b)
     #17: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #convs(sequent(a,virg(convf(g),b)))
     #18: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #sequent(a,virg(convf(g),b))
     #19: #convs(sequent(a,virg(convf(and(f,g)),b))) -> #virg(convf(g),b)
     #20: #substf(imp(f,g),s) -> #imp(substf(f,s),substf(g,s))
     #21: #substf(imp(f,g),s) -> #substf(f,s)
     #22: #substf(imp(f,g),s) -> #substf(g,s)
     #23: #*(x,*(y,z)) ->= #*(*(x,y),z)
     #24: #*(x,*(y,z)) ->= #*(x,y)
     #25: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #*(convs(sequent(virg(convf(f),a),b)),convs(sequent(virg(convf(g),a),b)))
     #26: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #convs(sequent(virg(convf(f),a),b))
     #27: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #sequent(virg(convf(f),a),b)
     #28: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #virg(convf(f),a)
     #29: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #convs(sequent(virg(convf(g),a),b))
     #30: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #sequent(virg(convf(g),a),b)
     #31: #convs(sequent(virg(convf(or(f,g)),a),b)) -> #virg(convf(g),a)
     #32: #substt(substt(x,s),t) -> #substt(x,ron(s,t))
     #33: #substt(substt(x,s),t) -> #ron(s,t)
     #34: #substf(substf(f,s),t) -> #substf(f,ron(s,t))
     #35: #substf(substf(f,s),t) -> #ron(s,t)
     #36: #sequent(convf(neg(f)),b) -> #sequent(emptyfset(),virg(convf(f),b))
     #37: #sequent(convf(neg(f)),b) -> #virg(convf(f),b)
     #38: #sequent(virg(convf(neg(f)),a),b) -> #sequent(a,virg(convf(f),b))
     #39: #sequent(virg(convf(neg(f)),a),b) -> #virg(convf(f),b)
     #40: #substf(forall(f),s) -> #substf(f,.(1(),ron(s,shift())))
     #41: #substf(forall(f),s) -> #.(1(),ron(s,shift()))
     #42: #substf(forall(f),s) -> #ron(s,shift())
     #43: #convs(sequent(a,convf(and(f,g)))) -> #*(convs(sequent(a,convf(f))),convs(sequent(a,convf(g))))
     #44: #convs(sequent(a,convf(and(f,g)))) -> #convs(sequent(a,convf(f)))
     #45: #convs(sequent(a,convf(and(f,g)))) -> #sequent(a,convf(f))
     #46: #convs(sequent(a,convf(and(f,g)))) -> #convs(sequent(a,convf(g)))
     #47: #convs(sequent(a,convf(and(f,g)))) -> #sequent(a,convf(g))
     #48: #sequent(a,convf(neg(f))) -> #sequent(virg(convf(f),a),emptyfset())
     #49: #sequent(a,convf(neg(f))) -> #virg(convf(f),a)
     #50: #substf(or(f,g),s) -> #or(substf(f,s),substf(g,s))
     #51: #substf(or(f,g),s) -> #substf(f,s)
     #52: #substf(or(f,g),s) -> #substf(g,s)
     #53: #imp(f,g) -> #or(neg(f),g)
     #54: #imp(f,g) -> #neg(f)
     #55: #sequent(virg(convf(and(f,g)),a),b) -> #sequent(virg(convf(g),virg(convf(f),a)),b)
     #56: #sequent(virg(convf(and(f,g)),a),b) -> #virg(convf(g),virg(convf(f),a))
     #57: #sequent(virg(convf(and(f,g)),a),b) -> #virg(convf(f),a)
     #58: #ron(.(x,s),t) -> #.(substt(x,t),ron(s,t))
     #59: #ron(.(x,s),t) -> #substt(x,t)
     #60: #ron(.(x,s),t) -> #ron(s,t)
     #61: #sequent(a,virg(convf(neg(f)),b)) -> #sequent(virg(convf(f),a),b)
     #62: #sequent(a,virg(convf(neg(f)),b)) -> #virg(convf(f),a)
     #63: #sequent(a,virg(convf(or(f,g)),b)) -> #sequent(a,virg(virg(convf(f),convf(g)),b))
     #64: #sequent(a,virg(convf(or(f,g)),b)) -> #virg(virg(convf(f),convf(g)),b)
     #65: #sequent(a,virg(convf(or(f,g)),b)) -> #virg(convf(f),convf(g))
     #66: #ron(ron(s,t),u) -> #ron(s,ron(t,u))
     #67: #ron(ron(s,t),u) -> #ron(t,u)
     #68: #substf(neg(f),s) -> #neg(substf(f,s))
     #69: #substf(neg(f),s) -> #substf(f,s)
     #70: #substt(ef(x),y) -> #substt(x,y)
     #71: #virg(x,virg(y,z)) ->= #virg(virg(x,y),z)
     #72: #virg(x,virg(y,z)) ->= #virg(x,y)
     #73: #substf(exists(f),s) -> #exists(substf(f,.(1(),ron(s,shift()))))
     #74: #substf(exists(f),s) -> #substf(f,.(1(),ron(s,shift())))
     #75: #substf(exists(f),s) -> #.(1(),ron(s,shift()))
     #76: #substf(exists(f),s) -> #ron(s,shift())
     #77: #substf(and(f,g),s) -> #and(substf(f,s),substf(g,s))
     #78: #substf(and(f,g),s) -> #substf(f,s)
     #79: #substf(and(f,g),s) -> #substf(g,s)
Number of SCCs: 6, DPs: 37
  SCC { #71 #72 }
only weak rules.
Number of SCCs: 5, DPs: 35
  SCC { #23 #24 }
only weak rules.
Number of SCCs: 4, DPs: 33
  SCC { #32 #33 #59 #60 #66 #67 #70 }
POLO(Sum)... succeeded.
      #sequent	w: 0
      1 	w: 8366
      ron	w: x1 + x2 + 2
      convs	w: 0
      #. 	w: 0
      emptyfset	w: 0
      #exists	w: 0
      and	w: 0
      #ron	w: x1
      convf	w: 0
      #substf	w: 0
      #virg	w: 0
      #* 	w: 0
      Pe	w: 0
      #substt	w: x1
      substf	w: 0
      forall	w: 0
      virg	w: 0
      #imp	w: 0
      or	w: 0
      neg	w: 0
      . 	w: x1 + x2 + 21239
      ef	w: x1 + 2438
      #convs	w: 0
      emptysset	w: 0
      id	w: 50259
      #or	w: 0
      #neg	w: 0
      substt	w: x1 + x2 + 1
      imp	w: 0
      sequent	w: 0
      #and	w: 0
      * 	w: 0
      shift	w: 20653
      exists	w: 0
    USABLE RULES: { }
    Removed DPs: #32 #33 #59 #60 #66 #67 #70
Number of SCCs: 3, DPs: 26
  SCC { #21 #22 #34 #40 #51 #52 #69 #74 #78 #79 }
POLO(Sum)... succeeded.
      #sequent	w: 0
      1 	w: 0
      ron	w: x1 + x2 + 2
      convs	w: 0
      #. 	w: 0
      emptyfset	w: 0
      #exists	w: 0
      and	w: x1 + x2 + 1
      #ron	w: 0
      convf	w: 0
      #substf	w: x1 + x2
      #virg	w: 0
      #* 	w: 0
      Pe	w: 0
      #substt	w: 0
      substf	w: x1 + x2 + 3
      forall	w: x1 + 16207
      virg	w: 0
      #imp	w: 0
      or	w: x1 + x2 + 1
      neg	w: x1 + 1
      . 	w: x2 + 1
      ef	w: x1 + 2438
      #convs	w: 0
      emptysset	w: 0
      id	w: 162
      #or	w: 0
      #neg	w: 0
      substt	w: x1 + x2 + 1
      imp	w: x1 + x2 + 1
      sequent	w: 0
      #and	w: 0
      * 	w: 0
      shift	w: 16203
      exists	w: x1 + 16207
    USABLE RULES: { 14..20 }
    Removed DPs: #21 #22 #34 #40 #51 #52 #69 #74 #78 #79
Number of SCCs: 2, DPs: 16
  SCC { #4 #11 #36 #38 #48 #55 #61 #63 }
POLO(Sum)... succeeded.
      #sequent	w: x1 + x2
      1 	w: 0
      ron	w: x1 + x2 + 2
      convs	w: 0
      #. 	w: 0
      emptyfset	w: 1
      #exists	w: 0
      and	w: x1 + x2 + 2
      #ron	w: 0
      convf	w: x1 + 1
      #substf	w: x2
      #virg	w: 0
      #* 	w: 0
      Pe	w: 0
      #substt	w: 0
      substf	w: 3
      forall	w: 16207
      virg	w: x1 + x2
      #imp	w: 0
      or	w: x1 + x2 + 31895
      neg	w: x1 + 6
      . 	w: x2 + 1
      ef	w: x1 + 1
      #convs	w: 0
      emptysset	w: 0
      id	w: 2685
      #or	w: 0
      #neg	w: 0
      substt	w: x1 + x2 + 1
      imp	w: 1
      sequent	w: 0
      #and	w: 0
      * 	w: 0
      shift	w: 23974
      exists	w: 16207
    USABLE RULES: { 14..22 54 }
    Removed DPs: #4 #11 #36 #38 #48 #55 #61 #63
Number of SCCs: 1, DPs: 8
  SCC { #7 #9 #14 #17 #26 #29 #44 #46 }
POLO(Sum)... succeeded.
      #sequent	w: x1 + x2
      1 	w: 0
      ron	w: x1 + x2 + 2
      convs	w: 0
      #. 	w: 0
      emptyfset	w: 1
      #exists	w: 0
      and	w: x1 + x2 + 1
      #ron	w: 0
      convf	w: x1 + 1
      #substf	w: x2
      #virg	w: 0
      #* 	w: 0
      Pe	w: 0
      #substt	w: 0
      substf	w: 3
      forall	w: 16207
      virg	w: x1 + x2
      #imp	w: 0
      or	w: x1 + x2 + 1
      neg	w: x1 + 1
      . 	w: x2 + 1
      ef	w: x1 + 38145
      #convs	w: x1
      emptysset	w: 0
      id	w: 1
      #or	w: 0
      #neg	w: 0
      substt	w: x1 + x2 + 1
      imp	w: 1
      sequent	w: x1 + x2
      #and	w: 0
      * 	w: 0
      shift	w: 1
      exists	w: 16207
    USABLE RULES: { 14..22 30..37 54 }
    Removed DPs: #7 #9 #14 #17 #26 #29 #44 #46
Number of SCCs: 0, DPs: 0
Next Dependency Pairs:
     #80: #*(*(convs(sequent(virg(f,a),virg(g,b))),convs(sequent(a,b))),_1) -> #*(convs(sequent(a,b)),_1)
     #81: #*(*(convs(sequent(virg(f,a),b)),convs(sequent(a,b))),_1) -> #*(convs(sequent(a,b)),_1)
     #82: #*(*(convs(sequent(emptyfset(),emptyfset())),convs(sequent(a,b))),_1) -> #*(convs(sequent(emptyfset(),emptyfset())),_1)
     #83: #*(*(convs(sequent(a,virg(f,b))),convs(sequent(a,b))),_1) -> #*(convs(sequent(a,b)),_1)
     #84: #*(x,*(y,z)) ->= #*(*(x,y),z)
     #85: #*(x,*(y,z)) ->= #*(x,y)
     #86: #*(*(convs(sequent(emptyfset(),b)),convs(sequent(a,b))),_1) -> #*(convs(sequent(emptyfset(),b)),_1)
     #87: #*(*(a,a),_1) -> #*(a,_1)
     #88: #*(*(emptysset(),a),_1) -> #*(a,_1)
     #89: #*(*(convs(sequent(a,emptyfset())),convs(sequent(a,b))),_1) -> #*(convs(sequent(a,emptyfset())),_1)
     #90: #*(*(convs(sequent(virg(f,a),b)),convs(sequent(a,emptyfset()))),_1) -> #*(convs(sequent(a,emptyfset())),_1)
     #91: #virg(virg(a,a),_1) -> #virg(a,_1)
     #92: #virg(virg(emptyfset(),a),_1) -> #virg(a,_1)
     #93: #virg(x,virg(y,z)) ->= #virg(virg(x,y),z)
     #94: #virg(x,virg(y,z)) ->= #virg(x,y)
     #95: #*(*(convs(sequent(emptyfset(),b)),convs(sequent(a,virg(f,b)))),_1) -> #*(convs(sequent(emptyfset(),b)),_1)
Number of SCCs: 2, DPs: 16
  SCC { #91..94 }
POLO(Sum)... succeeded.
      #sequent	w: x1 + x2
      1 	w: 0
      ron	w: x1 + x2 + 42152
      convs	w: 0
      #. 	w: 0
      emptyfset	w: 1
      #exists	w: 0
      and	w: x1 + x2 + 2
      #ron	w: 0
      convf	w: x1 + 1
      #substf	w: x2
      #virg	w: x1 + x2
      #* 	w: 0
      Pe	w: 0
      #substt	w: 0
      substf	w: 3
      forall	w: 16207
      virg	w: x1 + x2 + 1
      #imp	w: 0
      or	w: x1 + x2 + 2
      neg	w: x1 + 2
      . 	w: x2 + 1
      ef	w: x1 + 1
      #convs	w: x1
      emptysset	w: 0
      id	w: 1
      #or	w: 0
      #neg	w: 0
      substt	w: x1 + x2 + 42151
      imp	w: 1
      sequent	w: x1 + x2
      #and	w: 0
      * 	w: 0
      shift	w: 13324
      exists	w: 16207
    USABLE RULES: { 14..22 30..37 54 }
    Removed DPs: #91 #92 #94
Number of SCCs: 2, DPs: 13
  SCC { #93 }
only weak rules.
Number of SCCs: 1, DPs: 12
  SCC { #80..90 #95 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.