YES We show the termination of the TRS R: from(X) -> cons(X,n__from(n__s(X))) head(cons(X,XS)) -> X |2nd|(cons(X,XS)) -> head(activate(XS)) take(|0|(),XS) -> nil() take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) sel(|0|(),cons(X,XS)) -> X sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) from(X) -> n__from(X) s(X) -> n__s(X) take(X1,X2) -> n__take(X1,X2) activate(n__from(X)) -> from(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) activate(X) -> X -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: |2nd|#(cons(X,XS)) -> head#(activate(XS)) p2: |2nd|#(cons(X,XS)) -> activate#(XS) p3: take#(s(N),cons(X,XS)) -> activate#(XS) p4: sel#(s(N),cons(X,XS)) -> sel#(N,activate(XS)) p5: sel#(s(N),cons(X,XS)) -> activate#(XS) p6: activate#(n__from(X)) -> from#(activate(X)) p7: activate#(n__from(X)) -> activate#(X) p8: activate#(n__s(X)) -> s#(activate(X)) p9: activate#(n__s(X)) -> activate#(X) p10: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p11: activate#(n__take(X1,X2)) -> activate#(X1) p12: activate#(n__take(X1,X2)) -> activate#(X2) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: {p4} {p3, p7, p9, p10, p11, p12} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: sel#(s(N),cons(X,XS)) -> sel#(N,activate(XS)) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: sel#_A(x1,x2) = x1 + (0,1) s_A(x1) = x1 + (0,2) cons_A(x1,x2) = (1,0) activate_A(x1) = x1 + (7,5) from_A(x1) = ((0,0),(0,1)) x1 + (7,1) n__from_A(x1) = ((0,0),(0,1)) x1 + (1,1) n__s_A(x1) = x1 + (0,2) take_A(x1,x2) = ((0,1),(0,0)) x1 + (3,4) |0|_A() = (2,1) nil_A() = (1,1) n__take_A(x1,x2) = ((0,1),(0,0)) x1 + (2,3) precedence: cons > take > activate = from > s = n__s > sel# = n__take > n__from > |0| > nil partial status: pi(sel#) = [1] pi(s) = [1] pi(cons) = [] pi(activate) = [1] pi(from) = [] pi(n__from) = [] pi(n__s) = [1] pi(take) = [] pi(|0|) = [] pi(nil) = [] pi(n__take) = [] The next rules are strictly ordered: p1 We remove them from the problem. Then no dependency pair remains. -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> activate#(X2) p3: activate#(n__take(X1,X2)) -> activate#(X1) p4: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p5: activate#(n__s(X)) -> activate#(X) p6: activate#(n__from(X)) -> activate#(X) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: take#_A(x1,x2) = ((1,0),(0,0)) x2 + (2,3) s_A(x1) = x1 + (0,1) cons_A(x1,x2) = ((1,0),(0,0)) x2 + (0,2) activate#_A(x1) = ((1,0),(0,0)) x1 + (1,3) n__take_A(x1,x2) = ((1,0),(0,0)) x1 + ((1,0),(0,0)) x2 + (2,3) activate_A(x1) = x1 + (0,4) n__s_A(x1) = x1 + (0,1) n__from_A(x1) = ((1,0),(0,0)) x1 + (2,3) from_A(x1) = ((1,0),(0,0)) x1 + (2,4) take_A(x1,x2) = ((1,0),(0,0)) x1 + ((1,0),(0,0)) x2 + (2,3) |0|_A() = (2,0) nil_A() = (1,0) precedence: take# = cons = activate# = n__take = activate = n__from = from = take = |0| = nil > s > n__s partial status: pi(take#) = [] pi(s) = [] pi(cons) = [] pi(activate#) = [] pi(n__take) = [] pi(activate) = [] pi(n__s) = [] pi(n__from) = [] pi(from) = [] pi(take) = [] pi(|0|) = [] pi(nil) = [] The next rules are strictly ordered: p2 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> activate#(X1) p3: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p4: activate#(n__s(X)) -> activate#(X) p5: activate#(n__from(X)) -> activate#(X) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__from(X)) -> activate#(X) p3: activate#(n__s(X)) -> activate#(X) p4: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p5: activate#(n__take(X1,X2)) -> activate#(X1) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: take#_A(x1,x2) = ((0,1),(0,0)) x1 + ((0,1),(0,0)) x2 + (5,2) s_A(x1) = ((0,1),(0,1)) x1 + (2,0) cons_A(x1,x2) = ((0,0),(0,1)) x2 + (3,0) activate#_A(x1) = ((0,1),(0,0)) x1 + (4,2) n__from_A(x1) = ((1,1),(0,1)) x1 + (5,2) n__s_A(x1) = ((0,0),(0,1)) x1 + (2,0) n__take_A(x1,x2) = x1 + ((0,1),(0,1)) x2 + (1,2) activate_A(x1) = ((1,1),(0,1)) x1 from_A(x1) = ((1,1),(0,1)) x1 + (6,2) take_A(x1,x2) = x1 + ((0,1),(0,1)) x2 + (2,2) |0|_A() = (1,1) nil_A() = (2,2) precedence: s = activate = take > |0| > nil > n__from = from > cons > take# = activate# = n__s = n__take partial status: pi(take#) = [] pi(s) = [] pi(cons) = [] pi(activate#) = [] pi(n__from) = [] pi(n__s) = [] pi(n__take) = [1] pi(activate) = [1] pi(from) = [] pi(take) = [] pi(|0|) = [] pi(nil) = [] The next rules are strictly ordered: p2 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__s(X)) -> activate#(X) p3: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p4: activate#(n__take(X1,X2)) -> activate#(X1) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> activate#(X1) p3: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p4: activate#(n__s(X)) -> activate#(X) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: take#_A(x1,x2) = ((1,0),(0,0)) x1 + ((1,0),(0,0)) x2 + (3,3) s_A(x1) = ((1,0),(1,1)) x1 + (1,3) cons_A(x1,x2) = ((1,0),(1,0)) x2 activate#_A(x1) = ((1,0),(0,0)) x1 + (3,3) n__take_A(x1,x2) = x1 + x2 + (4,4) activate_A(x1) = ((1,0),(1,1)) x1 n__s_A(x1) = ((1,0),(1,1)) x1 + (1,3) from_A(x1) = ((0,0),(1,0)) x1 + (2,2) n__from_A(x1) = ((0,0),(1,0)) x1 + (2,0) take_A(x1,x2) = x1 + x2 + (4,5) |0|_A() = (1,0) nil_A() = (2,1) precedence: |0| > cons = n__take = activate = from = take = nil > take# = activate# > s = n__s > n__from partial status: pi(take#) = [] pi(s) = [1] pi(cons) = [] pi(activate#) = [] pi(n__take) = [] pi(activate) = [1] pi(n__s) = [1] pi(from) = [] pi(n__from) = [] pi(take) = [] pi(|0|) = [] pi(nil) = [] The next rules are strictly ordered: p4 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> activate#(X1) p3: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: {p1, p2, p3} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) p3: activate#(n__take(X1,X2)) -> activate#(X1) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: take#_A(x1,x2) = ((0,1),(0,1)) x2 + (3,5) s_A(x1) = x1 + (6,2) cons_A(x1,x2) = ((0,0),(0,1)) x2 + (1,0) activate#_A(x1) = ((0,1),(0,1)) x1 + (2,5) n__take_A(x1,x2) = ((0,0),(0,1)) x1 + ((0,1),(0,1)) x2 + (4,4) activate_A(x1) = ((1,1),(0,1)) x1 + (5,0) from_A(x1) = (7,1) n__from_A(x1) = (7,1) n__s_A(x1) = x1 + (6,2) take_A(x1,x2) = ((0,0),(0,1)) x1 + ((0,1),(0,1)) x2 + (4,4) |0|_A() = (1,1) nil_A() = (0,0) precedence: take# = activate# > n__take = activate = take = |0| > s = cons = from = n__from = n__s = nil partial status: pi(take#) = [] pi(s) = [] pi(cons) = [] pi(activate#) = [] pi(n__take) = [] pi(activate) = [1] pi(from) = [] pi(n__from) = [] pi(n__s) = [] pi(take) = [] pi(|0|) = [] pi(nil) = [] The next rules are strictly ordered: p3 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: {p1, p2} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) p2: activate#(n__take(X1,X2)) -> take#(activate(X1),activate(X2)) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The set of usable rules consists of r1, r4, r5, r8, r9, r10, r11, r12, r13, r14 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^2 order: standard order interpretations: take#_A(x1,x2) = ((1,0),(0,0)) x2 + (1,2) s_A(x1) = ((1,0),(1,1)) x1 + (1,3) cons_A(x1,x2) = ((1,0),(0,0)) x2 + (0,2) activate#_A(x1) = ((1,0),(0,0)) x1 + (0,2) n__take_A(x1,x2) = ((1,0),(1,0)) x2 + (2,1) activate_A(x1) = ((1,0),(1,1)) x1 + (0,3) from_A(x1) = (2,3) n__from_A(x1) = (2,3) n__s_A(x1) = ((1,0),(1,1)) x1 + (1,3) take_A(x1,x2) = ((1,0),(1,0)) x2 + (2,3) |0|_A() = (1,0) nil_A() = (0,0) precedence: s = cons = activate# = activate = from = n__from = take > take# = n__take = n__s = |0| = nil partial status: pi(take#) = [] pi(s) = [] pi(cons) = [] pi(activate#) = [] pi(n__take) = [] pi(activate) = [1] pi(from) = [] pi(n__from) = [] pi(n__s) = [1] pi(take) = [] pi(|0|) = [] pi(nil) = [] The next rules are strictly ordered: p2 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: take#(s(N),cons(X,XS)) -> activate#(XS) and R consists of: r1: from(X) -> cons(X,n__from(n__s(X))) r2: head(cons(X,XS)) -> X r3: |2nd|(cons(X,XS)) -> head(activate(XS)) r4: take(|0|(),XS) -> nil() r5: take(s(N),cons(X,XS)) -> cons(X,n__take(N,activate(XS))) r6: sel(|0|(),cons(X,XS)) -> X r7: sel(s(N),cons(X,XS)) -> sel(N,activate(XS)) r8: from(X) -> n__from(X) r9: s(X) -> n__s(X) r10: take(X1,X2) -> n__take(X1,X2) r11: activate(n__from(X)) -> from(activate(X)) r12: activate(n__s(X)) -> s(activate(X)) r13: activate(n__take(X1,X2)) -> take(activate(X1),activate(X2)) r14: activate(X) -> X The estimated dependency graph contains the following SCCs: (no SCCs)