YES Problem: a__first(0(),X) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__from(X) -> cons(mark(X),from(s(X))) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() mark(s(X)) -> s(mark(X)) mark(cons(X1,X2)) -> cons(mark(X1),X2) a__first(X1,X2) -> first(X1,X2) a__from(X) -> from(X) Proof: DP Processor: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__from#(X) -> mark#(X) mark#(first(X1,X2)) -> mark#(X2) mark#(first(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(mark(X)) mark#(s(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) TRS: a__first(0(),X) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__from(X) -> cons(mark(X),from(s(X))) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() mark(s(X)) -> s(mark(X)) mark(cons(X1,X2)) -> cons(mark(X1),X2) a__first(X1,X2) -> first(X1,X2) a__from(X) -> from(X) TDG Processor: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__from#(X) -> mark#(X) mark#(first(X1,X2)) -> mark#(X2) mark#(first(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(mark(X)) mark#(s(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) TRS: a__first(0(),X) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__from(X) -> cons(mark(X),from(s(X))) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() mark(s(X)) -> s(mark(X)) mark(cons(X1,X2)) -> cons(mark(X1),X2) a__first(X1,X2) -> first(X1,X2) a__from(X) -> from(X) graph: a__from#(X) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) a__from#(X) -> mark#(X) -> mark#(s(X)) -> mark#(X) a__from#(X) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) a__from#(X) -> mark#(X) -> mark#(from(X)) -> mark#(X) a__from#(X) -> mark#(X) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) a__from#(X) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X1) a__from#(X) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X2) mark#(from(X)) -> a__from#(mark(X)) -> a__from#(X) -> mark#(X) mark#(from(X)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(from(X)) -> mark#(X) -> mark#(s(X)) -> mark#(X) mark#(from(X)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) mark#(from(X)) -> mark#(X) -> mark#(from(X)) -> mark#(X) mark#(from(X)) -> mark#(X) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(from(X)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X1) mark#(from(X)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X2) mark#(first(X1,X2)) -> mark#(X2) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X2) -> mark#(s(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X2) -> mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> mark#(X2) -> mark#(from(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(first(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> mark#(X2) mark#(first(X1,X2)) -> mark#(X1) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X1) -> mark#(s(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(first(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X2) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) -> a__first#(s(X),cons(Y,Z)) -> mark#(Y) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(s(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> a__from#(mark(X)) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X1) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X2) mark#(s(X)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) -> mark#(s(X)) -> mark#(X) mark#(s(X)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) mark#(s(X)) -> mark#(X) -> mark#(from(X)) -> mark#(X) mark#(s(X)) -> mark#(X) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(s(X)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X2) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(cons(X1,X2)) -> mark#(X1) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(s(X)) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(from(X)) -> a__from#(mark(X)) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(from(X)) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(first(X1,X2)) -> mark#(X1) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(first(X1,X2)) -> mark#(X2) KBO Processor: argument filtering: pi(0) = [] pi(a__first) = [0,1] pi(nil) = [] pi(s) = [0] pi(cons) = [0] pi(mark) = [0] pi(first) = [0,1] pi(a__from) = [0] pi(from) = [0] pi(a__first#) = 1 pi(mark#) = 0 pi(a__from#) = [0] weight function: w0 = 1 w(mark#) = w(a__first#) = w(from) = w(a__from) = w(cons) = w(s) = w( nil) = w(0) = 1 w(a__from#) = w(first) = w(mark) = w(a__first) = 0 precedence: mark# > a__from# ~ mark > a__from ~ a__first > a__first# ~ from ~ first ~ cons ~ s ~ nil ~ 0 problem: DPs: TRS: a__first(0(),X) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__from(X) -> cons(mark(X),from(s(X))) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() mark(s(X)) -> s(mark(X)) mark(cons(X1,X2)) -> cons(mark(X1),X2) a__first(X1,X2) -> first(X1,X2) a__from(X) -> from(X) Qed