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