YES Problem: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Proof: DP Processor: DPs: eq#(s(X),s(Y)) -> eq#(X,Y) le#(s(X),s(Y)) -> le#(X,Y) min#(cons(N,cons(M,L))) -> le#(N,M) min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) replace#(N,M,cons(K,L)) -> eq#(N,K) replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) selsort#(cons(N,L)) -> min#(cons(N,L)) selsort#(cons(N,L)) -> eq#(N,min(cons(N,L))) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) ifselsort#(true(),cons(N,L)) -> selsort#(L) ifselsort#(false(),cons(N,L)) -> replace#(min(cons(N,L)),N,L) ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) ifselsort#(false(),cons(N,L)) -> min#(cons(N,L)) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) TDG Processor: DPs: eq#(s(X),s(Y)) -> eq#(X,Y) le#(s(X),s(Y)) -> le#(X,Y) min#(cons(N,cons(M,L))) -> le#(N,M) min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) replace#(N,M,cons(K,L)) -> eq#(N,K) replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) selsort#(cons(N,L)) -> min#(cons(N,L)) selsort#(cons(N,L)) -> eq#(N,min(cons(N,L))) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) ifselsort#(true(),cons(N,L)) -> selsort#(L) ifselsort#(false(),cons(N,L)) -> replace#(min(cons(N,L)),N,L) ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) ifselsort#(false(),cons(N,L)) -> min#(cons(N,L)) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) graph: ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) -> selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) -> selsort#(cons(N,L)) -> eq#(N,min(cons(N,L))) ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) -> selsort#(cons(N,L)) -> min#(cons(N,L)) ifselsort#(false(),cons(N,L)) -> replace#(min(cons(N,L)),N,L) -> replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) ifselsort#(false(),cons(N,L)) -> replace#(min(cons(N,L)),N,L) -> replace#(N,M,cons(K,L)) -> eq#(N,K) ifselsort#(false(),cons(N,L)) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifselsort#(false(),cons(N,L)) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> le#(N,M) ifselsort#(true(),cons(N,L)) -> selsort#(L) -> selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) ifselsort#(true(),cons(N,L)) -> selsort#(L) -> selsort#(cons(N,L)) -> eq#(N,min(cons(N,L))) ifselsort#(true(),cons(N,L)) -> selsort#(L) -> selsort#(cons(N,L)) -> min#(cons(N,L)) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) -> ifselsort#(false(),cons(N,L)) -> min#(cons(N,L)) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) -> ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) -> ifselsort#(false(),cons(N,L)) -> replace#(min(cons(N,L)),N,L) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) -> ifselsort#(true(),cons(N,L)) -> selsort#(L) selsort#(cons(N,L)) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) selsort#(cons(N,L)) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> le#(N,M) selsort#(cons(N,L)) -> eq#(N,min(cons(N,L))) -> eq#(s(X),s(Y)) -> eq#(X,Y) ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) -> replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) -> replace#(N,M,cons(K,L)) -> eq#(N,K) replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) -> ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) replace#(N,M,cons(K,L)) -> eq#(N,K) -> eq#(s(X),s(Y)) -> eq#(X,Y) ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) -> min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) -> min#(cons(N,cons(M,L))) -> le#(N,M) ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) -> min#(cons(N,cons(M,L))) -> le#(N,M) min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) -> ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) -> ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) min#(cons(N,cons(M,L))) -> le#(N,M) -> le#(s(X),s(Y)) -> le#(X,Y) le#(s(X),s(Y)) -> le#(X,Y) -> le#(s(X),s(Y)) -> le#(X,Y) eq#(s(X),s(Y)) -> eq#(X,Y) -> eq#(s(X),s(Y)) -> eq#(X,Y) SCC Processor: #sccs: 5 #rules: 10 #arcs: 30/256 DPs: ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),N,L)) selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) ifselsort#(true(),cons(N,L)) -> selsort#(L) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) KBO Processor: argument filtering: pi(0) = [] pi(eq) = [] pi(true) = [] pi(s) = [] pi(false) = [] pi(le) = [] pi(nil) = [] pi(cons) = [1] pi(min) = 0 pi(ifmin) = 1 pi(replace) = 2 pi(ifrepl) = 3 pi(selsort) = 0 pi(ifselsort) = 1 pi(selsort#) = 0 pi(ifselsort#) = 1 weight function: w0 = 1 w(ifselsort#) = w(cons) = w(nil) = w(le) = w(false) = w(s) = w( true) = w(eq) = w(0) = 1 w(selsort#) = w(ifselsort) = w(selsort) = w(ifrepl) = w(replace) = w( ifmin) = w(min) = 0 precedence: replace ~ nil ~ le ~ s ~ 0 > eq > ifselsort# ~ selsort# ~ ifselsort ~ selsort ~ ifrepl ~ ifmin ~ min ~ cons ~ false ~ true problem: DPs: selsort#(cons(N,L)) -> ifselsort#(eq(N,min(cons(N,L))),cons(N,L)) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/1 DPs: replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) ifrepl#(false(),N,M,cons(K,L)) -> replace#(N,M,L) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Subterm Criterion Processor: simple projection: pi(replace#) = 2 pi(ifrepl#) = 3 problem: DPs: replace#(N,M,cons(K,L)) -> ifrepl#(eq(N,K),N,M,cons(K,L)) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 2/1 DPs: eq#(s(X),s(Y)) -> eq#(X,Y) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Subterm Criterion Processor: simple projection: pi(eq#) = 1 problem: DPs: TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Qed DPs: min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) -> min#(cons(N,L)) ifmin#(false(),cons(N,cons(M,L))) -> min#(cons(M,L)) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) KBO Processor: argument filtering: pi(0) = [] pi(eq) = [] pi(true) = [] pi(s) = [] pi(false) = [] pi(le) = [] pi(nil) = [] pi(cons) = [1] pi(min) = 0 pi(ifmin) = 1 pi(replace) = 2 pi(ifrepl) = 3 pi(selsort) = 0 pi(ifselsort) = 1 pi(min#) = 0 pi(ifmin#) = 1 weight function: w0 = 1 w(ifselsort) = w(ifmin) = w(nil) = w(le) = w(false) = w(s) = w( true) = w(eq) = w(0) = 1 w(ifmin#) = w(min#) = w(selsort) = w(ifrepl) = w(replace) = w(min) = w( cons) = 0 precedence: cons ~ nil > le ~ eq > ifmin# ~ min# ~ ifselsort ~ selsort ~ ifrepl ~ replace ~ ifmin ~ min ~ false ~ s ~ true ~ 0 problem: DPs: min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/1 DPs: le#(s(X),s(Y)) -> le#(X,Y) TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Subterm Criterion Processor: simple projection: pi(le#) = 1 problem: DPs: TRS: eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(X,Y) le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) min(cons(0(),nil())) -> 0() min(cons(s(N),nil())) -> s(N) min(cons(N,cons(M,L))) -> ifmin(le(N,M),cons(N,cons(M,L))) ifmin(true(),cons(N,cons(M,L))) -> min(cons(N,L)) ifmin(false(),cons(N,cons(M,L))) -> min(cons(M,L)) replace(N,M,nil()) -> nil() replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) ifrepl(true(),N,M,cons(K,L)) -> cons(M,L) ifrepl(false(),N,M,cons(K,L)) -> cons(K,replace(N,M,L)) selsort(nil()) -> nil() selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) ifselsort(true(),cons(N,L)) -> cons(N,selsort(L)) ifselsort(false(),cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) Qed