YES(?,O(n^1))

Problem:
 f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v))
 f(x,y,y) -> y
 f(x,y,g(y)) -> x
 f(x,x,y) -> x
 f(g(x),x,y) -> y

Proof:
 Complexity Transformation Processor:
  strict:
   f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v))
   f(x,y,y) -> y
   f(x,y,g(y)) -> x
   f(x,x,y) -> x
   f(g(x),x,y) -> y
  weak:
   
  Matrix Interpretation Processor:
   dimension: 1
   max_matrix:
    1
    interpretation:
     [g](x0) = x0 + 1,
     
     [f](x0, x1, x2) = x0 + x1 + x2
    orientation:
     f(f(x,y,z),u,f(x,y,v)) = u + v + 2x + 2y + z >= u + v + x + y + z = f(x,y,f(z,u,v))
     
     f(x,y,y) = x + 2y >= y = y
     
     f(x,y,g(y)) = x + 2y + 1 >= x = x
     
     f(x,x,y) = 2x + y >= x = x
     
     f(g(x),x,y) = 2x + y + 1 >= y = y
    problem:
     strict:
      f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v))
      f(x,y,y) -> y
      f(x,x,y) -> x
     weak:
      f(x,y,g(y)) -> x
      f(g(x),x,y) -> y
    Matrix Interpretation Processor:
     dimension: 1
     max_matrix:
      1
      interpretation:
       [g](x0) = x0,
       
       [f](x0, x1, x2) = x0 + x1 + x2 + 1
      orientation:
       f(f(x,y,z),u,f(x,y,v)) = u + v + 2x + 2y + z + 3 >= u + v + x + y + z + 2 = f(x,y,f(z,u,v))
       
       f(x,y,y) = x + 2y + 1 >= y = y
       
       f(x,x,y) = 2x + y + 1 >= x = x
       
       f(x,y,g(y)) = x + 2y + 1 >= x = x
       
       f(g(x),x,y) = 2x + y + 1 >= y = y
      problem:
       strict:
        
       weak:
        f(f(x,y,z),u,f(x,y,v)) -> f(x,y,f(z,u,v))
        f(x,y,y) -> y
        f(x,x,y) -> x
        f(x,y,g(y)) -> x
        f(g(x),x,y) -> y
      Qed