YES

Problem:
 lcs(e(),y) -> 0()
 lcs(x,e()) -> 0()
 lcs(a(x),a(y)) -> s(lcs(x,y))
 lcs(b(x),b(y)) -> s(lcs(x,y))
 lcs(a(x),b(y)) -> max(lcs(x,b(y)),lcs(a(x),y))
 lcs(b(x),a(y)) -> max(lcs(x,a(y)),lcs(b(x),y))
 max(x,0()) -> 0()
 max(0(),y) -> 0()
 max(s(x),s(y)) -> max(x,y)

Proof:
 DP Processor:
  DPs:
   lcs#(a(x),a(y)) -> lcs#(x,y)
   lcs#(b(x),b(y)) -> lcs#(x,y)
   lcs#(a(x),b(y)) -> lcs#(a(x),y)
   lcs#(a(x),b(y)) -> lcs#(x,b(y))
   lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(x),y))
   lcs#(b(x),a(y)) -> lcs#(b(x),y)
   lcs#(b(x),a(y)) -> lcs#(x,a(y))
   lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y))
   max#(s(x),s(y)) -> max#(x,y)
  TRS:
   lcs(e(),y) -> 0()
   lcs(x,e()) -> 0()
   lcs(a(x),a(y)) -> s(lcs(x,y))
   lcs(b(x),b(y)) -> s(lcs(x,y))
   lcs(a(x),b(y)) -> max(lcs(x,b(y)),lcs(a(x),y))
   lcs(b(x),a(y)) -> max(lcs(x,a(y)),lcs(b(x),y))
   max(x,0()) -> 0()
   max(0(),y) -> 0()
   max(s(x),s(y)) -> max(x,y)
  Matrix Interpretation Processor: dim=1
   
   usable rules:
    lcs(e(),y) -> 0()
    lcs(x,e()) -> 0()
    lcs(a(x),a(y)) -> s(lcs(x,y))
    lcs(b(x),b(y)) -> s(lcs(x,y))
    lcs(a(x),b(y)) -> max(lcs(x,b(y)),lcs(a(x),y))
    lcs(b(x),a(y)) -> max(lcs(x,a(y)),lcs(b(x),y))
    max(x,0()) -> 0()
    max(0(),y) -> 0()
    max(s(x),s(y)) -> max(x,y)
   interpretation:
    [max#](x0, x1) = x1 + 6,
    
    [lcs#](x0, x1) = 3x0 + x1 + 1,
    
    [max](x0, x1) = 0,
    
    [b](x0) = 3x0 + 5,
    
    [s](x0) = 2x0 + 1,
    
    [a](x0) = 4x0 + 7,
    
    [0] = 0,
    
    [lcs](x0, x1) = 2x1 + 6,
    
    [e] = 4
   orientation:
    lcs#(a(x),a(y)) = 12x + 4y + 29 >= 3x + y + 1 = lcs#(x,y)
    
    lcs#(b(x),b(y)) = 9x + 3y + 21 >= 3x + y + 1 = lcs#(x,y)
    
    lcs#(a(x),b(y)) = 12x + 3y + 27 >= 12x + y + 22 = lcs#(a(x),y)
    
    lcs#(a(x),b(y)) = 12x + 3y + 27 >= 3x + 3y + 6 = lcs#(x,b(y))
    
    lcs#(a(x),b(y)) = 12x + 3y + 27 >= 2y + 12 = max#(lcs(x,b(y)),lcs(a(x),y))
    
    lcs#(b(x),a(y)) = 9x + 4y + 23 >= 9x + y + 16 = lcs#(b(x),y)
    
    lcs#(b(x),a(y)) = 9x + 4y + 23 >= 3x + 4y + 8 = lcs#(x,a(y))
    
    lcs#(b(x),a(y)) = 9x + 4y + 23 >= 2y + 12 = max#(lcs(x,a(y)),lcs(b(x),y))
    
    max#(s(x),s(y)) = 2y + 7 >= y + 6 = max#(x,y)
    
    lcs(e(),y) = 2y + 6 >= 0 = 0()
    
    lcs(x,e()) = 14 >= 0 = 0()
    
    lcs(a(x),a(y)) = 8y + 20 >= 4y + 13 = s(lcs(x,y))
    
    lcs(b(x),b(y)) = 6y + 16 >= 4y + 13 = s(lcs(x,y))
    
    lcs(a(x),b(y)) = 6y + 16 >= 0 = max(lcs(x,b(y)),lcs(a(x),y))
    
    lcs(b(x),a(y)) = 8y + 20 >= 0 = max(lcs(x,a(y)),lcs(b(x),y))
    
    max(x,0()) = 0 >= 0 = 0()
    
    max(0(),y) = 0 >= 0 = 0()
    
    max(s(x),s(y)) = 0 >= 0 = max(x,y)
   problem:
    DPs:
     
    TRS:
     lcs(e(),y) -> 0()
     lcs(x,e()) -> 0()
     lcs(a(x),a(y)) -> s(lcs(x,y))
     lcs(b(x),b(y)) -> s(lcs(x,y))
     lcs(a(x),b(y)) -> max(lcs(x,b(y)),lcs(a(x),y))
     lcs(b(x),a(y)) -> max(lcs(x,a(y)),lcs(b(x),y))
     max(x,0()) -> 0()
     max(0(),y) -> 0()
     max(s(x),s(y)) -> max(x,y)
   Qed