YES
O(n)
TRS:
 {
         first(0(), X) -> nil(),
  first(s(X), cons(Y)) -> cons(Y),
               from(X) -> cons(X)
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
           first(0(), X) -> nil(),
    first(s(X), cons(Y)) -> cons(Y),
                 from(X) -> cons(X)
   }
  BOUND:
   Automaton:
    {
         from_0(8) -> 6,
         from_0(7) -> 6,
         from_0(6) -> 6,
            s_0(8) -> 8,
            s_0(7) -> 8,
            s_0(6) -> 8,
         cons_1(8) -> 6,
         cons_1(7) -> 6,
         cons_1(6) -> 6,
         cons_0(8) -> 6,
         cons_0(7) -> 6,
         cons_0(6) -> 6,
             0_0() -> 7,
     first_0(8, 8) -> 6,
     first_0(8, 7) -> 6,
     first_0(8, 6) -> 6,
     first_0(7, 8) -> 6,
     first_0(7, 7) -> 6,
     first_0(7, 6) -> 6,
     first_0(6, 8) -> 6,
     first_0(6, 7) -> 6,
     first_0(6, 6) -> 6,
           nil_1() -> 6,
           nil_0() -> 6
    }
   Strict:
    {}
   Qed