YES

Problem:
 app(app(map(),f),nil()) -> nil()
 app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))

Proof:
 DP Processor:
  DPs:
   app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
   app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
   app#(app(map(),f),app(app(cons(),x),xs)) -> app#(cons(),app(f,x))
   app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(cons(),app(f,x)),app(app(map(),f),xs))
  TRS:
   app(app(map(),f),nil()) -> nil()
   app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
  CDG Processor:
   DPs:
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(cons(),app(f,x))
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(cons(),app(f,x)),app(app(map(),f),xs))
   TRS:
    app(app(map(),f),nil()) -> nil()
    app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
   graph:
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(cons(),app(f,x))
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(cons(),app(f,x)),app(app(map(),f),xs))
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(cons(),app(f,x))
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x) ->
    app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(cons(),app(f,x)),app(app(map(),f),xs))
   Restore Modifier:
    DPs:
     app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
     app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
     app#(app(map(),f),app(app(cons(),x),xs)) -> app#(cons(),app(f,x))
     app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(cons(),app(f,x)),app(app(map(),f),xs))
    TRS:
     app(app(map(),f),nil()) -> nil()
     app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
    SCC Processor:
     #sccs: 1
     #rules: 2
     #arcs: 8/16
     DPs:
      app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
      app#(app(map(),f),app(app(cons(),x),xs)) -> app#(f,x)
     TRS:
      app(app(map(),f),nil()) -> nil()
      app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
     Matrix Interpretation Processor:
      dimension: 1
      interpretation:
       [app#](x0, x1) = x0 + 1,
       
       [cons] = 0,
       
       [nil] = 1,
       
       [app](x0, x1) = x1 + 1,
       
       [map] = 0
      orientation:
       app#(app(map(),f),app(app(cons(),x),xs)) = f + 2 >= f + 2 = app#(app(map(),f),xs)
       
       app#(app(map(),f),app(app(cons(),x),xs)) = f + 2 >= f + 1 = app#(f,x)
       
       app(app(map(),f),nil()) = 2 >= 1 = nil()
       
       app(app(map(),f),app(app(cons(),x),xs)) = xs + 2 >= xs + 2 = app(app(cons(),app(f,x)),app(app(map(),f),xs))
      problem:
       DPs:
        app#(app(map(),f),app(app(cons(),x),xs)) -> app#(app(map(),f),xs)
       TRS:
        app(app(map(),f),nil()) -> nil()
        app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
      Matrix Interpretation Processor:
       dimension: 1
       interpretation:
        [app#](x0, x1) = x1 + 1,
        
        [cons] = 0,
        
        [nil] = 0,
        
        [app](x0, x1) = x1 + 1,
        
        [map] = 0
       orientation:
        app#(app(map(),f),app(app(cons(),x),xs)) = xs + 2 >= xs + 1 = app#(app(map(),f),xs)
        
        app(app(map(),f),nil()) = 1 >= 0 = nil()
        
        app(app(map(),f),app(app(cons(),x),xs)) = xs + 2 >= xs + 2 = app(app(cons(),app(f,x)),app(app(map(),f),xs))
       problem:
        DPs:
         
        TRS:
         app(app(map(),f),nil()) -> nil()
         app(app(map(),f),app(app(cons(),x),xs)) -> app(app(cons(),app(f,x)),app(app(map(),f),xs))
       Qed