YES Problem 1: (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) (RULES and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ) (STRATEGY INNERMOST) Problem 1: Dependency Pairs Processor: -> Pairs: EQ(apply(t:S,s:S),apply(t':S,s':S)) -> AND(eq(t:S,t':S),eq(s:S,s':S)) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> AND(eq(t:S,t':S),eq(l:S,l':S)) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> AND(eq(x:S,x':S),eq(t:S,t':S)) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) REN(var(l:S),var(k:S),var(l':S)) -> EQ(l:S,l':S) REN(var(l:S),var(k:S),var(l':S)) -> IF(eq(l:S,l':S),var(k:S),var(l':S)) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) Problem 1: SCC Processor: -> Pairs: EQ(apply(t:S,s:S),apply(t':S,s':S)) -> AND(eq(t:S,t':S),eq(s:S,s':S)) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> AND(eq(t:S,t':S),eq(l:S,l':S)) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> AND(eq(x:S,x':S),eq(t:S,t':S)) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) REN(var(l:S),var(k:S),var(l':S)) -> EQ(l:S,l':S) REN(var(l:S),var(k:S),var(l':S)) -> IF(eq(l:S,l':S),var(k:S),var(l':S)) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) ->->-> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->->Cycle: ->->-> Pairs: REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) ->->-> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(s:S,s':S) EQ(apply(t:S,s:S),apply(t':S,s':S)) -> EQ(t:S,t':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(l:S,l':S) EQ(cons(t:S,l:S),cons(t':S,l':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(t:S,t':S) EQ(lambda(x:S,t:S),lambda(x':S,t':S)) -> EQ(x:S,x':S) EQ(var(l:S),var(l':S)) -> EQ(l:S,l':S) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Projection: pi(EQ) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pairs Processor: -> Pairs: REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,s:S) REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) -> Usable rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->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) = 2 [fSNonEmpty] = 0 [false] = 0 [lambda](X1,X2) = 2.X2 + 2 [nil] = 1 [true] = 1 [var](X) = 2 [AND](X1,X2) = 0 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [REN](X1,X2,X3) = 2.X2 + 2.X3 Problem 1.2: SCC Processor: -> Pairs: REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) ->->-> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) Problem 1.2: Reduction Pairs Processor: -> Pairs: REN(x:S,y:S,apply(t:S,s:S)) -> REN(x:S,y:S,t:S) 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) -> Usable rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->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 + X3 [ren](X1,X2,X3) = 2.X1 + 2.X2 + X3 [apply](X1,X2) = X1 + 1 [cons](X1,X2) = 1 [fSNonEmpty] = 0 [false] = 0 [lambda](X1,X2) = 2.X1 + X2 + 1 [nil] = 0 [true] = 1 [var](X) = 0 [AND](X1,X2) = 0 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [REN](X1,X2,X3) = 2.X1 + 2.X3 Problem 1.2: SCC Processor: -> Pairs: 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: 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)) 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) ->->-> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) Problem 1.2: Reduction Pairs Processor: -> Pairs: 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)) 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) -> Usable rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->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.X2 [cons](X1,X2) = 0 [fSNonEmpty] = 0 [false] = 0 [lambda](X1,X2) = 2.X2 + 1 [nil] = 0 [true] = 2 [var](X) = 2 [AND](X1,X2) = 0 [EQ](X1,X2) = 0 [IF](X1,X2,X3) = 0 [REN](X1,X2,X3) = X2 + 2.X3 Problem 1.2: SCC Processor: -> Pairs: 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: 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) ->->-> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) Problem 1.2: Subterm Processor: -> Pairs: 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) -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Projection: pi(REN) = 3 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: and(ffalse,y:S) -> ffalse and(ttrue,y:S) -> y:S eq(apply(t:S,s:S),apply(t':S,s':S)) -> and(eq(t:S,t':S),eq(s:S,s':S)) eq(apply(t:S,s:S),lambda(x:S,t:S)) -> ffalse eq(apply(t:S,s:S),var(l:S)) -> ffalse eq(cons(t:S,l:S),cons(t':S,l':S)) -> and(eq(t:S,t':S),eq(l:S,l':S)) eq(cons(t:S,l:S),nil) -> ffalse eq(lambda(x:S,t:S),apply(t:S,s:S)) -> ffalse eq(lambda(x:S,t:S),lambda(x':S,t':S)) -> and(eq(x:S,x':S),eq(t:S,t':S)) eq(lambda(x:S,t:S),var(l:S)) -> ffalse eq(nil,cons(t:S,l:S)) -> ffalse eq(nil,nil) -> ttrue eq(var(l:S),apply(t:S,s:S)) -> ffalse eq(var(l:S),lambda(x:S,t:S)) -> ffalse eq(var(l:S),var(l':S)) -> eq(l:S,l':S) if(ffalse,var(k:S),var(l':S)) -> var(l':S) if(ttrue,var(k:S),var(l':S)) -> var(k:S) ren(var(l:S),var(k:S),var(l':S)) -> if(eq(l:S,l':S),var(k:S),var(l':S)) 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)) 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))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.