MAYBE
Input TRS:
      1: eq(0(),0()) -> true()
      2: eq(0(),s(y)) -> false()
      3: eq(s(x),0()) -> false()
      4: eq(s(x),s(y)) -> eq(x,y)
      5: lt(0(),s(y)) -> true()
      6: lt(x,0()) -> false()
      7: lt(s(x),s(y)) -> lt(x,y)
      8: bin2s(nil()) -> 0()
      9: bin2s(cons(x,xs)) -> bin2ss(x,xs)
      10: bin2ss(x,nil()) -> x
      11: bin2ss(x,cons(0(),xs)) -> bin2ss(double(x),xs)
      12: bin2ss(x,cons(1(),xs)) -> bin2ss(s(double(x)),xs)
      13: half(0()) -> 0()
      14: half(s(0())) -> 0()
      15: half(s(s(x))) -> s(half(x))
      16: log(0()) -> 0()
      17: log(s(0())) -> 0()
      18: log(s(s(x))) -> s(log(half(s(s(x)))))
      19: more(nil()) -> nil()
      20: more(cons(xs,ys)) -> cons(cons(0(),xs),cons(cons(1(),xs),cons(xs,ys)))
      21: s2bin(x) -> s2bin1(x,0(),cons(nil(),nil()))
      22: s2bin1(x,y,lists) -> if1(lt(y,log(x)),x,y,lists)
      23: if1(true(),x,y,lists) -> s2bin1(x,s(y),more(lists))
      24: if1(false(),x,y,lists) -> s2bin2(x,lists)
      25: s2bin2(x,nil()) -> bug_list_not()
      26: s2bin2(x,cons(xs,ys)) -> if2(eq(x,bin2s(xs)),x,xs,ys)
      27: if2(true(),x,xs,ys) -> xs
      28: if2(false(),x,xs,ys) -> s2bin2(x,ys)
Number of strict rules: 28
Direct POLO(bPol) ... failed.
Uncurrying half
      1: eq(0(),0()) -> true()
      2: eq(0(),s(y)) -> false()
      3: eq(s(x),0()) -> false()
      4: eq(s(x),s(y)) -> eq(x,y)
      5: lt(0(),s(y)) -> true()
      6: lt(x,0()) -> false()
      7: lt(s(x),s(y)) -> lt(x,y)
      8: bin2s(nil()) -> 0()
      9: bin2s(cons(x,xs)) -> bin2ss(x,xs)
      10: bin2ss(x,nil()) -> x
      11: bin2ss(x,cons(0(),xs)) -> bin2ss(double(x),xs)
      12: bin2ss(x,cons(1(),xs)) -> bin2ss(s(double(x)),xs)
      13: half^1_0() -> 0()
      14: half^1_s(0()) -> 0()
      15: half^1_s(s(x)) -> s(half(x))
      16: log(0()) -> 0()
      17: log(s(0())) -> 0()
      18: log(s(s(x))) -> s(log(half^1_s(s(x))))
      19: more(nil()) -> nil()
      20: more(cons(xs,ys)) -> cons(cons(0(),xs),cons(cons(1(),xs),cons(xs,ys)))
      21: s2bin(x) -> s2bin1(x,0(),cons(nil(),nil()))
      22: s2bin1(x,y,lists) -> if1(lt(y,log(x)),x,y,lists)
      23: if1(true(),x,y,lists) -> s2bin1(x,s(y),more(lists))
      24: if1(false(),x,y,lists) -> s2bin2(x,lists)
      25: s2bin2(x,nil()) -> bug_list_not()
      26: s2bin2(x,cons(xs,ys)) -> if2(eq(x,bin2s(xs)),x,xs,ys)
      27: if2(true(),x,xs,ys) -> xs
      28: if2(false(),x,xs,ys) -> s2bin2(x,ys)
      29: half(0()) ->= half^1_0()
      30: half(s(_1)) ->= half^1_s(_1)
