YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 1409 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 225 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 362 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 45 ms] (8) QTRS (9) RisEmptyProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a____(__(X, Y), Z) -> a____(mark(X), a____(mark(Y), mark(Z))) a____(X, nil) -> mark(X) a____(nil, X) -> mark(X) a__U11(tt, V) -> a__U12(a__isPalListKind(V), V) a__U12(tt, V) -> a__U13(a__isNeList(V)) a__U13(tt) -> tt a__U21(tt, V1, V2) -> a__U22(a__isPalListKind(V1), V1, V2) a__U22(tt, V1, V2) -> a__U23(a__isPalListKind(V2), V1, V2) a__U23(tt, V1, V2) -> a__U24(a__isPalListKind(V2), V1, V2) a__U24(tt, V1, V2) -> a__U25(a__isList(V1), V2) a__U25(tt, V2) -> a__U26(a__isList(V2)) a__U26(tt) -> tt a__U31(tt, V) -> a__U32(a__isPalListKind(V), V) a__U32(tt, V) -> a__U33(a__isQid(V)) a__U33(tt) -> tt a__U41(tt, V1, V2) -> a__U42(a__isPalListKind(V1), V1, V2) a__U42(tt, V1, V2) -> a__U43(a__isPalListKind(V2), V1, V2) a__U43(tt, V1, V2) -> a__U44(a__isPalListKind(V2), V1, V2) a__U44(tt, V1, V2) -> a__U45(a__isList(V1), V2) a__U45(tt, V2) -> a__U46(a__isNeList(V2)) a__U46(tt) -> tt a__U51(tt, V1, V2) -> a__U52(a__isPalListKind(V1), V1, V2) a__U52(tt, V1, V2) -> a__U53(a__isPalListKind(V2), V1, V2) a__U53(tt, V1, V2) -> a__U54(a__isPalListKind(V2), V1, V2) a__U54(tt, V1, V2) -> a__U55(a__isNeList(V1), V2) a__U55(tt, V2) -> a__U56(a__isList(V2)) a__U56(tt) -> tt a__U61(tt, V) -> a__U62(a__isPalListKind(V), V) a__U62(tt, V) -> a__U63(a__isQid(V)) a__U63(tt) -> tt a__U71(tt, I, P) -> a__U72(a__isPalListKind(I), P) a__U72(tt, P) -> a__U73(a__isPal(P), P) a__U73(tt, P) -> a__U74(a__isPalListKind(P)) a__U74(tt) -> tt a__U81(tt, V) -> a__U82(a__isPalListKind(V), V) a__U82(tt, V) -> a__U83(a__isNePal(V)) a__U83(tt) -> tt a__U91(tt, V2) -> a__U92(a__isPalListKind(V2)) a__U92(tt) -> tt a__isList(V) -> a__U11(a__isPalListKind(V), V) a__isList(nil) -> tt a__isList(__(V1, V2)) -> a__U21(a__isPalListKind(V1), V1, V2) a__isNeList(V) -> a__U31(a__isPalListKind(V), V) a__isNeList(__(V1, V2)) -> a__U41(a__isPalListKind(V1), V1, V2) a__isNeList(__(V1, V2)) -> a__U51(a__isPalListKind(V1), V1, V2) a__isNePal(V) -> a__U61(a__isPalListKind(V), V) a__isNePal(__(I, __(P, I))) -> a__U71(a__isQid(I), I, P) a__isPal(V) -> a__U81(a__isPalListKind(V), V) a__isPal(nil) -> tt a__isPalListKind(a) -> tt a__isPalListKind(e) -> tt a__isPalListKind(i) -> tt a__isPalListKind(nil) -> tt a__isPalListKind(o) -> tt a__isPalListKind(u) -> tt a__isPalListKind(__(V1, V2)) -> a__U91(a__isPalListKind(V1), V2) 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(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(U13(X)) -> a__U13(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) mark(U23(X1, X2, X3)) -> a__U23(mark(X1), X2, X3) mark(U24(X1, X2, X3)) -> a__U24(mark(X1), X2, X3) mark(U25(X1, X2)) -> a__U25(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U26(X)) -> a__U26(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X1, X2)) -> a__U32(mark(X1), X2) mark(U33(X)) -> a__U33(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2, X3)) -> a__U42(mark(X1), X2, X3) mark(U43(X1, X2, X3)) -> a__U43(mark(X1), X2, X3) mark(U44(X1, X2, X3)) -> a__U44(mark(X1), X2, X3) mark(U45(X1, X2)) -> a__U45(mark(X1), X2) mark(U46(X)) -> a__U46(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(U53(X1, X2, X3)) -> a__U53(mark(X1), X2, X3) mark(U54(X1, X2, X3)) -> a__U54(mark(X1), X2, X3) mark(U55(X1, X2)) -> a__U55(mark(X1), X2) mark(U56(X)) -> a__U56(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(U63(X)) -> a__U63(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U73(X1, X2)) -> a__U73(mark(X1), X2) mark(isPal(X)) -> a__isPal(X) mark(U74(X)) -> a__U74(mark(X)) mark(U81(X1, X2)) -> a__U81(mark(X1), X2) mark(U82(X1, X2)) -> a__U82(mark(X1), X2) mark(U83(X)) -> a__U83(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(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__U11(X1, X2) -> U11(X1, X2) a__U12(X1, X2) -> U12(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__U13(X) -> U13(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2, X3) -> U22(X1, X2, X3) a__U23(X1, X2, X3) -> U23(X1, X2, X3) a__U24(X1, X2, X3) -> U24(X1, X2, X3) a__U25(X1, X2) -> U25(X1, X2) a__isList(X) -> isList(X) a__U26(X) -> U26(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X1, X2) -> U32(X1, X2) a__U33(X) -> U33(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2, X3) -> U42(X1, X2, X3) a__U43(X1, X2, X3) -> U43(X1, X2, X3) a__U44(X1, X2, X3) -> U44(X1, X2, X3) a__U45(X1, X2) -> U45(X1, X2) a__U46(X) -> U46(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__U53(X1, X2, X3) -> U53(X1, X2, X3) a__U54(X1, X2, X3) -> U54(X1, X2, X3) a__U55(X1, X2) -> U55(X1, X2) a__U56(X) -> U56(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X1, X2) -> U62(X1, X2) a__U63(X) -> U63(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2) -> U72(X1, X2) a__U73(X1, X2) -> U73(X1, X2) a__isPal(X) -> isPal(X) a__U74(X) -> U74(X) a__U81(X1, X2) -> U81(X1, X2) a__U82(X1, X2) -> U82(X1, X2) a__U83(X) -> U83(X) a__isNePal(X) -> isNePal(X) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: a__isList(x0) a__isNeList(x0) a__isNePal(x0) a__isPal(x0) mark(__(x0, x1)) mark(U11(x0, x1)) mark(U12(x0, x1)) mark(isPalListKind(x0)) mark(U13(x0)) mark(isNeList(x0)) mark(U21(x0, x1, x2)) mark(U22(x0, x1, x2)) mark(U23(x0, x1, x2)) mark(U24(x0, x1, x2)) mark(U25(x0, x1)) mark(isList(x0)) mark(U26(x0)) mark(U31(x0, x1)) mark(U32(x0, x1)) mark(U33(x0)) mark(isQid(x0)) mark(U41(x0, x1, x2)) mark(U42(x0, x1, x2)) mark(U43(x0, x1, x2)) mark(U44(x0, x1, x2)) mark(U45(x0, x1)) mark(U46(x0)) mark(U51(x0, x1, x2)) mark(U52(x0, x1, x2)) mark(U53(x0, x1, x2)) mark(U54(x0, x1, x2)) mark(U55(x0, x1)) mark(U56(x0)) mark(U61(x0, x1)) mark(U62(x0, x1)) mark(U63(x0)) mark(U71(x0, x1, x2)) mark(U72(x0, x1)) mark(U73(x0, x1)) mark(isPal(x0)) mark(U74(x0)) mark(U81(x0, x1)) mark(U82(x0, x1)) mark(U83(x0)) mark(isNePal(x0)) mark(U91(x0, x1)) mark(U92(x0)) mark(nil) mark(tt) mark(a) mark(e) mark(i) mark(o) mark(u) a____(x0, x1) a__U11(x0, x1) a__U12(x0, x1) a__isPalListKind(x0) a__U13(x0) a__U21(x0, x1, x2) a__U22(x0, x1, x2) a__U23(x0, x1, x2) a__U24(x0, x1, x2) a__U25(x0, x1) a__U26(x0) a__U31(x0, x1) a__U32(x0, x1) a__U33(x0) a__isQid(x0) a__U41(x0, x1, x2) a__U42(x0, x1, x2) a__U43(x0, x1, x2) a__U44(x0, x1, x2) a__U45(x0, x1) a__U46(x0) a__U51(x0, x1, x2) a__U52(x0, x1, x2) a__U53(x0, x1, x2) a__U54(x0, x1, x2) a__U55(x0, x1) a__U56(x0) a__U61(x0, x1) a__U62(x0, x1) a__U63(x0) a__U71(x0, x1, x2) a__U72(x0, x1) a__U73(x0, x1) a__U74(x0) a__U81(x0, x1) a__U82(x0, x1) a__U83(x0) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: a____/2(YES,YES) __/2(YES,YES) mark/1)YES( nil/0) a__U11/2(YES,YES) tt/0) a__U12/2(YES,YES) a__isPalListKind/1)YES( a__U13/1)YES( a__isNeList/1(YES) a__U21/3(YES,YES,YES) a__U22/3(YES,YES,YES) a__U23/3(YES,YES,YES) a__U24/3(YES,YES,YES) a__U25/2(YES,YES) a__isList/1(YES) a__U26/1)YES( a__U31/2(YES,YES) a__U32/2(YES,YES) a__U33/1)YES( a__isQid/1(YES) a__U41/3(YES,YES,YES) a__U42/3(YES,YES,YES) a__U43/3(YES,YES,YES) a__U44/3(YES,YES,YES) a__U45/2(YES,YES) a__U46/1(YES) a__U51/3(YES,YES,YES) a__U52/3(YES,YES,YES) a__U53/3(YES,YES,YES) a__U54/3(YES,YES,YES) a__U55/2(YES,YES) a__U56/1(YES) a__U61/2(YES,YES) a__U62/2(YES,YES) a__U63/1)YES( a__U71/3(YES,YES,YES) a__U72/2(YES,YES) a__U73/2(YES,YES) a__isPal/1(YES) a__U74/1)YES( a__U81/2(YES,YES) a__U82/2(YES,YES) a__U83/1)YES( a__isNePal/1(YES) a__U91/2(YES,YES) a__U92/1)YES( a/0) e/0) i/0) o/0) u/0) U11/2(YES,YES) U12/2(YES,YES) isPalListKind/1)YES( U13/1)YES( isNeList/1(YES) U21/3(YES,YES,YES) U22/3(YES,YES,YES) U23/3(YES,YES,YES) U24/3(YES,YES,YES) U25/2(YES,YES) isList/1(YES) U26/1)YES( U31/2(YES,YES) U32/2(YES,YES) U33/1)YES( isQid/1(YES) U41/3(YES,YES,YES) U42/3(YES,YES,YES) U43/3(YES,YES,YES) U44/3(YES,YES,YES) U45/2(YES,YES) U46/1(YES) U51/3(YES,YES,YES) U52/3(YES,YES,YES) U53/3(YES,YES,YES) U54/3(YES,YES,YES) U55/2(YES,YES) U56/1(YES) U61/2(YES,YES) U62/2(YES,YES) U63/1)YES( U71/3(YES,YES,YES) U72/2(YES,YES) U73/2(YES,YES) isPal/1(YES) U74/1)YES( U81/2(YES,YES) U82/2(YES,YES) U83/1)YES( isNePal/1(YES) U91/2(YES,YES) U92/1)YES( Quasi precedence: [a_____2, ___2] > [a__U21_3, U21_3] > [a__U22_3, U22_3] > [a__U23_3, U23_3] > [a__U24_3, U24_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U21_3, U21_3] > [a__U22_3, U22_3] > [a__U23_3, U23_3] > [a__U24_3, U24_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_3, U42_3] > [a__U43_3, U43_3] > [a__U44_3, U44_3] > [a__U45_2, U45_2] > [a__U46_1, U46_1] > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_3, U42_3] > [a__U43_3, U43_3] > [a__U44_3, U44_3] > [a__U45_2, U45_2] > [a__U46_1, U46_1] > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_3, U42_3] > [a__U43_3, U43_3] > [a__U44_3, U44_3] > [a__U45_2, U45_2] > [a__U46_1, U46_1] > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_3, U42_3] > [a__U43_3, U43_3] > [a__U44_3, U44_3] > [a__U45_2, U45_2] > [a__U46_1, U46_1] > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_3, U52_3] > [a__U53_3, U53_3] > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_3, U52_3] > [a__U53_3, U53_3] > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_3, U52_3] > [a__U53_3, U53_3] > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_3, U52_3] > [a__U53_3, U53_3] > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U71_3, U71_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] [a_____2, ___2] > [a__U71_3, U71_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] [a_____2, ___2] > [a__U91_2, U91_2] a > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] a > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] a > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] a > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] e > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] e > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] e > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] e > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] i > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] i > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] i > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] i > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] u > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U11_2, U11_2] > [a__U12_2, a__isNeList_1, U12_2, isNeList_1] > [a__U31_2, U31_2] > [a__U32_2, U32_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] u > [nil, tt, a__U54_3, o, U54_3] > [a__U25_2, a__isList_1, a__U55_2, U25_2, isList_1, U55_2] > [a__U56_1, U56_1] u > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__U73_2, U73_2] u > [nil, tt, a__U54_3, o, U54_3] > [a__U72_2, U72_2] > [a__isPal_1, isPal_1] > [a__U81_2, U81_2] > [a__U82_2, U82_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] > [a__isQid_1, a__U62_2, isQid_1, U62_2] Status: a_____2: [1,2] ___2: [1,2] nil: multiset status a__U11_2: multiset status tt: multiset status a__U12_2: multiset status a__isNeList_1: multiset status a__U21_3: multiset status a__U22_3: multiset status a__U23_3: multiset status a__U24_3: multiset status a__U25_2: multiset status a__isList_1: multiset status a__U31_2: multiset status a__U32_2: multiset status a__isQid_1: multiset status a__U41_3: multiset status a__U42_3: multiset status a__U43_3: multiset status a__U44_3: multiset status a__U45_2: multiset status a__U46_1: multiset status a__U51_3: multiset status a__U52_3: multiset status a__U53_3: multiset status a__U54_3: multiset status a__U55_2: multiset status a__U56_1: multiset status a__U61_2: multiset status a__U62_2: multiset status a__U71_3: multiset status a__U72_2: multiset status a__U73_2: multiset status a__isPal_1: multiset status a__U81_2: multiset status a__U82_2: multiset status a__isNePal_1: multiset status a__U91_2: multiset status a: multiset status e: multiset status i: multiset status o: multiset status u: multiset status U11_2: multiset status U12_2: multiset status isNeList_1: multiset status U21_3: multiset status U22_3: multiset status U23_3: multiset status U24_3: multiset status U25_2: multiset status isList_1: multiset status U31_2: multiset status U32_2: multiset status isQid_1: multiset status U41_3: multiset status U42_3: multiset status U43_3: multiset status U44_3: multiset status U45_2: multiset status U46_1: multiset status U51_3: multiset status U52_3: multiset status U53_3: multiset status U54_3: multiset status U55_2: multiset status U56_1: multiset status U61_2: multiset status U62_2: multiset status U71_3: multiset status U72_2: multiset status U73_2: multiset status isPal_1: multiset status U81_2: multiset status U82_2: multiset status isNePal_1: multiset status U91_2: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a____(__(X, Y), Z) -> a____(mark(X), a____(mark(Y), mark(Z))) a____(X, nil) -> mark(X) a____(nil, X) -> mark(X) a__U11(tt, V) -> a__U12(a__isPalListKind(V), V) a__U12(tt, V) -> a__U13(a__isNeList(V)) a__U21(tt, V1, V2) -> a__U22(a__isPalListKind(V1), V1, V2) a__U22(tt, V1, V2) -> a__U23(a__isPalListKind(V2), V1, V2) a__U23(tt, V1, V2) -> a__U24(a__isPalListKind(V2), V1, V2) a__U24(tt, V1, V2) -> a__U25(a__isList(V1), V2) a__U25(tt, V2) -> a__U26(a__isList(V2)) a__U31(tt, V) -> a__U32(a__isPalListKind(V), V) a__U32(tt, V) -> a__U33(a__isQid(V)) a__U41(tt, V1, V2) -> a__U42(a__isPalListKind(V1), V1, V2) a__U42(tt, V1, V2) -> a__U43(a__isPalListKind(V2), V1, V2) a__U43(tt, V1, V2) -> a__U44(a__isPalListKind(V2), V1, V2) a__U44(tt, V1, V2) -> a__U45(a__isList(V1), V2) a__U45(tt, V2) -> a__U46(a__isNeList(V2)) a__U46(tt) -> tt a__U51(tt, V1, V2) -> a__U52(a__isPalListKind(V1), V1, V2) a__U52(tt, V1, V2) -> a__U53(a__isPalListKind(V2), V1, V2) a__U53(tt, V1, V2) -> a__U54(a__isPalListKind(V2), V1, V2) a__U54(tt, V1, V2) -> a__U55(a__isNeList(V1), V2) a__U55(tt, V2) -> a__U56(a__isList(V2)) a__U56(tt) -> tt a__U61(tt, V) -> a__U62(a__isPalListKind(V), V) a__U62(tt, V) -> a__U63(a__isQid(V)) a__U71(tt, I, P) -> a__U72(a__isPalListKind(I), P) a__U72(tt, P) -> a__U73(a__isPal(P), P) a__U73(tt, P) -> a__U74(a__isPalListKind(P)) a__U81(tt, V) -> a__U82(a__isPalListKind(V), V) a__U82(tt, V) -> a__U83(a__isNePal(V)) a__U91(tt, V2) -> a__U92(a__isPalListKind(V2)) a__isList(V) -> a__U11(a__isPalListKind(V), V) a__isList(nil) -> tt a__isList(__(V1, V2)) -> a__U21(a__isPalListKind(V1), V1, V2) a__isNeList(V) -> a__U31(a__isPalListKind(V), V) a__isNeList(__(V1, V2)) -> a__U41(a__isPalListKind(V1), V1, V2) a__isNeList(__(V1, V2)) -> a__U51(a__isPalListKind(V1), V1, V2) a__isNePal(V) -> a__U61(a__isPalListKind(V), V) a__isNePal(__(I, __(P, I))) -> a__U71(a__isQid(I), I, P) a__isPal(V) -> a__U81(a__isPalListKind(V), V) a__isPal(nil) -> tt a__isPalListKind(a) -> tt a__isPalListKind(e) -> tt a__isPalListKind(i) -> tt a__isPalListKind(u) -> tt a__isPalListKind(__(V1, V2)) -> a__U91(a__isPalListKind(V1), V2) a__isQid(a) -> tt a__isQid(e) -> tt a__isQid(i) -> tt a__isQid(o) -> tt a__isQid(u) -> tt ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U13(tt) -> tt a__U26(tt) -> tt a__U33(tt) -> tt a__U63(tt) -> tt a__U74(tt) -> tt a__U83(tt) -> tt a__U92(tt) -> tt a__isPalListKind(nil) -> tt a__isPalListKind(o) -> tt mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(U13(X)) -> a__U13(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) mark(U23(X1, X2, X3)) -> a__U23(mark(X1), X2, X3) mark(U24(X1, X2, X3)) -> a__U24(mark(X1), X2, X3) mark(U25(X1, X2)) -> a__U25(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U26(X)) -> a__U26(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X1, X2)) -> a__U32(mark(X1), X2) mark(U33(X)) -> a__U33(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2, X3)) -> a__U42(mark(X1), X2, X3) mark(U43(X1, X2, X3)) -> a__U43(mark(X1), X2, X3) mark(U44(X1, X2, X3)) -> a__U44(mark(X1), X2, X3) mark(U45(X1, X2)) -> a__U45(mark(X1), X2) mark(U46(X)) -> a__U46(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(U53(X1, X2, X3)) -> a__U53(mark(X1), X2, X3) mark(U54(X1, X2, X3)) -> a__U54(mark(X1), X2, X3) mark(U55(X1, X2)) -> a__U55(mark(X1), X2) mark(U56(X)) -> a__U56(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(U63(X)) -> a__U63(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U73(X1, X2)) -> a__U73(mark(X1), X2) mark(isPal(X)) -> a__isPal(X) mark(U74(X)) -> a__U74(mark(X)) mark(U81(X1, X2)) -> a__U81(mark(X1), X2) mark(U82(X1, X2)) -> a__U82(mark(X1), X2) mark(U83(X)) -> a__U83(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(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__U11(X1, X2) -> U11(X1, X2) a__U12(X1, X2) -> U12(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__U13(X) -> U13(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2, X3) -> U22(X1, X2, X3) a__U23(X1, X2, X3) -> U23(X1, X2, X3) a__U24(X1, X2, X3) -> U24(X1, X2, X3) a__U25(X1, X2) -> U25(X1, X2) a__isList(X) -> isList(X) a__U26(X) -> U26(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X1, X2) -> U32(X1, X2) a__U33(X) -> U33(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2, X3) -> U42(X1, X2, X3) a__U43(X1, X2, X3) -> U43(X1, X2, X3) a__U44(X1, X2, X3) -> U44(X1, X2, X3) a__U45(X1, X2) -> U45(X1, X2) a__U46(X) -> U46(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__U53(X1, X2, X3) -> U53(X1, X2, X3) a__U54(X1, X2, X3) -> U54(X1, X2, X3) a__U55(X1, X2) -> U55(X1, X2) a__U56(X) -> U56(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X1, X2) -> U62(X1, X2) a__U63(X) -> U63(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2) -> U72(X1, X2) a__U73(X1, X2) -> U73(X1, X2) a__isPal(X) -> isPal(X) a__U74(X) -> U74(X) a__U81(X1, X2) -> U81(X1, X2) a__U82(X1, X2) -> U82(X1, X2) a__U83(X) -> U83(X) a__isNePal(X) -> isNePal(X) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: a__isList(x0) a__isNeList(x0) a__isNePal(x0) a__isPal(x0) mark(__(x0, x1)) mark(U11(x0, x1)) mark(U12(x0, x1)) mark(isPalListKind(x0)) mark(U13(x0)) mark(isNeList(x0)) mark(U21(x0, x1, x2)) mark(U22(x0, x1, x2)) mark(U23(x0, x1, x2)) mark(U24(x0, x1, x2)) mark(U25(x0, x1)) mark(isList(x0)) mark(U26(x0)) mark(U31(x0, x1)) mark(U32(x0, x1)) mark(U33(x0)) mark(isQid(x0)) mark(U41(x0, x1, x2)) mark(U42(x0, x1, x2)) mark(U43(x0, x1, x2)) mark(U44(x0, x1, x2)) mark(U45(x0, x1)) mark(U46(x0)) mark(U51(x0, x1, x2)) mark(U52(x0, x1, x2)) mark(U53(x0, x1, x2)) mark(U54(x0, x1, x2)) mark(U55(x0, x1)) mark(U56(x0)) mark(U61(x0, x1)) mark(U62(x0, x1)) mark(U63(x0)) mark(U71(x0, x1, x2)) mark(U72(x0, x1)) mark(U73(x0, x1)) mark(isPal(x0)) mark(U74(x0)) mark(U81(x0, x1)) mark(U82(x0, x1)) mark(U83(x0)) mark(isNePal(x0)) mark(U91(x0, x1)) mark(U92(x0)) mark(nil) mark(tt) mark(a) mark(e) mark(i) mark(o) mark(u) a____(x0, x1) a__U11(x0, x1) a__U12(x0, x1) a__isPalListKind(x0) a__U13(x0) a__U21(x0, x1, x2) a__U22(x0, x1, x2) a__U23(x0, x1, x2) a__U24(x0, x1, x2) a__U25(x0, x1) a__U26(x0) a__U31(x0, x1) a__U32(x0, x1) a__U33(x0) a__isQid(x0) a__U41(x0, x1, x2) a__U42(x0, x1, x2) a__U43(x0, x1, x2) a__U44(x0, x1, x2) a__U45(x0, x1) a__U46(x0) a__U51(x0, x1, x2) a__U52(x0, x1, x2) a__U53(x0, x1, x2) a__U54(x0, x1, x2) a__U55(x0, x1) a__U56(x0) a__U61(x0, x1) a__U62(x0, x1) a__U63(x0) a__U71(x0, x1, x2) a__U72(x0, x1) a__U73(x0, x1) a__U74(x0) a__U81(x0, x1) a__U82(x0, x1) a__U83(x0) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U12(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U13(x_1)) = 1 + 2*x_1 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U22(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U23(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U24(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U25(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U26(x_1)) = 1 + 2*x_1 POL(U31(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U32(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U33(x_1)) = 1 + 2*x_1 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U43(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U45(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U46(x_1)) = 1 + x_1 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U55(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U56(x_1)) = 1 + x_1 POL(U61(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U62(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U63(x_1)) = 1 + 2*x_1 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U72(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U73(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U74(x_1)) = 1 + 2*x_1 POL(U81(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U82(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U83(x_1)) = 1 + 2*x_1 POL(U91(x_1, x_2)) = 1 + x_1 + x_2 POL(U92(x_1)) = 1 + 2*x_1 POL(__(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a) = 1 POL(a__U11(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U12(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U13(x_1)) = 2 + 2*x_1 POL(a__U21(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U22(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U23(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U24(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U25(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U26(x_1)) = 2 + 2*x_1 POL(a__U31(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U32(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U33(x_1)) = 2 + 2*x_1 POL(a__U41(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U42(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U43(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U44(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U45(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U46(x_1)) = 2 + x_1 POL(a__U51(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U52(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U53(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U54(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U55(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U56(x_1)) = 2 + x_1 POL(a__U61(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U62(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U63(x_1)) = 2 + 2*x_1 POL(a__U71(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U72(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U73(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U74(x_1)) = 2 + 2*x_1 POL(a__U81(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U82(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U83(x_1)) = 2 + 2*x_1 POL(a__U91(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U92(x_1)) = 2 + 2*x_1 POL(a____(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__isList(x_1)) = 2 + 2*x_1 POL(a__isNeList(x_1)) = 2 + 2*x_1 POL(a__isNePal(x_1)) = 2 + 2*x_1 POL(a__isPal(x_1)) = 2 + 2*x_1 POL(a__isPalListKind(x_1)) = 2 + 2*x_1 POL(a__isQid(x_1)) = 2 + 2*x_1 POL(e) = 1 POL(i) = 1 POL(isList(x_1)) = 1 + 2*x_1 POL(isNeList(x_1)) = 1 + 2*x_1 POL(isNePal(x_1)) = 1 + 2*x_1 POL(isPal(x_1)) = 1 + 2*x_1 POL(isPalListKind(x_1)) = 1 + 2*x_1 POL(isQid(x_1)) = 1 + 2*x_1 POL(mark(x_1)) = 2*x_1 POL(nil) = 1 POL(o) = 1 POL(tt) = 1 POL(u) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U13(tt) -> tt a__U26(tt) -> tt a__U33(tt) -> tt a__U63(tt) -> tt a__U74(tt) -> tt a__U83(tt) -> tt a__U92(tt) -> tt a__isPalListKind(nil) -> tt a__isPalListKind(o) -> tt 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__U11(X1, X2) -> U11(X1, X2) a__U12(X1, X2) -> U12(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__U13(X) -> U13(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2, X3) -> U22(X1, X2, X3) a__U23(X1, X2, X3) -> U23(X1, X2, X3) a__U24(X1, X2, X3) -> U24(X1, X2, X3) a__U25(X1, X2) -> U25(X1, X2) a__isList(X) -> isList(X) a__U26(X) -> U26(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X1, X2) -> U32(X1, X2) a__U33(X) -> U33(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2, X3) -> U42(X1, X2, X3) a__U43(X1, X2, X3) -> U43(X1, X2, X3) a__U44(X1, X2, X3) -> U44(X1, X2, X3) a__U45(X1, X2) -> U45(X1, X2) a__U46(X) -> U46(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__U53(X1, X2, X3) -> U53(X1, X2, X3) a__U54(X1, X2, X3) -> U54(X1, X2, X3) a__U55(X1, X2) -> U55(X1, X2) a__U56(X) -> U56(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X1, X2) -> U62(X1, X2) a__U63(X) -> U63(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2) -> U72(X1, X2) a__U73(X1, X2) -> U73(X1, X2) a__isPal(X) -> isPal(X) a__U74(X) -> U74(X) a__U81(X1, X2) -> U81(X1, X2) a__U82(X1, X2) -> U82(X1, X2) a__U83(X) -> U83(X) a__isNePal(X) -> isNePal(X) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(U13(X)) -> a__U13(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) mark(U23(X1, X2, X3)) -> a__U23(mark(X1), X2, X3) mark(U24(X1, X2, X3)) -> a__U24(mark(X1), X2, X3) mark(U25(X1, X2)) -> a__U25(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U26(X)) -> a__U26(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X1, X2)) -> a__U32(mark(X1), X2) mark(U33(X)) -> a__U33(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2, X3)) -> a__U42(mark(X1), X2, X3) mark(U43(X1, X2, X3)) -> a__U43(mark(X1), X2, X3) mark(U44(X1, X2, X3)) -> a__U44(mark(X1), X2, X3) mark(U45(X1, X2)) -> a__U45(mark(X1), X2) mark(U46(X)) -> a__U46(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(U53(X1, X2, X3)) -> a__U53(mark(X1), X2, X3) mark(U54(X1, X2, X3)) -> a__U54(mark(X1), X2, X3) mark(U55(X1, X2)) -> a__U55(mark(X1), X2) mark(U56(X)) -> a__U56(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(U63(X)) -> a__U63(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U73(X1, X2)) -> a__U73(mark(X1), X2) mark(isPal(X)) -> a__isPal(X) mark(U74(X)) -> a__U74(mark(X)) mark(U81(X1, X2)) -> a__U81(mark(X1), X2) mark(U82(X1, X2)) -> a__U82(mark(X1), X2) mark(U83(X)) -> a__U83(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) The set Q consists of the following terms: a__isList(x0) a__isNeList(x0) a__isNePal(x0) a__isPal(x0) mark(__(x0, x1)) mark(U11(x0, x1)) mark(U12(x0, x1)) mark(isPalListKind(x0)) mark(U13(x0)) mark(isNeList(x0)) mark(U21(x0, x1, x2)) mark(U22(x0, x1, x2)) mark(U23(x0, x1, x2)) mark(U24(x0, x1, x2)) mark(U25(x0, x1)) mark(isList(x0)) mark(U26(x0)) mark(U31(x0, x1)) mark(U32(x0, x1)) mark(U33(x0)) mark(isQid(x0)) mark(U41(x0, x1, x2)) mark(U42(x0, x1, x2)) mark(U43(x0, x1, x2)) mark(U44(x0, x1, x2)) mark(U45(x0, x1)) mark(U46(x0)) mark(U51(x0, x1, x2)) mark(U52(x0, x1, x2)) mark(U53(x0, x1, x2)) mark(U54(x0, x1, x2)) mark(U55(x0, x1)) mark(U56(x0)) mark(U61(x0, x1)) mark(U62(x0, x1)) mark(U63(x0)) mark(U71(x0, x1, x2)) mark(U72(x0, x1)) mark(U73(x0, x1)) mark(isPal(x0)) mark(U74(x0)) mark(U81(x0, x1)) mark(U82(x0, x1)) mark(U83(x0)) mark(isNePal(x0)) mark(U91(x0, x1)) mark(U92(x0)) mark(nil) mark(tt) mark(a) mark(e) mark(i) mark(o) mark(u) a____(x0, x1) a__U11(x0, x1) a__U12(x0, x1) a__isPalListKind(x0) a__U13(x0) a__U21(x0, x1, x2) a__U22(x0, x1, x2) a__U23(x0, x1, x2) a__U24(x0, x1, x2) a__U25(x0, x1) a__U26(x0) a__U31(x0, x1) a__U32(x0, x1) a__U33(x0) a__isQid(x0) a__U41(x0, x1, x2) a__U42(x0, x1, x2) a__U43(x0, x1, x2) a__U44(x0, x1, x2) a__U45(x0, x1) a__U46(x0) a__U51(x0, x1, x2) a__U52(x0, x1, x2) a__U53(x0, x1, x2) a__U54(x0, x1, x2) a__U55(x0, x1) a__U56(x0) a__U61(x0, x1) a__U62(x0, x1) a__U63(x0) a__U71(x0, x1, x2) a__U72(x0, x1) a__U73(x0, x1) a__U74(x0) a__U81(x0, x1) a__U82(x0, x1) a__U83(x0) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: mark/1)YES( __/2(YES,YES) a____/2(YES,YES) U11/2(YES,YES) a__U11/2(YES,YES) U12/2(YES,YES) a__U12/2(YES,YES) isPalListKind/1(YES) a__isPalListKind/1)YES( U13/1(YES) a__U13/1)YES( isNeList/1(YES) a__isNeList/1(YES) U21/3(YES,YES,YES) a__U21/3(YES,YES,YES) U22/3(YES,YES,YES) a__U22/3(YES,YES,YES) U23/3(YES,YES,YES) a__U23/3(YES,YES,YES) U24/3(YES,YES,YES) a__U24/3(YES,YES,YES) U25/2(YES,YES) a__U25/2(YES,YES) isList/1)YES( a__isList/1)YES( U26/1)YES( a__U26/1)YES( U31/2(YES,YES) a__U31/2(YES,YES) U32/2(YES,YES) a__U32/2(YES,YES) U33/1)YES( a__U33/1)YES( isQid/1)YES( a__isQid/1)YES( U41/3(YES,YES,YES) a__U41/3(YES,YES,YES) U42/3(YES,YES,YES) a__U42/3(YES,YES,YES) U43/3(YES,YES,YES) a__U43/3(YES,YES,YES) U44/3(YES,YES,YES) a__U44/3(YES,YES,YES) U45/2(YES,YES) a__U45/2(YES,YES) U46/1)YES( a__U46/1)YES( U51/3(YES,YES,YES) a__U51/3(YES,YES,YES) U52/3(YES,YES,YES) a__U52/3(YES,YES,YES) U53/3(YES,YES,YES) a__U53/3(YES,YES,YES) U54/3(YES,YES,YES) a__U54/3(YES,YES,YES) U55/2(YES,YES) a__U55/2(YES,YES) U56/1)YES( a__U56/1)YES( U61/2(YES,YES) a__U61/2(YES,YES) U62/2(YES,YES) a__U62/2(YES,YES) U63/1(YES) a__U63/1)YES( U71/3(YES,YES,YES) a__U71/3(YES,YES,YES) U72/2(YES,YES) a__U72/2(YES,YES) U73/2(YES,YES) a__U73/2(YES,YES) isPal/1)YES( a__isPal/1)YES( U74/1(YES) a__U74/1(YES) U81/2(YES,YES) a__U81/2(YES,YES) U82/2(YES,YES) a__U82/2(YES,YES) U83/1)YES( a__U83/1)YES( isNePal/1(YES) a__isNePal/1)YES( U91/2(YES,YES) a__U91/2(YES,YES) U92/1)YES( a__U92/1)YES( Quasi precedence: ___2 > a_____2 U11_2 > a__U11_2 U12_2 > a__U12_2 [isNeList_1, a__isNeList_1] [U21_3, a__U21_3] U22_3 > a__U22_3 U23_3 > a__U23_3 [U24_3, a__U24_3] [U25_2, a__U25_2] U31_2 > a__U31_2 [U32_2, a__U32_2] U41_3 > a__U41_3 U42_3 > a__U42_3 U43_3 > a__U43_3 U44_3 > a__U44_3 [U45_2, a__U45_2] U51_3 > a__U51_3 U52_3 > a__U52_3 U53_3 > a__U53_3 U54_3 > a__U54_3 [U55_2, a__U55_2] U61_2 > a__U61_2 U62_2 > a__U62_2 [U71_3, a__U71_3] [U72_2, a__U72_2] U73_2 > a__U73_2 U74_1 > a__U74_1 [U81_2, a__U81_2] [U82_2, a__U82_2] U91_2 > a__U91_2 Status: ___2: multiset status a_____2: multiset status U11_2: multiset status a__U11_2: multiset status U12_2: multiset status a__U12_2: multiset status isPalListKind_1: [1] U13_1: multiset status isNeList_1: [1] a__isNeList_1: [1] U21_3: multiset status a__U21_3: multiset status U22_3: multiset status a__U22_3: multiset status U23_3: multiset status a__U23_3: [1,2,3] U24_3: [3,1,2] a__U24_3: [3,1,2] U25_2: multiset status a__U25_2: multiset status U31_2: multiset status a__U31_2: multiset status U32_2: multiset status a__U32_2: multiset status U41_3: multiset status a__U41_3: multiset status U42_3: multiset status a__U42_3: [3,1,2] U43_3: multiset status a__U43_3: multiset status U44_3: multiset status a__U44_3: multiset status U45_2: multiset status a__U45_2: multiset status U51_3: multiset status a__U51_3: multiset status U52_3: multiset status a__U52_3: [2,3,1] U53_3: multiset status a__U53_3: multiset status U54_3: multiset status a__U54_3: multiset status U55_2: multiset status a__U55_2: multiset status U61_2: multiset status a__U61_2: multiset status U62_2: multiset status a__U62_2: multiset status U63_1: [1] U71_3: multiset status a__U71_3: multiset status U72_2: multiset status a__U72_2: multiset status U73_2: multiset status a__U73_2: multiset status U74_1: multiset status a__U74_1: multiset status U81_2: multiset status a__U81_2: multiset status U82_2: multiset status a__U82_2: multiset status isNePal_1: [1] U91_2: multiset status a__U91_2: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X1, X2)) -> a__U12(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(U13(X)) -> a__U13(mark(X)) mark(U22(X1, X2, X3)) -> a__U22(mark(X1), X2, X3) mark(U23(X1, X2, X3)) -> a__U23(mark(X1), X2, X3) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2, X3)) -> a__U42(mark(X1), X2, X3) mark(U43(X1, X2, X3)) -> a__U43(mark(X1), X2, X3) mark(U44(X1, X2, X3)) -> a__U44(mark(X1), X2, X3) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(U53(X1, X2, X3)) -> a__U53(mark(X1), X2, X3) mark(U54(X1, X2, X3)) -> a__U54(mark(X1), X2, X3) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(U63(X)) -> a__U63(mark(X)) mark(U73(X1, X2)) -> a__U73(mark(X1), X2) mark(U74(X)) -> a__U74(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U24(X1, X2, X3)) -> a__U24(mark(X1), X2, X3) mark(U25(X1, X2)) -> a__U25(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U26(X)) -> a__U26(mark(X)) mark(U32(X1, X2)) -> a__U32(mark(X1), X2) mark(U33(X)) -> a__U33(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U45(X1, X2)) -> a__U45(mark(X1), X2) mark(U46(X)) -> a__U46(mark(X)) mark(U55(X1, X2)) -> a__U55(mark(X1), X2) mark(U56(X)) -> a__U56(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(isPal(X)) -> a__isPal(X) mark(U81(X1, X2)) -> a__U81(mark(X1), X2) mark(U82(X1, X2)) -> a__U82(mark(X1), X2) mark(U83(X)) -> a__U83(mark(X)) mark(U92(X)) -> a__U92(mark(X)) The set Q consists of the following terms: a__isList(x0) a__isNeList(x0) a__isNePal(x0) a__isPal(x0) mark(__(x0, x1)) mark(U11(x0, x1)) mark(U12(x0, x1)) mark(isPalListKind(x0)) mark(U13(x0)) mark(isNeList(x0)) mark(U21(x0, x1, x2)) mark(U22(x0, x1, x2)) mark(U23(x0, x1, x2)) mark(U24(x0, x1, x2)) mark(U25(x0, x1)) mark(isList(x0)) mark(U26(x0)) mark(U31(x0, x1)) mark(U32(x0, x1)) mark(U33(x0)) mark(isQid(x0)) mark(U41(x0, x1, x2)) mark(U42(x0, x1, x2)) mark(U43(x0, x1, x2)) mark(U44(x0, x1, x2)) mark(U45(x0, x1)) mark(U46(x0)) mark(U51(x0, x1, x2)) mark(U52(x0, x1, x2)) mark(U53(x0, x1, x2)) mark(U54(x0, x1, x2)) mark(U55(x0, x1)) mark(U56(x0)) mark(U61(x0, x1)) mark(U62(x0, x1)) mark(U63(x0)) mark(U71(x0, x1, x2)) mark(U72(x0, x1)) mark(U73(x0, x1)) mark(isPal(x0)) mark(U74(x0)) mark(U81(x0, x1)) mark(U82(x0, x1)) mark(U83(x0)) mark(isNePal(x0)) mark(U91(x0, x1)) mark(U92(x0)) mark(nil) mark(tt) mark(a) mark(e) mark(i) mark(o) mark(u) a____(x0, x1) a__U11(x0, x1) a__U12(x0, x1) a__isPalListKind(x0) a__U13(x0) a__U21(x0, x1, x2) a__U22(x0, x1, x2) a__U23(x0, x1, x2) a__U24(x0, x1, x2) a__U25(x0, x1) a__U26(x0) a__U31(x0, x1) a__U32(x0, x1) a__U33(x0) a__isQid(x0) a__U41(x0, x1, x2) a__U42(x0, x1, x2) a__U43(x0, x1, x2) a__U44(x0, x1, x2) a__U45(x0, x1) a__U46(x0) a__U51(x0, x1, x2) a__U52(x0, x1, x2) a__U53(x0, x1, x2) a__U54(x0, x1, x2) a__U55(x0, x1) a__U56(x0) a__U61(x0, x1) a__U62(x0, x1) a__U63(x0) a__U71(x0, x1, x2) a__U72(x0, x1) a__U73(x0, x1) a__U74(x0) a__U81(x0, x1) a__U82(x0, x1) a__U83(x0) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:a__U71_3 > U55_2 > U92_1 > U83_1 > U82_2 > a__U81_2 > a__U46_1 > a__U32_2 > a__U82_2 > isPal_1 > U32_2 > a__U83_1 > U56_1 > a__isNeList_1 > a__U56_1 > isQid_1 > a__U33_1 > a__U25_2 > a__U21_3 > a__isList_1 > mark_1 > a__isQid_1 > a__U26_1 > isNeList_1 > U71_3 > a__U92_1 > U25_2 > a__U55_2 > a__U72_2 > U81_2 > U21_3 > U24_3 > U46_1 > U26_1 > a__isPal_1 > U45_2 > a__U45_2 > isList_1 > U72_2 > a__U24_3 > U33_1 and weight map: mark_1=4 isNeList_1=1 a__isNeList_1=4 isList_1=2 a__isList_1=5 U26_1=2 a__U26_1=1 U33_1=2 a__U33_1=1 isQid_1=1 a__isQid_1=5 U46_1=2 a__U46_1=1 U56_1=2 a__U56_1=1 isPal_1=2 a__isPal_1=5 U83_1=5 a__U83_1=3 U92_1=3 a__U92_1=2 U21_3=1 a__U21_3=0 U24_3=1 a__U24_3=0 U25_2=2 a__U25_2=0 U32_2=1 a__U32_2=0 U45_2=2 a__U45_2=0 U55_2=3 a__U55_2=2 U71_3=1 a__U71_3=0 U72_2=1 a__U72_2=0 U81_2=1 a__U81_2=0 U82_2=3 a__U82_2=0 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U24(X1, X2, X3)) -> a__U24(mark(X1), X2, X3) mark(U25(X1, X2)) -> a__U25(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U26(X)) -> a__U26(mark(X)) mark(U32(X1, X2)) -> a__U32(mark(X1), X2) mark(U33(X)) -> a__U33(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U45(X1, X2)) -> a__U45(mark(X1), X2) mark(U46(X)) -> a__U46(mark(X)) mark(U55(X1, X2)) -> a__U55(mark(X1), X2) mark(U56(X)) -> a__U56(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(isPal(X)) -> a__isPal(X) mark(U81(X1, X2)) -> a__U81(mark(X1), X2) mark(U82(X1, X2)) -> a__U82(mark(X1), X2) mark(U83(X)) -> a__U83(mark(X)) mark(U92(X)) -> a__U92(mark(X)) ---------------------------------------- (8) Obligation: Q restricted rewrite system: R is empty. The set Q consists of the following terms: a__isList(x0) a__isNeList(x0) a__isNePal(x0) a__isPal(x0) mark(__(x0, x1)) mark(U11(x0, x1)) mark(U12(x0, x1)) mark(isPalListKind(x0)) mark(U13(x0)) mark(isNeList(x0)) mark(U21(x0, x1, x2)) mark(U22(x0, x1, x2)) mark(U23(x0, x1, x2)) mark(U24(x0, x1, x2)) mark(U25(x0, x1)) mark(isList(x0)) mark(U26(x0)) mark(U31(x0, x1)) mark(U32(x0, x1)) mark(U33(x0)) mark(isQid(x0)) mark(U41(x0, x1, x2)) mark(U42(x0, x1, x2)) mark(U43(x0, x1, x2)) mark(U44(x0, x1, x2)) mark(U45(x0, x1)) mark(U46(x0)) mark(U51(x0, x1, x2)) mark(U52(x0, x1, x2)) mark(U53(x0, x1, x2)) mark(U54(x0, x1, x2)) mark(U55(x0, x1)) mark(U56(x0)) mark(U61(x0, x1)) mark(U62(x0, x1)) mark(U63(x0)) mark(U71(x0, x1, x2)) mark(U72(x0, x1)) mark(U73(x0, x1)) mark(isPal(x0)) mark(U74(x0)) mark(U81(x0, x1)) mark(U82(x0, x1)) mark(U83(x0)) mark(isNePal(x0)) mark(U91(x0, x1)) mark(U92(x0)) mark(nil) mark(tt) mark(a) mark(e) mark(i) mark(o) mark(u) a____(x0, x1) a__U11(x0, x1) a__U12(x0, x1) a__isPalListKind(x0) a__U13(x0) a__U21(x0, x1, x2) a__U22(x0, x1, x2) a__U23(x0, x1, x2) a__U24(x0, x1, x2) a__U25(x0, x1) a__U26(x0) a__U31(x0, x1) a__U32(x0, x1) a__U33(x0) a__isQid(x0) a__U41(x0, x1, x2) a__U42(x0, x1, x2) a__U43(x0, x1, x2) a__U44(x0, x1, x2) a__U45(x0, x1) a__U46(x0) a__U51(x0, x1, x2) a__U52(x0, x1, x2) a__U53(x0, x1, x2) a__U54(x0, x1, x2) a__U55(x0, x1) a__U56(x0) a__U61(x0, x1) a__U62(x0, x1) a__U63(x0) a__U71(x0, x1, x2) a__U72(x0, x1) a__U73(x0, x1) a__U74(x0) a__U81(x0, x1) a__U82(x0, x1) a__U83(x0) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (9) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (10) YES