6.23/2.40 YES 6.38/2.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 6.38/2.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.38/2.41 6.38/2.41 6.38/2.41 Termination w.r.t. Q of the given QTRS could be proven: 6.38/2.41 6.38/2.41 (0) QTRS 6.38/2.41 (1) QTRSRRRProof [EQUIVALENT, 156 ms] 6.38/2.41 (2) QTRS 6.38/2.41 (3) QTRSRRRProof [EQUIVALENT, 24 ms] 6.38/2.41 (4) QTRS 6.38/2.41 (5) QTRSRRRProof [EQUIVALENT, 34 ms] 6.38/2.41 (6) QTRS 6.38/2.41 (7) QTRSRRRProof [EQUIVALENT, 24 ms] 6.38/2.41 (8) QTRS 6.38/2.41 (9) QTRSRRRProof [EQUIVALENT, 29 ms] 6.38/2.41 (10) QTRS 6.38/2.41 (11) QTRSRRRProof [EQUIVALENT, 0 ms] 6.38/2.41 (12) QTRS 6.38/2.41 (13) RisEmptyProof [EQUIVALENT, 0 ms] 6.38/2.41 (14) YES 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (0) 6.38/2.41 Obligation: 6.38/2.41 Q restricted rewrite system: 6.38/2.41 The TRS R consists of the following rules: 6.38/2.41 6.38/2.41 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 6.38/2.41 active(__(X, nil)) -> mark(X) 6.38/2.41 active(__(nil, X)) -> mark(X) 6.38/2.41 active(and(tt, X)) -> mark(X) 6.38/2.41 active(isList(V)) -> mark(isNeList(V)) 6.38/2.41 active(isList(nil)) -> mark(tt) 6.38/2.41 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 6.38/2.41 active(isNeList(V)) -> mark(isQid(V)) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 6.38/2.41 active(isNePal(V)) -> mark(isQid(V)) 6.38/2.41 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 6.38/2.41 active(isPal(V)) -> mark(isNePal(V)) 6.38/2.41 active(isPal(nil)) -> mark(tt) 6.38/2.41 active(isQid(a)) -> mark(tt) 6.38/2.41 active(isQid(e)) -> mark(tt) 6.38/2.41 active(isQid(i)) -> mark(tt) 6.38/2.41 active(isQid(o)) -> mark(tt) 6.38/2.41 active(isQid(u)) -> mark(tt) 6.38/2.41 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.41 mark(nil) -> active(nil) 6.38/2.41 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.41 mark(tt) -> active(tt) 6.38/2.41 mark(isList(X)) -> active(isList(X)) 6.38/2.41 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.41 mark(isQid(X)) -> active(isQid(X)) 6.38/2.41 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.41 mark(isPal(X)) -> active(isPal(X)) 6.38/2.41 mark(a) -> active(a) 6.38/2.41 mark(e) -> active(e) 6.38/2.41 mark(i) -> active(i) 6.38/2.41 mark(o) -> active(o) 6.38/2.41 mark(u) -> active(u) 6.38/2.41 __(mark(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.41 __(active(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, active(X2)) -> __(X1, X2) 6.38/2.41 and(mark(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.41 and(active(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, active(X2)) -> and(X1, X2) 6.38/2.41 isList(mark(X)) -> isList(X) 6.38/2.41 isList(active(X)) -> isList(X) 6.38/2.41 isNeList(mark(X)) -> isNeList(X) 6.38/2.41 isNeList(active(X)) -> isNeList(X) 6.38/2.41 isQid(mark(X)) -> isQid(X) 6.38/2.41 isQid(active(X)) -> isQid(X) 6.38/2.41 isNePal(mark(X)) -> isNePal(X) 6.38/2.41 isNePal(active(X)) -> isNePal(X) 6.38/2.41 isPal(mark(X)) -> isPal(X) 6.38/2.41 isPal(active(X)) -> isPal(X) 6.38/2.41 6.38/2.41 The set Q consists of the following terms: 6.38/2.41 6.38/2.41 active(__(__(x0, x1), x2)) 6.38/2.41 active(__(x0, nil)) 6.38/2.41 active(__(nil, x0)) 6.38/2.41 active(and(tt, x0)) 6.38/2.41 active(isList(x0)) 6.38/2.41 active(isNeList(x0)) 6.38/2.41 active(isNePal(x0)) 6.38/2.41 active(isPal(x0)) 6.38/2.41 active(isQid(a)) 6.38/2.41 active(isQid(e)) 6.38/2.41 active(isQid(i)) 6.38/2.41 active(isQid(o)) 6.38/2.41 active(isQid(u)) 6.38/2.41 mark(__(x0, x1)) 6.38/2.41 mark(nil) 6.38/2.41 mark(and(x0, x1)) 6.38/2.41 mark(tt) 6.38/2.41 mark(isList(x0)) 6.38/2.41 mark(isNeList(x0)) 6.38/2.41 mark(isQid(x0)) 6.38/2.41 mark(isNePal(x0)) 6.38/2.41 mark(isPal(x0)) 6.38/2.41 mark(a) 6.38/2.41 mark(e) 6.38/2.41 mark(i) 6.38/2.41 mark(o) 6.38/2.41 mark(u) 6.38/2.41 __(mark(x0), x1) 6.38/2.41 __(x0, mark(x1)) 6.38/2.41 __(active(x0), x1) 6.38/2.41 __(x0, active(x1)) 6.38/2.41 and(mark(x0), x1) 6.38/2.41 and(x0, mark(x1)) 6.38/2.41 and(active(x0), x1) 6.38/2.41 and(x0, active(x1)) 6.38/2.41 isList(mark(x0)) 6.38/2.41 isList(active(x0)) 6.38/2.41 isNeList(mark(x0)) 6.38/2.41 isNeList(active(x0)) 6.38/2.41 isQid(mark(x0)) 6.38/2.41 isQid(active(x0)) 6.38/2.41 isNePal(mark(x0)) 6.38/2.41 isNePal(active(x0)) 6.38/2.41 isPal(mark(x0)) 6.38/2.41 isPal(active(x0)) 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (1) QTRSRRRProof (EQUIVALENT) 6.38/2.41 Used ordering: 6.38/2.41 Polynomial interpretation [POLO]: 6.38/2.41 6.38/2.41 POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 6.38/2.41 POL(a) = 2 6.38/2.41 POL(active(x_1)) = x_1 6.38/2.41 POL(and(x_1, x_2)) = x_1 + x_2 6.38/2.41 POL(e) = 0 6.38/2.41 POL(i) = 1 6.38/2.41 POL(isList(x_1)) = 2 + x_1 6.38/2.41 POL(isNeList(x_1)) = x_1 6.38/2.41 POL(isNePal(x_1)) = x_1 6.38/2.41 POL(isPal(x_1)) = 2*x_1 6.38/2.41 POL(isQid(x_1)) = x_1 6.38/2.41 POL(mark(x_1)) = x_1 6.38/2.41 POL(nil) = 0 6.38/2.41 POL(o) = 1 6.38/2.41 POL(tt) = 0 6.38/2.41 POL(u) = 0 6.38/2.41 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.41 6.38/2.41 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 6.38/2.41 active(__(X, nil)) -> mark(X) 6.38/2.41 active(__(nil, X)) -> mark(X) 6.38/2.41 active(isList(V)) -> mark(isNeList(V)) 6.38/2.41 active(isList(nil)) -> mark(tt) 6.38/2.41 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 6.38/2.41 active(isQid(a)) -> mark(tt) 6.38/2.41 active(isQid(i)) -> mark(tt) 6.38/2.41 active(isQid(o)) -> mark(tt) 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (2) 6.38/2.41 Obligation: 6.38/2.41 Q restricted rewrite system: 6.38/2.41 The TRS R consists of the following rules: 6.38/2.41 6.38/2.41 active(and(tt, X)) -> mark(X) 6.38/2.41 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 6.38/2.41 active(isNeList(V)) -> mark(isQid(V)) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 6.38/2.41 active(isNePal(V)) -> mark(isQid(V)) 6.38/2.41 active(isPal(V)) -> mark(isNePal(V)) 6.38/2.41 active(isPal(nil)) -> mark(tt) 6.38/2.41 active(isQid(e)) -> mark(tt) 6.38/2.41 active(isQid(u)) -> mark(tt) 6.38/2.41 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.41 mark(nil) -> active(nil) 6.38/2.41 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.41 mark(tt) -> active(tt) 6.38/2.41 mark(isList(X)) -> active(isList(X)) 6.38/2.41 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.41 mark(isQid(X)) -> active(isQid(X)) 6.38/2.41 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.41 mark(isPal(X)) -> active(isPal(X)) 6.38/2.41 mark(a) -> active(a) 6.38/2.41 mark(e) -> active(e) 6.38/2.41 mark(i) -> active(i) 6.38/2.41 mark(o) -> active(o) 6.38/2.41 mark(u) -> active(u) 6.38/2.41 __(mark(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.41 __(active(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, active(X2)) -> __(X1, X2) 6.38/2.41 and(mark(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.41 and(active(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, active(X2)) -> and(X1, X2) 6.38/2.41 isList(mark(X)) -> isList(X) 6.38/2.41 isList(active(X)) -> isList(X) 6.38/2.41 isNeList(mark(X)) -> isNeList(X) 6.38/2.41 isNeList(active(X)) -> isNeList(X) 6.38/2.41 isQid(mark(X)) -> isQid(X) 6.38/2.41 isQid(active(X)) -> isQid(X) 6.38/2.41 isNePal(mark(X)) -> isNePal(X) 6.38/2.41 isNePal(active(X)) -> isNePal(X) 6.38/2.41 isPal(mark(X)) -> isPal(X) 6.38/2.41 isPal(active(X)) -> isPal(X) 6.38/2.41 6.38/2.41 The set Q consists of the following terms: 6.38/2.41 6.38/2.41 active(__(__(x0, x1), x2)) 6.38/2.41 active(__(x0, nil)) 6.38/2.41 active(__(nil, x0)) 6.38/2.41 active(and(tt, x0)) 6.38/2.41 active(isList(x0)) 6.38/2.41 active(isNeList(x0)) 6.38/2.41 active(isNePal(x0)) 6.38/2.41 active(isPal(x0)) 6.38/2.41 active(isQid(a)) 6.38/2.41 active(isQid(e)) 6.38/2.41 active(isQid(i)) 6.38/2.41 active(isQid(o)) 6.38/2.41 active(isQid(u)) 6.38/2.41 mark(__(x0, x1)) 6.38/2.41 mark(nil) 6.38/2.41 mark(and(x0, x1)) 6.38/2.41 mark(tt) 6.38/2.41 mark(isList(x0)) 6.38/2.41 mark(isNeList(x0)) 6.38/2.41 mark(isQid(x0)) 6.38/2.41 mark(isNePal(x0)) 6.38/2.41 mark(isPal(x0)) 6.38/2.41 mark(a) 6.38/2.41 mark(e) 6.38/2.41 mark(i) 6.38/2.41 mark(o) 6.38/2.41 mark(u) 6.38/2.41 __(mark(x0), x1) 6.38/2.41 __(x0, mark(x1)) 6.38/2.41 __(active(x0), x1) 6.38/2.41 __(x0, active(x1)) 6.38/2.41 and(mark(x0), x1) 6.38/2.41 and(x0, mark(x1)) 6.38/2.41 and(active(x0), x1) 6.38/2.41 and(x0, active(x1)) 6.38/2.41 isList(mark(x0)) 6.38/2.41 isList(active(x0)) 6.38/2.41 isNeList(mark(x0)) 6.38/2.41 isNeList(active(x0)) 6.38/2.41 isQid(mark(x0)) 6.38/2.41 isQid(active(x0)) 6.38/2.41 isNePal(mark(x0)) 6.38/2.41 isNePal(active(x0)) 6.38/2.41 isPal(mark(x0)) 6.38/2.41 isPal(active(x0)) 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (3) QTRSRRRProof (EQUIVALENT) 6.38/2.41 Used ordering: 6.38/2.41 Polynomial interpretation [POLO]: 6.38/2.41 6.38/2.41 POL(__(x_1, x_2)) = 2*x_1 + x_2 6.38/2.41 POL(a) = 0 6.38/2.41 POL(active(x_1)) = x_1 6.38/2.41 POL(and(x_1, x_2)) = x_1 + x_2 6.38/2.41 POL(e) = 2 6.38/2.41 POL(i) = 0 6.38/2.41 POL(isList(x_1)) = x_1 6.38/2.41 POL(isNeList(x_1)) = x_1 6.38/2.41 POL(isNePal(x_1)) = 2*x_1 6.38/2.41 POL(isPal(x_1)) = 2*x_1 6.38/2.41 POL(isQid(x_1)) = x_1 6.38/2.41 POL(mark(x_1)) = x_1 6.38/2.41 POL(nil) = 0 6.38/2.41 POL(o) = 0 6.38/2.41 POL(tt) = 0 6.38/2.41 POL(u) = 0 6.38/2.41 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.41 6.38/2.41 active(isQid(e)) -> mark(tt) 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (4) 6.38/2.41 Obligation: 6.38/2.41 Q restricted rewrite system: 6.38/2.41 The TRS R consists of the following rules: 6.38/2.41 6.38/2.41 active(and(tt, X)) -> mark(X) 6.38/2.41 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 6.38/2.41 active(isNeList(V)) -> mark(isQid(V)) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 6.38/2.41 active(isNePal(V)) -> mark(isQid(V)) 6.38/2.41 active(isPal(V)) -> mark(isNePal(V)) 6.38/2.41 active(isPal(nil)) -> mark(tt) 6.38/2.41 active(isQid(u)) -> mark(tt) 6.38/2.41 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.41 mark(nil) -> active(nil) 6.38/2.41 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.41 mark(tt) -> active(tt) 6.38/2.41 mark(isList(X)) -> active(isList(X)) 6.38/2.41 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.41 mark(isQid(X)) -> active(isQid(X)) 6.38/2.41 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.41 mark(isPal(X)) -> active(isPal(X)) 6.38/2.41 mark(a) -> active(a) 6.38/2.41 mark(e) -> active(e) 6.38/2.41 mark(i) -> active(i) 6.38/2.41 mark(o) -> active(o) 6.38/2.41 mark(u) -> active(u) 6.38/2.41 __(mark(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.41 __(active(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, active(X2)) -> __(X1, X2) 6.38/2.41 and(mark(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.41 and(active(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, active(X2)) -> and(X1, X2) 6.38/2.41 isList(mark(X)) -> isList(X) 6.38/2.41 isList(active(X)) -> isList(X) 6.38/2.41 isNeList(mark(X)) -> isNeList(X) 6.38/2.41 isNeList(active(X)) -> isNeList(X) 6.38/2.41 isQid(mark(X)) -> isQid(X) 6.38/2.41 isQid(active(X)) -> isQid(X) 6.38/2.41 isNePal(mark(X)) -> isNePal(X) 6.38/2.41 isNePal(active(X)) -> isNePal(X) 6.38/2.41 isPal(mark(X)) -> isPal(X) 6.38/2.41 isPal(active(X)) -> isPal(X) 6.38/2.41 6.38/2.41 The set Q consists of the following terms: 6.38/2.41 6.38/2.41 active(__(__(x0, x1), x2)) 6.38/2.41 active(__(x0, nil)) 6.38/2.41 active(__(nil, x0)) 6.38/2.41 active(and(tt, x0)) 6.38/2.41 active(isList(x0)) 6.38/2.41 active(isNeList(x0)) 6.38/2.41 active(isNePal(x0)) 6.38/2.41 active(isPal(x0)) 6.38/2.41 active(isQid(a)) 6.38/2.41 active(isQid(e)) 6.38/2.41 active(isQid(i)) 6.38/2.41 active(isQid(o)) 6.38/2.41 active(isQid(u)) 6.38/2.41 mark(__(x0, x1)) 6.38/2.41 mark(nil) 6.38/2.41 mark(and(x0, x1)) 6.38/2.41 mark(tt) 6.38/2.41 mark(isList(x0)) 6.38/2.41 mark(isNeList(x0)) 6.38/2.41 mark(isQid(x0)) 6.38/2.41 mark(isNePal(x0)) 6.38/2.41 mark(isPal(x0)) 6.38/2.41 mark(a) 6.38/2.41 mark(e) 6.38/2.41 mark(i) 6.38/2.41 mark(o) 6.38/2.41 mark(u) 6.38/2.41 __(mark(x0), x1) 6.38/2.41 __(x0, mark(x1)) 6.38/2.41 __(active(x0), x1) 6.38/2.41 __(x0, active(x1)) 6.38/2.41 and(mark(x0), x1) 6.38/2.41 and(x0, mark(x1)) 6.38/2.41 and(active(x0), x1) 6.38/2.41 and(x0, active(x1)) 6.38/2.41 isList(mark(x0)) 6.38/2.41 isList(active(x0)) 6.38/2.41 isNeList(mark(x0)) 6.38/2.41 isNeList(active(x0)) 6.38/2.41 isQid(mark(x0)) 6.38/2.41 isQid(active(x0)) 6.38/2.41 isNePal(mark(x0)) 6.38/2.41 isNePal(active(x0)) 6.38/2.41 isPal(mark(x0)) 6.38/2.41 isPal(active(x0)) 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (5) QTRSRRRProof (EQUIVALENT) 6.38/2.41 Used ordering: 6.38/2.41 Polynomial interpretation [POLO]: 6.38/2.41 6.38/2.41 POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 6.38/2.41 POL(a) = 0 6.38/2.41 POL(active(x_1)) = x_1 6.38/2.41 POL(and(x_1, x_2)) = x_1 + x_2 6.38/2.41 POL(e) = 0 6.38/2.41 POL(i) = 0 6.38/2.41 POL(isList(x_1)) = 1 + 2*x_1 6.38/2.41 POL(isNeList(x_1)) = 1 + 2*x_1 6.38/2.41 POL(isNePal(x_1)) = 2 + 2*x_1 6.38/2.41 POL(isPal(x_1)) = 2 + 2*x_1 6.38/2.41 POL(isQid(x_1)) = 2*x_1 6.38/2.41 POL(mark(x_1)) = x_1 6.38/2.41 POL(nil) = 2 6.38/2.41 POL(o) = 0 6.38/2.41 POL(tt) = 2 6.38/2.41 POL(u) = 2 6.38/2.41 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.41 6.38/2.41 active(and(tt, X)) -> mark(X) 6.38/2.41 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 6.38/2.41 active(isNeList(V)) -> mark(isQid(V)) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 6.38/2.41 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 6.38/2.41 active(isNePal(V)) -> mark(isQid(V)) 6.38/2.41 active(isPal(nil)) -> mark(tt) 6.38/2.41 active(isQid(u)) -> mark(tt) 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (6) 6.38/2.41 Obligation: 6.38/2.41 Q restricted rewrite system: 6.38/2.41 The TRS R consists of the following rules: 6.38/2.41 6.38/2.41 active(isPal(V)) -> mark(isNePal(V)) 6.38/2.41 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.41 mark(nil) -> active(nil) 6.38/2.41 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.41 mark(tt) -> active(tt) 6.38/2.41 mark(isList(X)) -> active(isList(X)) 6.38/2.41 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.41 mark(isQid(X)) -> active(isQid(X)) 6.38/2.41 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.41 mark(isPal(X)) -> active(isPal(X)) 6.38/2.41 mark(a) -> active(a) 6.38/2.41 mark(e) -> active(e) 6.38/2.41 mark(i) -> active(i) 6.38/2.41 mark(o) -> active(o) 6.38/2.41 mark(u) -> active(u) 6.38/2.41 __(mark(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.41 __(active(X1), X2) -> __(X1, X2) 6.38/2.41 __(X1, active(X2)) -> __(X1, X2) 6.38/2.41 and(mark(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.41 and(active(X1), X2) -> and(X1, X2) 6.38/2.41 and(X1, active(X2)) -> and(X1, X2) 6.38/2.41 isList(mark(X)) -> isList(X) 6.38/2.41 isList(active(X)) -> isList(X) 6.38/2.41 isNeList(mark(X)) -> isNeList(X) 6.38/2.41 isNeList(active(X)) -> isNeList(X) 6.38/2.41 isQid(mark(X)) -> isQid(X) 6.38/2.41 isQid(active(X)) -> isQid(X) 6.38/2.41 isNePal(mark(X)) -> isNePal(X) 6.38/2.41 isNePal(active(X)) -> isNePal(X) 6.38/2.41 isPal(mark(X)) -> isPal(X) 6.38/2.41 isPal(active(X)) -> isPal(X) 6.38/2.41 6.38/2.41 The set Q consists of the following terms: 6.38/2.41 6.38/2.41 active(__(__(x0, x1), x2)) 6.38/2.41 active(__(x0, nil)) 6.38/2.41 active(__(nil, x0)) 6.38/2.41 active(and(tt, x0)) 6.38/2.41 active(isList(x0)) 6.38/2.41 active(isNeList(x0)) 6.38/2.41 active(isNePal(x0)) 6.38/2.41 active(isPal(x0)) 6.38/2.41 active(isQid(a)) 6.38/2.41 active(isQid(e)) 6.38/2.41 active(isQid(i)) 6.38/2.41 active(isQid(o)) 6.38/2.41 active(isQid(u)) 6.38/2.41 mark(__(x0, x1)) 6.38/2.41 mark(nil) 6.38/2.41 mark(and(x0, x1)) 6.38/2.41 mark(tt) 6.38/2.41 mark(isList(x0)) 6.38/2.41 mark(isNeList(x0)) 6.38/2.41 mark(isQid(x0)) 6.38/2.41 mark(isNePal(x0)) 6.38/2.41 mark(isPal(x0)) 6.38/2.41 mark(a) 6.38/2.41 mark(e) 6.38/2.41 mark(i) 6.38/2.41 mark(o) 6.38/2.41 mark(u) 6.38/2.41 __(mark(x0), x1) 6.38/2.41 __(x0, mark(x1)) 6.38/2.41 __(active(x0), x1) 6.38/2.41 __(x0, active(x1)) 6.38/2.41 and(mark(x0), x1) 6.38/2.41 and(x0, mark(x1)) 6.38/2.41 and(active(x0), x1) 6.38/2.41 and(x0, active(x1)) 6.38/2.41 isList(mark(x0)) 6.38/2.41 isList(active(x0)) 6.38/2.41 isNeList(mark(x0)) 6.38/2.41 isNeList(active(x0)) 6.38/2.41 isQid(mark(x0)) 6.38/2.41 isQid(active(x0)) 6.38/2.41 isNePal(mark(x0)) 6.38/2.41 isNePal(active(x0)) 6.38/2.41 isPal(mark(x0)) 6.38/2.41 isPal(active(x0)) 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.41 6.38/2.41 (7) QTRSRRRProof (EQUIVALENT) 6.38/2.41 Used ordering: 6.38/2.41 Polynomial interpretation [POLO]: 6.38/2.41 6.38/2.41 POL(__(x_1, x_2)) = 2*x_1 + 2*x_2 6.38/2.41 POL(a) = 0 6.38/2.41 POL(active(x_1)) = x_1 6.38/2.41 POL(and(x_1, x_2)) = x_1 + x_2 6.38/2.41 POL(e) = 0 6.38/2.41 POL(i) = 0 6.38/2.41 POL(isList(x_1)) = 2*x_1 6.38/2.41 POL(isNeList(x_1)) = 2*x_1 6.38/2.41 POL(isNePal(x_1)) = 1 + x_1 6.38/2.41 POL(isPal(x_1)) = 2 + x_1 6.38/2.41 POL(isQid(x_1)) = 2*x_1 6.38/2.41 POL(mark(x_1)) = x_1 6.38/2.41 POL(nil) = 0 6.38/2.41 POL(o) = 0 6.38/2.41 POL(tt) = 0 6.38/2.41 POL(u) = 0 6.38/2.41 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.41 6.38/2.41 active(isPal(V)) -> mark(isNePal(V)) 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 6.38/2.41 ---------------------------------------- 6.38/2.42 6.38/2.42 (8) 6.38/2.42 Obligation: 6.38/2.42 Q restricted rewrite system: 6.38/2.42 The TRS R consists of the following rules: 6.38/2.42 6.38/2.42 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.42 mark(nil) -> active(nil) 6.38/2.42 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.42 mark(tt) -> active(tt) 6.38/2.42 mark(isList(X)) -> active(isList(X)) 6.38/2.42 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.42 mark(isQid(X)) -> active(isQid(X)) 6.38/2.42 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.42 mark(isPal(X)) -> active(isPal(X)) 6.38/2.42 mark(a) -> active(a) 6.38/2.42 mark(e) -> active(e) 6.38/2.42 mark(i) -> active(i) 6.38/2.42 mark(o) -> active(o) 6.38/2.42 mark(u) -> active(u) 6.38/2.42 __(mark(X1), X2) -> __(X1, X2) 6.38/2.42 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.42 __(active(X1), X2) -> __(X1, X2) 6.38/2.42 __(X1, active(X2)) -> __(X1, X2) 6.38/2.42 and(mark(X1), X2) -> and(X1, X2) 6.38/2.42 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.42 and(active(X1), X2) -> and(X1, X2) 6.38/2.42 and(X1, active(X2)) -> and(X1, X2) 6.38/2.42 isList(mark(X)) -> isList(X) 6.38/2.42 isList(active(X)) -> isList(X) 6.38/2.42 isNeList(mark(X)) -> isNeList(X) 6.38/2.42 isNeList(active(X)) -> isNeList(X) 6.38/2.42 isQid(mark(X)) -> isQid(X) 6.38/2.42 isQid(active(X)) -> isQid(X) 6.38/2.42 isNePal(mark(X)) -> isNePal(X) 6.38/2.42 isNePal(active(X)) -> isNePal(X) 6.38/2.42 isPal(mark(X)) -> isPal(X) 6.38/2.42 isPal(active(X)) -> isPal(X) 6.38/2.42 6.38/2.42 The set Q consists of the following terms: 6.38/2.42 6.38/2.42 active(__(__(x0, x1), x2)) 6.38/2.42 active(__(x0, nil)) 6.38/2.42 active(__(nil, x0)) 6.38/2.42 active(and(tt, x0)) 6.38/2.42 active(isList(x0)) 6.38/2.42 active(isNeList(x0)) 6.38/2.42 active(isNePal(x0)) 6.38/2.42 active(isPal(x0)) 6.38/2.42 active(isQid(a)) 6.38/2.42 active(isQid(e)) 6.38/2.42 active(isQid(i)) 6.38/2.42 active(isQid(o)) 6.38/2.42 active(isQid(u)) 6.38/2.42 mark(__(x0, x1)) 6.38/2.42 mark(nil) 6.38/2.42 mark(and(x0, x1)) 6.38/2.42 mark(tt) 6.38/2.42 mark(isList(x0)) 6.38/2.42 mark(isNeList(x0)) 6.38/2.42 mark(isQid(x0)) 6.38/2.42 mark(isNePal(x0)) 6.38/2.42 mark(isPal(x0)) 6.38/2.42 mark(a) 6.38/2.42 mark(e) 6.38/2.42 mark(i) 6.38/2.42 mark(o) 6.38/2.42 mark(u) 6.38/2.42 __(mark(x0), x1) 6.38/2.42 __(x0, mark(x1)) 6.38/2.42 __(active(x0), x1) 6.38/2.42 __(x0, active(x1)) 6.38/2.42 and(mark(x0), x1) 6.38/2.42 and(x0, mark(x1)) 6.38/2.42 and(active(x0), x1) 6.38/2.42 and(x0, active(x1)) 6.38/2.42 isList(mark(x0)) 6.38/2.42 isList(active(x0)) 6.38/2.42 isNeList(mark(x0)) 6.38/2.42 isNeList(active(x0)) 6.38/2.42 isQid(mark(x0)) 6.38/2.42 isQid(active(x0)) 6.38/2.42 isNePal(mark(x0)) 6.38/2.42 isNePal(active(x0)) 6.38/2.42 isPal(mark(x0)) 6.38/2.42 isPal(active(x0)) 6.38/2.42 6.38/2.42 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (9) QTRSRRRProof (EQUIVALENT) 6.38/2.42 Used ordering: 6.38/2.42 Polynomial interpretation [POLO]: 6.38/2.42 6.38/2.42 POL(__(x_1, x_2)) = 2 + x_1 + x_2 6.38/2.42 POL(a) = 2 6.38/2.42 POL(active(x_1)) = x_1 6.38/2.42 POL(and(x_1, x_2)) = 1 + x_1 + x_2 6.38/2.42 POL(e) = 2 6.38/2.42 POL(i) = 2 6.38/2.42 POL(isList(x_1)) = 2 + x_1 6.38/2.42 POL(isNeList(x_1)) = 2 + x_1 6.38/2.42 POL(isNePal(x_1)) = 2 + x_1 6.38/2.42 POL(isPal(x_1)) = 2 + x_1 6.38/2.42 POL(isQid(x_1)) = 2 + x_1 6.38/2.42 POL(mark(x_1)) = 1 + 2*x_1 6.38/2.42 POL(nil) = 2 6.38/2.42 POL(o) = 1 6.38/2.42 POL(tt) = 2 6.38/2.42 POL(u) = 2 6.38/2.42 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.42 6.38/2.42 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 6.38/2.42 mark(nil) -> active(nil) 6.38/2.42 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 6.38/2.42 mark(tt) -> active(tt) 6.38/2.42 mark(isList(X)) -> active(isList(X)) 6.38/2.42 mark(isNeList(X)) -> active(isNeList(X)) 6.38/2.42 mark(isQid(X)) -> active(isQid(X)) 6.38/2.42 mark(isNePal(X)) -> active(isNePal(X)) 6.38/2.42 mark(isPal(X)) -> active(isPal(X)) 6.38/2.42 mark(a) -> active(a) 6.38/2.42 mark(e) -> active(e) 6.38/2.42 mark(i) -> active(i) 6.38/2.42 mark(o) -> active(o) 6.38/2.42 mark(u) -> active(u) 6.38/2.42 __(mark(X1), X2) -> __(X1, X2) 6.38/2.42 __(X1, mark(X2)) -> __(X1, X2) 6.38/2.42 and(mark(X1), X2) -> and(X1, X2) 6.38/2.42 and(X1, mark(X2)) -> and(X1, X2) 6.38/2.42 isList(mark(X)) -> isList(X) 6.38/2.42 isNeList(mark(X)) -> isNeList(X) 6.38/2.42 isQid(mark(X)) -> isQid(X) 6.38/2.42 isNePal(mark(X)) -> isNePal(X) 6.38/2.42 isPal(mark(X)) -> isPal(X) 6.38/2.42 6.38/2.42 6.38/2.42 6.38/2.42 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (10) 6.38/2.42 Obligation: 6.38/2.42 Q restricted rewrite system: 6.38/2.42 The TRS R consists of the following rules: 6.38/2.42 6.38/2.42 __(active(X1), X2) -> __(X1, X2) 6.38/2.42 __(X1, active(X2)) -> __(X1, X2) 6.38/2.42 and(active(X1), X2) -> and(X1, X2) 6.38/2.42 and(X1, active(X2)) -> and(X1, X2) 6.38/2.42 isList(active(X)) -> isList(X) 6.38/2.42 isNeList(active(X)) -> isNeList(X) 6.38/2.42 isQid(active(X)) -> isQid(X) 6.38/2.42 isNePal(active(X)) -> isNePal(X) 6.38/2.42 isPal(active(X)) -> isPal(X) 6.38/2.42 6.38/2.42 The set Q consists of the following terms: 6.38/2.42 6.38/2.42 active(__(__(x0, x1), x2)) 6.38/2.42 active(__(x0, nil)) 6.38/2.42 active(__(nil, x0)) 6.38/2.42 active(and(tt, x0)) 6.38/2.42 active(isList(x0)) 6.38/2.42 active(isNeList(x0)) 6.38/2.42 active(isNePal(x0)) 6.38/2.42 active(isPal(x0)) 6.38/2.42 active(isQid(a)) 6.38/2.42 active(isQid(e)) 6.38/2.42 active(isQid(i)) 6.38/2.42 active(isQid(o)) 6.38/2.42 active(isQid(u)) 6.38/2.42 mark(__(x0, x1)) 6.38/2.42 mark(nil) 6.38/2.42 mark(and(x0, x1)) 6.38/2.42 mark(tt) 6.38/2.42 mark(isList(x0)) 6.38/2.42 mark(isNeList(x0)) 6.38/2.42 mark(isQid(x0)) 6.38/2.42 mark(isNePal(x0)) 6.38/2.42 mark(isPal(x0)) 6.38/2.42 mark(a) 6.38/2.42 mark(e) 6.38/2.42 mark(i) 6.38/2.42 mark(o) 6.38/2.42 mark(u) 6.38/2.42 __(mark(x0), x1) 6.38/2.42 __(x0, mark(x1)) 6.38/2.42 __(active(x0), x1) 6.38/2.42 __(x0, active(x1)) 6.38/2.42 and(mark(x0), x1) 6.38/2.42 and(x0, mark(x1)) 6.38/2.42 and(active(x0), x1) 6.38/2.42 and(x0, active(x1)) 6.38/2.42 isList(mark(x0)) 6.38/2.42 isList(active(x0)) 6.38/2.42 isNeList(mark(x0)) 6.38/2.42 isNeList(active(x0)) 6.38/2.42 isQid(mark(x0)) 6.38/2.42 isQid(active(x0)) 6.38/2.42 isNePal(mark(x0)) 6.38/2.42 isNePal(active(x0)) 6.38/2.42 isPal(mark(x0)) 6.38/2.42 isPal(active(x0)) 6.38/2.42 6.38/2.42 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (11) QTRSRRRProof (EQUIVALENT) 6.38/2.42 Used ordering: 6.38/2.42 Knuth-Bendix order [KBO] with precedence:active_1 > isPal_1 > isNePal_1 > isQid_1 > isNeList_1 > isList_1 > and_2 > ___2 6.38/2.42 6.38/2.42 and weight map: 6.38/2.42 6.38/2.42 active_1=0 6.38/2.42 isList_1=1 6.38/2.42 isNeList_1=1 6.38/2.42 isQid_1=1 6.38/2.42 isNePal_1=1 6.38/2.42 isPal_1=1 6.38/2.42 ___2=0 6.38/2.42 and_2=0 6.38/2.42 6.38/2.42 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.38/2.42 6.38/2.42 __(active(X1), X2) -> __(X1, X2) 6.38/2.42 __(X1, active(X2)) -> __(X1, X2) 6.38/2.42 and(active(X1), X2) -> and(X1, X2) 6.38/2.42 and(X1, active(X2)) -> and(X1, X2) 6.38/2.42 isList(active(X)) -> isList(X) 6.38/2.42 isNeList(active(X)) -> isNeList(X) 6.38/2.42 isQid(active(X)) -> isQid(X) 6.38/2.42 isNePal(active(X)) -> isNePal(X) 6.38/2.42 isPal(active(X)) -> isPal(X) 6.38/2.42 6.38/2.42 6.38/2.42 6.38/2.42 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (12) 6.38/2.42 Obligation: 6.38/2.42 Q restricted rewrite system: 6.38/2.42 R is empty. 6.38/2.42 The set Q consists of the following terms: 6.38/2.42 6.38/2.42 active(__(__(x0, x1), x2)) 6.38/2.42 active(__(x0, nil)) 6.38/2.42 active(__(nil, x0)) 6.38/2.42 active(and(tt, x0)) 6.38/2.42 active(isList(x0)) 6.38/2.42 active(isNeList(x0)) 6.38/2.42 active(isNePal(x0)) 6.38/2.42 active(isPal(x0)) 6.38/2.42 active(isQid(a)) 6.38/2.42 active(isQid(e)) 6.38/2.42 active(isQid(i)) 6.38/2.42 active(isQid(o)) 6.38/2.42 active(isQid(u)) 6.38/2.42 mark(__(x0, x1)) 6.38/2.42 mark(nil) 6.38/2.42 mark(and(x0, x1)) 6.38/2.42 mark(tt) 6.38/2.42 mark(isList(x0)) 6.38/2.42 mark(isNeList(x0)) 6.38/2.42 mark(isQid(x0)) 6.38/2.42 mark(isNePal(x0)) 6.38/2.42 mark(isPal(x0)) 6.38/2.42 mark(a) 6.38/2.42 mark(e) 6.38/2.42 mark(i) 6.38/2.42 mark(o) 6.38/2.42 mark(u) 6.38/2.42 __(mark(x0), x1) 6.38/2.42 __(x0, mark(x1)) 6.38/2.42 __(active(x0), x1) 6.38/2.42 __(x0, active(x1)) 6.38/2.42 and(mark(x0), x1) 6.38/2.42 and(x0, mark(x1)) 6.38/2.42 and(active(x0), x1) 6.38/2.42 and(x0, active(x1)) 6.38/2.42 isList(mark(x0)) 6.38/2.42 isList(active(x0)) 6.38/2.42 isNeList(mark(x0)) 6.38/2.42 isNeList(active(x0)) 6.38/2.42 isQid(mark(x0)) 6.38/2.42 isQid(active(x0)) 6.38/2.42 isNePal(mark(x0)) 6.38/2.42 isNePal(active(x0)) 6.38/2.42 isPal(mark(x0)) 6.38/2.42 isPal(active(x0)) 6.38/2.42 6.38/2.42 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (13) RisEmptyProof (EQUIVALENT) 6.38/2.42 The TRS R is empty. Hence, termination is trivially proven. 6.38/2.42 ---------------------------------------- 6.38/2.42 6.38/2.42 (14) 6.38/2.42 YES 6.46/2.44 EOF