YES(?,O(n^1))

Problem:
 f(s(X)) -> f(X)
 g(cons(0(),Y)) -> g(Y)
 g(cons(s(X),Y)) -> s(X)
 h(cons(X,Y)) -> h(g(cons(X,Y)))

Proof:
 RT Transformation Processor:
  strict:
   f(s(X)) -> f(X)
   g(cons(0(),Y)) -> g(Y)
   g(cons(s(X),Y)) -> s(X)
   h(cons(X,Y)) -> h(g(cons(X,Y)))
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [h](x0) = x0 + 1,
    
    [g](x0) = x0,
    
    [cons](x0, x1) = x0 + x1,
    
    [0] = 8,
    
    [f](x0) = x0,
    
    [s](x0) = x0 + 16
   orientation:
    f(s(X)) = X + 16 >= X = f(X)
    
    g(cons(0(),Y)) = Y + 8 >= Y = g(Y)
    
    g(cons(s(X),Y)) = X + Y + 16 >= X + 16 = s(X)
    
    h(cons(X,Y)) = X + Y + 1 >= X + Y + 1 = h(g(cons(X,Y)))
   problem:
    strict:
     g(cons(s(X),Y)) -> s(X)
     h(cons(X,Y)) -> h(g(cons(X,Y)))
    weak:
     f(s(X)) -> f(X)
     g(cons(0(),Y)) -> g(Y)
   Matrix Interpretation Processor:
    dimension: 1
    interpretation:
     [h](x0) = x0 + 4,
     
     [g](x0) = x0 + 8,
     
     [cons](x0, x1) = x0 + x1 + 24,
     
     [0] = 16,
     
     [f](x0) = x0 + 1,
     
     [s](x0) = x0
    orientation:
     g(cons(s(X),Y)) = X + Y + 32 >= X = s(X)
     
     h(cons(X,Y)) = X + Y + 28 >= X + Y + 36 = h(g(cons(X,Y)))
     
     f(s(X)) = X + 1 >= X + 1 = f(X)
     
     g(cons(0(),Y)) = Y + 48 >= Y + 8 = g(Y)
    problem:
     strict:
      h(cons(X,Y)) -> h(g(cons(X,Y)))
     weak:
      g(cons(s(X),Y)) -> s(X)
      f(s(X)) -> f(X)
      g(cons(0(),Y)) -> g(Y)
    Bounds Processor:
     bound: 1
     enrichment: match-rt
     automaton:
      final states: {8,7}
      transitions:
       h1(12) -> 7*
       g1(7) -> 12*
       g1(11) -> 12*
       g1(8) -> 12*
       cons1(8,7) -> 11*
       cons1(7,7) -> 11*
       cons1(8,8) -> 11*
       cons1(7,8) -> 11*
       s1(7) -> 12*
       s1(8) -> 12*
       h0(7) -> 7*
       h0(8) -> 7*
       cons0(8,7) -> 7*
       cons0(7,7) -> 7*
       cons0(8,8) -> 7*
       cons0(7,8) -> 7*
       g0(7) -> 7*
       g0(8) -> 7*
       s0(7) -> 7*
       s0(8) -> 7*
       f0(7) -> 7*
       f0(8) -> 7*
       00() -> 8*
     problem:
      strict:
       
      weak:
       h(cons(X,Y)) -> h(g(cons(X,Y)))
       g(cons(s(X),Y)) -> s(X)
       f(s(X)) -> f(X)
       g(cons(0(),Y)) -> g(Y)
     Qed