YES
Input TRS:
      1: active(fib(N)) -> mark(sel(N,fib1(s(0()),s(0()))))
      2: active(fib1(X,Y)) -> mark(cons(X,fib1(Y,add(X,Y))))
      3: active(add(0(),X)) -> mark(X)
      4: active(add(s(X),Y)) -> mark(s(add(X,Y)))
      5: active(sel(0(),cons(X,XS))) -> mark(X)
      6: active(sel(s(N),cons(X,XS))) -> mark(sel(N,XS))
      7: active(fib(X)) -> fib(active(X))
      8: active(sel(X1,X2)) -> sel(active(X1),X2)
      9: active(sel(X1,X2)) -> sel(X1,active(X2))
      10: active(fib1(X1,X2)) -> fib1(active(X1),X2)
      11: active(fib1(X1,X2)) -> fib1(X1,active(X2))
      12: active(s(X)) -> s(active(X))
      13: active(cons(X1,X2)) -> cons(active(X1),X2)
      14: active(add(X1,X2)) -> add(active(X1),X2)
      15: active(add(X1,X2)) -> add(X1,active(X2))
      16: fib(mark(X)) -> mark(fib(X))
      17: sel(mark(X1),X2) -> mark(sel(X1,X2))
      18: sel(X1,mark(X2)) -> mark(sel(X1,X2))
      19: fib1(mark(X1),X2) -> mark(fib1(X1,X2))
      20: fib1(X1,mark(X2)) -> mark(fib1(X1,X2))
      21: s(mark(X)) -> mark(s(X))
      22: cons(mark(X1),X2) -> mark(cons(X1,X2))
      23: add(mark(X1),X2) -> mark(add(X1,X2))
      24: add(X1,mark(X2)) -> mark(add(X1,X2))
      25: proper(fib(X)) -> fib(proper(X))
      26: proper(sel(X1,X2)) -> sel(proper(X1),proper(X2))
      27: proper(fib1(X1,X2)) -> fib1(proper(X1),proper(X2))
      28: proper(s(X)) -> s(proper(X))
      29: proper(0()) -> ok(0())
      30: proper(cons(X1,X2)) -> cons(proper(X1),proper(X2))
      31: proper(add(X1,X2)) -> add(proper(X1),proper(X2))
      32: fib(ok(X)) -> ok(fib(X))
      33: sel(ok(X1),ok(X2)) -> ok(sel(X1,X2))
      34: fib1(ok(X1),ok(X2)) -> ok(fib1(X1,X2))
      35: s(ok(X)) -> ok(s(X))
      36: cons(ok(X1),ok(X2)) -> ok(cons(X1,X2))
      37: add(ok(X1),ok(X2)) -> ok(add(X1,X2))
      38: top(mark(X)) -> top(proper(X))
      39: top(ok(X)) -> top(active(X))
