YES

Problem:
 g(A()) -> A()
 g(B()) -> A()
 g(B()) -> B()
 g(C()) -> A()
 g(C()) -> B()
 g(C()) -> C()
 foldB(t,0()) -> t
 foldB(t,s(n)) -> f(foldB(t,n),B())
 foldC(t,0()) -> t
 foldC(t,s(n)) -> f(foldC(t,n),C())
 f(t,x) -> f'(t,g(x))
 f'(triple(a,b,c),C()) -> triple(a,b,s(c))
 f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
 f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b))
 f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c)
 fold(t,x,0()) -> t
 fold(t,x,s(n)) -> f(fold(t,x,n),x)

Proof:
 DP Processor:
  DPs:
   foldB#(t,s(n)) -> foldB#(t,n)
   foldB#(t,s(n)) -> f#(foldB(t,n),B())
   foldC#(t,s(n)) -> foldC#(t,n)
   foldC#(t,s(n)) -> f#(foldC(t,n),C())
   f#(t,x) -> g#(x)
   f#(t,x) -> f'#(t,g(x))
   f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A())
   f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b)
   f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b))
   f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c)
   fold#(t,x,s(n)) -> fold#(t,x,n)
   fold#(t,x,s(n)) -> f#(fold(t,x,n),x)
  TRS:
   g(A()) -> A()
   g(B()) -> A()
   g(B()) -> B()
   g(C()) -> A()
   g(C()) -> B()
   g(C()) -> C()
   foldB(t,0()) -> t
   foldB(t,s(n)) -> f(foldB(t,n),B())
   foldC(t,0()) -> t
   foldC(t,s(n)) -> f(foldC(t,n),C())
   f(t,x) -> f'(t,g(x))
   f'(triple(a,b,c),C()) -> triple(a,b,s(c))
   f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
   f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b))
   f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c)
   fold(t,x,0()) -> t
   fold(t,x,s(n)) -> f(fold(t,x,n),x)
  Matrix Interpretation Processor: dim=1
   
   interpretation:
    [fold#](x0, x1, x2) = 6x0 + 5x1 + 4x2 + 6,
    
    [f''#](x0) = 4x0 + 1,
    
    [f'#](x0, x1) = 4x0 + 2x1,
    
    [foldC#](x0, x1) = 4x0 + 4x1,
    
    [f#](x0, x1) = 4x0 + 4x1 + 5,
    
    [foldB#](x0, x1) = 4x0 + 5x1,
    
    [g#](x0) = 0,
    
    [fold](x0, x1, x2) = x0 + x2,
    
    [f''](x0) = x0 + 6,
    
    [triple](x0, x1, x2) = 2x1 + x2,
    
    [f'](x0, x1) = x0 + 6,
    
    [foldC](x0, x1) = x0 + x1,
    
    [f](x0, x1) = x0 + 6,
    
    [s](x0) = x0 + 6,
    
    [foldB](x0, x1) = x0 + x1,
    
    [0] = 0,
    
    [C] = 4,
    
    [B] = 6,
    
    [g](x0) = 2x0 + 2,
    
    [A] = 1
   orientation:
    foldB#(t,s(n)) = 5n + 4t + 30 >= 5n + 4t = foldB#(t,n)
    
    foldB#(t,s(n)) = 5n + 4t + 30 >= 4n + 4t + 29 = f#(foldB(t,n),B())
    
    foldC#(t,s(n)) = 4n + 4t + 24 >= 4n + 4t = foldC#(t,n)
    
    foldC#(t,s(n)) = 4n + 4t + 24 >= 4n + 4t + 21 = f#(foldC(t,n),C())
    
    f#(t,x) = 4t + 4x + 5 >= 0 = g#(x)
    
    f#(t,x) = 4t + 4x + 5 >= 4t + 4x + 4 = f'#(t,g(x))
    
    f'#(triple(a,b,c),B()) = 8b + 4c + 12 >= 8b + 4c + 9 = f#(triple(a,b,c),A())
    
    f'#(triple(a,b,c),A()) = 8b + 4c + 2 >= 5b + 4c = foldB#(triple(s(a),0(),c),b)
    
    f'#(triple(a,b,c),A()) = 8b + 4c + 2 >= 4b + 4c + 1 = f''#(foldB(triple(s(a),0(),c),b))
    
    f''#(triple(a,b,c)) = 8b + 4c + 1 >= 8b + 4c = foldC#(triple(a,b,0()),c)
    
    fold#(t,x,s(n)) = 4n + 6t + 5x + 30 >= 4n + 6t + 5x + 6 = fold#(t,x,n)
    
    fold#(t,x,s(n)) = 4n + 6t + 5x + 30 >= 4n + 4t + 4x + 5 = f#(fold(t,x,n),x)
    
    g(A()) = 4 >= 1 = A()
    
    g(B()) = 14 >= 1 = A()
    
    g(B()) = 14 >= 6 = B()
    
    g(C()) = 10 >= 1 = A()
    
    g(C()) = 10 >= 6 = B()
    
    g(C()) = 10 >= 4 = C()
    
    foldB(t,0()) = t >= t = t
    
    foldB(t,s(n)) = n + t + 6 >= n + t + 6 = f(foldB(t,n),B())
    
    foldC(t,0()) = t >= t = t
    
    foldC(t,s(n)) = n + t + 6 >= n + t + 6 = f(foldC(t,n),C())
    
    f(t,x) = t + 6 >= t + 6 = f'(t,g(x))
    
    f'(triple(a,b,c),C()) = 2b + c + 6 >= 2b + c + 6 = triple(a,b,s(c))
    
    f'(triple(a,b,c),B()) = 2b + c + 6 >= 2b + c + 6 = f(triple(a,b,c),A())
    
    f'(triple(a,b,c),A()) = 2b + c + 6 >= b + c + 6 = f''(foldB(triple(s(a),0(),c),b))
    
    f''(triple(a,b,c)) = 2b + c + 6 >= 2b + c = foldC(triple(a,b,0()),c)
    
    fold(t,x,0()) = t >= t = t
    
    fold(t,x,s(n)) = n + t + 6 >= n + t + 6 = f(fold(t,x,n),x)
   problem:
    DPs:
     
    TRS:
     g(A()) -> A()
     g(B()) -> A()
     g(B()) -> B()
     g(C()) -> A()
     g(C()) -> B()
     g(C()) -> C()
     foldB(t,0()) -> t
     foldB(t,s(n)) -> f(foldB(t,n),B())
     foldC(t,0()) -> t
     foldC(t,s(n)) -> f(foldC(t,n),C())
     f(t,x) -> f'(t,g(x))
     f'(triple(a,b,c),C()) -> triple(a,b,s(c))
     f'(triple(a,b,c),B()) -> f(triple(a,b,c),A())
     f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b))
     f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c)
     fold(t,x,0()) -> t
     fold(t,x,s(n)) -> f(fold(t,x,n),x)
   Qed