MAYBE 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))) Usable Rule 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: f22(x,y) -> x f22(x,y) -> y le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(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)) 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: f22(x,y) -> x f22(x,y) -> y le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) eq(0(),0()) -> true() eq(0(),s(Y)) -> false() eq(s(X),0()) -> false() eq(s(X),s(Y)) -> eq(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)) 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) Restore Modifier: 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))) 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))) Open 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))) Open 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))) Open 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))) Open 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))) Open