Number of strict rules: 28
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #half(0()) ->? #half^1_0()
     #2: #bin2s(cons(x,xs)) -> #bin2ss(x,xs)
     #3: #bin2ss(x,cons(0(),xs)) -> #bin2ss(double(x),xs)
     #4: #if1(false(),x,y,lists) -> #s2bin2(x,lists)
     #5: #if1(true(),x,y,lists) -> #s2bin1(x,s(y),more(lists))
     #6: #if1(true(),x,y,lists) -> #more(lists)
     #7: #bin2ss(x,cons(1(),xs)) -> #bin2ss(s(double(x)),xs)
     #8: #half(s(_1)) ->? #half^1_s(_1)
     #9: #lt(s(x),s(y)) -> #lt(x,y)
     #10: #if2(false(),x,xs,ys) -> #s2bin2(x,ys)
     #11: #s2bin1(x,y,lists) -> #if1(lt(y,log(x)),x,y,lists)
     #12: #s2bin1(x,y,lists) -> #lt(y,log(x))
     #13: #s2bin1(x,y,lists) -> #log(x)
     #14: #s2bin2(x,cons(xs,ys)) -> #if2(eq(x,bin2s(xs)),x,xs,ys)
     #15: #s2bin2(x,cons(xs,ys)) -> #eq(x,bin2s(xs))
     #16: #s2bin2(x,cons(xs,ys)) -> #bin2s(xs)
     #17: #s2bin(x) -> #s2bin1(x,0(),cons(nil(),nil()))
     #18: #half^1_s(s(x)) -> #half(x)
     #19: #eq(s(x),s(y)) -> #eq(x,y)
     #20: #log(s(s(x))) -> #log(half^1_s(s(x)))
     #21: #log(s(s(x))) -> #half^1_s(s(x))
