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)
  TDG 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)
   graph:
    max#(s(x),s(y)) -> max#(x,y) -> max#(s(x),s(y)) -> max#(x,y)
    lcs#(b(x),b(y)) -> lcs#(x,y) ->
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y))
    lcs#(b(x),b(y)) -> lcs#(x,y) -> lcs#(b(x),a(y)) -> lcs#(x,a(y))
    lcs#(b(x),b(y)) -> lcs#(x,y) -> lcs#(b(x),a(y)) -> lcs#(b(x),y)
    lcs#(b(x),b(y)) -> lcs#(x,y) ->
    lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(x),y))
    lcs#(b(x),b(y)) -> lcs#(x,y) -> lcs#(a(x),b(y)) -> lcs#(x,b(y))
    lcs#(b(x),b(y)) -> lcs#(x,y) -> lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(b(x),b(y)) -> lcs#(x,y) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(b(x),b(y)) -> lcs#(x,y) ->
    lcs#(a(x),a(y)) -> lcs#(x,y)
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y)) ->
    max#(s(x),s(y)) -> max#(x,y)
    lcs#(b(x),a(y)) -> lcs#(b(x),y) ->
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(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)) -> lcs#(b(x),y) ->
    lcs#(b(x),a(y)) -> lcs#(b(x),y)
    lcs#(b(x),a(y)) -> lcs#(b(x),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#(a(x),b(y)) -> lcs#(x,b(y))
    lcs#(b(x),a(y)) -> lcs#(b(x),y) ->
    lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(b(x),a(y)) -> lcs#(b(x),y) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(b(x),a(y)) -> lcs#(b(x),y) -> lcs#(a(x),a(y)) -> lcs#(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))
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(b(x),a(y)) -> lcs#(x,a(y))
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(b(x),a(y)) -> lcs#(b(x),y)
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(x),y))
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(a(x),b(y)) -> lcs#(x,b(y))
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(b(x),a(y)) -> lcs#(x,a(y)) ->
    lcs#(a(x),a(y)) -> lcs#(x,y)
    lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(x),y)) ->
    max#(s(x),s(y)) -> max#(x,y)
    lcs#(a(x),b(y)) -> lcs#(a(x),y) ->
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y))
    lcs#(a(x),b(y)) -> lcs#(a(x),y) ->
    lcs#(b(x),a(y)) -> lcs#(x,a(y))
    lcs#(a(x),b(y)) -> lcs#(a(x),y) ->
    lcs#(b(x),a(y)) -> lcs#(b(x),y)
    lcs#(a(x),b(y)) -> lcs#(a(x),y) ->
    lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(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)) -> lcs#(a(x),y) ->
    lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(a(x),b(y)) -> lcs#(a(x),y) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(a(x),b(y)) -> lcs#(a(x),y) -> lcs#(a(x),a(y)) -> lcs#(x,y)
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) ->
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y))
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) ->
    lcs#(b(x),a(y)) -> lcs#(x,a(y))
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) ->
    lcs#(b(x),a(y)) -> lcs#(b(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#(a(x),b(y)) -> lcs#(x,b(y)) ->
    lcs#(a(x),b(y)) -> lcs#(x,b(y))
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) ->
    lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(a(x),b(y)) -> lcs#(x,b(y)) -> lcs#(a(x),a(y)) -> lcs#(x,y)
    lcs#(a(x),a(y)) -> lcs#(x,y) ->
    lcs#(b(x),a(y)) -> max#(lcs(x,a(y)),lcs(b(x),y))
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(b(x),a(y)) -> lcs#(x,a(y))
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(b(x),a(y)) -> lcs#(b(x),y)
    lcs#(a(x),a(y)) -> lcs#(x,y) ->
    lcs#(a(x),b(y)) -> max#(lcs(x,b(y)),lcs(a(x),y))
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(a(x),b(y)) -> lcs#(x,b(y))
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(a(x),b(y)) -> lcs#(a(x),y)
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(b(x),b(y)) -> lcs#(x,y)
    lcs#(a(x),a(y)) -> lcs#(x,y) -> lcs#(a(x),a(y)) -> lcs#(x,y)
   SCC Processor:
    #sccs: 2
    #rules: 7
    #arcs: 51/81
    DPs:
     lcs#(b(x),b(y)) -> lcs#(x,y)
     lcs#(a(x),a(y)) -> lcs#(x,y)
     lcs#(a(x),b(y)) -> lcs#(a(x),y)
     lcs#(a(x),b(y)) -> lcs#(x,b(y))
     lcs#(b(x),a(y)) -> lcs#(b(x),y)
     lcs#(b(x),a(y)) -> lcs#(x,a(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)
    Subterm Criterion Processor:
     simple projection:
      pi(lcs#) = 1
     problem:
      DPs:
       lcs#(a(x),b(y)) -> lcs#(x,b(y))
       lcs#(b(x),a(y)) -> lcs#(x,a(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)
     Subterm Criterion Processor:
      simple projection:
       pi(lcs#) = 0
      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
    
    DPs:
     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)
    Subterm Criterion Processor:
     simple projection:
      pi(max#) = 1
     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