Number of strict rules: 39
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #active(fib1(X,Y)) -> #cons(X,fib1(Y,add(X,Y)))
     #2: #active(fib1(X,Y)) -> #fib1(Y,add(X,Y))
     #3: #active(fib1(X,Y)) -> #add(X,Y)
     #4: #s(ok(X)) -> #s(X)
     #5: #add(ok(X1),ok(X2)) -> #add(X1,X2)
     #6: #top(mark(X)) -> #top(proper(X))
     #7: #top(mark(X)) -> #proper(X)
     #8: #active(sel(s(N),cons(X,XS))) -> #sel(N,XS)
     #9: #active(cons(X1,X2)) -> #cons(active(X1),X2)
     #10: #active(cons(X1,X2)) -> #active(X1)
     #11: #active(sel(X1,X2)) -> #sel(X1,active(X2))
     #12: #active(sel(X1,X2)) -> #active(X2)
     #13: #active(fib1(X1,X2)) -> #fib1(X1,active(X2))
     #14: #active(fib1(X1,X2)) -> #active(X2)
     #15: #add(X1,mark(X2)) -> #add(X1,X2)
     #16: #add(mark(X1),X2) -> #add(X1,X2)
     #17: #active(s(X)) -> #s(active(X))
     #18: #active(s(X)) -> #active(X)
     #19: #proper(add(X1,X2)) -> #add(proper(X1),proper(X2))
     #20: #proper(add(X1,X2)) -> #proper(X1)
     #21: #proper(add(X1,X2)) -> #proper(X2)
     #22: #active(add(X1,X2)) -> #add(active(X1),X2)
     #23: #active(add(X1,X2)) -> #active(X1)
     #24: #proper(cons(X1,X2)) -> #cons(proper(X1),proper(X2))
     #25: #proper(cons(X1,X2)) -> #proper(X1)
     #26: #proper(cons(X1,X2)) -> #proper(X2)
     #27: #proper(fib(X)) -> #fib(proper(X))
     #28: #proper(fib(X)) -> #proper(X)
     #29: #fib1(X1,mark(X2)) -> #fib1(X1,X2)
     #30: #active(fib(X)) -> #fib(active(X))
     #31: #active(fib(X)) -> #active(X)
     #32: #top(ok(X)) -> #top(active(X))
     #33: #top(ok(X)) -> #active(X)
     #34: #active(fib1(X1,X2)) -> #fib1(active(X1),X2)
     #35: #active(fib1(X1,X2)) -> #active(X1)
     #36: #sel(ok(X1),ok(X2)) -> #sel(X1,X2)
     #37: #proper(s(X)) -> #s(proper(X))
     #38: #proper(s(X)) -> #proper(X)
     #39: #cons(mark(X1),X2) -> #cons(X1,X2)
     #40: #fib1(ok(X1),ok(X2)) -> #fib1(X1,X2)
     #41: #proper(fib1(X1,X2)) -> #fib1(proper(X1),proper(X2))
     #42: #proper(fib1(X1,X2)) -> #proper(X1)
     #43: #proper(fib1(X1,X2)) -> #proper(X2)
     #44: #sel(mark(X1),X2) -> #sel(X1,X2)
     #45: #fib(ok(X)) -> #fib(X)
     #46: #fib1(mark(X1),X2) -> #fib1(X1,X2)
     #47: #proper(sel(X1,X2)) -> #sel(proper(X1),proper(X2))
     #48: #proper(sel(X1,X2)) -> #proper(X1)
     #49: #proper(sel(X1,X2)) -> #proper(X2)
     #50: #cons(ok(X1),ok(X2)) -> #cons(X1,X2)
     #51: #s(mark(X)) -> #s(X)
     #52: #fib(mark(X)) -> #fib(X)
     #53: #active(fib(N)) -> #sel(N,fib1(s(0()),s(0())))
     #54: #active(fib(N)) -> #fib1(s(0()),s(0()))
     #55: #active(fib(N)) -> #s(0())
     #56: #active(fib(N)) -> #s(0())
     #57: #active(sel(X1,X2)) -> #sel(active(X1),X2)
     #58: #active(sel(X1,X2)) -> #active(X1)
     #59: #active(add(X1,X2)) -> #add(X1,active(X2))
     #60: #active(add(X1,X2)) -> #active(X2)
     #61: #active(add(s(X),Y)) -> #s(add(X,Y))
     #62: #active(add(s(X),Y)) -> #add(X,Y)
     #63: #sel(X1,mark(X2)) -> #sel(X1,X2)