Number of SCCs: 7, DPs: 11
  SCC { #9 }
POLO(Sum)... succeeded.
      bin2ss	w: 0
      1 	w: 0
      #s2bin1	w: 0
      s 	w: x1 + 1
      #s2bin	w: 0
      #lt	w: x1 + x2
      eq	w: 0
      if1	w: 0
      false	w: 0
      #bin2ss	w: 0
      #log	w: 0
      #half	w: 0
      #more	w: 0
      half^1_s	w: 0
      #s2bin2	w: 0
      true	w: 0
      bin2s	w: 0
      more	w: 0
      #eq	w: 0
      #if1	w: 0
      half	w: 0
      if2	w: 0
      log	w: 0
      0 	w: 0
      double	w: 0
      nil	w: 0
      #half^1_s	w: 0
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 0
      #bin2s	w: 0
      cons	w: 0
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: 0
      lt	w: 0
    USABLE RULES: { }
    Removed DPs: #9
Number of SCCs: 6, DPs: 10
  SCC { #19 }
POLO(Sum)... succeeded.
      bin2ss	w: 0
      1 	w: 0
      #s2bin1	w: 0
      s 	w: x1 + 1
      #s2bin	w: 0
      #lt	w: 0
      eq	w: 0
      if1	w: 0
      false	w: 0
      #bin2ss	w: 0
      #log	w: 0
      #half	w: 0
      #more	w: 0
      half^1_s	w: 0
      #s2bin2	w: 0
      true	w: 0
      bin2s	w: 0
      more	w: 0
      #eq	w: x1 + x2
      #if1	w: 0
      half	w: 0
      if2	w: 0
      log	w: 0
      0 	w: 0
      double	w: 0
      nil	w: 0
      #half^1_s	w: 0
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 0
      #bin2s	w: 0
      cons	w: 0
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: 0
      lt	w: 0
    USABLE RULES: { }
    Removed DPs: #19
Number of SCCs: 5, DPs: 9
  SCC { #20 }
POLO(Sum)... succeeded.
      bin2ss	w: 0
      1 	w: 0
      #s2bin1	w: 0
      s 	w: x1 + 2
      #s2bin	w: 0
      #lt	w: 0
      eq	w: 0
      if1	w: 0
      false	w: 0
      #bin2ss	w: 0
      #log	w: x1
      #half	w: 0
      #more	w: 0
      half^1_s	w: x1 + 1
      #s2bin2	w: 0
      true	w: 0
      bin2s	w: 0
      more	w: 0
      #eq	w: 0
      #if1	w: 0
      half	w: x1 + 1
      if2	w: 0
      log	w: 0
      0 	w: 1
      double	w: 0
      nil	w: 0
      #half^1_s	w: 0
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 1
      #bin2s	w: 0
      cons	w: 0
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: 0
      lt	w: 0
    USABLE RULES: { 13..15 29 30 }
    Removed DPs: #20
Number of SCCs: 4, DPs: 8
  SCC { #8 #18 }
POLO(Sum)... succeeded.
      bin2ss	w: 0
      1 	w: 0
      #s2bin1	w: 0
      s 	w: x1 + 1
      #s2bin	w: 0
      #lt	w: 0
      eq	w: 0
      if1	w: 0
      false	w: 0
      #bin2ss	w: 0
      #log	w: x1
      #half	w: x1
      #more	w: 0
      half^1_s	w: x1 + 62898
      #s2bin2	w: 0
      true	w: 0
      bin2s	w: 0
      more	w: 0
      #eq	w: 0
      #if1	w: 0
      half	w: x1 + 62898
      if2	w: 0
      log	w: 0
      0 	w: 16304
      double	w: 0
      nil	w: 0
      #half^1_s	w: x1
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 16304
      #bin2s	w: 0
      cons	w: 0
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: 0
      lt	w: 0
    USABLE RULES: { 13..15 29 30 }
    Removed DPs: #8 #18
Number of SCCs: 3, DPs: 6
  SCC { #3 #7 }
POLO(Sum)... succeeded.
      bin2ss	w: 0
      1 	w: 1
      #s2bin1	w: 0
      s 	w: x1 + 42207
      #s2bin	w: 0
      #lt	w: 0
      eq	w: 0
      if1	w: 0
      false	w: 0
      #bin2ss	w: x1 + x2
      #log	w: x1
      #half	w: 0
      #more	w: 0
      half^1_s	w: x1 + 62898
      #s2bin2	w: 0
      true	w: 0
      bin2s	w: 0
      more	w: 0
      #eq	w: 0
      #if1	w: 0
      half	w: x1 + 62898
      if2	w: 0
      log	w: 0
      0 	w: 16304
      double	w: 11943
      nil	w: 0
      #half^1_s	w: 0
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 16304
      #bin2s	w: 0
      cons	w: x1 + x2 + 54150
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: 0
      lt	w: 0
    USABLE RULES: { 13..15 29 30 }
    Removed DPs: #3 #7
Number of SCCs: 2, DPs: 4
  SCC { #10 #14 }
POLO(Sum)... succeeded.
      bin2ss	w: x1
      1 	w: 1
      #s2bin1	w: 0
      s 	w: x1
      #s2bin	w: 0
      #lt	w: 0
      eq	w: x2 + 1
      if1	w: 0
      false	w: 1
      #bin2ss	w: 0
      #log	w: x1
      #half	w: 0
      #more	w: 0
      half^1_s	w: 62899
      #s2bin2	w: x1 + x2
      true	w: 0
      bin2s	w: x1 + 1
      more	w: 0
      #eq	w: 0
      #if1	w: 0
      half	w: 62899
      if2	w: 0
      log	w: 0
      0 	w: 1
      double	w: 0
      nil	w: 1
      #half^1_s	w: 0
      s2bin2	w: 0
      s2bin1	w: 0
      s2bin	w: 0
      half^1_0	w: 1
      #bin2s	w: 0
      cons	w: x1 + x2 + 3
      #half^1_0	w: 0
      bug_list_not	w: 0
      #if2	w: x1 + x2 + x4
      lt	w: 0
    USABLE RULES: { 1..4 8..15 29 30 }
    Removed DPs: #10 #14
Number of SCCs: 1, DPs: 2
  SCC { #5 #11 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.