/export/starexec/sandbox/solver/bin/starexec_run_ttt2 /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren(Z,var (cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Proof: DP Processor: DPs: eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren(Z, var (cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) TDG Processor: DPs: eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren(Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) graph: ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) -> ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) -> ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) -> ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(var(L),var(K),var(Lp)) -> if#(eq(L,Lp),var(K),var(Lp)) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) -> ren#(var(L),var(K),var(Lp)) -> eq#(L,Lp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(var(L),var(Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> and#(eq(T,Tp),eq(X,Xp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> and#(eq(T,Tp),eq(S,Sp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> and#(eq(T,Tp),eq(L,Lp)) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) -> eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) SCC Processor: #sccs: 2 #rules: 11 #arcs: 104/256 DPs: ren#(X,Y,lambda(Z,T)) -> ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) -> ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren( Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Arctic Interpretation Processor: dimension: 1 usable rules: if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren (Z, var (cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) interpretation: [eq](x0, x1) = x0 + x1 + 0, [lambda](x0, x1) = 4x1, [and](x0, x1) = x0 + x1 + 0, [nil] = 3, [cons](x0, x1) = x0 + x1, [ren](x0, x1, x2) = x2, [false] = 7, [apply](x0, x1) = x0 + x1 + 7, [ren#](x0, x1, x2) = x2, [if](x0, x1, x2) = 5, [var](x0) = 5, [true] = 6 orientation: ren#(X,Y,lambda(Z,T)) = 4T >= T = ren#(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T) ren#(X,Y,apply(T,S)) = S + T + 7 >= S = ren#(X,Y,S) ren#(X,Y,apply(T,S)) = S + T + 7 >= T = ren#(X,Y,T) ren#(X,Y,lambda(Z,T)) = 4T >= T = ren#(X,Y,ren(Z,var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),T)) and(false(),false()) = 7 >= 7 = false() and(true(),false()) = 7 >= 7 = false() and(false(),true()) = 7 >= 7 = false() and(true(),true()) = 6 >= 6 = true() eq(nil(),nil()) = 3 >= 6 = true() eq(cons(T,L),nil()) = L + T + 3 >= 7 = false() eq(nil(),cons(T,L)) = L + T + 3 >= 7 = false() eq(cons(T,L),cons(Tp,Lp)) = L + Lp + T + Tp + 0 >= L + Lp + T + Tp + 0 = and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) = 5 >= L + Lp + 0 = eq(L,Lp) eq(var(L),apply(T,S)) = S + T + 7 >= 7 = false() eq(var(L),lambda(X,T)) = 4T + 5 >= 7 = false() eq(apply(T,S),var(L)) = S + T + 7 >= 7 = false() eq(apply(T,S),apply(Tp,Sp)) = S + Sp + T + Tp + 7 >= S + Sp + T + Tp + 0 = and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) = S + T + 4Tp + 7 >= 7 = false() eq(lambda(X,T),var(L)) = 4T + 5 >= 7 = false() eq(lambda(X,T),apply(Tp,Sp)) = Sp + 4T + Tp + 7 >= 7 = false() eq(lambda(X,T),lambda(Xp,Tp)) = 4T + 4Tp + 0 >= T + Tp + X + Xp + 0 = and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) = 5 >= 5 = var(K) if(false(),var(K),var(L)) = 5 >= 5 = var(L) ren(var(L),var(K),var(Lp)) = 5 >= 5 = if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) = S + T + 7 >= S + T + 7 = apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) = 4T >= 4T = lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren(Z,var (cons (X, cons ( Y, cons ( lambda ( Z,T), nil ())))), T))) problem: DPs: ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren (Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Restore Modifier: DPs: ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren (Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Size-Change Termination Processor: DPs: TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren ( Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) The DP: ren#(X,Y,apply(T,S)) -> ren#(X,Y,S) has the edges: 0 >= 0 1 >= 1 2 > 2 The DP: ren#(X,Y,apply(T,S)) -> ren#(X,Y,T) has the edges: 0 >= 0 1 >= 1 2 > 2 Qed DPs: eq#(cons(T,L),cons(Tp,Lp)) -> eq#(L,Lp) eq#(cons(T,L),cons(Tp,Lp)) -> eq#(T,Tp) eq#(var(L),var(Lp)) -> eq#(L,Lp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(S,Sp) eq#(apply(T,S),apply(Tp,Sp)) -> eq#(T,Tp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(X,Xp) eq#(lambda(X,T),lambda(Xp,Tp)) -> eq#(T,Tp) TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren( Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Subterm Criterion Processor: simple projection: pi(eq#) = 0 problem: DPs: TRS: and(false(),false()) -> false() and(true(),false()) -> false() and(false(),true()) -> false() and(true(),true()) -> true() eq(nil(),nil()) -> true() eq(cons(T,L),nil()) -> false() eq(nil(),cons(T,L)) -> false() eq(cons(T,L),cons(Tp,Lp)) -> and(eq(T,Tp),eq(L,Lp)) eq(var(L),var(Lp)) -> eq(L,Lp) eq(var(L),apply(T,S)) -> false() eq(var(L),lambda(X,T)) -> false() eq(apply(T,S),var(L)) -> false() eq(apply(T,S),apply(Tp,Sp)) -> and(eq(T,Tp),eq(S,Sp)) eq(apply(T,S),lambda(X,Tp)) -> false() eq(lambda(X,T),var(L)) -> false() eq(lambda(X,T),apply(Tp,Sp)) -> false() eq(lambda(X,T),lambda(Xp,Tp)) -> and(eq(T,Tp),eq(X,Xp)) if(true(),var(K),var(L)) -> var(K) if(false(),var(K),var(L)) -> var(L) ren(var(L),var(K),var(Lp)) -> if(eq(L,Lp),var(K),var(Lp)) ren(X,Y,apply(T,S)) -> apply(ren(X,Y,T),ren(X,Y,S)) ren(X,Y,lambda(Z,T)) -> lambda(var(cons(X,cons(Y,cons(lambda(Z,T),nil())))),ren(X,Y,ren (Z, var ( cons ( X, cons (Y,cons(lambda(Z,T),nil())))), T))) Qed