YES

Problem 1: 

(VAR m n x y)
(THEORY 
(C eq))
(RULES
eq(0,0) -> true
eq(0,s(x)) -> false
eq(s(x),0) -> false
eq(s(x),s(y)) -> eq(x,y)
if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
if_rm(true,n,add(m,x)) -> rm(n,x)
purge(add(n,x)) -> add(n,purge(rm(n,x)))
purge(nil) -> nil
rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
rm(n,nil) -> nil
)

Problem 1: 

Dependency Pairs Processor:
-> FAxioms:
 EQ(x4,x5) = EQ(x5,x4)
-> Pairs:
 EQ(s(x),s(y)) -> EQ(x,y)
 IF_RM(false,n,add(m,x)) -> RM(n,x)
 IF_RM(true,n,add(m,x)) -> RM(n,x)
 PURGE(add(n,x)) -> PURGE(rm(n,x))
 PURGE(add(n,x)) -> RM(n,x)
 RM(n,add(m,x)) -> EQ(n,m)
 RM(n,add(m,x)) -> IF_RM(eq(n,m),n,add(m,x))
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty

Problem 1: 

SCC Processor:
-> FAxioms:
 EQ(x4,x5) = EQ(x5,x4)
-> Pairs:
 EQ(s(x),s(y)) -> EQ(x,y)
 IF_RM(false,n,add(m,x)) -> RM(n,x)
 IF_RM(true,n,add(m,x)) -> RM(n,x)
 PURGE(add(n,x)) -> PURGE(rm(n,x))
 PURGE(add(n,x)) -> RM(n,x)
 RM(n,add(m,x)) -> EQ(n,m)
 RM(n,add(m,x)) -> IF_RM(eq(n,m),n,add(m,x))
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 EQ(s(x),s(y)) -> EQ(x,y)
-> FAxioms:
 eq(x4,x5) -> eq(x5,x4)
 EQ(x4,x5) -> EQ(x5,x4)
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
->->-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->->Cycle:
->->-> Pairs:
 IF_RM(false,n,add(m,x)) -> RM(n,x)
 IF_RM(true,n,add(m,x)) -> RM(n,x)
 RM(n,add(m,x)) -> IF_RM(eq(n,m),n,add(m,x))
-> FAxioms:
 eq(x4,x5) -> eq(x5,x4)
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
->->-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->->Cycle:
->->-> Pairs:
 PURGE(add(n,x)) -> PURGE(rm(n,x))
-> FAxioms:
 eq(x4,x5) -> eq(x5,x4)
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
->->-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty


The problem is decomposed in 3 subproblems.

Problem 1.1: 

Subterm Processor:
-> FAxioms:
 EQ(x4,x5) = EQ(x5,x4)
-> Pairs:
 EQ(s(x),s(y)) -> EQ(x,y)
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Projection:
 pi(EQ) = [1,2]

Problem 1.1: 

SCC Processor:
-> FAxioms:
 EQ(x4,x5) = EQ(x5,x4)
-> Pairs:
 Empty
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> FAxioms:
 Empty
-> Pairs:
 IF_RM(false,n,add(m,x)) -> RM(n,x)
 IF_RM(true,n,add(m,x)) -> RM(n,x)
 RM(n,add(m,x)) -> IF_RM(eq(n,m),n,add(m,x))
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Projection:
 pi(IF_RM) = [3]
 pi(RM) = [2]

Problem 1.2: 

SCC Processor:
-> FAxioms:
 Empty
-> Pairs:
 RM(n,add(m,x)) -> IF_RM(eq(n,m),n,add(m,x))
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.3: 

Reduction Pairs Processor:
-> FAxioms:
 Empty
-> Pairs:
 PURGE(add(n,x)) -> PURGE(rm(n,x))
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Usable Equations:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> Usable Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[eq](X1,X2) = 2
[if_rm](X1,X2,X3) = 2.X3 + 1
[purge](X) = 0
[rm](X1,X2) = 2.X2 + 1
[0] = 2
[add](X1,X2) = 2.X1 + 2.X2 + 2
[false] = 0
[nil] = 2
[s](X) = 0
[true] = 1
[EQ](X1,X2) = 0
[IF_RM](X1,X2,X3) = 0
[PURGE](X) = 2.X
[RM](X1,X2) = 0

Problem 1.3: 

SCC Processor:
-> FAxioms:
 Empty
-> Pairs:
 Empty
-> EAxioms:
 eq(x4,x5) = eq(x5,x4)
-> Rules:
 eq(0,0) -> true
 eq(0,s(x)) -> false
 eq(s(x),0) -> false
 eq(s(x),s(y)) -> eq(x,y)
 if_rm(false,n,add(m,x)) -> add(m,rm(n,x))
 if_rm(true,n,add(m,x)) -> rm(n,x)
 purge(add(n,x)) -> add(n,purge(rm(n,x)))
 purge(nil) -> nil
 rm(n,add(m,x)) -> if_rm(eq(n,m),n,add(m,x))
 rm(n,nil) -> nil
-> SRules:
 Empty
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.