YES

TRS:

  active(and(true(),X)) -> mark(X)
  active(and(false(),Y)) -> mark(false())
  active(if(true(),X,Y)) -> mark(X)
  active(if(false(),X,Y)) -> mark(Y)
  active(add(0(),X)) -> mark(X)
  active(add(s(X),Y)) -> mark(s(add(X,Y)))
  active(first(0(),X)) -> mark(nil())
  active(first(s(X),cons(Y,Z))) -> mark(cons(Y,first(X,Z)))
  active(from(X)) -> mark(cons(X,from(s(X))))
  mark(and(X1,X2)) -> active(and(mark(X1),X2))
  mark(true()) -> active(true())
  mark(false()) -> active(false())
  mark(if(X1,X2,X3)) -> active(if(mark(X1),X2,X3))
  mark(add(X1,X2)) -> active(add(mark(X1),X2))
  mark(0()) -> active(0())
  mark(s(X)) -> active(s(X))
  mark(first(X1,X2)) -> active(first(mark(X1),mark(X2)))
  mark(nil()) -> active(nil())
  mark(cons(X1,X2)) -> active(cons(X1,X2))
  mark(from(X)) -> active(from(X))
  and(mark(X1),X2) -> and(X1,X2)
  and(X1,mark(X2)) -> and(X1,X2)
  and(active(X1),X2) -> and(X1,X2)
  and(X1,active(X2)) -> and(X1,X2)
  if(mark(X1),X2,X3) -> if(X1,X2,X3)
  if(X1,mark(X2),X3) -> if(X1,X2,X3)
  if(X1,X2,mark(X3)) -> if(X1,X2,X3)
  if(active(X1),X2,X3) -> if(X1,X2,X3)
  if(X1,active(X2),X3) -> if(X1,X2,X3)
  if(X1,X2,active(X3)) -> if(X1,X2,X3)
  add(mark(X1),X2) -> add(X1,X2)
  add(X1,mark(X2)) -> add(X1,X2)
  add(active(X1),X2) -> add(X1,X2)
  add(X1,active(X2)) -> add(X1,X2)
  s(mark(X)) -> s(X)
  s(active(X)) -> s(X)
  first(mark(X1),X2) -> first(X1,X2)
  first(X1,mark(X2)) -> first(X1,X2)
  first(active(X1),X2) -> first(X1,X2)
  first(X1,active(X2)) -> first(X1,X2)
  cons(mark(X1),X2) -> cons(X1,X2)
  cons(X1,mark(X2)) -> cons(X1,X2)
  cons(active(X1),X2) -> cons(X1,X2)
  cons(X1,active(X2)) -> cons(X1,X2)
  from(mark(X)) -> from(X)
  from(active(X)) -> from(X)

max/plus interpretations on N:

  active_A(x1) = max{89, x1}
  active#_A(x1) = max{173, 59 + x1}
  and_A(x1,x2) = max{83, 31 + x1, 102 + x2}
  and#_A(x1,x2) = max{139, 245, 162}
  true_A = 81
  true#_A = 225
  mark_A(x1) = max{17, 50 + x1}
  mark#_A(x1) = max{141, 143 + x1}
  false_A = 52
  false#_A = 196
  if_A(x1,x2,x3) = max{16, x1, 169 + x2, 84 + x3}
  if#_A(x1,x2,x3) = max{233, 128, 143 + x2, 144 + x3}
  add_A(x1,x2) = max{41, 42 + x1, 85 + x2}
  add#_A(x1,x2) = max{181, 183, 180}
  0_A = 39
  0#_A = 314
  s_A(x1) = max{39, 36}
  s#_A(x1) = max{173, 84}
  first_A(x1,x2) = max{112, 213 + x1, 145 + x2}
  first#_A(x1,x2) = max{140, 138, 139}
  nil_A = 169
  nil#_A = 313
  cons_A(x1,x2) = max{29, 39, -56}
  cons#_A(x1,x2) = max{0, 1, 2}
  from_A(x1) = max{124, 33}
  from#_A(x1) = max{175, 174}

precedence:

  true = false = if = 0 > mark > and > active > add = first = from > s = nil = cons