/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES

Problem 1: 

(VAR k l l' s s' t t' x x' y z)
(RULES
and(false,y) -> false
and(true,y) -> y
eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
eq(apply(t,s),lambda(x,t)) -> false
eq(apply(t,s),var(l)) -> false
eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
eq(cons(t,l),nil) -> false
eq(lambda(x,t),apply(t,s)) -> false
eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
eq(lambda(x,t),var(l)) -> false
eq(nil,cons(t,l)) -> false
eq(nil,nil) -> true
eq(var(l),apply(t,s)) -> false
eq(var(l),lambda(x,t)) -> false
eq(var(l),var(l')) -> eq(l,l')
if(false,var(k),var(l')) -> var(l')
if(true,var(k),var(l')) -> var(k)
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)))
) 
(STRATEGY INNERMOST)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 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(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(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(var(l),var(l')) -> EQ(l,l')
 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(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)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))

Problem 1: 

SCC Processor:
-> Pairs:
 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(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(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(var(l),var(l')) -> EQ(l,l')
 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(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)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 EQ(apply(t,s),apply(t',s')) -> EQ(s,s')
 EQ(apply(t,s),apply(t',s')) -> EQ(t,t')
 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')) -> EQ(t,t')
 EQ(lambda(x,t),lambda(x',t')) -> EQ(x,x')
 EQ(var(l),var(l')) -> EQ(l,l')
->->-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->->Cycle:
->->-> Pairs:
 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))
 REN(x,y,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
->->-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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 problem is decomposed in 2 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 EQ(apply(t,s),apply(t',s')) -> EQ(s,s')
 EQ(apply(t,s),apply(t',s')) -> EQ(t,t')
 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')) -> EQ(t,t')
 EQ(lambda(x,t),lambda(x',t')) -> EQ(x,x')
 EQ(var(l),var(l')) -> EQ(l,l')
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Projection:
 pi(EQ) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Reduction Pairs Processor:
-> Pairs:
 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))
 REN(x,y,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
-> Usable rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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 type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[and](X1,X2) = X2
[eq](X1,X2) = 2
[if](X1,X2,X3) = 2.X2
[ren](X1,X2,X3) = X3
[apply](X1,X2) = 2.X1 + X2 + 1
[cons](X1,X2) = 2
[false] = 0
[lambda](X1,X2) = X2 + 2
[nil] = 1
[true] = 2
[var](X) = 0
[REN](X1,X2,X3) = 2.X3

Problem 1.2: 

SCC Processor:
-> Pairs:
 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,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 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,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
->->-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))

Problem 1.2: 

Reduction Pairs Processor:
-> Pairs:
 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,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
-> Usable rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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 type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[and](X1,X2) = X2
[eq](X1,X2) = 2
[if](X1,X2,X3) = 2
[ren](X1,X2,X3) = X3
[apply](X1,X2) = 2.X1 + 2.X2 + 1
[cons](X1,X2) = 0
[false] = 0
[lambda](X1,X2) = 2.X2 + 2
[nil] = 2
[true] = 0
[var](X) = 2
[REN](X1,X2,X3) = 2.X3

Problem 1.2: 

SCC Processor:
-> Pairs:
 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)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 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)
->->-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))

Problem 1.2: 

Reduction Pairs Processor:
-> Pairs:
 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)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
-> Usable rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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 type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[and](X1,X2) = X2
[eq](X1,X2) = X1 + 2.X2 + 2
[if](X1,X2,X3) = X2 + X3
[ren](X1,X2,X3) = 2.X2 + X3
[apply](X1,X2) = X2 + 1
[cons](X1,X2) = 2.X2
[false] = 0
[lambda](X1,X2) = X2 + 2
[nil] = 0
[true] = 2
[var](X) = 2.X
[REN](X1,X2,X3) = X2 + 2.X3

Problem 1.2: 

SCC Processor:
-> Pairs:
 REN(x,y,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 REN(x,y,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
->->-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))

Problem 1.2: 

Subterm Processor:
-> Pairs:
 REN(x,y,lambda(z,t)) -> REN(z,var(cons(x,cons(y,cons(lambda(z,t),nil)))),t)
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Projection:
 pi(REN) = 3

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 and(false,y) -> false
 and(true,y) -> y
 eq(apply(t,s),apply(t',s')) -> and(eq(t,t'),eq(s,s'))
 eq(apply(t,s),lambda(x,t)) -> false
 eq(apply(t,s),var(l)) -> false
 eq(cons(t,l),cons(t',l')) -> and(eq(t,t'),eq(l,l'))
 eq(cons(t,l),nil) -> false
 eq(lambda(x,t),apply(t,s)) -> false
 eq(lambda(x,t),lambda(x',t')) -> and(eq(x,x'),eq(t,t'))
 eq(lambda(x,t),var(l)) -> false
 eq(nil,cons(t,l)) -> false
 eq(nil,nil) -> true
 eq(var(l),apply(t,s)) -> false
 eq(var(l),lambda(x,t)) -> false
 eq(var(l),var(l')) -> eq(l,l')
 if(false,var(k),var(l')) -> var(l')
 if(true,var(k),var(l')) -> var(k)
 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)))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.