YES

Problem:
 and(true(),y) -> y
 and(false(),y) -> false()
 eq(nil(),nil()) -> true()
 eq(cons(t,l),nil()) -> false()
 eq(nil(),cons(t,l)) -> false()
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(var(l),var(l')) -> eq(l,l')
 eq(var(l),apply(t,s)) -> false()
 eq(var(l),lambda(x,t)) -> false()
 eq(apply(t,s),var(l)) -> false()
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false()
 eq(lambda(x,t),var(l)) -> false()
 eq(lambda(x,t),apply(t,s)) -> false()
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 if(true(),var(k),var(l')) -> var(k)
 if(false(),var(k),var(l')) -> var(l')
 ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
 ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
 ren(x,y,lambda(z,t)) ->
 lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(z,var
                                                                   (cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                 t)))

Proof:
 DP Processor:
  DPs:
   eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
   eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
   eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
   eq#(var(l),var(l')) -> eq#(l,l')
   eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
   eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
   eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
   eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
   eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
   eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
   ren#(var(l),var(k),var(l')) -> eq#(l,l')
   ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
   ren#(x,y,apply(t,s)) -> ren#(x,y,s)
   ren#(x,y,apply(t,s)) -> ren#(x,y,t)
   ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
   ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
  TRS:
   and(true(),y) -> y
   and(false(),y) -> false()
   eq(nil(),nil()) -> true()
   eq(cons(t,l),nil()) -> false()
   eq(nil(),cons(t,l)) -> false()
   eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
   eq(var(l),var(l')) -> eq(l,l')
   eq(var(l),apply(t,s)) -> false()
   eq(var(l),lambda(x,t)) -> false()
   eq(apply(t,s),var(l)) -> false()
   eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
   eq(apply(t,s),lambda(x,t)) -> false()
   eq(lambda(x,t),var(l)) -> false()
   eq(lambda(x,t),apply(t,s)) -> false()
   eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
   if(true(),var(k),var(l')) -> var(k)
   if(false(),var(k),var(l')) -> var(l')
   ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
   ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
   ren(x,y,lambda(z,t)) ->
   lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(z,
                                                                   var
                                                                   (cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                   t)))
  TDG Processor:
   DPs:
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    ren#(var(l),var(k),var(l')) -> eq#(l,l')
    ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
    ren#(x,y,apply(t,s)) -> ren#(x,y,s)
    ren#(x,y,apply(t,s)) -> ren#(x,y,t)
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
   TRS:
    and(true(),y) -> y
    and(false(),y) -> false()
    eq(nil(),nil()) -> true()
    eq(cons(t,l),nil()) -> false()
    eq(nil(),cons(t,l)) -> false()
    eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
    eq(var(l),var(l')) -> eq(l,l')
    eq(var(l),apply(t,s)) -> false()
    eq(var(l),lambda(x,t)) -> false()
    eq(apply(t,s),var(l)) -> false()
    eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
    eq(apply(t,s),lambda(x,t)) -> false()
    eq(lambda(x,t),var(l)) -> false()
    eq(lambda(x,t),apply(t,s)) -> false()
    eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
    if(true(),var(k),var(l')) -> var(k)
    if(false(),var(k),var(l')) -> var(l')
    ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
    ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
    ren(x,y,lambda(z,t)) ->
    lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
   graph:
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    ren#(var(l),var(k),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,t)
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,s)
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t) ->
    ren#(var(l),var(k),var(l')) -> eq#(l,l')
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,t)
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,s)
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)) ->
    ren#(var(l),var(k),var(l')) -> eq#(l,l')
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,t)
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,s)
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
    ren#(x,y,apply(t,s)) -> ren#(x,y,s) ->
    ren#(var(l),var(k),var(l')) -> eq#(l,l')
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,t)
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(x,y,apply(t,s)) -> ren#(x,y,s)
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(var(l),var(k),var(l')) -> if#(eq(l,l'),var(k),var(l'))
    ren#(x,y,apply(t,s)) -> ren#(x,y,t) ->
    ren#(var(l),var(k),var(l')) -> eq#(l,l')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(var(l),var(l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> and#(eq(x,x'),eq(t,t'))
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> and#(eq(t,t'),eq(s,s'))
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(var(l),var(l')) -> eq#(l,l')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> and#(eq(t,t'),eq(l,l'))
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') ->
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
    eq#(cons(t,l),cons(t',l')) -> eq#(t,t') -> eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
   SCC Processor:
    #sccs: 2
    #rules: 11
    #arcs: 104/256
    DPs:
     ren#(x,y,lambda(z,t)) -> ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
     ren#(x,y,apply(t,s)) -> ren#(x,y,s)
     ren#(x,y,apply(t,s)) -> ren#(x,y,t)
     ren#(x,y,lambda(z,t)) -> ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
    TRS:
     and(true(),y) -> y
     and(false(),y) -> false()
     eq(nil(),nil()) -> true()
     eq(cons(t,l),nil()) -> false()
     eq(nil(),cons(t,l)) -> false()
     eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
     eq(var(l),var(l')) -> eq(l,l')
     eq(var(l),apply(t,s)) -> false()
     eq(var(l),lambda(x,t)) -> false()
     eq(apply(t,s),var(l)) -> false()
     eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
     eq(apply(t,s),lambda(x,t)) -> false()
     eq(lambda(x,t),var(l)) -> false()
     eq(lambda(x,t),apply(t,s)) -> false()
     eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
     if(true(),var(k),var(l')) -> var(k)
     if(false(),var(k),var(l')) -> var(l')
     ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
     ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
     ren(x,y,lambda(z,t)) ->
     lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(
                                                                    z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
    Arctic Interpretation Processor:
     dimension: 1
     usable rules:
      if(true(),var(k),var(l')) -> var(k)
      if(false(),var(k),var(l')) -> var(l')
      ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
      ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
      ren(x,y,lambda(z,t)) ->
      lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren
                                                                  (z,
                                                                   var
                                                                   (cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                   t)))
     interpretation:
      [eq](x0, x1) = 2x0 + 3x1 + 0,
      
      [lambda](x0, x1) = x0 + 4x1 + 1,
      
      [and](x0, x1) = 1x1 + 0,
      
      [nil] = 2,
      
      [cons](x0, x1) = x0 + x1 + 0,
      
      [ren](x0, x1, x2) = x2,
      
      [true] = 0,
      
      [apply](x0, x1) = 4x0 + 2x1 + 0,
      
      [ren#](x0, x1, x2) = x2 + 0,
      
      [if](x0, x1, x2) = x2,
      
      [var](x0) = 1,
      
      [false] = 2
     orientation:
      ren#(x,y,lambda(z,t)) = 4t + z + 1 >= t + 0 = ren#(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t)
      
      ren#(x,y,apply(t,s)) = 2s + 4t + 0 >= s + 0 = ren#(x,y,s)
      
      ren#(x,y,apply(t,s)) = 2s + 4t + 0 >= t + 0 = ren#(x,y,t)
      
      ren#(x,y,lambda(z,t)) = 4t + z + 1 >= t + 0 = ren#(x,y,ren(z,var(cons(x,cons(y,cons(lambda(z,t),nil())))),t))
      
      and(true(),y) = 1y + 0 >= y = y
      
      and(false(),y) = 1y + 0 >= 2 = false()
      
      eq(nil(),nil()) = 5 >= 0 = true()
      
      eq(cons(t,l),nil()) = 2l + 2t + 5 >= 2 = false()
      
      eq(nil(),cons(t,l)) = 3l + 3t + 4 >= 2 = false()
      
      eq(cons(t,l),cons(t',l')) = 2l + 3l' + 2t + 3t' + 3 >= 3l + 4l' + 1 = and(eq(t,t'),eq(l,l'))
      
      eq(var(l),var(l')) = 4 >= 2l + 3l' + 0 = eq(l,l')
      
      eq(var(l),apply(t,s)) = 5s + 7t + 3 >= 2 = false()
      
      eq(var(l),lambda(x,t)) = 7t + 3x + 4 >= 2 = false()
      
      eq(apply(t,s),var(l)) = 4s + 6t + 4 >= 2 = false()
      
      eq(apply(t,s),apply(t',s')) = 4s + 5s' + 6t + 7t' + 3 >= 3s + 4s' + 1 = and(eq(t,t'),eq(s,s'))
      
      eq(apply(t,s),lambda(x,t)) = 4s + 7t + 3x + 4 >= 2 = false()
      
      eq(lambda(x,t),var(l)) = 6t + 2x + 4 >= 2 = false()
      
      eq(lambda(x,t),apply(t,s)) = 5s + 7t + 2x + 3 >= 2 = false()
      
      eq(lambda(x,t),lambda(x',t')) = 6t + 7t' + 2x + 3x' + 4 >= 3t + 4t' + 1 = and(eq(x,x'),eq(t,t'))
      
      if(true(),var(k),var(l')) = 1 >= 1 = var(k)
      
      if(false(),var(k),var(l')) = 1 >= 1 = var(l')
      
      ren(var(l),var(k),var(l')) = 1 >= 1 = if(eq(l,l'),var(k),var(l'))
      
      ren(x,y,apply(t,s)) = 2s + 4t + 0 >= 2s + 4t + 0 = apply(ren(x,y,t),ren(x,y,s))
      
      ren(x,y,lambda(z,t)) = 4t + z + 1 >= 4t + 1 = lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(z,var
                                                                  (cons
                                                                   (x,
                                                                    cons
                                                                    (
                                                                    y,
                                                                    cons
                                                                    (
                                                                    lambda
                                                                    (
                                                                    z,t),
                                                                    nil
                                                                    ())))),
                                                                t)))
     problem:
      DPs:
       ren#(x,y,apply(t,s)) -> ren#(x,y,s)
       ren#(x,y,apply(t,s)) -> ren#(x,y,t)
      TRS:
       and(true(),y) -> y
       and(false(),y) -> false()
       eq(nil(),nil()) -> true()
       eq(cons(t,l),nil()) -> false()
       eq(nil(),cons(t,l)) -> false()
       eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
       eq(var(l),var(l')) -> eq(l,l')
       eq(var(l),apply(t,s)) -> false()
       eq(var(l),lambda(x,t)) -> false()
       eq(apply(t,s),var(l)) -> false()
       eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
       eq(apply(t,s),lambda(x,t)) -> false()
       eq(lambda(x,t),var(l)) -> false()
       eq(lambda(x,t),apply(t,s)) -> false()
       eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
       if(true(),var(k),var(l')) -> var(k)
       if(false(),var(k),var(l')) -> var(l')
       ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
       ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
       ren(x,y,lambda(z,t)) ->
       lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren
                                                                   (z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
     Restore Modifier:
      DPs:
       ren#(x,y,apply(t,s)) -> ren#(x,y,s)
       ren#(x,y,apply(t,s)) -> ren#(x,y,t)
      TRS:
       and(true(),y) -> y
       and(false(),y) -> false()
       eq(nil(),nil()) -> true()
       eq(cons(t,l),nil()) -> false()
       eq(nil(),cons(t,l)) -> false()
       eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
       eq(var(l),var(l')) -> eq(l,l')
       eq(var(l),apply(t,s)) -> false()
       eq(var(l),lambda(x,t)) -> false()
       eq(apply(t,s),var(l)) -> false()
       eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
       eq(apply(t,s),lambda(x,t)) -> false()
       eq(lambda(x,t),var(l)) -> false()
       eq(lambda(x,t),apply(t,s)) -> false()
       eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
       if(true(),var(k),var(l')) -> var(k)
       if(false(),var(k),var(l')) -> var(l')
       ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
       ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
       ren(x,y,lambda(z,t)) ->
       lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren
                                                                   (z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
      Size-Change Termination Processor:
       DPs:
        
       TRS:
        and(true(),y) -> y
        and(false(),y) -> false()
        eq(nil(),nil()) -> true()
        eq(cons(t,l),nil()) -> false()
        eq(nil(),cons(t,l)) -> false()
        eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
        eq(var(l),var(l')) -> eq(l,l')
        eq(var(l),apply(t,s)) -> false()
        eq(var(l),lambda(x,t)) -> false()
        eq(apply(t,s),var(l)) -> false()
        eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
        eq(apply(t,s),lambda(x,t)) -> false()
        eq(lambda(x,t),var(l)) -> false()
        eq(lambda(x,t),apply(t,s)) -> false()
        eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
        if(true(),var(k),var(l')) -> var(k)
        if(false(),var(k),var(l')) -> var(l')
        ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
        ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
        ren(x,y,lambda(z,t)) ->
        lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren
                                                                    (
                                                                    z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
       The DP: ren#(x,y,apply(t,s)) -> ren#(x,y,s) has the edges:
         0 >=  0
         1 >=  1
         2 >   2
       The DP: ren#(x,y,apply(t,s)) -> ren#(x,y,t) has the edges:
         0 >=  0
         1 >=  1
         2 >   2
       Qed
    
    DPs:
     eq#(cons(t,l),cons(t',l')) -> eq#(l,l')
     eq#(cons(t,l),cons(t',l')) -> eq#(t,t')
     eq#(var(l),var(l')) -> eq#(l,l')
     eq#(apply(t,s),apply(t',s')) -> eq#(s,s')
     eq#(apply(t,s),apply(t',s')) -> eq#(t,t')
     eq#(lambda(x,t),lambda(x',t')) -> eq#(t,t')
     eq#(lambda(x,t),lambda(x',t')) -> eq#(x,x')
    TRS:
     and(true(),y) -> y
     and(false(),y) -> false()
     eq(nil(),nil()) -> true()
     eq(cons(t,l),nil()) -> false()
     eq(nil(),cons(t,l)) -> false()
     eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
     eq(var(l),var(l')) -> eq(l,l')
     eq(var(l),apply(t,s)) -> false()
     eq(var(l),lambda(x,t)) -> false()
     eq(apply(t,s),var(l)) -> false()
     eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
     eq(apply(t,s),lambda(x,t)) -> false()
     eq(lambda(x,t),var(l)) -> false()
     eq(lambda(x,t),apply(t,s)) -> false()
     eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
     if(true(),var(k),var(l')) -> var(k)
     if(false(),var(k),var(l')) -> var(l')
     ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
     ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
     ren(x,y,lambda(z,t)) ->
     lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren(
                                                                    z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
    Subterm Criterion Processor:
     simple projection:
      pi(eq#) = 0
     problem:
      DPs:
       
      TRS:
       and(true(),y) -> y
       and(false(),y) -> false()
       eq(nil(),nil()) -> true()
       eq(cons(t,l),nil()) -> false()
       eq(nil(),cons(t,l)) -> false()
       eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
       eq(var(l),var(l')) -> eq(l,l')
       eq(var(l),apply(t,s)) -> false()
       eq(var(l),lambda(x,t)) -> false()
       eq(apply(t,s),var(l)) -> false()
       eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
       eq(apply(t,s),lambda(x,t)) -> false()
       eq(lambda(x,t),var(l)) -> false()
       eq(lambda(x,t),apply(t,s)) -> false()
       eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
       if(true(),var(k),var(l')) -> var(k)
       if(false(),var(k),var(l')) -> var(l')
       ren(var(l),var(k),var(l')) -> if(eq(l,l'),var(k),var(l'))
       ren(x,y,apply(t,s)) -> apply(ren(x,y,t),ren(x,y,s))
       ren(x,y,lambda(z,t)) ->
       lambda(var(cons(x,cons(y,cons(lambda(z,t),nil())))),ren(x,y,ren
                                                                   (z,
                                                                    var
                                                                    (
                                                                    cons
                                                                    (
                                                                    x,
                                                                    cons
                                                                    (y,cons(lambda(z,t),nil())))),
                                                                    t)))
     Qed