YES(?,O(n^3))

Problem:
 f(a()) -> g(h(a()))
 h(g(x)) -> g(h(f(x)))
 k(x,h(x),a()) -> h(x)
 k(f(x),y,x) -> f(x)

Proof:
 RT Transformation Processor:
  strict:
   f(a()) -> g(h(a()))
   h(g(x)) -> g(h(f(x)))
   k(x,h(x),a()) -> h(x)
   k(f(x),y,x) -> f(x)
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   interpretation:
    [k](x0, x1, x2) = x0 + x1 + x2 + 25,
    
    [g](x0) = x0 + 24,
    
    [h](x0) = x0,
    
    [f](x0) = x0,
    
    [a] = 0
   orientation:
    f(a()) = 0 >= 24 = g(h(a()))
    
    h(g(x)) = x + 24 >= x + 24 = g(h(f(x)))
    
    k(x,h(x),a()) = 2x + 25 >= x = h(x)
    
    k(f(x),y,x) = 2x + y + 25 >= x = f(x)
   problem:
    strict:
     f(a()) -> g(h(a()))
     h(g(x)) -> g(h(f(x)))
    weak:
     k(x,h(x),a()) -> h(x)
     k(f(x),y,x) -> f(x)
   Matrix Interpretation Processor:
    dimension: 1
    interpretation:
     [k](x0, x1, x2) = x0 + x1 + x2,
     
     [g](x0) = x0 + 1,
     
     [h](x0) = x0 + 2,
     
     [f](x0) = x0 + 4,
     
     [a] = 1
    orientation:
     f(a()) = 5 >= 4 = g(h(a()))
     
     h(g(x)) = x + 3 >= x + 7 = g(h(f(x)))
     
     k(x,h(x),a()) = 2x + 3 >= x + 2 = h(x)
     
     k(f(x),y,x) = 2x + y + 4 >= x + 4 = f(x)
    problem:
     strict:
      h(g(x)) -> g(h(f(x)))
     weak:
      f(a()) -> g(h(a()))
      k(x,h(x),a()) -> h(x)
      k(f(x),y,x) -> f(x)
    Matrix Interpretation Processor:
     dimension: 3
     interpretation:
                        [1 2 2]     [1 0 0]     [1 0 0]     [1]
      [k](x0, x1, x2) = [0 0 0]x0 + [0 1 0]x1 + [0 0 1]x2 + [7]
                        [0 0 1]     [0 0 0]     [0 0 0]     [7],
      
                [1 0 1]     [0]
      [g](x0) = [0 0 3]x0 + [1]
                [0 0 0]     [0],
      
                [1 1 0]     [1]
      [h](x0) = [0 0 0]x0 + [2]
                [0 0 0]     [0],
      
                [1 0 3]  
      [f](x0) = [0 0 1]x0
                [0 0 0]  ,
      
            [7]
      [a] = [1]
            [1]
     orientation:
                [1 0 4]    [2]    [1 0 4]    [1]             
      h(g(x)) = [0 0 0]x + [2] >= [0 0 0]x + [1] = g(h(f(x)))
                [0 0 0]    [0]    [0 0 0]    [0]             
      
               [10]    [9]            
      f(a()) = [1 ] >= [1] = g(h(a()))
               [0 ]    [0]            
      
                      [2 3 2]    [9 ]    [1 1 0]    [1]       
      k(x,h(x),a()) = [0 0 0]x + [10] >= [0 0 0]x + [2] = h(x)
                      [0 0 1]    [7 ]    [0 0 0]    [0]       
      
                    [2 0 5]    [1 0 0]    [1]    [1 0 3]        
      k(f(x),y,x) = [0 0 1]x + [0 1 0]y + [7] >= [0 0 1]x = f(x)
                    [0 0 0]    [0 0 0]    [7]    [0 0 0]        
     problem:
      strict:
       
      weak:
       h(g(x)) -> g(h(f(x)))
       f(a()) -> g(h(a()))
       k(x,h(x),a()) -> h(x)
       k(f(x),y,x) -> f(x)
     Qed