YES Problem: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Proof: DP Processor: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(0(),cons(X,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(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#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) TDG Processor: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(0(),cons(X,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(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#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) graph: a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(s(X)) -> mark#(X) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X1) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X2) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X1) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X2) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) a__sel#(0(),cons(X,Z)) -> mark#(X) -> mark#(from(X)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) -> a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) -> a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) -> a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) -> a__sel#(0(),cons(X,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(s(X)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(cons(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(sel(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(sel(X1,X2)) -> mark#(X2) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(first(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(first(X1,X2)) -> mark#(X2) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(from(X)) -> a__from#(mark(X)) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) -> mark#(from(X)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(s(X)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X2) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X1) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(first(X1,X2)) -> mark#(X2) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) a__sel#(s(X),cons(Y,Z)) -> mark#(X) -> mark#(from(X)) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(s(X)) -> mark#(X) 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#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(sel(X1,X2)) -> mark#(X1) a__first#(s(X),cons(Y,Z)) -> mark#(Y) -> mark#(sel(X1,X2)) -> mark#(X2) 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) 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) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) -> a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) -> a__sel#(s(X),cons(Y,Z)) -> mark#(X) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) -> a__sel#(s(X),cons(Y,Z)) -> mark#(Z) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) -> a__sel#(0(),cons(X,Z)) -> mark#(X) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(s(X)) -> mark#(X) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(first(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(from(X)) -> a__from#(mark(X)) mark#(sel(X1,X2)) -> mark#(X2) -> mark#(from(X)) -> mark#(X) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(s(X)) -> mark#(X) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(first(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> a__from#(mark(X)) mark#(sel(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> mark#(X) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) -> a__first#(s(X),cons(Y,Z)) -> mark#(Y) mark#(first(X1,X2)) -> mark#(X2) -> mark#(s(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X2) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(first(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X2) -> mark#(sel(X1,X2)) -> mark#(X2) 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#(X2) -> mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> mark#(X2) -> mark#(from(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X1) -> mark#(s(X)) -> mark#(X) mark#(first(X1,X2)) -> mark#(X1) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(first(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(first(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X2) 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)) -> mark#(X1) -> mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(s(X)) -> mark#(X) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(sel(X1,X2)) -> mark#(X2) 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#(cons(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> a__from#(mark(X)) mark#(cons(X1,X2)) -> mark#(X1) -> mark#(from(X)) -> mark#(X) mark#(from(X)) -> mark#(X) -> mark#(s(X)) -> mark#(X) mark#(from(X)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(from(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(from(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(from(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X2) 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#(from(X)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) mark#(from(X)) -> mark#(X) -> mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(mark(X)) -> a__from#(X) -> mark#(X) mark#(s(X)) -> mark#(X) -> mark#(s(X)) -> mark#(X) mark#(s(X)) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(s(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X2) 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) mark#(s(X)) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) mark#(s(X)) -> mark#(X) -> mark#(from(X)) -> mark#(X) a__from#(X) -> mark#(X) -> mark#(s(X)) -> mark#(X) a__from#(X) -> mark#(X) -> mark#(cons(X1,X2)) -> mark#(X1) a__from#(X) -> mark#(X) -> mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) a__from#(X) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X1) a__from#(X) -> mark#(X) -> mark#(sel(X1,X2)) -> mark#(X2) 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) a__from#(X) -> mark#(X) -> mark#(from(X)) -> a__from#(mark(X)) a__from#(X) -> mark#(X) -> mark#(from(X)) -> mark#(X) Arctic Interpretation Processor: dimension: 1 usable rules: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) interpretation: [cons](x0, x1) = 4x0 + x1, [first](x0, x1) = x0 + x1, [mark](x0) = x0, [from](x0) = 4x0 + 0, [0] = 1, [sel](x0, x1) = x0 + 2x1 + 0, [a__from](x0) = 4x0 + 0, [nil] = 1, [a__sel#](x0, x1) = x0 + 2x1 + 0, [mark#](x0) = x0 + 0, [a__from#](x0) = x0 + 0, [a__sel](x0, x1) = x0 + 2x1 + 0, [a__first#](x0, x1) = x0 + x1 + 0, [a__first](x0, x1) = x0 + x1, [s](x0) = x0 orientation: a__from#(X) = X + 0 >= X + 0 = mark#(X) a__first#(s(X),cons(Y,Z)) = X + 4Y + Z + 0 >= Y + 0 = mark#(Y) a__sel#(0(),cons(X,Z)) = 6X + 2Z + 1 >= X + 0 = mark#(X) a__sel#(s(X),cons(Y,Z)) = X + 6Y + 2Z + 0 >= Z + 0 = mark#(Z) a__sel#(s(X),cons(Y,Z)) = X + 6Y + 2Z + 0 >= X + 0 = mark#(X) a__sel#(s(X),cons(Y,Z)) = X + 6Y + 2Z + 0 >= X + 2Z + 0 = a__sel#(mark(X),mark(Z)) mark#(from(X)) = 4X + 0 >= X + 0 = mark#(X) mark#(from(X)) = 4X + 0 >= X + 0 = a__from#(mark(X)) mark#(first(X1,X2)) = X1 + X2 + 0 >= X2 + 0 = mark#(X2) mark#(first(X1,X2)) = X1 + X2 + 0 >= X1 + 0 = mark#(X1) mark#(first(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) = X1 + 2X2 + 0 >= X2 + 0 = mark#(X2) mark#(sel(X1,X2)) = X1 + 2X2 + 0 >= X1 + 0 = mark#(X1) mark#(sel(X1,X2)) = X1 + 2X2 + 0 >= X1 + 2X2 + 0 = a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) = 4X1 + X2 + 0 >= X1 + 0 = mark#(X1) mark#(s(X)) = X + 0 >= X + 0 = mark#(X) a__from(X) = 4X + 0 >= 4X + 0 = cons(mark(X),from(s(X))) a__first(0(),Z) = Z + 1 >= 1 = nil() a__first(s(X),cons(Y,Z)) = X + 4Y + Z >= X + 4Y + Z = cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) = 6X + 2Z + 1 >= X = mark(X) a__sel(s(X),cons(Y,Z)) = X + 6Y + 2Z + 0 >= X + 2Z + 0 = a__sel(mark(X),mark(Z)) mark(from(X)) = 4X + 0 >= 4X + 0 = a__from(mark(X)) mark(first(X1,X2)) = X1 + X2 >= X1 + X2 = a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) = X1 + 2X2 + 0 >= X1 + 2X2 + 0 = a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) = 4X1 + X2 >= 4X1 + X2 = cons(mark(X1),X2) mark(s(X)) = X >= X = s(mark(X)) mark(0()) = 1 >= 1 = 0() mark(nil()) = 1 >= 1 = nil() a__from(X) = 4X + 0 >= 4X + 0 = from(X) a__first(X1,X2) = X1 + X2 >= X1 + X2 = first(X1,X2) a__sel(X1,X2) = X1 + 2X2 + 0 >= X1 + 2X2 + 0 = sel(X1,X2) problem: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(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#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Restore Modifier: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(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#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Arctic Interpretation Processor: dimension: 1 usable rules: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) interpretation: [cons](x0, x1) = x0 + x1, [first](x0, x1) = 1x0 + 1x1 + 2, [mark](x0) = x0 + 0, [from](x0) = x0 + 0, [0] = 4, [sel](x0, x1) = x0 + x1 + 0, [a__from](x0) = x0 + 0, [nil] = 5, [a__sel#](x0, x1) = x0 + x1 + 0, [mark#](x0) = x0 + 0, [a__from#](x0) = x0 + 0, [a__sel](x0, x1) = x0 + x1 + 0, [a__first#](x0, x1) = 1x0 + 1x1 + 0, [a__first](x0, x1) = 1x0 + 1x1 + 2, [s](x0) = x0 orientation: a__from#(X) = X + 0 >= X + 0 = mark#(X) a__first#(s(X),cons(Y,Z)) = 1X + 1Y + 1Z + 0 >= Y + 0 = mark#(Y) a__sel#(s(X),cons(Y,Z)) = X + Y + Z + 0 >= Z + 0 = mark#(Z) a__sel#(s(X),cons(Y,Z)) = X + Y + Z + 0 >= X + 0 = mark#(X) a__sel#(s(X),cons(Y,Z)) = X + Y + Z + 0 >= X + Z + 0 = a__sel#(mark(X),mark(Z)) mark#(from(X)) = X + 0 >= X + 0 = mark#(X) mark#(from(X)) = X + 0 >= X + 0 = a__from#(mark(X)) mark#(first(X1,X2)) = 1X1 + 1X2 + 2 >= X2 + 0 = mark#(X2) mark#(first(X1,X2)) = 1X1 + 1X2 + 2 >= X1 + 0 = mark#(X1) mark#(first(X1,X2)) = 1X1 + 1X2 + 2 >= 1X1 + 1X2 + 1 = a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) = X1 + X2 + 0 >= X2 + 0 = mark#(X2) mark#(sel(X1,X2)) = X1 + X2 + 0 >= X1 + 0 = mark#(X1) mark#(sel(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) = X1 + X2 + 0 >= X1 + 0 = mark#(X1) mark#(s(X)) = X + 0 >= X + 0 = mark#(X) a__from(X) = X + 0 >= X + 0 = cons(mark(X),from(s(X))) a__first(0(),Z) = 1Z + 5 >= 5 = nil() a__first(s(X),cons(Y,Z)) = 1X + 1Y + 1Z + 2 >= 1X + Y + 1Z + 2 = cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) = X + Z + 4 >= X + 0 = mark(X) a__sel(s(X),cons(Y,Z)) = X + Y + Z + 0 >= X + Z + 0 = a__sel(mark(X),mark(Z)) mark(from(X)) = X + 0 >= X + 0 = a__from(mark(X)) mark(first(X1,X2)) = 1X1 + 1X2 + 2 >= 1X1 + 1X2 + 2 = a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = cons(mark(X1),X2) mark(s(X)) = X + 0 >= X + 0 = s(mark(X)) mark(0()) = 4 >= 4 = 0() mark(nil()) = 5 >= 5 = nil() a__from(X) = X + 0 >= X + 0 = from(X) a__first(X1,X2) = 1X1 + 1X2 + 2 >= 1X1 + 1X2 + 2 = first(X1,X2) a__sel(X1,X2) = X1 + X2 + 0 >= X1 + X2 + 0 = sel(X1,X2) problem: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Restore Modifier: DPs: a__from#(X) -> mark#(X) a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> mark#(Z) a__sel#(s(X),cons(Y,Z)) -> mark#(X) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> mark#(X) mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> mark#(X2) mark#(sel(X1,X2)) -> mark#(X1) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Arctic Interpretation Processor: dimension: 1 usable rules: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) interpretation: [cons](x0, x1) = x0 + x1, [first](x0, x1) = 2x0 + 2x1 + 2, [mark](x0) = x0 + 0, [from](x0) = 2x0 + 2, [0] = 0, [sel](x0, x1) = 3x0 + 3x1 + 3, [a__from](x0) = 2x0 + 2, [nil] = 2, [a__sel#](x0, x1) = 7x0 + 7x1 + 7, [mark#](x0) = 4x0 + 0, [a__from#](x0) = 6x0 + 1, [a__sel](x0, x1) = 3x0 + 3x1 + 3, [a__first#](x0, x1) = 5x0 + 6x1 + 0, [a__first](x0, x1) = 2x0 + 2x1 + 2, [s](x0) = x0 orientation: a__from#(X) = 6X + 1 >= 4X + 0 = mark#(X) a__first#(s(X),cons(Y,Z)) = 5X + 6Y + 6Z + 0 >= 4Y + 0 = mark#(Y) a__sel#(s(X),cons(Y,Z)) = 7X + 7Y + 7Z + 7 >= 4Z + 0 = mark#(Z) a__sel#(s(X),cons(Y,Z)) = 7X + 7Y + 7Z + 7 >= 4X + 0 = mark#(X) a__sel#(s(X),cons(Y,Z)) = 7X + 7Y + 7Z + 7 >= 7X + 7Z + 7 = a__sel#(mark(X),mark(Z)) mark#(from(X)) = 6X + 6 >= 4X + 0 = mark#(X) mark#(from(X)) = 6X + 6 >= 6X + 6 = a__from#(mark(X)) mark#(first(X1,X2)) = 6X1 + 6X2 + 6 >= 5X1 + 6X2 + 6 = a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) = 7X1 + 7X2 + 7 >= 4X2 + 0 = mark#(X2) mark#(sel(X1,X2)) = 7X1 + 7X2 + 7 >= 4X1 + 0 = mark#(X1) mark#(sel(X1,X2)) = 7X1 + 7X2 + 7 >= 7X1 + 7X2 + 7 = a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) = 4X1 + 4X2 + 0 >= 4X1 + 0 = mark#(X1) mark#(s(X)) = 4X + 0 >= 4X + 0 = mark#(X) a__from(X) = 2X + 2 >= 2X + 2 = cons(mark(X),from(s(X))) a__first(0(),Z) = 2Z + 2 >= 2 = nil() a__first(s(X),cons(Y,Z)) = 2X + 2Y + 2Z + 2 >= 2X + Y + 2Z + 2 = cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) = 3X + 3Z + 3 >= X + 0 = mark(X) a__sel(s(X),cons(Y,Z)) = 3X + 3Y + 3Z + 3 >= 3X + 3Z + 3 = a__sel(mark(X),mark(Z)) mark(from(X)) = 2X + 2 >= 2X + 2 = a__from(mark(X)) mark(first(X1,X2)) = 2X1 + 2X2 + 2 >= 2X1 + 2X2 + 2 = a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) = 3X1 + 3X2 + 3 >= 3X1 + 3X2 + 3 = a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = cons(mark(X1),X2) mark(s(X)) = X + 0 >= X + 0 = s(mark(X)) mark(0()) = 0 >= 0 = 0() mark(nil()) = 2 >= 2 = nil() a__from(X) = 2X + 2 >= 2X + 2 = from(X) a__first(X1,X2) = 2X1 + 2X2 + 2 >= 2X1 + 2X2 + 2 = first(X1,X2) a__sel(X1,X2) = 3X1 + 3X2 + 3 >= 3X1 + 3X2 + 3 = sel(X1,X2) problem: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Restore Modifier: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) mark#(from(X)) -> a__from#(mark(X)) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(sel(X1,X2)) -> a__sel#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) SCC Processor: #sccs: 2 #rules: 5 #arcs: 130/49 DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) mark#(first(X1,X2)) -> a__first#(mark(X1),mark(X2)) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Arctic Interpretation Processor: dimension: 1 usable rules: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) interpretation: [cons](x0, x1) = x0 + x1 + 0, [first](x0, x1) = 4x0 + 4x1 + 0, [mark](x0) = x0, [from](x0) = x0 + 7, [0] = 1, [sel](x0, x1) = x1, [a__from](x0) = x0 + 7, [nil] = 1, [mark#](x0) = x0 + 0, [a__sel](x0, x1) = x1, [a__first#](x0, x1) = x0 + x1, [a__first](x0, x1) = 4x0 + 4x1 + 0, [s](x0) = x0 orientation: a__first#(s(X),cons(Y,Z)) = X + Y + Z + 0 >= Y + 0 = mark#(Y) mark#(first(X1,X2)) = 4X1 + 4X2 + 0 >= X1 + X2 = a__first#(mark(X1),mark(X2)) mark#(cons(X1,X2)) = X1 + X2 + 0 >= X1 + 0 = mark#(X1) mark#(s(X)) = X + 0 >= X + 0 = mark#(X) a__from(X) = X + 7 >= X + 7 = cons(mark(X),from(s(X))) a__first(0(),Z) = 4Z + 5 >= 1 = nil() a__first(s(X),cons(Y,Z)) = 4X + 4Y + 4Z + 4 >= 4X + Y + 4Z + 0 = cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) = X + Z + 0 >= X = mark(X) a__sel(s(X),cons(Y,Z)) = Y + Z + 0 >= Z = a__sel(mark(X),mark(Z)) mark(from(X)) = X + 7 >= X + 7 = a__from(mark(X)) mark(first(X1,X2)) = 4X1 + 4X2 + 0 >= 4X1 + 4X2 + 0 = a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) = X2 >= X2 = a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) = X1 + X2 + 0 >= X1 + X2 + 0 = cons(mark(X1),X2) mark(s(X)) = X >= X = s(mark(X)) mark(0()) = 1 >= 1 = 0() mark(nil()) = 1 >= 1 = nil() a__from(X) = X + 7 >= X + 7 = from(X) a__first(X1,X2) = 4X1 + 4X2 + 0 >= 4X1 + 4X2 + 0 = first(X1,X2) a__sel(X1,X2) = X2 >= X2 = sel(X1,X2) problem: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Restore Modifier: DPs: a__first#(s(X),cons(Y,Z)) -> mark#(Y) mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) SCC Processor: #sccs: 1 #rules: 2 #arcs: 10/9 DPs: mark#(cons(X1,X2)) -> mark#(X1) mark#(s(X)) -> mark#(X) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Size-Change Termination Processor: DPs: TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) The DP: mark#(cons(X1,X2)) -> mark#(X1) has the edges: 0 > 0 The DP: mark#(s(X)) -> mark#(X) has the edges: 0 > 0 Qed DPs: a__sel#(s(X),cons(Y,Z)) -> a__sel#(mark(X),mark(Z)) TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Maximal Polynomial Processor: usable rules: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) interpretations: a__sel#(x0, x1) = max(0, -1 + x0) sel(x0, x1) = max(0, 0 + x0 + x1) a__sel(x0, x1) = max(0, 0 + x0 + x1) first(x0, x1) = max(0, 0 + x1) nil = 0 a__first(x0, x1) = max(0, x1) 0 = 0 cons(x0, x1) = max(0, x0, -2 + x1) from(x0) = max(0, 0 + x0) s(x0) = max(2, 2 + x0) mark(x0) = max(0, x0) a__from(x0) = max(0, 0 + x0) problem: DPs: TRS: a__from(X) -> cons(mark(X),from(s(X))) a__first(0(),Z) -> nil() a__first(s(X),cons(Y,Z)) -> cons(mark(Y),first(X,Z)) a__sel(0(),cons(X,Z)) -> mark(X) a__sel(s(X),cons(Y,Z)) -> a__sel(mark(X),mark(Z)) mark(from(X)) -> a__from(mark(X)) mark(first(X1,X2)) -> a__first(mark(X1),mark(X2)) mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) mark(cons(X1,X2)) -> cons(mark(X1),X2) mark(s(X)) -> s(mark(X)) mark(0()) -> 0() mark(nil()) -> nil() a__from(X) -> from(X) a__first(X1,X2) -> first(X1,X2) a__sel(X1,X2) -> sel(X1,X2) Qed