TRS Standard pair #487069267

details

property	value
status	complete
benchmark	selsort.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n174.star.cs.uiowa.edu
space	Rubio_04

run statistics

property	value
solver	ttt2-1.20
configuration	ttt2
runtime (wallclock)	2.9775 seconds
cpu usage	10.4543
user time	8.5303
system time	1.92395
max virtual memory	6137336.0
max residence set size	101808.0

stage attributes

key	value
starexec-result	YES

output

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()

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to TRS Standard