Number of SCCs: 9, DPs: 36
  SCC { #45 #52 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: 0
      proper	w: 0
      fib	w: 0
      ok	w: x1 + 1
      0 	w: 0
      #sel	w: 0
      sel	w: 0
      #s 	w: 0
      mark	w: x1 + 1
      #proper	w: 0
      active	w: 0
      cons	w: 0
      #active	w: 0
      #add	w: 0
      add	w: 0
      #fib	w: x1
    USABLE RULES: { }
    Removed DPs: #45 #52
Number of SCCs: 8, DPs: 34
  SCC { #4 #51 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: 0
      proper	w: 0
      fib	w: 0
      ok	w: x1 + 1
      0 	w: 0
      #sel	w: 0
      sel	w: 0
      #s 	w: x1
      mark	w: x1 + 1
      #proper	w: 0
      active	w: 0
      cons	w: 0
      #active	w: 0
      #add	w: 0
      add	w: 0
      #fib	w: 0
    USABLE RULES: { }
    Removed DPs: #4 #51
Number of SCCs: 7, DPs: 32
  SCC { #6 #32 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      #cons	s: [2,1]	p: 0	w: max(x1 + 1, x2 + 1)
      s 	s: [1]	p: 4	w: x1
      top	s: []	p: 0	w: 1
      #top	s: 1
      #fib1	s: []	p: 0	w: max(x2 + 1)
      fib1	s: [1,2]	p: 3	w: max(x1 + 7746, x2 + 7746)
      proper	s: 1
      fib	s: [1]	p: 4	w: x1 + 65504
      ok	s: 1
      0 	s: []	p: 5	w: 1
      #sel	s: [1,2]	p: 0	w: x1 + x2 + 1
      sel	s: [1,2]	p: 1	w: x1 + x2 + 57757
      #s 	s: []	p: 0	w: 1
      mark	s: [1]	p: 0	w: x1
      #proper	s: []	p: 0	w: 1
      active	s: 1
      cons	s: [1]	p: 2	w: max(x1, x2)
      #active	s: []	p: 0	w: 1
      #add	s: []	p: 0	w: max(x1 + 1)
      add	s: [2,1]	p: 5	w: max(x1, x2)
      #fib	s: []	p: 0	w: 1
    USABLE RULES: { 1..37 }
    Removed DPs: #6
Number of SCCs: 7, DPs: 31
  SCC { #32 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: x1 + 26531
      top	w: 0
      #top	w: x1
      #fib1	w: 0
      fib1	w: x1 + 14459
      proper	w: x1 + 2
      fib	w: x1 + 1
      ok	w: x1 + 2
      0 	w: 1
      #sel	w: 0
      sel	w: x1 + 1
      #s 	w: 0
      mark	w: 1
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1 + 29273
      #active	w: 0
      #add	w: 0
      add	w: x1 + 1
      #fib	w: 0
    USABLE RULES: { 1..37 }
    Removed DPs: #32
Number of SCCs: 6, DPs: 30
  SCC { #39 #50 }
POLO(Sum)... succeeded.
      #cons	w: x2
      s 	w: x1 + 1
      top	w: 0
      #top	w: x1
      #fib1	w: 0
      fib1	w: x1 + 13068
      proper	w: x1 + 1
      fib	w: x1 + 1
      ok	w: x1 + 1
      0 	w: 1
      #sel	w: 0
      sel	w: x1 + 1
      #s 	w: 0
      mark	w: 1
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1 + 22863
      #active	w: 0
      #add	w: 0
      add	w: x1 + 1
      #fib	w: 0
    USABLE RULES: { 1..37 }
    Removed DPs: #50
Number of SCCs: 6, DPs: 29
  SCC { #39 }
POLO(Sum)... succeeded.
      #cons	w: x1
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 113815
      ok	w: x1 + 1
      0 	w: 1
      #sel	w: 0
      sel	w: x1 + 56907
      #s 	w: 0
      mark	w: x1 + 56909
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 56906
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #39
Number of SCCs: 5, DPs: 28
  SCC { #5 #15 #16 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 156176
      ok	w: x1 + 1
      0 	w: 31364
      #sel	w: 0
      sel	w: x1 + 62406
      #s 	w: 0
      mark	w: x1 + 93771
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: x1 + x2
      add	w: x1 + x2 + 62405
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #5 #15 #16
Number of SCCs: 4, DPs: 25
  SCC { #29 #40 #46 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: x1
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 93657
      ok	w: x1 + 1
      0 	w: 31249
      #sel	w: 0
      sel	w: x1 + 62406
      #s 	w: 0
      mark	w: x1 + 31252
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #40 #46
Number of SCCs: 4, DPs: 23
  SCC { #29 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: x2
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 2565
      ok	w: x1 + 1
      0 	w: 1
      #sel	w: 0
      sel	w: x1 + 2562
      #s 	w: 0
      mark	w: x1 + 4
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #29
Number of SCCs: 3, DPs: 22
  SCC { #36 #44 #63 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 5
      ok	w: x1 + 1
      0 	w: 1
      #sel	w: x2
      sel	w: x1 + 2
      #s 	w: 0
      mark	w: x1 + 4
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #36 #63
Number of SCCs: 3, DPs: 20
  SCC { #44 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 0
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1
      proper	w: x1 + 1
      fib	w: x1 + 8487
      ok	w: x1 + 1
      0 	w: 1
      #sel	w: x1
      sel	w: x1 + 8484
      #s 	w: 0
      mark	w: x1 + 4
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16 22..24 29 32 36 37 }
    Removed DPs: #44
Number of SCCs: 2, DPs: 19
  SCC { #10 #12 #14 #18 #23 #31 #35 #58 #60 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: x1 + 17209
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1 + x2 + 1
      proper	w: 0
      fib	w: x1
      ok	w: x1 + 30595
      0 	w: 17211
      #sel	w: 0
      sel	w: x1 + x2
      #s 	w: 0
      mark	w: 17212
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: x1
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16..20 22..24 32..34 36 37 }
    Removed DPs: #14 #18 #23 #35 #60
Number of SCCs: 2, DPs: 14
  SCC { #10 #12 #31 #58 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: x1 + 1
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1 + x2 + 2
      proper	w: 0
      fib	w: x1 + 1
      ok	w: x1 + 1
      0 	w: 32113
      #sel	w: 0
      sel	w: x1 + x2
      #s 	w: 0
      mark	w: 4
      #proper	w: 0
      active	w: x1 + 1
      cons	w: x1
      #active	w: x1
      #add	w: 0
      add	w: x1 + x2 + 1
      #fib	w: 0
    USABLE RULES: { 16..20 22..24 32..34 36 37 }
    Removed DPs: #31
Number of SCCs: 2, DPs: 13
  SCC { #10 #12 #58 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: 2
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: 1
      proper	w: 0
      fib	w: 2
      ok	w: 1
      0 	w: 43368
      #sel	w: 0
      sel	w: x1 + x2
      #s 	w: 0
      mark	w: x1
      #proper	w: 0
      active	w: 1
      cons	w: x1 + 2
      #active	w: x1
      #add	w: 0
      add	w: 1
      #fib	w: 0
    USABLE RULES: { 17..20 22..24 32..34 36 37 }
    Removed DPs: #10
Number of SCCs: 2, DPs: 12
  SCC { #12 #58 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: x1 + 1
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: 0
      proper	w: 0
      fib	w: 4
      ok	w: 4
      0 	w: 2
      #sel	w: 0
      sel	w: x1 + x2 + 1
      #s 	w: 0
      mark	w: 3
      #proper	w: 0
      active	w: x1 + 1
      cons	w: 3
      #active	w: x1
      #add	w: 0
      add	w: x1 + x2
      #fib	w: 0
    USABLE RULES: { 17 18 22..24 32 33 }
    Removed DPs: #12 #58
Number of SCCs: 1, DPs: 10
  SCC { #20 #21 #25 #26 #28 #38 #42 #43 #48 #49 }
POLO(Sum)... succeeded.
      #cons	w: 0
      s 	w: x1 + 1
      top	w: 0
      #top	w: 0
      #fib1	w: 0
      fib1	w: x1 + x2 + 1
      proper	w: 0
      fib	w: x1 + 1
      ok	w: 4336
      0 	w: 1
      #sel	w: 0
      sel	w: x1 + x2 + 1
      #s 	w: 0
      mark	w: x1 + 22818
      #proper	w: x1
      active	w: 22824
      cons	w: x1 + x2 + 1
      #active	w: 0
      #add	w: 0
      add	w: x1 + x2 + 6
      #fib	w: 0
    USABLE RULES: { 17..20 22..24 32..34 36 37 }
    Removed DPs: #20 #21 #25 #26 #28 #38 #42 #43 #48 #49
Number of SCCs: 0, DPs: 0