YES proof of /export/starexec/sandbox2/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, 147 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 56 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 34 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 22 ms] (8) QTRS (9) QTRSRRRProof [EQUIVALENT, 17 ms] (10) QTRS (11) QTRSRRRProof [EQUIVALENT, 0 ms] (12) QTRS (13) RisEmptyProof [EQUIVALENT, 0 ms] (14) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) active(__(X, nil)) -> mark(X) active(__(nil, X)) -> mark(X) active(and(tt, X)) -> mark(X) active(isList(V)) -> mark(isNeList(V)) active(isList(nil)) -> mark(tt) active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) active(isNeList(V)) -> mark(isQid(V)) active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) active(isNePal(V)) -> mark(isQid(V)) active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) active(isPal(V)) -> mark(isNePal(V)) active(isPal(nil)) -> mark(tt) active(isQid(a)) -> mark(tt) active(isQid(e)) -> mark(tt) active(isQid(i)) -> mark(tt) active(isQid(o)) -> mark(tt) active(isQid(u)) -> mark(tt) mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isList(active(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isNeList(active(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isQid(active(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isNePal(active(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(a) = 2 POL(active(x_1)) = x_1 POL(and(x_1, x_2)) = x_1 + x_2 POL(e) = 0 POL(i) = 1 POL(isList(x_1)) = 2 + x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = x_1 POL(isPal(x_1)) = 2*x_1 POL(isQid(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(o) = 1 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) active(__(X, nil)) -> mark(X) active(__(nil, X)) -> mark(X) active(isList(V)) -> mark(isNeList(V)) active(isList(nil)) -> mark(tt) active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) active(isQid(a)) -> mark(tt) active(isQid(i)) -> mark(tt) active(isQid(o)) -> mark(tt) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(and(tt, X)) -> mark(X) active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) active(isNeList(V)) -> mark(isQid(V)) active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) active(isNePal(V)) -> mark(isQid(V)) active(isPal(V)) -> mark(isNePal(V)) active(isPal(nil)) -> mark(tt) active(isQid(e)) -> mark(tt) active(isQid(u)) -> mark(tt) mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isList(active(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isNeList(active(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isQid(active(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isNePal(active(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(__(x_1, x_2)) = 2*x_1 + x_2 POL(a) = 0 POL(active(x_1)) = x_1 POL(and(x_1, x_2)) = x_1 + x_2 POL(e) = 2 POL(i) = 0 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = 2*x_1 POL(isPal(x_1)) = 2*x_1 POL(isQid(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(o) = 0 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(isQid(e)) -> mark(tt) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(and(tt, X)) -> mark(X) active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) active(isNeList(V)) -> mark(isQid(V)) active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) active(isNePal(V)) -> mark(isQid(V)) active(isPal(V)) -> mark(isNePal(V)) active(isPal(nil)) -> mark(tt) active(isQid(u)) -> mark(tt) mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isList(active(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isNeList(active(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isQid(active(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isNePal(active(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(a) = 0 POL(active(x_1)) = x_1 POL(and(x_1, x_2)) = x_1 + x_2 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = 1 + 2*x_1 POL(isNeList(x_1)) = 1 + 2*x_1 POL(isNePal(x_1)) = 2 + 2*x_1 POL(isPal(x_1)) = 2 + 2*x_1 POL(isQid(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 2 POL(o) = 0 POL(tt) = 2 POL(u) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(and(tt, X)) -> mark(X) active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) active(isNeList(V)) -> mark(isQid(V)) active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) active(isNePal(V)) -> mark(isQid(V)) active(isPal(nil)) -> mark(tt) active(isQid(u)) -> mark(tt) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(isPal(V)) -> mark(isNePal(V)) mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isList(active(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isNeList(active(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isQid(active(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isNePal(active(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(__(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a) = 0 POL(active(x_1)) = x_1 POL(and(x_1, x_2)) = x_1 + x_2 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = 2*x_1 POL(isNeList(x_1)) = 2*x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPal(x_1)) = 2 + x_1 POL(isQid(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(o) = 0 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(isPal(V)) -> mark(isNePal(V)) ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isList(active(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isNeList(active(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isQid(active(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isNePal(active(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (9) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(__(x_1, x_2)) = 2 + x_1 + x_2 POL(a) = 2 POL(active(x_1)) = x_1 POL(and(x_1, x_2)) = 1 + x_1 + x_2 POL(e) = 2 POL(i) = 2 POL(isList(x_1)) = 2 + x_1 POL(isNeList(x_1)) = 2 + x_1 POL(isNePal(x_1)) = 2 + x_1 POL(isPal(x_1)) = 2 + x_1 POL(isQid(x_1)) = 2 + x_1 POL(mark(x_1)) = 1 + 2*x_1 POL(nil) = 2 POL(o) = 1 POL(tt) = 2 POL(u) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(tt) -> active(tt) mark(isList(X)) -> active(isList(X)) mark(isNeList(X)) -> active(isNeList(X)) mark(isQid(X)) -> active(isQid(X)) mark(isNePal(X)) -> active(isNePal(X)) mark(isPal(X)) -> active(isPal(X)) mark(a) -> active(a) mark(e) -> active(e) mark(i) -> active(i) mark(o) -> active(o) mark(u) -> active(u) __(mark(X1), X2) -> __(X1, X2) __(X1, mark(X2)) -> __(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) isList(mark(X)) -> isList(X) isNeList(mark(X)) -> isNeList(X) isQid(mark(X)) -> isQid(X) isNePal(mark(X)) -> isNePal(X) isPal(mark(X)) -> isPal(X) ---------------------------------------- (10) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(active(X)) -> isList(X) isNeList(active(X)) -> isNeList(X) isQid(active(X)) -> isQid(X) isNePal(active(X)) -> isNePal(X) isPal(active(X)) -> isPal(X) The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (11) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:active_1 > isPal_1 > isNePal_1 > isQid_1 > isNeList_1 > isList_1 > and_2 > ___2 and weight map: active_1=0 isList_1=1 isNeList_1=1 isQid_1=1 isNePal_1=1 isPal_1=1 ___2=0 and_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: __(active(X1), X2) -> __(X1, X2) __(X1, active(X2)) -> __(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) isList(active(X)) -> isList(X) isNeList(active(X)) -> isNeList(X) isQid(active(X)) -> isQid(X) isNePal(active(X)) -> isNePal(X) isPal(active(X)) -> isPal(X) ---------------------------------------- (12) Obligation: Q restricted rewrite system: R is empty. The set Q consists of the following terms: active(__(__(x0, x1), x2)) active(__(x0, nil)) active(__(nil, x0)) active(and(tt, x0)) active(isList(x0)) active(isNeList(x0)) active(isNePal(x0)) active(isPal(x0)) active(isQid(a)) active(isQid(e)) active(isQid(i)) active(isQid(o)) active(isQid(u)) mark(__(x0, x1)) mark(nil) mark(and(x0, x1)) mark(tt) mark(isList(x0)) mark(isNeList(x0)) mark(isQid(x0)) mark(isNePal(x0)) mark(isPal(x0)) mark(a) mark(e) mark(i) mark(o) mark(u) __(mark(x0), x1) __(x0, mark(x1)) __(active(x0), x1) __(x0, active(x1)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) isList(mark(x0)) isList(active(x0)) isNeList(mark(x0)) isNeList(active(x0)) isQid(mark(x0)) isQid(active(x0)) isNePal(mark(x0)) isNePal(active(x0)) isPal(mark(x0)) isPal(active(x0)) ---------------------------------------- (13) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (14) YES