/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR K L M N X Y) (RULES eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ) Problem 1: Innermost Equivalent Processor: -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: EQ(s(X),s(Y)) -> EQ(X,Y) IFMIN(false,cons(N,cons(M,L))) -> MIN(cons(M,L)) IFMIN(true,cons(N,cons(M,L))) -> MIN(cons(N,L)) IFREPL(false,N,M,cons(K,L)) -> REPLACE(N,M,L) IFSELSORT(false,cons(N,L)) -> MIN(cons(N,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(true,cons(N,L)) -> SELSORT(L) LE(s(X),s(Y)) -> LE(X,Y) MIN(cons(N,cons(M,L))) -> IFMIN(le(N,M),cons(N,cons(M,L))) MIN(cons(N,cons(M,L))) -> LE(N,M) REPLACE(N,M,cons(K,L)) -> EQ(N,K) REPLACE(N,M,cons(K,L)) -> IFREPL(eq(N,K),N,M,cons(K,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)) SELSORT(cons(N,L)) -> MIN(cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil Problem 1: SCC Processor: -> Pairs: EQ(s(X),s(Y)) -> EQ(X,Y) IFMIN(false,cons(N,cons(M,L))) -> MIN(cons(M,L)) IFMIN(true,cons(N,cons(M,L))) -> MIN(cons(N,L)) IFREPL(false,N,M,cons(K,L)) -> REPLACE(N,M,L) IFSELSORT(false,cons(N,L)) -> MIN(cons(N,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(true,cons(N,L)) -> SELSORT(L) LE(s(X),s(Y)) -> LE(X,Y) MIN(cons(N,cons(M,L))) -> IFMIN(le(N,M),cons(N,cons(M,L))) MIN(cons(N,cons(M,L))) -> LE(N,M) REPLACE(N,M,cons(K,L)) -> EQ(N,K) REPLACE(N,M,cons(K,L)) -> IFREPL(eq(N,K),N,M,cons(K,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)) SELSORT(cons(N,L)) -> MIN(cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: LE(s(X),s(Y)) -> LE(X,Y) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->->Cycle: ->->-> Pairs: IFMIN(false,cons(N,cons(M,L))) -> MIN(cons(M,L)) 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))) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->->Cycle: ->->-> Pairs: EQ(s(X),s(Y)) -> EQ(X,Y) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->->Cycle: ->->-> Pairs: 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)) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->->Cycle: ->->-> Pairs: IFSELSORT(false,cons(N,L)) -> SELSORT(replace(min(cons(N,L)),N,L)) IFSELSORT(true,cons(N,L)) -> SELSORT(L) SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil The problem is decomposed in 5 subproblems. Problem 1.1: Subterm Processor: -> Pairs: LE(s(X),s(Y)) -> LE(X,Y) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Projection: pi(LE) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pairs Processor: -> Pairs: IFMIN(false,cons(N,cons(M,L))) -> MIN(cons(M,L)) 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))) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil -> Usable rules: le(0,Y) -> true le(s(X),0) -> false le(s(X),s(Y)) -> le(X,Y) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [le](X1,X2) = 2.X1 + 2.X2 + 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [false] = 0 [s](X) = 2.X [true] = 2 [IFMIN](X1,X2) = 2.X2 + 1 [MIN](X) = 2.X + 1 Problem 1.2: SCC Processor: -> Pairs: 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))) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: 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))) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil Problem 1.2: Reduction Pairs Processor: -> Pairs: 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))) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil -> Usable rules: le(0,Y) -> true le(s(X),0) -> false le(s(X),s(Y)) -> le(X,Y) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [le](X1,X2) = 1 [0] = 1 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [false] = 1 [s](X) = 0 [true] = 1 [IFMIN](X1,X2) = 2.X1 + 2.X2 [MIN](X) = 2.X + 2 Problem 1.2: SCC Processor: -> Pairs: MIN(cons(N,cons(M,L))) -> IFMIN(le(N,M),cons(N,cons(M,L))) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: EQ(s(X),s(Y)) -> EQ(X,Y) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Projection: pi(EQ) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Subterm Processor: -> Pairs: 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)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Projection: pi(IFREPL) = 4 pi(REPLACE) = 3 Problem 1.4: SCC Processor: -> Pairs: REPLACE(N,M,cons(K,L)) -> IFREPL(eq(N,K),N,M,cons(K,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.5: Reduction Pairs Processor: -> Pairs: IFSELSORT(false,cons(N,L)) -> SELSORT(replace(min(cons(N,L)),N,L)) IFSELSORT(true,cons(N,L)) -> SELSORT(L) SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil -> Usable rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [eq](X1,X2) = 2 [ifmin](X1,X2) = 0 [ifrepl](X1,X2,X3,X4) = 2.X2 + 2.X3 + X4 [le](X1,X2) = 2 [min](X) = 0 [replace](X1,X2,X3) = 2.X1 + 2.X2 + X3 [0] = 0 [cons](X1,X2) = 2.X1 + X2 + 1 [false] = 2 [nil] = 2 [s](X) = 0 [true] = 0 [IFSELSORT](X1,X2) = 2.X2 + 1 [SELSORT](X) = 2.X + 1 Problem 1.5: SCC Processor: -> Pairs: IFSELSORT(true,cons(N,L)) -> SELSORT(L) SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: IFSELSORT(true,cons(N,L)) -> SELSORT(L) SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) ->->-> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil Problem 1.5: Subterm Processor: -> Pairs: IFSELSORT(true,cons(N,L)) -> SELSORT(L) SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Projection: pi(IFSELSORT) = 2 pi(SELSORT) = 1 Problem 1.5: SCC Processor: -> Pairs: SELSORT(cons(N,L)) -> IFSELSORT(eq(N,min(cons(N,L))),cons(N,L)) -> Rules: eq(0,0) -> true eq(0,s(Y)) -> false eq(s(X),0) -> false eq(s(X),s(Y)) -> eq(X,Y) ifmin(false,cons(N,cons(M,L))) -> min(cons(M,L)) ifmin(true,cons(N,cons(M,L))) -> min(cons(N,L)) ifrepl(false,N,M,cons(K,L)) -> cons(K,replace(N,M,L)) ifrepl(true,N,M,cons(K,L)) -> cons(M,L) ifselsort(false,cons(N,L)) -> cons(min(cons(N,L)),selsort(replace(min(cons(N,L)),N,L))) ifselsort(true,cons(N,L)) -> cons(N,selsort(L)) 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))) replace(N,M,cons(K,L)) -> ifrepl(eq(N,K),N,M,cons(K,L)) replace(N,M,nil) -> nil selsort(cons(N,L)) -> ifselsort(eq(N,min(cons(N,L))),cons(N,L)) selsort(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite.