MAYBE

Problem:
 eq(0(),0()) -> true()
 eq(0(),s(m)) -> false()
 eq(s(n),0()) -> false()
 eq(s(n),s(m)) -> eq(n,m)
 le(0(),m) -> true()
 le(s(n),0()) -> false()
 le(s(n),s(m)) -> le(n,m)
 min(cons(x,nil())) -> x
 min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
 if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
 if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
 replace(n,m,nil()) -> nil()
 replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
 if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
 if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
 empty(nil()) -> true()
 empty(cons(n,x)) -> false()
 head(cons(n,x)) -> n
 tail(nil()) -> nil()
 tail(cons(n,x)) -> x
 sort(x) -> sortIter(x,nil())
 sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
 if(true(),x,y,z) -> y
 if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)

Proof:
 DP Processor:
  DPs:
   eq#(s(n),s(m)) -> eq#(n,m)
   le#(s(n),s(m)) -> le#(n,m)
   min#(cons(n,cons(m,x))) -> le#(n,m)
   min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
   if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
   if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
   replace#(n,m,cons(k,x)) -> eq#(n,k)
   replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
   if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
   sort#(x) -> sortIter#(x,nil())
   sortIter#(x,y) -> min#(x)
   sortIter#(x,y) -> empty#(x)
   sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
   if#(false(),x,y,z) -> tail#(x)
   if#(false(),x,y,z) -> head#(x)
   if#(false(),x,y,z) -> min#(x)
   if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x))
   if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
  TRS:
   eq(0(),0()) -> true()
   eq(0(),s(m)) -> false()
   eq(s(n),0()) -> false()
   eq(s(n),s(m)) -> eq(n,m)
   le(0(),m) -> true()
   le(s(n),0()) -> false()
   le(s(n),s(m)) -> le(n,m)
   min(cons(x,nil())) -> x
   min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
   if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
   if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
   replace(n,m,nil()) -> nil()
   replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
   if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
   if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
   empty(nil()) -> true()
   empty(cons(n,x)) -> false()
   head(cons(n,x)) -> n
   tail(nil()) -> nil()
   tail(cons(n,x)) -> x
   sort(x) -> sortIter(x,nil())
   sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
   if(true(),x,y,z) -> y
   if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
  Usable Rule Processor:
   DPs:
    eq#(s(n),s(m)) -> eq#(n,m)
    le#(s(n),s(m)) -> le#(n,m)
    min#(cons(n,cons(m,x))) -> le#(n,m)
    min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
    if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
    if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
    replace#(n,m,cons(k,x)) -> eq#(n,k)
    replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
    if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
    sort#(x) -> sortIter#(x,nil())
    sortIter#(x,y) -> min#(x)
    sortIter#(x,y) -> empty#(x)
    sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
    if#(false(),x,y,z) -> tail#(x)
    if#(false(),x,y,z) -> head#(x)
    if#(false(),x,y,z) -> min#(x)
    if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x))
    if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
   TRS:
    f31(x,y) -> x
    f31(x,y) -> y
    le(0(),m) -> true()
    le(s(n),0()) -> false()
    le(s(n),s(m)) -> le(n,m)
    eq(0(),0()) -> true()
    eq(0(),s(m)) -> false()
    eq(s(n),0()) -> false()
    eq(s(n),s(m)) -> eq(n,m)
    min(cons(x,nil())) -> x
    min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
    if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
    if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
    empty(nil()) -> true()
    empty(cons(n,x)) -> false()
    tail(nil()) -> nil()
    tail(cons(n,x)) -> x
    head(cons(n,x)) -> n
    replace(n,m,nil()) -> nil()
    replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
    if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
    if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
   CDG Processor:
    DPs:
     eq#(s(n),s(m)) -> eq#(n,m)
     le#(s(n),s(m)) -> le#(n,m)
     min#(cons(n,cons(m,x))) -> le#(n,m)
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
     if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
     if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
     replace#(n,m,cons(k,x)) -> eq#(n,k)
     replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
     if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
     sort#(x) -> sortIter#(x,nil())
     sortIter#(x,y) -> min#(x)
     sortIter#(x,y) -> empty#(x)
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
     if#(false(),x,y,z) -> tail#(x)
     if#(false(),x,y,z) -> head#(x)
     if#(false(),x,y,z) -> min#(x)
     if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x))
     if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
    TRS:
     f31(x,y) -> x
     f31(x,y) -> y
     le(0(),m) -> true()
     le(s(n),0()) -> false()
     le(s(n),s(m)) -> le(n,m)
     eq(0(),0()) -> true()
     eq(0(),s(m)) -> false()
     eq(s(n),0()) -> false()
     eq(s(n),s(m)) -> eq(n,m)
     min(cons(x,nil())) -> x
     min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
     if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
     if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
     empty(nil()) -> true()
     empty(cons(n,x)) -> false()
     tail(nil()) -> nil()
     tail(cons(n,x)) -> x
     head(cons(n,x)) -> n
     replace(n,m,nil()) -> nil()
     replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
     if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
     if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
    graph:
     if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z) ->
     sortIter#(x,y) -> min#(x)
     if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z) ->
     sortIter#(x,y) -> empty#(x)
     if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z) ->
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
     if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x)) ->
     replace#(n,m,cons(k,x)) -> eq#(n,k)
     if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x)) ->
     replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
     if#(false(),x,y,z) -> min#(x) ->
     min#(cons(n,cons(m,x))) -> le#(n,m)
     if#(false(),x,y,z) -> min#(x) ->
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil()))) ->
     if#(false(),x,y,z) -> tail#(x)
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil()))) ->
     if#(false(),x,y,z) -> head#(x)
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil()))) ->
     if#(false(),x,y,z) -> min#(x)
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil()))) ->
     if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x))
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil()))) ->
     if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
     sortIter#(x,y) -> min#(x) -> min#(cons(n,cons(m,x))) -> le#(n,m)
     sortIter#(x,y) -> min#(x) ->
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
     sort#(x) -> sortIter#(x,nil()) -> sortIter#(x,y) -> min#(x)
     sort#(x) -> sortIter#(x,nil()) -> sortIter#(x,y) -> empty#(x)
     sort#(x) -> sortIter#(x,nil()) ->
     sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
     if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x) ->
     replace#(n,m,cons(k,x)) -> eq#(n,k)
     if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x) ->
     replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
     replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x)) ->
     if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
     replace#(n,m,cons(k,x)) -> eq#(n,k) ->
     eq#(s(n),s(m)) -> eq#(n,m)
     if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x)) ->
     min#(cons(n,cons(m,x))) -> le#(n,m)
     if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x)) ->
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
     if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x)) ->
     min#(cons(n,cons(m,x))) -> le#(n,m)
     if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x)) ->
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x))) ->
     if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
     min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x))) ->
     if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
     min#(cons(n,cons(m,x))) -> le#(n,m) -> le#(s(n),s(m)) -> le#(n,m)
     le#(s(n),s(m)) -> le#(n,m) -> le#(s(n),s(m)) -> le#(n,m)
     eq#(s(n),s(m)) -> eq#(n,m) -> eq#(s(n),s(m)) -> eq#(n,m)
    Restore Modifier:
     DPs:
      eq#(s(n),s(m)) -> eq#(n,m)
      le#(s(n),s(m)) -> le#(n,m)
      min#(cons(n,cons(m,x))) -> le#(n,m)
      min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
      if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
      if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
      replace#(n,m,cons(k,x)) -> eq#(n,k)
      replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
      if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
      sort#(x) -> sortIter#(x,nil())
      sortIter#(x,y) -> min#(x)
      sortIter#(x,y) -> empty#(x)
      sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
      if#(false(),x,y,z) -> tail#(x)
      if#(false(),x,y,z) -> head#(x)
      if#(false(),x,y,z) -> min#(x)
      if#(false(),x,y,z) -> replace#(min(x),head(x),tail(x))
      if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
     TRS:
      eq(0(),0()) -> true()
      eq(0(),s(m)) -> false()
      eq(s(n),0()) -> false()
      eq(s(n),s(m)) -> eq(n,m)
      le(0(),m) -> true()
      le(s(n),0()) -> false()
      le(s(n),s(m)) -> le(n,m)
      min(cons(x,nil())) -> x
      min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
      if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
      if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
      replace(n,m,nil()) -> nil()
      replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
      if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
      if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
      empty(nil()) -> true()
      empty(cons(n,x)) -> false()
      head(cons(n,x)) -> n
      tail(nil()) -> nil()
      tail(cons(n,x)) -> x
      sort(x) -> sortIter(x,nil())
      sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
      if(true(),x,y,z) -> y
      if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
     SCC Processor:
      #sccs: 5
      #rules: 9
      #arcs: 30/324
      DPs:
       if#(false(),x,y,z) -> sortIter#(replace(min(x),head(x),tail(x)),z)
       sortIter#(x,y) -> if#(empty(x),x,y,append(y,cons(min(x),nil())))
      TRS:
       eq(0(),0()) -> true()
       eq(0(),s(m)) -> false()
       eq(s(n),0()) -> false()
       eq(s(n),s(m)) -> eq(n,m)
       le(0(),m) -> true()
       le(s(n),0()) -> false()
       le(s(n),s(m)) -> le(n,m)
       min(cons(x,nil())) -> x
       min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
       if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
       if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
       replace(n,m,nil()) -> nil()
       replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
       if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
       if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
       empty(nil()) -> true()
       empty(cons(n,x)) -> false()
       head(cons(n,x)) -> n
       tail(nil()) -> nil()
       tail(cons(n,x)) -> x
       sort(x) -> sortIter(x,nil())
       sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
       if(true(),x,y,z) -> y
       if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
      Open
      
      DPs:
       min#(cons(n,cons(m,x))) -> if_min#(le(n,m),cons(n,cons(m,x)))
       if_min#(false(),cons(n,cons(m,x))) -> min#(cons(m,x))
       if_min#(true(),cons(n,cons(m,x))) -> min#(cons(n,x))
      TRS:
       eq(0(),0()) -> true()
       eq(0(),s(m)) -> false()
       eq(s(n),0()) -> false()
       eq(s(n),s(m)) -> eq(n,m)
       le(0(),m) -> true()
       le(s(n),0()) -> false()
       le(s(n),s(m)) -> le(n,m)
       min(cons(x,nil())) -> x
       min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
       if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
       if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
       replace(n,m,nil()) -> nil()
       replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
       if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
       if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
       empty(nil()) -> true()
       empty(cons(n,x)) -> false()
       head(cons(n,x)) -> n
       tail(nil()) -> nil()
       tail(cons(n,x)) -> x
       sort(x) -> sortIter(x,nil())
       sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
       if(true(),x,y,z) -> y
       if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
      Open
      
      DPs:
       le#(s(n),s(m)) -> le#(n,m)
      TRS:
       eq(0(),0()) -> true()
       eq(0(),s(m)) -> false()
       eq(s(n),0()) -> false()
       eq(s(n),s(m)) -> eq(n,m)
       le(0(),m) -> true()
       le(s(n),0()) -> false()
       le(s(n),s(m)) -> le(n,m)
       min(cons(x,nil())) -> x
       min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
       if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
       if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
       replace(n,m,nil()) -> nil()
       replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
       if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
       if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
       empty(nil()) -> true()
       empty(cons(n,x)) -> false()
       head(cons(n,x)) -> n
       tail(nil()) -> nil()
       tail(cons(n,x)) -> x
       sort(x) -> sortIter(x,nil())
       sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
       if(true(),x,y,z) -> y
       if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
      Open
      
      DPs:
       replace#(n,m,cons(k,x)) -> if_replace#(eq(n,k),n,m,cons(k,x))
       if_replace#(false(),n,m,cons(k,x)) -> replace#(n,m,x)
      TRS:
       eq(0(),0()) -> true()
       eq(0(),s(m)) -> false()
       eq(s(n),0()) -> false()
       eq(s(n),s(m)) -> eq(n,m)
       le(0(),m) -> true()
       le(s(n),0()) -> false()
       le(s(n),s(m)) -> le(n,m)
       min(cons(x,nil())) -> x
       min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
       if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
       if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
       replace(n,m,nil()) -> nil()
       replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
       if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
       if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
       empty(nil()) -> true()
       empty(cons(n,x)) -> false()
       head(cons(n,x)) -> n
       tail(nil()) -> nil()
       tail(cons(n,x)) -> x
       sort(x) -> sortIter(x,nil())
       sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
       if(true(),x,y,z) -> y
       if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
      Open
      
      DPs:
       eq#(s(n),s(m)) -> eq#(n,m)
      TRS:
       eq(0(),0()) -> true()
       eq(0(),s(m)) -> false()
       eq(s(n),0()) -> false()
       eq(s(n),s(m)) -> eq(n,m)
       le(0(),m) -> true()
       le(s(n),0()) -> false()
       le(s(n),s(m)) -> le(n,m)
       min(cons(x,nil())) -> x
       min(cons(n,cons(m,x))) -> if_min(le(n,m),cons(n,cons(m,x)))
       if_min(true(),cons(n,cons(m,x))) -> min(cons(n,x))
       if_min(false(),cons(n,cons(m,x))) -> min(cons(m,x))
       replace(n,m,nil()) -> nil()
       replace(n,m,cons(k,x)) -> if_replace(eq(n,k),n,m,cons(k,x))
       if_replace(true(),n,m,cons(k,x)) -> cons(m,x)
       if_replace(false(),n,m,cons(k,x)) -> cons(k,replace(n,m,x))
       empty(nil()) -> true()
       empty(cons(n,x)) -> false()
       head(cons(n,x)) -> n
       tail(nil()) -> nil()
       tail(cons(n,x)) -> x
       sort(x) -> sortIter(x,nil())
       sortIter(x,y) -> if(empty(x),x,y,append(y,cons(min(x),nil())))
       if(true(),x,y,z) -> y
       if(false(),x,y,z) -> sortIter(replace(min(x),head(x),tail(x)),z)
      Open