YES We show the termination of the TRS R: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) a____(X,nil()) -> mark(X) a____(nil(),X) -> mark(X) a__and(tt(),X) -> mark(X) a__isList(V) -> a__isNeList(V) a__isList(nil()) -> tt() a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) a__isNeList(V) -> a__isQid(V) a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) a__isNePal(V) -> a__isQid(V) a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) a__isPal(V) -> a__isNePal(V) a__isPal(nil()) -> tt() a__isQid(a()) -> tt() a__isQid(e()) -> tt() a__isQid(i()) -> tt() a__isQid(o()) -> tt() a__isQid(u()) -> tt() mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) mark(and(X1,X2)) -> a__and(mark(X1),X2) mark(isList(X)) -> a__isList(X) mark(isNeList(X)) -> a__isNeList(X) mark(isQid(X)) -> a__isQid(X) mark(isNePal(X)) -> a__isNePal(X) mark(isPal(X)) -> a__isPal(X) mark(nil()) -> nil() mark(tt()) -> tt() mark(a()) -> a() mark(e()) -> e() mark(i()) -> i() mark(o()) -> o() mark(u()) -> u() a____(X1,X2) -> __(X1,X2) a__and(X1,X2) -> and(X1,X2) a__isList(X) -> isList(X) a__isNeList(X) -> isNeList(X) a__isQid(X) -> isQid(X) a__isNePal(X) -> isNePal(X) a__isPal(X) -> isPal(X) -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> mark#(X) p3: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p4: a____#(__(X,Y),Z) -> mark#(Y) p5: a____#(__(X,Y),Z) -> mark#(Z) p6: a____#(X,nil()) -> mark#(X) p7: a____#(nil(),X) -> mark#(X) p8: a__and#(tt(),X) -> mark#(X) p9: a__isList#(V) -> a__isNeList#(V) p10: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p11: a__isList#(__(V1,V2)) -> a__isList#(V1) p12: a__isNeList#(V) -> a__isQid#(V) p13: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p14: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p15: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p16: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p17: a__isNePal#(V) -> a__isQid#(V) p18: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p19: a__isNePal#(__(I,__(P,I))) -> a__isQid#(I) p20: a__isPal#(V) -> a__isNePal#(V) p21: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p22: mark#(__(X1,X2)) -> mark#(X1) p23: mark#(__(X1,X2)) -> mark#(X2) p24: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p25: mark#(and(X1,X2)) -> mark#(X1) p26: mark#(isList(X)) -> a__isList#(X) p27: mark#(isNeList(X)) -> a__isNeList#(X) p28: mark#(isQid(X)) -> a__isQid#(X) p29: mark#(isNePal(X)) -> a__isNePal#(X) p30: mark#(isPal(X)) -> a__isPal#(X) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p13, p14, p15, p16, p18, p20, p21, p22, p23, p24, p25, p26, p27, p29, p30} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(nil(),X) -> mark#(X) p3: mark#(isPal(X)) -> a__isPal#(X) p4: a__isPal#(V) -> a__isNePal#(V) p5: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p6: a__and#(tt(),X) -> mark#(X) p7: mark#(isNePal(X)) -> a__isNePal#(X) p8: mark#(isNeList(X)) -> a__isNeList#(X) p9: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p10: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p11: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p12: a__isList#(__(V1,V2)) -> a__isList#(V1) p13: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p14: a__isList#(V) -> a__isNeList#(V) p15: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p16: mark#(isList(X)) -> a__isList#(X) p17: mark#(and(X1,X2)) -> mark#(X1) p18: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p19: mark#(__(X1,X2)) -> mark#(X2) p20: mark#(__(X1,X2)) -> mark#(X1) p21: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p22: a____#(X,nil()) -> mark#(X) p23: a____#(__(X,Y),Z) -> mark#(Z) p24: a____#(__(X,Y),Z) -> mark#(Y) p25: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p26: a____#(__(X,Y),Z) -> mark#(X) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + x2 + 5 ___A(x1,x2) = x1 + x2 + 2 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 2 nil_A() = 4 mark#_A(x1) = x1 + 3 isPal_A(x1) = x1 + 1 a__isPal#_A(x1) = x1 + 4 a__isNePal#_A(x1) = x1 + 4 a__and#_A(x1,x2) = x1 + x2 + 2 a__isQid_A(x1) = x1 tt_A() = 2 isNePal_A(x1) = x1 + 1 isNeList_A(x1) = x1 a__isNeList#_A(x1) = x1 a__isNeList_A(x1) = x1 isList_A(x1) = x1 a__isList#_A(x1) = x1 a__isList_A(x1) = x1 and_A(x1,x2) = x1 + x2 a__and_A(x1,x2) = x1 + x2 a__isNePal_A(x1) = x1 + 1 a__isPal_A(x1) = x1 + 1 a_A() = 3 e_A() = 3 i_A() = 3 o_A() = 3 u_A() = 3 isQid_A(x1) = x1 precedence: a____# = mark# = a__isNeList# = a__isList# > nil > a__isPal# = a__isNePal# > isPal = a__and# = isNePal = a__isNePal = a__isPal > and = a__and > __ = mark = a____ = a = e = i = u > a__isQid = tt = isNeList = a__isNeList = isList = a__isList = o = isQid partial status: pi(a____#) = [] pi(__) = [] pi(mark) = [1] pi(a____) = [1, 2] pi(nil) = [] pi(mark#) = [] pi(isPal) = [1] pi(a__isPal#) = [1] pi(a__isNePal#) = [1] pi(a__and#) = [1, 2] pi(a__isQid) = [] pi(tt) = [] pi(isNePal) = [] pi(isNeList) = [] pi(a__isNeList#) = [] pi(a__isNeList) = [] pi(isList) = [1] pi(a__isList#) = [] pi(a__isList) = [1] pi(and) = [] pi(a__and) = [] pi(a__isNePal) = [] pi(a__isPal) = [1] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: mark#(isPal(X)) -> a__isPal#(X) p3: a__isPal#(V) -> a__isNePal#(V) p4: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p5: a__and#(tt(),X) -> mark#(X) p6: mark#(isNePal(X)) -> a__isNePal#(X) p7: mark#(isNeList(X)) -> a__isNeList#(X) p8: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p9: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p10: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p11: a__isList#(__(V1,V2)) -> a__isList#(V1) p12: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p13: a__isList#(V) -> a__isNeList#(V) p14: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p15: mark#(isList(X)) -> a__isList#(X) p16: mark#(and(X1,X2)) -> mark#(X1) p17: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p18: mark#(__(X1,X2)) -> mark#(X2) p19: mark#(__(X1,X2)) -> mark#(X1) p20: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p21: a____#(X,nil()) -> mark#(X) p22: a____#(__(X,Y),Z) -> mark#(Z) p23: a____#(__(X,Y),Z) -> mark#(Y) p24: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p25: a____#(__(X,Y),Z) -> mark#(X) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20, p21, p22, p23, p24, p25} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> mark#(X) p3: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p4: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p5: a____#(__(X,Y),Z) -> mark#(Y) p6: mark#(__(X1,X2)) -> mark#(X1) p7: mark#(__(X1,X2)) -> mark#(X2) p8: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p9: a__and#(tt(),X) -> mark#(X) p10: mark#(and(X1,X2)) -> mark#(X1) p11: mark#(isList(X)) -> a__isList#(X) p12: a__isList#(V) -> a__isNeList#(V) p13: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p14: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p15: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p16: a__isList#(__(V1,V2)) -> a__isList#(V1) p17: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p18: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p19: mark#(isNeList(X)) -> a__isNeList#(X) p20: mark#(isNePal(X)) -> a__isNePal#(X) p21: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p22: mark#(isPal(X)) -> a__isPal#(X) p23: a__isPal#(V) -> a__isNePal#(V) p24: a____#(__(X,Y),Z) -> mark#(Z) p25: a____#(X,nil()) -> mark#(X) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + x2 + 9 ___A(x1,x2) = x1 + x2 + 9 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 9 mark#_A(x1) = x1 and_A(x1,x2) = x1 + x2 + 2 a__and#_A(x1,x2) = x2 + 1 tt_A() = 1 isList_A(x1) = x1 + 3 a__isList#_A(x1) = x1 + 1 a__isNeList#_A(x1) = x1 a__isList_A(x1) = x1 + 3 isNeList_A(x1) = x1 + 2 a__isNeList_A(x1) = x1 + 2 isNePal_A(x1) = x1 + 1 a__isNePal#_A(x1) = x1 a__isQid_A(x1) = x1 + 1 isPal_A(x1) = x1 + 2 a__isPal#_A(x1) = x1 + 1 nil_A() = 2 a__and_A(x1,x2) = x1 + x2 + 2 a__isNePal_A(x1) = x1 + 1 a__isPal_A(x1) = x1 + 2 a_A() = 2 e_A() = 2 i_A() = 2 o_A() = 2 u_A() = 2 isQid_A(x1) = x1 + 1 precedence: isList = a__isList = isNeList = a__isNeList > __ = a____ = and = a__isPal# = nil = a__and > mark > a____# = a__and# = tt = a__isList# = a__isNeList# = isNePal = a__isQid = isPal = a__isNePal = a__isPal = a = e = i = o = u = isQid > mark# = a__isNePal# partial status: pi(a____#) = [] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(mark#) = [1] pi(and) = [] pi(a__and#) = [2] pi(tt) = [] pi(isList) = [] pi(a__isList#) = [1] pi(a__isNeList#) = [1] pi(a__isList) = [] pi(isNeList) = [] pi(a__isNeList) = [] pi(isNePal) = [] pi(a__isNePal#) = [1] pi(a__isQid) = [] pi(isPal) = [] pi(a__isPal#) = [1] pi(nil) = [] pi(a__and) = [] pi(a__isNePal) = [] pi(a__isPal) = [1] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p3: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p4: a____#(__(X,Y),Z) -> mark#(Y) p5: mark#(__(X1,X2)) -> mark#(X1) p6: mark#(__(X1,X2)) -> mark#(X2) p7: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p8: a__and#(tt(),X) -> mark#(X) p9: mark#(and(X1,X2)) -> mark#(X1) p10: mark#(isList(X)) -> a__isList#(X) p11: a__isList#(V) -> a__isNeList#(V) p12: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p13: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p14: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p15: a__isList#(__(V1,V2)) -> a__isList#(V1) p16: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p17: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p18: mark#(isNeList(X)) -> a__isNeList#(X) p19: mark#(isNePal(X)) -> a__isNePal#(X) p20: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p21: mark#(isPal(X)) -> a__isPal#(X) p22: a__isPal#(V) -> a__isNePal#(V) p23: a____#(__(X,Y),Z) -> mark#(Z) p24: a____#(X,nil()) -> mark#(X) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20, p21, p22, p23, p24} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(X,nil()) -> mark#(X) p3: mark#(isPal(X)) -> a__isPal#(X) p4: a__isPal#(V) -> a__isNePal#(V) p5: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p6: a__and#(tt(),X) -> mark#(X) p7: mark#(isNePal(X)) -> a__isNePal#(X) p8: mark#(isNeList(X)) -> a__isNeList#(X) p9: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p10: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p11: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p12: a__isList#(__(V1,V2)) -> a__isList#(V1) p13: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p14: a__isList#(V) -> a__isNeList#(V) p15: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p16: mark#(isList(X)) -> a__isList#(X) p17: mark#(and(X1,X2)) -> mark#(X1) p18: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p19: mark#(__(X1,X2)) -> mark#(X2) p20: mark#(__(X1,X2)) -> mark#(X1) p21: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p22: a____#(__(X,Y),Z) -> mark#(Z) p23: a____#(__(X,Y),Z) -> mark#(Y) p24: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + x2 + 2 ___A(x1,x2) = x1 + x2 + 13 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 13 nil_A() = 2 mark#_A(x1) = x1 + 3 isPal_A(x1) = x1 + 12 a__isPal#_A(x1) = x1 + 1 a__isNePal#_A(x1) = x1 a__and#_A(x1,x2) = x1 + x2 + 3 a__isQid_A(x1) = 2 tt_A() = 1 isNePal_A(x1) = x1 + 11 isNeList_A(x1) = x1 + 3 a__isNeList#_A(x1) = x1 a__isNeList_A(x1) = x1 + 3 isList_A(x1) = x1 + 4 a__isList#_A(x1) = x1 + 1 a__isList_A(x1) = x1 + 4 and_A(x1,x2) = x1 + x2 + 4 a__and_A(x1,x2) = x1 + x2 + 4 a__isNePal_A(x1) = x1 + 11 a__isPal_A(x1) = x1 + 12 a_A() = 2 e_A() = 2 i_A() = 2 o_A() = 2 u_A() = 2 isQid_A(x1) = 2 precedence: a__isNeList# = isList = a__isList# = a__isList > mark = a____ = and = a__and > isPal = a__isQid = a__isNePal = a__isPal = a = e = i = o = u > a__isNeList = isQid > isNePal = isNeList > a____# > nil = mark# = a__isPal# = a__isNePal# = a__and# = tt > __ partial status: pi(a____#) = [1] pi(__) = [2] pi(mark) = [1] pi(a____) = [] pi(nil) = [] pi(mark#) = [1] pi(isPal) = [] pi(a__isPal#) = [1] pi(a__isNePal#) = [1] pi(a__and#) = [2] pi(a__isQid) = [] pi(tt) = [] pi(isNePal) = [1] pi(isNeList) = [] pi(a__isNeList#) = [1] pi(a__isNeList) = [] pi(isList) = [1] pi(a__isList#) = [] pi(a__isList) = [1] pi(and) = [2] pi(a__and) = [2] pi(a__isNePal) = [] pi(a__isPal) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: mark#(isPal(X)) -> a__isPal#(X) p3: a__isPal#(V) -> a__isNePal#(V) p4: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p5: a__and#(tt(),X) -> mark#(X) p6: mark#(isNePal(X)) -> a__isNePal#(X) p7: mark#(isNeList(X)) -> a__isNeList#(X) p8: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p9: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p10: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p11: a__isList#(__(V1,V2)) -> a__isList#(V1) p12: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p13: a__isList#(V) -> a__isNeList#(V) p14: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p15: mark#(isList(X)) -> a__isList#(X) p16: mark#(and(X1,X2)) -> mark#(X1) p17: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p18: mark#(__(X1,X2)) -> mark#(X2) p19: mark#(__(X1,X2)) -> mark#(X1) p20: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p21: a____#(__(X,Y),Z) -> mark#(Z) p22: a____#(__(X,Y),Z) -> mark#(Y) p23: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20, p21, p22, p23} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p5: a____#(__(X,Y),Z) -> mark#(Z) p6: mark#(__(X1,X2)) -> mark#(X1) p7: mark#(__(X1,X2)) -> mark#(X2) p8: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p9: a__and#(tt(),X) -> mark#(X) p10: mark#(and(X1,X2)) -> mark#(X1) p11: mark#(isList(X)) -> a__isList#(X) p12: a__isList#(V) -> a__isNeList#(V) p13: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p14: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p15: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p16: a__isList#(__(V1,V2)) -> a__isList#(V1) p17: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p18: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p19: mark#(isNeList(X)) -> a__isNeList#(X) p20: mark#(isNePal(X)) -> a__isNePal#(X) p21: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p22: mark#(isPal(X)) -> a__isPal#(X) p23: a__isPal#(V) -> a__isNePal#(V) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + x2 + 1 ___A(x1,x2) = x1 + x2 + 9 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 9 mark#_A(x1) = x1 and_A(x1,x2) = x1 + x2 a__and#_A(x1,x2) = x2 tt_A() = 2 isList_A(x1) = x1 + 4 a__isList#_A(x1) = x1 + 1 a__isNeList#_A(x1) = x1 a__isList_A(x1) = x1 + 4 isNeList_A(x1) = x1 + 3 a__isNeList_A(x1) = x1 + 3 isNePal_A(x1) = x1 + 3 a__isNePal#_A(x1) = x1 a__isQid_A(x1) = x1 + 2 isPal_A(x1) = x1 + 6 a__isPal#_A(x1) = x1 + 5 a__and_A(x1,x2) = x1 + x2 a__isNePal_A(x1) = x1 + 3 a__isPal_A(x1) = x1 + 6 nil_A() = 3 a_A() = 3 e_A() = 1 i_A() = 1 o_A() = 1 u_A() = 1 isQid_A(x1) = x1 + 2 precedence: e = o > u > nil > __ = a____ = isPal = a__isPal = a > mark = and = a__and = a__isNePal > isNePal > a____# = mark# = a__and# = a__isList# = a__isNeList# = a__isNePal# = a__isPal# > isNeList = a__isNeList = a__isQid > tt = isList = a__isList > i = isQid partial status: pi(a____#) = [1] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(mark#) = [1] pi(and) = [1, 2] pi(a__and#) = [2] pi(tt) = [] pi(isList) = [1] pi(a__isList#) = [1] pi(a__isNeList#) = [1] pi(a__isList) = [1] pi(isNeList) = [1] pi(a__isNeList) = [1] pi(isNePal) = [1] pi(a__isNePal#) = [1] pi(a__isQid) = [1] pi(isPal) = [1] pi(a__isPal#) = [1] pi(a__and) = [1, 2] pi(a__isNePal) = [1] pi(a__isPal) = [1] pi(nil) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [1] The next rules are strictly ordered: p22 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p5: a____#(__(X,Y),Z) -> mark#(Z) p6: mark#(__(X1,X2)) -> mark#(X1) p7: mark#(__(X1,X2)) -> mark#(X2) p8: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p9: a__and#(tt(),X) -> mark#(X) p10: mark#(and(X1,X2)) -> mark#(X1) p11: mark#(isList(X)) -> a__isList#(X) p12: a__isList#(V) -> a__isNeList#(V) p13: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p14: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p15: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p16: a__isList#(__(V1,V2)) -> a__isList#(V1) p17: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p18: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p19: mark#(isNeList(X)) -> a__isNeList#(X) p20: mark#(isNePal(X)) -> a__isNePal#(X) p21: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p22: a__isPal#(V) -> a__isNePal#(V) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20, p21} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> mark#(Z) p3: mark#(isNePal(X)) -> a__isNePal#(X) p4: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p5: a__and#(tt(),X) -> mark#(X) p6: mark#(isNeList(X)) -> a__isNeList#(X) p7: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p8: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p9: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p10: a__isList#(__(V1,V2)) -> a__isList#(V1) p11: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p12: a__isList#(V) -> a__isNeList#(V) p13: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p14: mark#(isList(X)) -> a__isList#(X) p15: mark#(and(X1,X2)) -> mark#(X1) p16: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p17: mark#(__(X1,X2)) -> mark#(X2) p18: mark#(__(X1,X2)) -> mark#(X1) p19: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p20: a____#(__(X,Y),Z) -> mark#(Y) p21: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + x2 + 1 ___A(x1,x2) = x1 + x2 + 9 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 9 mark#_A(x1) = x1 isNePal_A(x1) = x1 a__isNePal#_A(x1) = x1 a__and#_A(x1,x2) = x2 + 1 a__isQid_A(x1) = 0 isPal_A(x1) = x1 + 1 tt_A() = 0 isNeList_A(x1) = x1 + 1 a__isNeList#_A(x1) = x1 + 1 a__isNeList_A(x1) = x1 + 1 isList_A(x1) = x1 + 3 a__isList#_A(x1) = x1 + 2 a__isList_A(x1) = x1 + 3 and_A(x1,x2) = x1 + x2 + 2 a__and_A(x1,x2) = x1 + x2 + 2 a__isNePal_A(x1) = x1 a__isPal_A(x1) = x1 + 1 nil_A() = 1 a_A() = 1 e_A() = 1 i_A() = 1 o_A() = 1 u_A() = 1 isQid_A(x1) = 0 precedence: isNeList = a__isNeList > __ = a____ > a____# = mark = mark# = isNePal = a__isQid = tt = a__isNeList# = isList = a__isList# = a__isList = a__isNePal = a__isPal = nil > and = a__and > a__isNePal# = a__and# = a > isPal = e > i = o = u = isQid partial status: pi(a____#) = [1] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(mark#) = [] pi(isNePal) = [] pi(a__isNePal#) = [] pi(a__and#) = [] pi(a__isQid) = [] pi(isPal) = [] pi(tt) = [] pi(isNeList) = [1] pi(a__isNeList#) = [] pi(a__isNeList) = [1] pi(isList) = [] pi(a__isList#) = [] pi(a__isList) = [1] pi(and) = [] pi(a__and) = [1, 2] pi(a__isNePal) = [] pi(a__isPal) = [] pi(nil) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: mark#(isNePal(X)) -> a__isNePal#(X) p3: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p4: a__and#(tt(),X) -> mark#(X) p5: mark#(isNeList(X)) -> a__isNeList#(X) p6: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p7: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p8: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p9: a__isList#(__(V1,V2)) -> a__isList#(V1) p10: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p11: a__isList#(V) -> a__isNeList#(V) p12: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p13: mark#(isList(X)) -> a__isList#(X) p14: mark#(and(X1,X2)) -> mark#(X1) p15: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p16: mark#(__(X1,X2)) -> mark#(X2) p17: mark#(__(X1,X2)) -> mark#(X1) p18: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p19: a____#(__(X,Y),Z) -> mark#(Y) p20: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19, p20} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p5: mark#(__(X1,X2)) -> mark#(X1) p6: mark#(__(X1,X2)) -> mark#(X2) p7: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p8: a__and#(tt(),X) -> mark#(X) p9: mark#(and(X1,X2)) -> mark#(X1) p10: mark#(isList(X)) -> a__isList#(X) p11: a__isList#(V) -> a__isNeList#(V) p12: a__isNeList#(__(V1,V2)) -> a__and#(a__isList(V1),isNeList(V2)) p13: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p14: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p15: a__isList#(__(V1,V2)) -> a__isList#(V1) p16: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p17: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p18: mark#(isNeList(X)) -> a__isNeList#(X) p19: mark#(isNePal(X)) -> a__isNePal#(X) p20: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + 1 ___A(x1,x2) = x1 + x2 + 12 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 12 mark#_A(x1) = x1 + 1 and_A(x1,x2) = x1 + x2 + 5 a__and#_A(x1,x2) = x2 + 2 tt_A() = 0 isList_A(x1) = x1 + 3 a__isList#_A(x1) = x1 + 2 a__isNeList#_A(x1) = x1 + 1 a__isList_A(x1) = x1 + 3 isNeList_A(x1) = x1 + 2 a__isNeList_A(x1) = x1 + 2 isNePal_A(x1) = x1 + 2 a__isNePal#_A(x1) = x1 + 1 a__isQid_A(x1) = 0 isPal_A(x1) = x1 + 21 a__and_A(x1,x2) = x1 + x2 + 5 a__isNePal_A(x1) = x1 + 2 a__isPal_A(x1) = x1 + 21 nil_A() = 0 a_A() = 0 e_A() = 0 i_A() = 0 o_A() = 1 u_A() = 1 isQid_A(x1) = 0 precedence: i > isList = a__isList# = a__isList = isNeList = a__isNeList = isPal = a__isPal > u > a____# = mark# = a__and# = a__isNeList# = a__isNePal# > __ = a____ > mark = and = tt = isNePal = a__isQid = a__and = a__isNePal = nil = a = e = o = isQid partial status: pi(a____#) = [1] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(mark#) = [1] pi(and) = [2] pi(a__and#) = [2] pi(tt) = [] pi(isList) = [1] pi(a__isList#) = [1] pi(a__isNeList#) = [1] pi(a__isList) = [1] pi(isNeList) = [] pi(a__isNeList) = [] pi(isNePal) = [1] pi(a__isNePal#) = [1] pi(a__isQid) = [] pi(isPal) = [] pi(a__and) = [2] pi(a__isNePal) = [1] pi(a__isPal) = [] pi(nil) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] The next rules are strictly ordered: p12 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p5: mark#(__(X1,X2)) -> mark#(X1) p6: mark#(__(X1,X2)) -> mark#(X2) p7: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p8: a__and#(tt(),X) -> mark#(X) p9: mark#(and(X1,X2)) -> mark#(X1) p10: mark#(isList(X)) -> a__isList#(X) p11: a__isList#(V) -> a__isNeList#(V) p12: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p13: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p14: a__isList#(__(V1,V2)) -> a__isList#(V1) p15: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p16: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p17: mark#(isNeList(X)) -> a__isNeList#(X) p18: mark#(isNePal(X)) -> a__isNePal#(X) p19: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p19} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> mark#(Y) p3: mark#(isNePal(X)) -> a__isNePal#(X) p4: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p5: a__and#(tt(),X) -> mark#(X) p6: mark#(isNeList(X)) -> a__isNeList#(X) p7: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p8: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p9: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p10: a__isList#(__(V1,V2)) -> a__isList#(V1) p11: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p12: a__isList#(V) -> a__isNeList#(V) p13: mark#(isList(X)) -> a__isList#(X) p14: mark#(and(X1,X2)) -> mark#(X1) p15: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p16: mark#(__(X1,X2)) -> mark#(X2) p17: mark#(__(X1,X2)) -> mark#(X1) p18: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p19: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + 1 ___A(x1,x2) = x1 + x2 + 7 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 7 mark#_A(x1) = x1 + 3 isNePal_A(x1) = x1 + 1 a__isNePal#_A(x1) = x1 + 2 a__and#_A(x1,x2) = x2 + 4 a__isQid_A(x1) = x1 isPal_A(x1) = x1 + 5 tt_A() = 4 isNeList_A(x1) = x1 a__isNeList#_A(x1) = x1 a__isNeList_A(x1) = x1 isList_A(x1) = x1 + 2 a__isList#_A(x1) = x1 + 1 a__isList_A(x1) = x1 + 2 and_A(x1,x2) = x1 + x2 + 2 a__and_A(x1,x2) = x1 + x2 + 2 a__isNePal_A(x1) = x1 + 1 a__isPal_A(x1) = x1 + 5 nil_A() = 3 a_A() = 5 e_A() = 5 i_A() = 5 o_A() = 5 u_A() = 5 isQid_A(x1) = x1 precedence: a__isList# > a__isNeList# > a____# = __ = a____ = mark# = nil > a__isNePal# = a__and# > mark = isList = a__isList = and = a__and = a__isNePal > a__isNeList > a__isQid = tt > isNeList = a__isPal > isNePal = a = e = i = o = u = isQid > isPal partial status: pi(a____#) = [] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(mark#) = [] pi(isNePal) = [] pi(a__isNePal#) = [1] pi(a__and#) = [] pi(a__isQid) = [] pi(isPal) = [] pi(tt) = [] pi(isNeList) = [1] pi(a__isNeList#) = [1] pi(a__isNeList) = [1] pi(isList) = [1] pi(a__isList#) = [1] pi(a__isList) = [1] pi(and) = [] pi(a__and) = [] pi(a__isNePal) = [1] pi(a__isPal) = [] pi(nil) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] The next rules are strictly ordered: p5 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> mark#(Y) p3: mark#(isNePal(X)) -> a__isNePal#(X) p4: a__isNePal#(__(I,__(P,I))) -> a__and#(a__isQid(I),isPal(P)) p5: mark#(isNeList(X)) -> a__isNeList#(X) p6: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p7: a__isNeList#(__(V1,V2)) -> a__and#(a__isNeList(V1),isList(V2)) p8: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p9: a__isList#(__(V1,V2)) -> a__isList#(V1) p10: a__isList#(__(V1,V2)) -> a__and#(a__isList(V1),isList(V2)) p11: a__isList#(V) -> a__isNeList#(V) p12: mark#(isList(X)) -> a__isList#(X) p13: mark#(and(X1,X2)) -> mark#(X1) p14: mark#(and(X1,X2)) -> a__and#(mark(X1),X2) p15: mark#(__(X1,X2)) -> mark#(X2) p16: mark#(__(X1,X2)) -> mark#(X1) p17: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p18: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2, p13, p15, p16, p17, p18} {p6, p8, p9, p11} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> a____#(mark(X1),mark(X2)) p5: mark#(__(X1,X2)) -> mark#(X1) p6: mark#(__(X1,X2)) -> mark#(X2) p7: mark#(and(X1,X2)) -> mark#(X1) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 ___A(x1,x2) = x1 + x2 + 13 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 13 mark#_A(x1) = x1 + 1 and_A(x1,x2) = x1 + x2 + 2 a__and_A(x1,x2) = x1 + x2 + 2 tt_A() = 2 a__isList_A(x1) = x1 + 5 a__isNeList_A(x1) = x1 + 4 nil_A() = 3 isList_A(x1) = x1 + 5 a__isQid_A(x1) = 3 isNeList_A(x1) = x1 + 4 a__isNePal_A(x1) = x1 + 4 isPal_A(x1) = x1 + 7 a__isPal_A(x1) = x1 + 7 a_A() = 1 e_A() = 1 i_A() = 1 o_A() = 1 u_A() = 1 isQid_A(x1) = 3 isNePal_A(x1) = x1 + 4 precedence: mark# > a____# = a__isList = a__isNeList = isList = isNeList > a__isQid = a = e = i = isQid > mark = a____ = tt > nil = o > a__isPal > isPal > __ = and = a__and = a__isNePal > u > isNePal partial status: pi(a____#) = [1] pi(__) = [1] pi(mark) = [1] pi(a____) = [] pi(mark#) = [1] pi(and) = [] pi(a__and) = [] pi(tt) = [] pi(a__isList) = [] pi(a__isNeList) = [] pi(nil) = [] pi(isList) = [] pi(a__isQid) = [] pi(isNeList) = [] pi(a__isNePal) = [] pi(isPal) = [] pi(a__isPal) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(isQid) = [] pi(isNePal) = [1] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) p3: a____#(__(X,Y),Z) -> mark#(Y) p4: mark#(__(X1,X2)) -> mark#(X1) p5: mark#(__(X1,X2)) -> mark#(X2) p6: mark#(and(X1,X2)) -> mark#(X1) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1, p2} {p4, p5, p6} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) p2: a____#(__(X,Y),Z) -> a____#(mark(Y),mark(Z)) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 + 1 ___A(x1,x2) = x1 + x2 + 6 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 6 a__and_A(x1,x2) = x2 + 1 tt_A() = 2 a__isList_A(x1) = x1 + 4 a__isNeList_A(x1) = x1 + 3 nil_A() = 3 isList_A(x1) = x1 + 4 a__isQid_A(x1) = x1 + 2 isNeList_A(x1) = x1 + 3 a__isNePal_A(x1) = x1 + 3 isPal_A(x1) = x1 + 4 a__isPal_A(x1) = x1 + 4 a_A() = 3 e_A() = 3 i_A() = 1 o_A() = 3 u_A() = 3 and_A(x1,x2) = x2 + 1 isQid_A(x1) = x1 + 2 isNePal_A(x1) = x1 + 3 precedence: __ = a____ > a____# = mark = tt = a__isList > a__and > a__isNePal > isList = a__isQid > a__isPal = a > isPal = e = i = o = isQid > a__isNeList = isNeList = and = isNePal > nil > u partial status: pi(a____#) = [1] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(a__and) = [2] pi(tt) = [] pi(a__isList) = [] pi(a__isNeList) = [1] pi(nil) = [] pi(isList) = [] pi(a__isQid) = [1] pi(isNeList) = [1] pi(a__isNePal) = [1] pi(isPal) = [] pi(a__isPal) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(and) = [2] pi(isQid) = [] pi(isNePal) = [] 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: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a____#(__(X,Y),Z) -> a____#(mark(X),a____(mark(Y),mark(Z))) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15, r16, r17, r18, r19, r20, r21, r22, r23, r24, r25, r26, r27, r28, r29, r30, r31, r32, r33, r34, r35, r36, r37, r38, r39, r40 Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a____#_A(x1,x2) = x1 ___A(x1,x2) = x1 + x2 + 5 mark_A(x1) = x1 a_____A(x1,x2) = x1 + x2 + 5 a__and_A(x1,x2) = x2 + 1 tt_A() = 1 a__isList_A(x1) = x1 + 3 a__isNeList_A(x1) = x1 + 2 nil_A() = 0 isList_A(x1) = x1 + 3 a__isQid_A(x1) = 1 isNeList_A(x1) = x1 + 2 a__isNePal_A(x1) = x1 + 2 isPal_A(x1) = x1 + 3 a__isPal_A(x1) = x1 + 3 a_A() = 2 e_A() = 2 i_A() = 2 o_A() = 2 u_A() = 2 and_A(x1,x2) = x2 + 1 isQid_A(x1) = 1 isNePal_A(x1) = x1 + 2 precedence: __ = a____ > a____# > isPal = a__isPal = a = e > a__and = o = and > mark = tt = a__isQid > a__isList = isList > a__isNeList > nil = isNeList > a__isNePal = i = u = isNePal > isQid partial status: pi(a____#) = [1] pi(__) = [] pi(mark) = [1] pi(a____) = [] pi(a__and) = [] pi(tt) = [] pi(a__isList) = [] pi(a__isNeList) = [1] pi(nil) = [] pi(isList) = [] pi(a__isQid) = [] pi(isNeList) = [] pi(a__isNePal) = [1] pi(isPal) = [] pi(a__isPal) = [] pi(a) = [] pi(e) = [] pi(i) = [] pi(o) = [] pi(u) = [] pi(and) = [] pi(isQid) = [] pi(isNePal) = [1] 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: mark#(__(X1,X2)) -> mark#(X1) p2: mark#(and(X1,X2)) -> mark#(X1) p3: mark#(__(X1,X2)) -> mark#(X2) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: mark#_A(x1) = x1 ___A(x1,x2) = x1 + x2 + 1 and_A(x1,x2) = x1 + x2 + 1 precedence: mark# = __ > and partial status: pi(mark#) = [1] pi(__) = [] pi(and) = [] The next rules are strictly ordered: p1 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: mark#(and(X1,X2)) -> mark#(X1) p2: mark#(__(X1,X2)) -> mark#(X2) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(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: mark#(and(X1,X2)) -> mark#(X1) p2: mark#(__(X1,X2)) -> mark#(X2) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: mark#_A(x1) = x1 and_A(x1,x2) = x1 + x2 + 1 ___A(x1,x2) = x1 + x2 + 1 precedence: mark# = __ > and partial status: pi(mark#) = [] pi(and) = [] pi(__) = [2] The next rules are strictly ordered: p1 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: mark#(__(X1,X2)) -> mark#(X2) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: mark#(__(X1,X2)) -> mark#(X2) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: mark#_A(x1) = x1 ___A(x1,x2) = x1 + x2 + 1 precedence: mark# = __ partial status: pi(mark#) = [] pi(__) = [2] 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: a__isNeList#(__(V1,V2)) -> a__isNeList#(V1) p2: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p3: a__isList#(V) -> a__isNeList#(V) p4: a__isList#(__(V1,V2)) -> a__isList#(V1) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the monotone reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a__isNeList#_A(x1) = x1 ___A(x1,x2) = x1 + x2 + 2 a__isList#_A(x1) = x1 + 1 precedence: a__isNeList# = __ = a__isList# partial status: pi(a__isNeList#) = [1] pi(__) = [1, 2] pi(a__isList#) = [1] The next rules are strictly ordered: p1 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p2: a__isList#(V) -> a__isNeList#(V) p3: a__isList#(__(V1,V2)) -> a__isList#(V1) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(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: a__isNeList#(__(V1,V2)) -> a__isList#(V1) p2: a__isList#(__(V1,V2)) -> a__isList#(V1) p3: a__isList#(V) -> a__isNeList#(V) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a__isNeList#_A(x1) = x1 ___A(x1,x2) = x1 + x2 + 2 a__isList#_A(x1) = x1 + 1 precedence: a__isNeList# = __ = a__isList# partial status: pi(a__isNeList#) = [1] pi(__) = [2] pi(a__isList#) = [1] The next rules are strictly ordered: p1 We remove them from the problem. -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: a__isList#(__(V1,V2)) -> a__isList#(V1) p2: a__isList#(V) -> a__isNeList#(V) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The estimated dependency graph contains the following SCCs: {p1} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: a__isList#(__(V1,V2)) -> a__isList#(V1) and R consists of: r1: a____(__(X,Y),Z) -> a____(mark(X),a____(mark(Y),mark(Z))) r2: a____(X,nil()) -> mark(X) r3: a____(nil(),X) -> mark(X) r4: a__and(tt(),X) -> mark(X) r5: a__isList(V) -> a__isNeList(V) r6: a__isList(nil()) -> tt() r7: a__isList(__(V1,V2)) -> a__and(a__isList(V1),isList(V2)) r8: a__isNeList(V) -> a__isQid(V) r9: a__isNeList(__(V1,V2)) -> a__and(a__isList(V1),isNeList(V2)) r10: a__isNeList(__(V1,V2)) -> a__and(a__isNeList(V1),isList(V2)) r11: a__isNePal(V) -> a__isQid(V) r12: a__isNePal(__(I,__(P,I))) -> a__and(a__isQid(I),isPal(P)) r13: a__isPal(V) -> a__isNePal(V) r14: a__isPal(nil()) -> tt() r15: a__isQid(a()) -> tt() r16: a__isQid(e()) -> tt() r17: a__isQid(i()) -> tt() r18: a__isQid(o()) -> tt() r19: a__isQid(u()) -> tt() r20: mark(__(X1,X2)) -> a____(mark(X1),mark(X2)) r21: mark(and(X1,X2)) -> a__and(mark(X1),X2) r22: mark(isList(X)) -> a__isList(X) r23: mark(isNeList(X)) -> a__isNeList(X) r24: mark(isQid(X)) -> a__isQid(X) r25: mark(isNePal(X)) -> a__isNePal(X) r26: mark(isPal(X)) -> a__isPal(X) r27: mark(nil()) -> nil() r28: mark(tt()) -> tt() r29: mark(a()) -> a() r30: mark(e()) -> e() r31: mark(i()) -> i() r32: mark(o()) -> o() r33: mark(u()) -> u() r34: a____(X1,X2) -> __(X1,X2) r35: a__and(X1,X2) -> and(X1,X2) r36: a__isList(X) -> isList(X) r37: a__isNeList(X) -> isNeList(X) r38: a__isQid(X) -> isQid(X) r39: a__isNePal(X) -> isNePal(X) r40: a__isPal(X) -> isPal(X) The set of usable rules consists of (no rules) Take the reduction pair: weighted path order base order: matrix interpretations: carrier: N^1 order: lexicographic order interpretations: a__isList#_A(x1) = x1 ___A(x1,x2) = x1 + x2 + 1 precedence: a__isList# = __ partial status: pi(a__isList#) = [] pi(__) = [2] The next rules are strictly ordered: p1 We remove them from the problem. Then no dependency pair remains.