0.00/0.20 YES 0.00/0.20 0.00/0.20 Problem 1: 0.00/0.20 0.00/0.20 (VAR v_NonEmpty:S k:S l:S l':S s:S s':S t:S t':S x:S x':S y:S z:S) 0.00/0.20 (RULES 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ) 0.00/0.20 (STRATEGY INNERMOST) 0.00/0.20 0.00/0.20 Problem 1: 0.00/0.20 0.00/0.20 Dependency Pairs Processor: 0.00/0.20 -> Pairs: 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> AND(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> AND(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> AND(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) 0.00/0.20 EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 REN(var(l:S),var(k:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 REN(var(l:S),var(k:S),var(l':S)) -> IF(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 0.00/0.20 Problem 1: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> AND(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> AND(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> AND(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) 0.00/0.20 EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 REN(var(l:S),var(k:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 REN(var(l:S),var(k:S),var(l':S)) -> IF(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 ->->Cycle: 0.00/0.20 ->->-> Pairs: 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) 0.00/0.20 EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 ->->-> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->->Cycle: 0.00/0.20 ->->-> Pairs: 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 ->->-> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 0.00/0.20 0.00/0.20 The problem is decomposed in 2 subproblems. 0.00/0.20 0.00/0.20 Problem 1.1: 0.00/0.20 0.00/0.20 Subterm Processor: 0.00/0.20 -> Pairs: 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) 0.00/0.20 EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) 0.00/0.20 EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) 0.00/0.20 EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) 0.00/0.20 EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Projection: 0.00/0.20 pi(EQ) = 1 0.00/0.20 0.00/0.20 Problem 1.1: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 Empty 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 There is no strongly connected component 0.00/0.20 0.00/0.20 The problem is finite. 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 Reduction Pairs Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 -> Usable rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Interpretation type: 0.00/0.20 Linear 0.00/0.20 ->Coefficients: 0.00/0.20 Natural Numbers 0.00/0.20 ->Dimension: 0.00/0.20 1 0.00/0.20 ->Bound: 0.00/0.20 2 0.00/0.20 ->Interpretation: 0.00/0.20 0.00/0.20 [and](X1,X2) = X2 0.00/0.20 [eq](X1,X2) = 2 0.00/0.20 [if](X1,X2,X3) = 2 0.00/0.20 [ren](X1,X2,X3) = X3 0.00/0.20 [apply](X1,X2) = 2.X1 + 2.X2 + 1 0.00/0.20 [cons](X1,X2) = 2 0.00/0.20 [fSNonEmpty] = 0 0.00/0.20 [false] = 0 0.00/0.20 [lambda](X1,X2) = 2.X2 + 2 0.00/0.20 [nil] = 1 0.00/0.20 [true] = 1 0.00/0.20 [var](X) = 2 0.00/0.20 [AND](X1,X2) = 0 0.00/0.20 [EQ](X1,X2) = 0 0.00/0.20 [IF](X1,X2,X3) = 0 0.00/0.20 [REN](X1,X2,X3) = 2.X2 + 2.X3 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 ->->Cycle: 0.00/0.20 ->->-> Pairs: 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 ->->-> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 Reduction Pairs Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 -> Usable rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Interpretation type: 0.00/0.20 Linear 0.00/0.20 ->Coefficients: 0.00/0.20 Natural Numbers 0.00/0.20 ->Dimension: 0.00/0.20 1 0.00/0.20 ->Bound: 0.00/0.20 2 0.00/0.20 ->Interpretation: 0.00/0.20 0.00/0.20 [and](X1,X2) = X2 0.00/0.20 [eq](X1,X2) = 2 0.00/0.20 [if](X1,X2,X3) = 2.X2 + X3 0.00/0.20 [ren](X1,X2,X3) = 2.X1 + 2.X2 + X3 0.00/0.20 [apply](X1,X2) = X1 + 1 0.00/0.20 [cons](X1,X2) = 1 0.00/0.20 [fSNonEmpty] = 0 0.00/0.20 [false] = 0 0.00/0.20 [lambda](X1,X2) = 2.X1 + X2 + 1 0.00/0.20 [nil] = 0 0.00/0.20 [true] = 1 0.00/0.20 [var](X) = 0 0.00/0.20 [AND](X1,X2) = 0 0.00/0.20 [EQ](X1,X2) = 0 0.00/0.20 [IF](X1,X2,X3) = 0 0.00/0.20 [REN](X1,X2,X3) = 2.X1 + 2.X3 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 ->->Cycle: 0.00/0.20 ->->-> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 ->->-> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 Reduction Pairs Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S)) 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 -> Usable rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Interpretation type: 0.00/0.20 Linear 0.00/0.20 ->Coefficients: 0.00/0.20 Natural Numbers 0.00/0.20 ->Dimension: 0.00/0.20 1 0.00/0.20 ->Bound: 0.00/0.20 2 0.00/0.20 ->Interpretation: 0.00/0.20 0.00/0.20 [and](X1,X2) = X2 0.00/0.20 [eq](X1,X2) = 2 0.00/0.20 [if](X1,X2,X3) = 2 0.00/0.20 [ren](X1,X2,X3) = X3 0.00/0.20 [apply](X1,X2) = 2.X2 0.00/0.20 [cons](X1,X2) = 0 0.00/0.20 [fSNonEmpty] = 0 0.00/0.20 [false] = 0 0.00/0.20 [lambda](X1,X2) = 2.X2 + 1 0.00/0.20 [nil] = 0 0.00/0.20 [true] = 2 0.00/0.20 [var](X) = 2 0.00/0.20 [AND](X1,X2) = 0 0.00/0.20 [EQ](X1,X2) = 0 0.00/0.20 [IF](X1,X2,X3) = 0 0.00/0.20 [REN](X1,X2,X3) = X2 + 2.X3 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 ->->Cycle: 0.00/0.20 ->->-> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 ->->-> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 Subterm Processor: 0.00/0.20 -> Pairs: 0.00/0.20 REN(x:S,y:S,lambda(z:S,t:S)) -> REN(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S) 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Projection: 0.00/0.20 pi(REN) = 3 0.00/0.20 0.00/0.20 Problem 1.2: 0.00/0.20 0.00/0.20 SCC Processor: 0.00/0.20 -> Pairs: 0.00/0.20 Empty 0.00/0.20 -> Rules: 0.00/0.20 and(ffalse,y:S) -> ffalse 0.00/0.20 and(ttrue,y:S) -> y:S 0.00/0.20 eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) 0.00/0.20 eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(apply(t:S,s:S),var(l:S)) -> ffalse 0.00/0.20 eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) 0.00/0.20 eq(cons(t:S,l:S),nil) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) 0.00/0.20 eq(lambda(x:S,t:S),var(l:S)) -> ffalse 0.00/0.20 eq(nil,cons(t:S,l:S)) -> ffalse 0.00/0.20 eq(nil,nil) -> ttrue 0.00/0.20 eq(var(l:S),apply(t:S,s:S)) -> ffalse 0.00/0.20 eq(var(l:S),lambda(x:S,t:S)) -> ffalse 0.00/0.20 eq(var(l:S),var(l':S)) -> eq(l:S,l':S) 0.00/0.20 if(ffalse,var(k:S),var(l':S)) -> var(l':S) 0.00/0.20 if(ttrue,var(k:S),var(l':S)) -> var(k:S) 0.00/0.20 ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 0.00/0.20 ren(x:S,y:S,apply(t:S,s:S)) -> apply(ren(x:S,y:S,t:S),ren(x:S,y:S,s:S)) 0.00/0.20 ren(x:S,y:S,lambda(z:S,t:S)) -> lambda(var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),ren(x:S,y:S,ren(z:S,var(cons(x:S,cons(y:S,cons(lambda(z:S,t:S),nil)))),t:S))) 0.00/0.20 ->Strongly Connected Components: 0.00/0.20 There is no strongly connected component 0.00/0.20 0.00/0.20 The problem is finite. 0.00/0.20 EOF