YES

Problem:
 f(0()) -> true()
 f(1()) -> false()
 f(s(x)) -> f(x)
 if(true(),s(x),s(y)) -> s(x)
 if(false(),s(x),s(y)) -> s(y)
 g(x,c(y)) -> c(g(x,y))
 g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))

Proof:
 DP Processor:
  DPs:
   f#(s(x)) -> f#(x)
   g#(x,c(y)) -> g#(x,y)
   g#(x,c(y)) -> g#(s(x),y)
   g#(x,c(y)) -> f#(x)
   g#(x,c(y)) -> if#(f(x),c(g(s(x),y)),c(y))
   g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
  TRS:
   f(0()) -> true()
   f(1()) -> false()
   f(s(x)) -> f(x)
   if(true(),s(x),s(y)) -> s(x)
   if(false(),s(x),s(y)) -> s(y)
   g(x,c(y)) -> c(g(x,y))
   g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
  TDG Processor:
   DPs:
    f#(s(x)) -> f#(x)
    g#(x,c(y)) -> g#(x,y)
    g#(x,c(y)) -> g#(s(x),y)
    g#(x,c(y)) -> f#(x)
    g#(x,c(y)) -> if#(f(x),c(g(s(x),y)),c(y))
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
   TRS:
    f(0()) -> true()
    f(1()) -> false()
    f(s(x)) -> f(x)
    if(true(),s(x),s(y)) -> s(x)
    if(false(),s(x),s(y)) -> s(y)
    g(x,c(y)) -> c(g(x,y))
    g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
   graph:
    g#(x,c(y)) -> g#(s(x),y) ->
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
    g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> if#(f(x),c(g(s(x),y)),c(y))
    g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> f#(x)
    g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> g#(s(x),y)
    g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> g#(x,y)
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y))) ->
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y))) ->
    g#(x,c(y)) -> if#(f(x),c(g(s(x),y)),c(y))
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y))) ->
    g#(x,c(y)) -> f#(x)
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y))) ->
    g#(x,c(y)) -> g#(s(x),y)
    g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y))) -> g#(x,c(y)) -> g#(x,y)
    g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
    g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> if#(f(x),c(g(s(x),y)),c(y))
    g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> f#(x)
    g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(s(x),y)
    g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(x,y)
    g#(x,c(y)) -> f#(x) -> f#(s(x)) -> f#(x)
    f#(s(x)) -> f#(x) -> f#(s(x)) -> f#(x)
   SCC Processor:
    #sccs: 2
    #rules: 4
    #arcs: 17/36
    DPs:
     g#(x,c(y)) -> g#(s(x),y)
     g#(x,c(y)) -> g#(x,y)
     g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
    TRS:
     f(0()) -> true()
     f(1()) -> false()
     f(s(x)) -> f(x)
     if(true(),s(x),s(y)) -> s(x)
     if(false(),s(x),s(y)) -> s(y)
     g(x,c(y)) -> c(g(x,y))
     g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
    EDG Processor:
     DPs:
      g#(x,c(y)) -> g#(s(x),y)
      g#(x,c(y)) -> g#(x,y)
      g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
     TRS:
      f(0()) -> true()
      f(1()) -> false()
      f(s(x)) -> f(x)
      if(true(),s(x),s(y)) -> s(x)
      if(false(),s(x),s(y)) -> s(y)
      g(x,c(y)) -> c(g(x,y))
      g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
     graph:
      g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> g#(x,y)
      g#(x,c(y)) -> g#(s(x),y) -> g#(x,c(y)) -> g#(s(x),y)
      g#(x,c(y)) -> g#(s(x),y) ->
      g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
      g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(x,y)
      g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(s(x),y)
      g#(x,c(y)) -> g#(x,y) -> g#(x,c(y)) -> g#(x,if(f(x),c(g(s(x),y)),c(y)))
     SCC Processor:
      #sccs: 1
      #rules: 2
      #arcs: 6/9
      DPs:
       g#(x,c(y)) -> g#(s(x),y)
       g#(x,c(y)) -> g#(x,y)
      TRS:
       f(0()) -> true()
       f(1()) -> false()
       f(s(x)) -> f(x)
       if(true(),s(x),s(y)) -> s(x)
       if(false(),s(x),s(y)) -> s(y)
       g(x,c(y)) -> c(g(x,y))
       g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
      Size-Change Termination Processor:
       DPs:
        
       TRS:
        f(0()) -> true()
        f(1()) -> false()
        f(s(x)) -> f(x)
        if(true(),s(x),s(y)) -> s(x)
        if(false(),s(x),s(y)) -> s(y)
        g(x,c(y)) -> c(g(x,y))
        g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
       The DP: g#(x,c(y)) -> g#(s(x),y) has the edges:
         1 >   1
       The DP: g#(x,c(y)) -> g#(x,y) has the edges:
         0 >=  0
         1 >   1
       Qed
    
    DPs:
     f#(s(x)) -> f#(x)
    TRS:
     f(0()) -> true()
     f(1()) -> false()
     f(s(x)) -> f(x)
     if(true(),s(x),s(y)) -> s(x)
     if(false(),s(x),s(y)) -> s(y)
     g(x,c(y)) -> c(g(x,y))
     g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
    Subterm Criterion Processor:
     simple projection:
      pi(f#) = 0
     problem:
      DPs:
       
      TRS:
       f(0()) -> true()
       f(1()) -> false()
       f(s(x)) -> f(x)
       if(true(),s(x),s(y)) -> s(x)
       if(false(),s(x),s(y)) -> s(y)
       g(x,c(y)) -> c(g(x,y))
       g(x,c(y)) -> g(x,if(f(x),c(g(s(x),y)),c(y)))
     Qed