/export/starexec/sandbox2/solver/bin/starexec_run_ttt2-1.17+nonreach /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/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(cons) = [1,1] pi(replace) = [2,2] pi(ifrepl) = [3,3] pi(selsort#) = 0 pi(ifselsort#) = 1 problem: 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)) 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(cons) = [1,1] pi(replace) = 2 pi(ifrepl) = 3 pi(selsort#) = 0 pi(ifselsort#) = 1 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#) = 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: [ifmin#](x0, x1) = x0 + 3x1 + 0, [min#](x0) = 4x0 + 0, [cons](x0, x1) = 1x1 + 0, [le](x0, x1) = 3, [false] = 0, [s](x0) = x0 + 0, [true] = 2, [0] = 0 orientation: min#(cons(N,cons(M,L))) = 6L + 5 >= 5L + 4 = ifmin#(le(N,M),cons(N,cons(M,L))) ifmin#(true(),cons(N,cons(M,L))) = 5L + 4 >= 5L + 4 = min#(cons(N,L)) ifmin#(false(),cons(N,cons(M,L))) = 5L + 4 >= 5L + 4 = min#(cons(M,L)) le(0(),Y) = 3 >= 2 = true() le(s(X),0()) = 3 >= 0 = false() le(s(X),s(Y)) = 3 >= 3 = le(X,Y) problem: DPs: 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) Restore Modifier: DPs: 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))) SCC Processor: #sccs: 0 #rules: 0 #arcs: 4/4 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