/export/starexec/sandbox/solver/bin/starexec_run_ttt2 /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- 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))) Subterm Criterion Processor: simple projection: pi(s) = [0,0] pi(cons) = [1,1] pi(replace) = 2 pi(ifrepl) = 3 pi(selsort#) = [0,0] pi(ifselsort#) = 1 problem: DPs: ifselsort#(false(),cons(N,L)) -> selsort#(replace(min(cons(N,L)),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))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/4 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#) = 0 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))) Usable Rule Processor: 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: le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) Arctic Interpretation Processor: dimension: 1 usable rules: le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) interpretation: [false] = 2, [s](x0) = x0, [min#](x0) = x0 + 0, [ifmin#](x0, x1) = x0 + x1 + 0, [le](x0, x1) = 1x0 + 2, [0] = 3, [cons](x0, x1) = 2x0 + 2x1 + 0, [true] = 3 orientation: min#(cons(N,cons(M,L))) = 4L + 4M + 2N + 2 >= 4L + 4M + 2N + 2 = ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) = 4L + 4M + 2N + 3 >= 2L + 2N + 0 = min#(cons(N,L)) ifmin#(false(),cons(N,cons(M,L))) = 4L + 4M + 2N + 2 >= 2L + 2M + 0 = min#(cons(M,L)) le(0(),Y) = 4 >= 3 = true() le(s(X),0()) = 1X + 2 >= 2 = false() le(s(X),s(Y)) = 1X + 2 >= 1X + 2 = le(X,Y) problem: 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)) TRS: le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) Restore Modifier: 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)) 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: 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)) TRS: le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) KBO Processor: argument filtering: pi(0) = [] pi(true) = [] pi(s) = 0 pi(false) = [] pi(le) = 0 pi(cons) = [1] pi(min#) = 0 pi(ifmin#) = 1 usable rules: weight function: w0 = 1 w(ifmin#) = w(min#) = w(cons) = w(le) = w(false) = w(s) = w(true) = w(0) = 1 precedence: cons > s > 0 > min# > true > ifmin# > false > le problem: DPs: min#(cons(N,cons(M,L))) -> ifmin#(le(N,M),cons(N,cons(M,L))) TRS: le(0(),Y) -> true() le(s(X),0()) -> false() le(s(X),s(Y)) -> le(X,Y) Restore Modifier: 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#) = 0 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