15.11/4.73 YES 15.11/4.75 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 15.11/4.75 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.11/4.75 15.11/4.75 15.11/4.75 Termination w.r.t. Q of the given QTRS could be proven: 15.11/4.75 15.11/4.75 (0) QTRS 15.11/4.75 (1) QTRSRRRProof [EQUIVALENT, 379 ms] 15.11/4.75 (2) QTRS 15.11/4.75 (3) QTRSRRRProof [EQUIVALENT, 202 ms] 15.11/4.75 (4) QTRS 15.11/4.75 (5) QTRSRRRProof [EQUIVALENT, 197 ms] 15.11/4.75 (6) QTRS 15.11/4.75 (7) QTRSRRRProof [EQUIVALENT, 158 ms] 15.11/4.75 (8) QTRS 15.11/4.75 (9) QTRSRRRProof [EQUIVALENT, 109 ms] 15.11/4.75 (10) QTRS 15.11/4.75 (11) QTRSRRRProof [EQUIVALENT, 110 ms] 15.11/4.75 (12) QTRS 15.11/4.75 (13) QTRSRRRProof [EQUIVALENT, 188 ms] 15.11/4.75 (14) QTRS 15.11/4.75 (15) QTRSRRRProof [EQUIVALENT, 114 ms] 15.11/4.75 (16) QTRS 15.11/4.75 (17) QTRSRRRProof [EQUIVALENT, 107 ms] 15.11/4.75 (18) QTRS 15.11/4.75 (19) QTRSRRRProof [EQUIVALENT, 94 ms] 15.11/4.75 (20) QTRS 15.11/4.75 (21) QTRSRRRProof [EQUIVALENT, 19 ms] 15.11/4.75 (22) QTRS 15.11/4.75 (23) QTRSRRRProof [EQUIVALENT, 6 ms] 15.11/4.75 (24) QTRS 15.11/4.75 (25) QTRSRRRProof [EQUIVALENT, 0 ms] 15.11/4.75 (26) QTRS 15.11/4.75 (27) QTRSRRRProof [EQUIVALENT, 0 ms] 15.11/4.75 (28) QTRS 15.11/4.75 (29) QTRSRRRProof [EQUIVALENT, 3 ms] 15.11/4.75 (30) QTRS 15.11/4.75 (31) RisEmptyProof [EQUIVALENT, 0 ms] 15.11/4.75 (32) YES 15.11/4.75 15.11/4.75 15.11/4.75 ---------------------------------------- 15.11/4.75 15.11/4.75 (0) 15.11/4.75 Obligation: 15.11/4.75 Q restricted rewrite system: 15.11/4.75 The TRS R consists of the following rules: 15.11/4.75 15.11/4.75 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 15.11/4.75 active(__(X, nil)) -> mark(X) 15.11/4.75 active(__(nil, X)) -> mark(X) 15.11/4.75 active(U11(tt)) -> mark(tt) 15.11/4.75 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.75 active(U22(tt)) -> mark(tt) 15.11/4.75 active(U31(tt)) -> mark(tt) 15.11/4.75 active(U41(tt, V2)) -> mark(U42(isNeList(V2))) 15.11/4.75 active(U42(tt)) -> mark(tt) 15.11/4.75 active(U51(tt, V2)) -> mark(U52(isList(V2))) 15.11/4.75 active(U52(tt)) -> mark(tt) 15.11/4.75 active(U61(tt)) -> mark(tt) 15.11/4.75 active(U71(tt, P)) -> mark(U72(isPal(P))) 15.11/4.75 active(U72(tt)) -> mark(tt) 15.11/4.75 active(U81(tt)) -> mark(tt) 15.11/4.75 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.75 active(isList(nil)) -> mark(tt) 15.11/4.75 active(isList(__(V1, V2))) -> mark(U21(isList(V1), V2)) 15.11/4.75 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.75 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.75 active(isNeList(__(V1, V2))) -> mark(U51(isNeList(V1), V2)) 15.11/4.75 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.75 active(isNePal(__(I, __(P, I)))) -> mark(U71(isQid(I), P)) 15.11/4.75 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.75 active(isPal(nil)) -> mark(tt) 15.11/4.75 active(isQid(a)) -> mark(tt) 15.11/4.75 active(isQid(e)) -> mark(tt) 15.11/4.75 active(isQid(i)) -> mark(tt) 15.11/4.75 active(isQid(o)) -> mark(tt) 15.11/4.75 active(isQid(u)) -> mark(tt) 15.11/4.75 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.75 mark(nil) -> active(nil) 15.11/4.75 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.75 mark(tt) -> active(tt) 15.11/4.75 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.75 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.75 mark(isList(X)) -> active(isList(X)) 15.11/4.75 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.75 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.75 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.75 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.75 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.75 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.75 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.75 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.75 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.75 mark(isPal(X)) -> active(isPal(X)) 15.11/4.75 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.75 mark(isQid(X)) -> active(isQid(X)) 15.11/4.75 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.75 mark(a) -> active(a) 15.11/4.75 mark(e) -> active(e) 15.11/4.75 mark(i) -> active(i) 15.11/4.75 mark(o) -> active(o) 15.11/4.75 mark(u) -> active(u) 15.11/4.75 __(mark(X1), X2) -> __(X1, X2) 15.11/4.75 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.75 __(active(X1), X2) -> __(X1, X2) 15.11/4.75 __(X1, active(X2)) -> __(X1, X2) 15.11/4.75 U11(mark(X)) -> U11(X) 15.11/4.75 U11(active(X)) -> U11(X) 15.11/4.75 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.75 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.75 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.75 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.75 U22(mark(X)) -> U22(X) 15.11/4.75 U22(active(X)) -> U22(X) 15.11/4.75 isList(mark(X)) -> isList(X) 15.11/4.75 isList(active(X)) -> isList(X) 15.11/4.75 U31(mark(X)) -> U31(X) 15.11/4.75 U31(active(X)) -> U31(X) 15.11/4.75 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.75 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.75 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.75 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.75 U42(mark(X)) -> U42(X) 15.11/4.75 U42(active(X)) -> U42(X) 15.11/4.75 isNeList(mark(X)) -> isNeList(X) 15.11/4.75 isNeList(active(X)) -> isNeList(X) 15.11/4.75 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.75 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.75 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.75 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.75 U52(mark(X)) -> U52(X) 15.11/4.75 U52(active(X)) -> U52(X) 15.11/4.75 U61(mark(X)) -> U61(X) 15.11/4.75 U61(active(X)) -> U61(X) 15.11/4.75 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.75 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.75 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.75 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.75 U72(mark(X)) -> U72(X) 15.11/4.75 U72(active(X)) -> U72(X) 15.11/4.75 isPal(mark(X)) -> isPal(X) 15.11/4.75 isPal(active(X)) -> isPal(X) 15.11/4.75 U81(mark(X)) -> U81(X) 15.11/4.75 U81(active(X)) -> U81(X) 15.11/4.75 isQid(mark(X)) -> isQid(X) 15.11/4.75 isQid(active(X)) -> isQid(X) 15.11/4.75 isNePal(mark(X)) -> isNePal(X) 15.11/4.75 isNePal(active(X)) -> isNePal(X) 15.11/4.75 15.11/4.75 The set Q consists of the following terms: 15.11/4.75 15.11/4.75 active(__(__(x0, x1), x2)) 15.11/4.75 active(__(x0, nil)) 15.11/4.75 active(__(nil, x0)) 15.11/4.75 active(U11(tt)) 15.11/4.75 active(U21(tt, x0)) 15.11/4.75 active(U22(tt)) 15.11/4.75 active(U31(tt)) 15.11/4.75 active(U41(tt, x0)) 15.11/4.75 active(U42(tt)) 15.11/4.75 active(U51(tt, x0)) 15.11/4.75 active(U52(tt)) 15.11/4.75 active(U61(tt)) 15.11/4.75 active(U71(tt, x0)) 15.11/4.75 active(U72(tt)) 15.11/4.75 active(U81(tt)) 15.11/4.75 active(isList(x0)) 15.11/4.75 active(isNeList(x0)) 15.11/4.75 active(isNePal(x0)) 15.11/4.75 active(isPal(x0)) 15.11/4.75 active(isQid(a)) 15.11/4.75 active(isQid(e)) 15.11/4.75 active(isQid(i)) 15.11/4.75 active(isQid(o)) 15.11/4.75 active(isQid(u)) 15.11/4.75 mark(__(x0, x1)) 15.11/4.75 mark(nil) 15.11/4.75 mark(U11(x0)) 15.11/4.75 mark(tt) 15.11/4.75 mark(U21(x0, x1)) 15.11/4.75 mark(U22(x0)) 15.11/4.75 mark(isList(x0)) 15.11/4.75 mark(U31(x0)) 15.11/4.75 mark(U41(x0, x1)) 15.11/4.75 mark(U42(x0)) 15.11/4.75 mark(isNeList(x0)) 15.11/4.75 mark(U51(x0, x1)) 15.11/4.75 mark(U52(x0)) 15.11/4.75 mark(U61(x0)) 15.11/4.75 mark(U71(x0, x1)) 15.11/4.75 mark(U72(x0)) 15.11/4.75 mark(isPal(x0)) 15.11/4.75 mark(U81(x0)) 15.11/4.75 mark(isQid(x0)) 15.11/4.75 mark(isNePal(x0)) 15.11/4.75 mark(a) 15.11/4.75 mark(e) 15.11/4.75 mark(i) 15.11/4.75 mark(o) 15.11/4.75 mark(u) 15.11/4.75 __(mark(x0), x1) 15.11/4.75 __(x0, mark(x1)) 15.11/4.75 __(active(x0), x1) 15.11/4.75 __(x0, active(x1)) 15.11/4.75 U11(mark(x0)) 15.11/4.75 U11(active(x0)) 15.11/4.75 U21(mark(x0), x1) 15.11/4.75 U21(x0, mark(x1)) 15.11/4.75 U21(active(x0), x1) 15.11/4.75 U21(x0, active(x1)) 15.11/4.75 U22(mark(x0)) 15.11/4.75 U22(active(x0)) 15.11/4.75 isList(mark(x0)) 15.11/4.75 isList(active(x0)) 15.11/4.75 U31(mark(x0)) 15.11/4.75 U31(active(x0)) 15.11/4.75 U41(mark(x0), x1) 15.11/4.75 U41(x0, mark(x1)) 15.11/4.75 U41(active(x0), x1) 15.11/4.75 U41(x0, active(x1)) 15.11/4.75 U42(mark(x0)) 15.11/4.75 U42(active(x0)) 15.11/4.75 isNeList(mark(x0)) 15.11/4.75 isNeList(active(x0)) 15.11/4.75 U51(mark(x0), x1) 15.11/4.75 U51(x0, mark(x1)) 15.11/4.75 U51(active(x0), x1) 15.11/4.75 U51(x0, active(x1)) 15.11/4.75 U52(mark(x0)) 15.11/4.75 U52(active(x0)) 15.11/4.75 U61(mark(x0)) 15.11/4.75 U61(active(x0)) 15.11/4.75 U71(mark(x0), x1) 15.11/4.75 U71(x0, mark(x1)) 15.11/4.75 U71(active(x0), x1) 15.11/4.75 U71(x0, active(x1)) 15.11/4.75 U72(mark(x0)) 15.11/4.75 U72(active(x0)) 15.11/4.75 isPal(mark(x0)) 15.11/4.75 isPal(active(x0)) 15.11/4.75 U81(mark(x0)) 15.11/4.75 U81(active(x0)) 15.11/4.75 isQid(mark(x0)) 15.11/4.75 isQid(active(x0)) 15.11/4.75 isNePal(mark(x0)) 15.11/4.75 isNePal(active(x0)) 15.11/4.75 15.11/4.75 15.11/4.75 ---------------------------------------- 15.11/4.75 15.11/4.75 (1) QTRSRRRProof (EQUIVALENT) 15.11/4.75 Used ordering: 15.11/4.75 Polynomial interpretation [POLO]: 15.11/4.75 15.11/4.75 POL(U11(x_1)) = x_1 15.11/4.75 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.11/4.75 POL(U22(x_1)) = x_1 15.11/4.75 POL(U31(x_1)) = x_1 15.11/4.75 POL(U41(x_1, x_2)) = 2 + x_1 + 2*x_2 15.11/4.75 POL(U42(x_1)) = 1 + x_1 15.11/4.75 POL(U51(x_1, x_2)) = x_1 + 2*x_2 15.11/4.75 POL(U52(x_1)) = x_1 15.11/4.75 POL(U61(x_1)) = x_1 15.11/4.75 POL(U71(x_1, x_2)) = x_1 + x_2 15.11/4.75 POL(U72(x_1)) = x_1 15.11/4.75 POL(U81(x_1)) = x_1 15.11/4.75 POL(__(x_1, x_2)) = 1 + 2*x_1 + x_2 15.11/4.75 POL(a) = 0 15.11/4.75 POL(active(x_1)) = x_1 15.11/4.75 POL(e) = 0 15.11/4.75 POL(i) = 0 15.11/4.75 POL(isList(x_1)) = 2*x_1 15.11/4.75 POL(isNeList(x_1)) = 2*x_1 15.11/4.75 POL(isNePal(x_1)) = x_1 15.11/4.75 POL(isPal(x_1)) = x_1 15.11/4.75 POL(isQid(x_1)) = x_1 15.11/4.75 POL(mark(x_1)) = x_1 15.11/4.75 POL(nil) = 0 15.11/4.75 POL(o) = 0 15.11/4.75 POL(tt) = 0 15.11/4.75 POL(u) = 0 15.11/4.75 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.75 15.11/4.75 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 15.11/4.75 active(__(X, nil)) -> mark(X) 15.11/4.75 active(__(nil, X)) -> mark(X) 15.11/4.75 active(U41(tt, V2)) -> mark(U42(isNeList(V2))) 15.11/4.75 active(U42(tt)) -> mark(tt) 15.11/4.75 active(isList(__(V1, V2))) -> mark(U21(isList(V1), V2)) 15.11/4.75 active(isNeList(__(V1, V2))) -> mark(U51(isNeList(V1), V2)) 15.11/4.75 active(isNePal(__(I, __(P, I)))) -> mark(U71(isQid(I), P)) 15.11/4.75 15.11/4.75 15.11/4.75 15.11/4.75 15.11/4.75 ---------------------------------------- 15.11/4.75 15.11/4.75 (2) 15.11/4.75 Obligation: 15.11/4.75 Q restricted rewrite system: 15.11/4.75 The TRS R consists of the following rules: 15.11/4.75 15.11/4.75 active(U11(tt)) -> mark(tt) 15.11/4.75 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.75 active(U22(tt)) -> mark(tt) 15.11/4.75 active(U31(tt)) -> mark(tt) 15.11/4.75 active(U51(tt, V2)) -> mark(U52(isList(V2))) 15.11/4.75 active(U52(tt)) -> mark(tt) 15.11/4.75 active(U61(tt)) -> mark(tt) 15.11/4.75 active(U71(tt, P)) -> mark(U72(isPal(P))) 15.11/4.75 active(U72(tt)) -> mark(tt) 15.11/4.75 active(U81(tt)) -> mark(tt) 15.11/4.75 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.75 active(isList(nil)) -> mark(tt) 15.11/4.75 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.75 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.75 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.75 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.75 active(isPal(nil)) -> mark(tt) 15.11/4.75 active(isQid(a)) -> mark(tt) 15.11/4.75 active(isQid(e)) -> mark(tt) 15.11/4.75 active(isQid(i)) -> mark(tt) 15.11/4.75 active(isQid(o)) -> mark(tt) 15.11/4.75 active(isQid(u)) -> mark(tt) 15.11/4.75 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.75 mark(nil) -> active(nil) 15.11/4.75 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.75 mark(tt) -> active(tt) 15.11/4.75 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.75 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.75 mark(isList(X)) -> active(isList(X)) 15.11/4.75 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.75 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.75 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.75 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.75 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.75 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.75 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.75 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.75 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.75 mark(isPal(X)) -> active(isPal(X)) 15.11/4.75 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.75 mark(isQid(X)) -> active(isQid(X)) 15.11/4.75 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.75 mark(a) -> active(a) 15.11/4.75 mark(e) -> active(e) 15.11/4.75 mark(i) -> active(i) 15.11/4.75 mark(o) -> active(o) 15.11/4.75 mark(u) -> active(u) 15.11/4.75 __(mark(X1), X2) -> __(X1, X2) 15.11/4.75 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.75 __(active(X1), X2) -> __(X1, X2) 15.11/4.75 __(X1, active(X2)) -> __(X1, X2) 15.11/4.75 U11(mark(X)) -> U11(X) 15.11/4.75 U11(active(X)) -> U11(X) 15.11/4.75 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.75 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.75 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.75 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.75 U22(mark(X)) -> U22(X) 15.11/4.75 U22(active(X)) -> U22(X) 15.11/4.75 isList(mark(X)) -> isList(X) 15.11/4.75 isList(active(X)) -> isList(X) 15.11/4.75 U31(mark(X)) -> U31(X) 15.11/4.75 U31(active(X)) -> U31(X) 15.11/4.75 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.75 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.75 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.75 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.75 U42(mark(X)) -> U42(X) 15.11/4.75 U42(active(X)) -> U42(X) 15.11/4.75 isNeList(mark(X)) -> isNeList(X) 15.11/4.75 isNeList(active(X)) -> isNeList(X) 15.11/4.75 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.75 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.75 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.75 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.75 U52(mark(X)) -> U52(X) 15.11/4.75 U52(active(X)) -> U52(X) 15.11/4.75 U61(mark(X)) -> U61(X) 15.11/4.75 U61(active(X)) -> U61(X) 15.11/4.75 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.75 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.75 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.75 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.75 U72(mark(X)) -> U72(X) 15.11/4.75 U72(active(X)) -> U72(X) 15.11/4.75 isPal(mark(X)) -> isPal(X) 15.11/4.75 isPal(active(X)) -> isPal(X) 15.11/4.75 U81(mark(X)) -> U81(X) 15.11/4.75 U81(active(X)) -> U81(X) 15.11/4.75 isQid(mark(X)) -> isQid(X) 15.11/4.75 isQid(active(X)) -> isQid(X) 15.11/4.75 isNePal(mark(X)) -> isNePal(X) 15.11/4.75 isNePal(active(X)) -> isNePal(X) 15.11/4.75 15.11/4.75 The set Q consists of the following terms: 15.11/4.75 15.11/4.75 active(__(__(x0, x1), x2)) 15.11/4.75 active(__(x0, nil)) 15.11/4.75 active(__(nil, x0)) 15.11/4.75 active(U11(tt)) 15.11/4.75 active(U21(tt, x0)) 15.11/4.75 active(U22(tt)) 15.11/4.75 active(U31(tt)) 15.11/4.75 active(U41(tt, x0)) 15.11/4.75 active(U42(tt)) 15.11/4.75 active(U51(tt, x0)) 15.11/4.75 active(U52(tt)) 15.11/4.75 active(U61(tt)) 15.11/4.75 active(U71(tt, x0)) 15.11/4.75 active(U72(tt)) 15.11/4.75 active(U81(tt)) 15.11/4.75 active(isList(x0)) 15.11/4.75 active(isNeList(x0)) 15.11/4.75 active(isNePal(x0)) 15.11/4.75 active(isPal(x0)) 15.11/4.75 active(isQid(a)) 15.11/4.75 active(isQid(e)) 15.11/4.75 active(isQid(i)) 15.11/4.75 active(isQid(o)) 15.11/4.75 active(isQid(u)) 15.11/4.75 mark(__(x0, x1)) 15.11/4.75 mark(nil) 15.11/4.75 mark(U11(x0)) 15.11/4.75 mark(tt) 15.11/4.75 mark(U21(x0, x1)) 15.11/4.75 mark(U22(x0)) 15.11/4.75 mark(isList(x0)) 15.11/4.75 mark(U31(x0)) 15.11/4.75 mark(U41(x0, x1)) 15.11/4.75 mark(U42(x0)) 15.11/4.75 mark(isNeList(x0)) 15.11/4.75 mark(U51(x0, x1)) 15.11/4.75 mark(U52(x0)) 15.11/4.75 mark(U61(x0)) 15.11/4.75 mark(U71(x0, x1)) 15.11/4.75 mark(U72(x0)) 15.11/4.75 mark(isPal(x0)) 15.11/4.75 mark(U81(x0)) 15.11/4.75 mark(isQid(x0)) 15.11/4.75 mark(isNePal(x0)) 15.11/4.75 mark(a) 15.11/4.75 mark(e) 15.11/4.75 mark(i) 15.11/4.75 mark(o) 15.11/4.75 mark(u) 15.11/4.75 __(mark(x0), x1) 15.11/4.75 __(x0, mark(x1)) 15.11/4.75 __(active(x0), x1) 15.11/4.75 __(x0, active(x1)) 15.11/4.75 U11(mark(x0)) 15.11/4.75 U11(active(x0)) 15.11/4.75 U21(mark(x0), x1) 15.11/4.75 U21(x0, mark(x1)) 15.11/4.75 U21(active(x0), x1) 15.11/4.75 U21(x0, active(x1)) 15.11/4.75 U22(mark(x0)) 15.11/4.75 U22(active(x0)) 15.11/4.75 isList(mark(x0)) 15.11/4.75 isList(active(x0)) 15.11/4.75 U31(mark(x0)) 15.11/4.75 U31(active(x0)) 15.11/4.75 U41(mark(x0), x1) 15.11/4.75 U41(x0, mark(x1)) 15.11/4.75 U41(active(x0), x1) 15.11/4.75 U41(x0, active(x1)) 15.11/4.75 U42(mark(x0)) 15.11/4.75 U42(active(x0)) 15.11/4.75 isNeList(mark(x0)) 15.11/4.75 isNeList(active(x0)) 15.11/4.75 U51(mark(x0), x1) 15.11/4.75 U51(x0, mark(x1)) 15.11/4.75 U51(active(x0), x1) 15.11/4.75 U51(x0, active(x1)) 15.11/4.75 U52(mark(x0)) 15.11/4.75 U52(active(x0)) 15.11/4.75 U61(mark(x0)) 15.11/4.75 U61(active(x0)) 15.11/4.75 U71(mark(x0), x1) 15.11/4.75 U71(x0, mark(x1)) 15.11/4.75 U71(active(x0), x1) 15.11/4.75 U71(x0, active(x1)) 15.11/4.75 U72(mark(x0)) 15.11/4.75 U72(active(x0)) 15.11/4.75 isPal(mark(x0)) 15.11/4.75 isPal(active(x0)) 15.11/4.75 U81(mark(x0)) 15.11/4.75 U81(active(x0)) 15.11/4.75 isQid(mark(x0)) 15.11/4.75 isQid(active(x0)) 15.11/4.75 isNePal(mark(x0)) 15.11/4.75 isNePal(active(x0)) 15.11/4.75 15.11/4.75 15.11/4.75 ---------------------------------------- 15.11/4.75 15.11/4.75 (3) QTRSRRRProof (EQUIVALENT) 15.11/4.75 Used ordering: 15.11/4.75 Polynomial interpretation [POLO]: 15.11/4.75 15.11/4.75 POL(U11(x_1)) = x_1 15.11/4.75 POL(U21(x_1, x_2)) = 2 + x_1 + 2*x_2 15.11/4.75 POL(U22(x_1)) = 2 + 2*x_1 15.11/4.75 POL(U31(x_1)) = x_1 15.11/4.75 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.75 POL(U42(x_1)) = x_1 15.11/4.75 POL(U51(x_1, x_2)) = x_1 + x_2 15.11/4.75 POL(U52(x_1)) = x_1 15.11/4.75 POL(U61(x_1)) = x_1 15.11/4.75 POL(U71(x_1, x_2)) = x_1 + 2*x_2 15.11/4.75 POL(U72(x_1)) = x_1 15.11/4.75 POL(U81(x_1)) = 2*x_1 15.11/4.75 POL(__(x_1, x_2)) = x_1 + x_2 15.11/4.75 POL(a) = 0 15.11/4.75 POL(active(x_1)) = x_1 15.11/4.75 POL(e) = 0 15.11/4.75 POL(i) = 0 15.11/4.75 POL(isList(x_1)) = x_1 15.11/4.75 POL(isNeList(x_1)) = x_1 15.11/4.75 POL(isNePal(x_1)) = x_1 15.11/4.75 POL(isPal(x_1)) = 2*x_1 15.11/4.75 POL(isQid(x_1)) = x_1 15.11/4.75 POL(mark(x_1)) = x_1 15.11/4.75 POL(nil) = 0 15.11/4.75 POL(o) = 0 15.11/4.75 POL(tt) = 0 15.11/4.75 POL(u) = 0 15.11/4.75 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.75 15.11/4.75 active(U22(tt)) -> mark(tt) 15.11/4.75 15.11/4.75 15.11/4.75 15.11/4.75 15.11/4.75 ---------------------------------------- 15.11/4.75 15.11/4.75 (4) 15.11/4.75 Obligation: 15.11/4.75 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U51(tt, V2)) -> mark(U52(isList(V2))) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U71(tt, P)) -> mark(U72(isPal(P))) 15.11/4.76 active(U72(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.76 active(isPal(nil)) -> mark(tt) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(e)) -> mark(tt) 15.11/4.76 active(isQid(i)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.11/4.76 U22(mark(x0)) 15.11/4.76 U22(active(x0)) 15.11/4.76 isList(mark(x0)) 15.11/4.76 isList(active(x0)) 15.11/4.76 U31(mark(x0)) 15.11/4.76 U31(active(x0)) 15.11/4.76 U41(mark(x0), x1) 15.11/4.76 U41(x0, mark(x1)) 15.11/4.76 U41(active(x0), x1) 15.11/4.76 U41(x0, active(x1)) 15.11/4.76 U42(mark(x0)) 15.11/4.76 U42(active(x0)) 15.11/4.76 isNeList(mark(x0)) 15.11/4.76 isNeList(active(x0)) 15.11/4.76 U51(mark(x0), x1) 15.11/4.76 U51(x0, mark(x1)) 15.11/4.76 U51(active(x0), x1) 15.11/4.76 U51(x0, active(x1)) 15.11/4.76 U52(mark(x0)) 15.11/4.76 U52(active(x0)) 15.11/4.76 U61(mark(x0)) 15.11/4.76 U61(active(x0)) 15.11/4.76 U71(mark(x0), x1) 15.11/4.76 U71(x0, mark(x1)) 15.11/4.76 U71(active(x0), x1) 15.11/4.76 U71(x0, active(x1)) 15.11/4.76 U72(mark(x0)) 15.11/4.76 U72(active(x0)) 15.11/4.76 isPal(mark(x0)) 15.11/4.76 isPal(active(x0)) 15.11/4.76 U81(mark(x0)) 15.11/4.76 U81(active(x0)) 15.11/4.76 isQid(mark(x0)) 15.11/4.76 isQid(active(x0)) 15.11/4.76 isNePal(mark(x0)) 15.11/4.76 isNePal(active(x0)) 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (5) QTRSRRRProof (EQUIVALENT) 15.11/4.76 Used ordering: 15.11/4.76 Polynomial interpretation [POLO]: 15.11/4.76 15.11/4.76 POL(U11(x_1)) = x_1 15.11/4.76 POL(U21(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U22(x_1)) = x_1 15.11/4.76 POL(U31(x_1)) = x_1 15.11/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U42(x_1)) = x_1 15.11/4.76 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 15.11/4.76 POL(U52(x_1)) = x_1 15.11/4.76 POL(U61(x_1)) = x_1 15.11/4.76 POL(U71(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U72(x_1)) = 2*x_1 15.11/4.76 POL(U81(x_1)) = x_1 15.11/4.76 POL(__(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(a) = 0 15.11/4.76 POL(active(x_1)) = x_1 15.11/4.76 POL(e) = 2 15.11/4.76 POL(i) = 0 15.11/4.76 POL(isList(x_1)) = x_1 15.11/4.76 POL(isNeList(x_1)) = x_1 15.11/4.76 POL(isNePal(x_1)) = x_1 15.11/4.76 POL(isPal(x_1)) = x_1 15.11/4.76 POL(isQid(x_1)) = x_1 15.11/4.76 POL(mark(x_1)) = x_1 15.11/4.76 POL(nil) = 0 15.11/4.76 POL(o) = 0 15.11/4.76 POL(tt) = 0 15.11/4.76 POL(u) = 0 15.11/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.76 15.11/4.76 active(isQid(e)) -> mark(tt) 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (6) 15.11/4.76 Obligation: 15.11/4.76 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U51(tt, V2)) -> mark(U52(isList(V2))) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U71(tt, P)) -> mark(U72(isPal(P))) 15.11/4.76 active(U72(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.76 active(isPal(nil)) -> mark(tt) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(i)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.11/4.76 U22(mark(x0)) 15.11/4.76 U22(active(x0)) 15.11/4.76 isList(mark(x0)) 15.11/4.76 isList(active(x0)) 15.11/4.76 U31(mark(x0)) 15.11/4.76 U31(active(x0)) 15.11/4.76 U41(mark(x0), x1) 15.11/4.76 U41(x0, mark(x1)) 15.11/4.76 U41(active(x0), x1) 15.11/4.76 U41(x0, active(x1)) 15.11/4.76 U42(mark(x0)) 15.11/4.76 U42(active(x0)) 15.11/4.76 isNeList(mark(x0)) 15.11/4.76 isNeList(active(x0)) 15.11/4.76 U51(mark(x0), x1) 15.11/4.76 U51(x0, mark(x1)) 15.11/4.76 U51(active(x0), x1) 15.11/4.76 U51(x0, active(x1)) 15.11/4.76 U52(mark(x0)) 15.11/4.76 U52(active(x0)) 15.11/4.76 U61(mark(x0)) 15.11/4.76 U61(active(x0)) 15.11/4.76 U71(mark(x0), x1) 15.11/4.76 U71(x0, mark(x1)) 15.11/4.76 U71(active(x0), x1) 15.11/4.76 U71(x0, active(x1)) 15.11/4.76 U72(mark(x0)) 15.11/4.76 U72(active(x0)) 15.11/4.76 isPal(mark(x0)) 15.11/4.76 isPal(active(x0)) 15.11/4.76 U81(mark(x0)) 15.11/4.76 U81(active(x0)) 15.11/4.76 isQid(mark(x0)) 15.11/4.76 isQid(active(x0)) 15.11/4.76 isNePal(mark(x0)) 15.11/4.76 isNePal(active(x0)) 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (7) QTRSRRRProof (EQUIVALENT) 15.11/4.76 Used ordering: 15.11/4.76 Polynomial interpretation [POLO]: 15.11/4.76 15.11/4.76 POL(U11(x_1)) = x_1 15.11/4.76 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U22(x_1)) = x_1 15.11/4.76 POL(U31(x_1)) = 2*x_1 15.11/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U42(x_1)) = x_1 15.11/4.76 POL(U51(x_1, x_2)) = 2 + x_1 + 2*x_2 15.11/4.76 POL(U52(x_1)) = x_1 15.11/4.76 POL(U61(x_1)) = x_1 15.11/4.76 POL(U71(x_1, x_2)) = 2 + x_1 + x_2 15.11/4.76 POL(U72(x_1)) = x_1 15.11/4.76 POL(U81(x_1)) = x_1 15.11/4.76 POL(__(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(a) = 0 15.11/4.76 POL(active(x_1)) = x_1 15.11/4.76 POL(e) = 0 15.11/4.76 POL(i) = 0 15.11/4.76 POL(isList(x_1)) = 2*x_1 15.11/4.76 POL(isNeList(x_1)) = 2*x_1 15.11/4.76 POL(isNePal(x_1)) = x_1 15.11/4.76 POL(isPal(x_1)) = x_1 15.11/4.76 POL(isQid(x_1)) = x_1 15.11/4.76 POL(mark(x_1)) = x_1 15.11/4.76 POL(nil) = 0 15.11/4.76 POL(o) = 0 15.11/4.76 POL(tt) = 0 15.11/4.76 POL(u) = 0 15.11/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.76 15.11/4.76 active(U51(tt, V2)) -> mark(U52(isList(V2))) 15.11/4.76 active(U71(tt, P)) -> mark(U72(isPal(P))) 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (8) 15.11/4.76 Obligation: 15.11/4.76 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U72(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.76 active(isPal(nil)) -> mark(tt) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(i)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.11/4.76 U22(mark(x0)) 15.11/4.76 U22(active(x0)) 15.11/4.76 isList(mark(x0)) 15.11/4.76 isList(active(x0)) 15.11/4.76 U31(mark(x0)) 15.11/4.76 U31(active(x0)) 15.11/4.76 U41(mark(x0), x1) 15.11/4.76 U41(x0, mark(x1)) 15.11/4.76 U41(active(x0), x1) 15.11/4.76 U41(x0, active(x1)) 15.11/4.76 U42(mark(x0)) 15.11/4.76 U42(active(x0)) 15.11/4.76 isNeList(mark(x0)) 15.11/4.76 isNeList(active(x0)) 15.11/4.76 U51(mark(x0), x1) 15.11/4.76 U51(x0, mark(x1)) 15.11/4.76 U51(active(x0), x1) 15.11/4.76 U51(x0, active(x1)) 15.11/4.76 U52(mark(x0)) 15.11/4.76 U52(active(x0)) 15.11/4.76 U61(mark(x0)) 15.11/4.76 U61(active(x0)) 15.11/4.76 U71(mark(x0), x1) 15.11/4.76 U71(x0, mark(x1)) 15.11/4.76 U71(active(x0), x1) 15.11/4.76 U71(x0, active(x1)) 15.11/4.76 U72(mark(x0)) 15.11/4.76 U72(active(x0)) 15.11/4.76 isPal(mark(x0)) 15.11/4.76 isPal(active(x0)) 15.11/4.76 U81(mark(x0)) 15.11/4.76 U81(active(x0)) 15.11/4.76 isQid(mark(x0)) 15.11/4.76 isQid(active(x0)) 15.11/4.76 isNePal(mark(x0)) 15.11/4.76 isNePal(active(x0)) 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (9) QTRSRRRProof (EQUIVALENT) 15.11/4.76 Used ordering: 15.11/4.76 Polynomial interpretation [POLO]: 15.11/4.76 15.11/4.76 POL(U11(x_1)) = x_1 15.11/4.76 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U22(x_1)) = x_1 15.11/4.76 POL(U31(x_1)) = x_1 15.11/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U42(x_1)) = 2*x_1 15.11/4.76 POL(U51(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U52(x_1)) = 2*x_1 15.11/4.76 POL(U61(x_1)) = x_1 15.11/4.76 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_2 15.11/4.76 POL(U72(x_1)) = x_1 15.11/4.76 POL(U81(x_1)) = x_1 15.11/4.76 POL(__(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(a) = 0 15.11/4.76 POL(active(x_1)) = x_1 15.11/4.76 POL(e) = 0 15.11/4.76 POL(i) = 1 15.11/4.76 POL(isList(x_1)) = 2*x_1 15.11/4.76 POL(isNeList(x_1)) = 2*x_1 15.11/4.76 POL(isNePal(x_1)) = 2*x_1 15.11/4.76 POL(isPal(x_1)) = 2 + 2*x_1 15.11/4.76 POL(isQid(x_1)) = 2*x_1 15.11/4.76 POL(mark(x_1)) = x_1 15.11/4.76 POL(nil) = 0 15.11/4.76 POL(o) = 0 15.11/4.76 POL(tt) = 0 15.11/4.76 POL(u) = 0 15.11/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.76 15.11/4.76 active(isPal(V)) -> mark(U81(isNePal(V))) 15.11/4.76 active(isPal(nil)) -> mark(tt) 15.11/4.76 active(isQid(i)) -> mark(tt) 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (10) 15.11/4.76 Obligation: 15.11/4.76 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U72(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.11/4.76 U22(mark(x0)) 15.11/4.76 U22(active(x0)) 15.11/4.76 isList(mark(x0)) 15.11/4.76 isList(active(x0)) 15.11/4.76 U31(mark(x0)) 15.11/4.76 U31(active(x0)) 15.11/4.76 U41(mark(x0), x1) 15.11/4.76 U41(x0, mark(x1)) 15.11/4.76 U41(active(x0), x1) 15.11/4.76 U41(x0, active(x1)) 15.11/4.76 U42(mark(x0)) 15.11/4.76 U42(active(x0)) 15.11/4.76 isNeList(mark(x0)) 15.11/4.76 isNeList(active(x0)) 15.11/4.76 U51(mark(x0), x1) 15.11/4.76 U51(x0, mark(x1)) 15.11/4.76 U51(active(x0), x1) 15.11/4.76 U51(x0, active(x1)) 15.11/4.76 U52(mark(x0)) 15.11/4.76 U52(active(x0)) 15.11/4.76 U61(mark(x0)) 15.11/4.76 U61(active(x0)) 15.11/4.76 U71(mark(x0), x1) 15.11/4.76 U71(x0, mark(x1)) 15.11/4.76 U71(active(x0), x1) 15.11/4.76 U71(x0, active(x1)) 15.11/4.76 U72(mark(x0)) 15.11/4.76 U72(active(x0)) 15.11/4.76 isPal(mark(x0)) 15.11/4.76 isPal(active(x0)) 15.11/4.76 U81(mark(x0)) 15.11/4.76 U81(active(x0)) 15.11/4.76 isQid(mark(x0)) 15.11/4.76 isQid(active(x0)) 15.11/4.76 isNePal(mark(x0)) 15.11/4.76 isNePal(active(x0)) 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (11) QTRSRRRProof (EQUIVALENT) 15.11/4.76 Used ordering: 15.11/4.76 Polynomial interpretation [POLO]: 15.11/4.76 15.11/4.76 POL(U11(x_1)) = x_1 15.11/4.76 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U22(x_1)) = x_1 15.11/4.76 POL(U31(x_1)) = x_1 15.11/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U42(x_1)) = x_1 15.11/4.76 POL(U51(x_1, x_2)) = 2*x_1 + x_2 15.11/4.76 POL(U52(x_1)) = 2*x_1 15.11/4.76 POL(U61(x_1)) = x_1 15.11/4.76 POL(U71(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U72(x_1)) = 1 + x_1 15.11/4.76 POL(U81(x_1)) = x_1 15.11/4.76 POL(__(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(a) = 0 15.11/4.76 POL(active(x_1)) = x_1 15.11/4.76 POL(e) = 0 15.11/4.76 POL(i) = 0 15.11/4.76 POL(isList(x_1)) = x_1 15.11/4.76 POL(isNeList(x_1)) = x_1 15.11/4.76 POL(isNePal(x_1)) = 2*x_1 15.11/4.76 POL(isPal(x_1)) = 2*x_1 15.11/4.76 POL(isQid(x_1)) = x_1 15.11/4.76 POL(mark(x_1)) = x_1 15.11/4.76 POL(nil) = 0 15.11/4.76 POL(o) = 0 15.11/4.76 POL(tt) = 0 15.11/4.76 POL(u) = 0 15.11/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.76 15.11/4.76 active(U72(tt)) -> mark(tt) 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (12) 15.11/4.76 Obligation: 15.11/4.76 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.11/4.76 U22(mark(x0)) 15.11/4.76 U22(active(x0)) 15.11/4.76 isList(mark(x0)) 15.11/4.76 isList(active(x0)) 15.11/4.76 U31(mark(x0)) 15.11/4.76 U31(active(x0)) 15.11/4.76 U41(mark(x0), x1) 15.11/4.76 U41(x0, mark(x1)) 15.11/4.76 U41(active(x0), x1) 15.11/4.76 U41(x0, active(x1)) 15.11/4.76 U42(mark(x0)) 15.11/4.76 U42(active(x0)) 15.11/4.76 isNeList(mark(x0)) 15.11/4.76 isNeList(active(x0)) 15.11/4.76 U51(mark(x0), x1) 15.11/4.76 U51(x0, mark(x1)) 15.11/4.76 U51(active(x0), x1) 15.11/4.76 U51(x0, active(x1)) 15.11/4.76 U52(mark(x0)) 15.11/4.76 U52(active(x0)) 15.11/4.76 U61(mark(x0)) 15.11/4.76 U61(active(x0)) 15.11/4.76 U71(mark(x0), x1) 15.11/4.76 U71(x0, mark(x1)) 15.11/4.76 U71(active(x0), x1) 15.11/4.76 U71(x0, active(x1)) 15.11/4.76 U72(mark(x0)) 15.11/4.76 U72(active(x0)) 15.11/4.76 isPal(mark(x0)) 15.11/4.76 isPal(active(x0)) 15.11/4.76 U81(mark(x0)) 15.11/4.76 U81(active(x0)) 15.11/4.76 isQid(mark(x0)) 15.11/4.76 isQid(active(x0)) 15.11/4.76 isNePal(mark(x0)) 15.11/4.76 isNePal(active(x0)) 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (13) QTRSRRRProof (EQUIVALENT) 15.11/4.76 Used ordering: 15.11/4.76 Polynomial interpretation [POLO]: 15.11/4.76 15.11/4.76 POL(U11(x_1)) = 2*x_1 15.11/4.76 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.11/4.76 POL(U22(x_1)) = x_1 15.11/4.76 POL(U31(x_1)) = x_1 15.11/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U42(x_1)) = x_1 15.11/4.76 POL(U51(x_1, x_2)) = x_1 + x_2 15.11/4.76 POL(U52(x_1)) = x_1 15.11/4.76 POL(U61(x_1)) = 2*x_1 15.11/4.76 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_2 15.11/4.76 POL(U72(x_1)) = x_1 15.11/4.76 POL(U81(x_1)) = x_1 15.11/4.76 POL(__(x_1, x_2)) = 2*x_1 + x_2 15.11/4.76 POL(a) = 0 15.11/4.76 POL(active(x_1)) = x_1 15.11/4.76 POL(e) = 0 15.11/4.76 POL(i) = 0 15.11/4.76 POL(isList(x_1)) = 2*x_1 15.11/4.76 POL(isNeList(x_1)) = x_1 15.11/4.76 POL(isNePal(x_1)) = 2*x_1 15.11/4.76 POL(isPal(x_1)) = 2*x_1 15.11/4.76 POL(isQid(x_1)) = x_1 15.11/4.76 POL(mark(x_1)) = x_1 15.11/4.76 POL(nil) = 0 15.11/4.76 POL(o) = 0 15.11/4.76 POL(tt) = 0 15.11/4.76 POL(u) = 2 15.11/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.11/4.76 15.11/4.76 active(isQid(u)) -> mark(tt) 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 15.11/4.76 ---------------------------------------- 15.11/4.76 15.11/4.76 (14) 15.11/4.76 Obligation: 15.11/4.76 Q restricted rewrite system: 15.11/4.76 The TRS R consists of the following rules: 15.11/4.76 15.11/4.76 active(U11(tt)) -> mark(tt) 15.11/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.11/4.76 active(U31(tt)) -> mark(tt) 15.11/4.76 active(U52(tt)) -> mark(tt) 15.11/4.76 active(U61(tt)) -> mark(tt) 15.11/4.76 active(U81(tt)) -> mark(tt) 15.11/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.11/4.76 active(isList(nil)) -> mark(tt) 15.11/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.11/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.11/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.11/4.76 active(isQid(a)) -> mark(tt) 15.11/4.76 active(isQid(o)) -> mark(tt) 15.11/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.11/4.76 mark(nil) -> active(nil) 15.11/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.11/4.76 mark(tt) -> active(tt) 15.11/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.11/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.11/4.76 mark(isList(X)) -> active(isList(X)) 15.11/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.11/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.11/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.11/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.11/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.11/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.11/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.11/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.11/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.11/4.76 mark(isPal(X)) -> active(isPal(X)) 15.11/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.11/4.76 mark(isQid(X)) -> active(isQid(X)) 15.11/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.11/4.76 mark(a) -> active(a) 15.11/4.76 mark(e) -> active(e) 15.11/4.76 mark(i) -> active(i) 15.11/4.76 mark(o) -> active(o) 15.11/4.76 mark(u) -> active(u) 15.11/4.76 __(mark(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.11/4.76 __(active(X1), X2) -> __(X1, X2) 15.11/4.76 __(X1, active(X2)) -> __(X1, X2) 15.11/4.76 U11(mark(X)) -> U11(X) 15.11/4.76 U11(active(X)) -> U11(X) 15.11/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.11/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.11/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.11/4.76 U22(mark(X)) -> U22(X) 15.11/4.76 U22(active(X)) -> U22(X) 15.11/4.76 isList(mark(X)) -> isList(X) 15.11/4.76 isList(active(X)) -> isList(X) 15.11/4.76 U31(mark(X)) -> U31(X) 15.11/4.76 U31(active(X)) -> U31(X) 15.11/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.11/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.11/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.11/4.76 U42(mark(X)) -> U42(X) 15.11/4.76 U42(active(X)) -> U42(X) 15.11/4.76 isNeList(mark(X)) -> isNeList(X) 15.11/4.76 isNeList(active(X)) -> isNeList(X) 15.11/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.11/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.11/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.11/4.76 U52(mark(X)) -> U52(X) 15.11/4.76 U52(active(X)) -> U52(X) 15.11/4.76 U61(mark(X)) -> U61(X) 15.11/4.76 U61(active(X)) -> U61(X) 15.11/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.11/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.11/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.11/4.76 U72(mark(X)) -> U72(X) 15.11/4.76 U72(active(X)) -> U72(X) 15.11/4.76 isPal(mark(X)) -> isPal(X) 15.11/4.76 isPal(active(X)) -> isPal(X) 15.11/4.76 U81(mark(X)) -> U81(X) 15.11/4.76 U81(active(X)) -> U81(X) 15.11/4.76 isQid(mark(X)) -> isQid(X) 15.11/4.76 isQid(active(X)) -> isQid(X) 15.11/4.76 isNePal(mark(X)) -> isNePal(X) 15.11/4.76 isNePal(active(X)) -> isNePal(X) 15.11/4.76 15.11/4.76 The set Q consists of the following terms: 15.11/4.76 15.11/4.76 active(__(__(x0, x1), x2)) 15.11/4.76 active(__(x0, nil)) 15.11/4.76 active(__(nil, x0)) 15.11/4.76 active(U11(tt)) 15.11/4.76 active(U21(tt, x0)) 15.11/4.76 active(U22(tt)) 15.11/4.76 active(U31(tt)) 15.11/4.76 active(U41(tt, x0)) 15.11/4.76 active(U42(tt)) 15.11/4.76 active(U51(tt, x0)) 15.11/4.76 active(U52(tt)) 15.11/4.76 active(U61(tt)) 15.11/4.76 active(U71(tt, x0)) 15.11/4.76 active(U72(tt)) 15.11/4.76 active(U81(tt)) 15.11/4.76 active(isList(x0)) 15.11/4.76 active(isNeList(x0)) 15.11/4.76 active(isNePal(x0)) 15.11/4.76 active(isPal(x0)) 15.11/4.76 active(isQid(a)) 15.11/4.76 active(isQid(e)) 15.11/4.76 active(isQid(i)) 15.11/4.76 active(isQid(o)) 15.11/4.76 active(isQid(u)) 15.11/4.76 mark(__(x0, x1)) 15.11/4.76 mark(nil) 15.11/4.76 mark(U11(x0)) 15.11/4.76 mark(tt) 15.11/4.76 mark(U21(x0, x1)) 15.11/4.76 mark(U22(x0)) 15.11/4.76 mark(isList(x0)) 15.11/4.76 mark(U31(x0)) 15.11/4.76 mark(U41(x0, x1)) 15.11/4.76 mark(U42(x0)) 15.11/4.76 mark(isNeList(x0)) 15.11/4.76 mark(U51(x0, x1)) 15.11/4.76 mark(U52(x0)) 15.11/4.76 mark(U61(x0)) 15.11/4.76 mark(U71(x0, x1)) 15.11/4.76 mark(U72(x0)) 15.11/4.76 mark(isPal(x0)) 15.11/4.76 mark(U81(x0)) 15.11/4.76 mark(isQid(x0)) 15.11/4.76 mark(isNePal(x0)) 15.11/4.76 mark(a) 15.11/4.76 mark(e) 15.11/4.76 mark(i) 15.11/4.76 mark(o) 15.11/4.76 mark(u) 15.11/4.76 __(mark(x0), x1) 15.11/4.76 __(x0, mark(x1)) 15.11/4.76 __(active(x0), x1) 15.11/4.76 __(x0, active(x1)) 15.11/4.76 U11(mark(x0)) 15.11/4.76 U11(active(x0)) 15.11/4.76 U21(mark(x0), x1) 15.11/4.76 U21(x0, mark(x1)) 15.11/4.76 U21(active(x0), x1) 15.11/4.76 U21(x0, active(x1)) 15.31/4.76 U22(mark(x0)) 15.31/4.76 U22(active(x0)) 15.31/4.76 isList(mark(x0)) 15.31/4.76 isList(active(x0)) 15.31/4.76 U31(mark(x0)) 15.31/4.76 U31(active(x0)) 15.31/4.76 U41(mark(x0), x1) 15.31/4.76 U41(x0, mark(x1)) 15.31/4.76 U41(active(x0), x1) 15.31/4.76 U41(x0, active(x1)) 15.31/4.76 U42(mark(x0)) 15.31/4.76 U42(active(x0)) 15.31/4.76 isNeList(mark(x0)) 15.31/4.76 isNeList(active(x0)) 15.31/4.76 U51(mark(x0), x1) 15.31/4.76 U51(x0, mark(x1)) 15.31/4.76 U51(active(x0), x1) 15.31/4.76 U51(x0, active(x1)) 15.31/4.76 U52(mark(x0)) 15.31/4.76 U52(active(x0)) 15.31/4.76 U61(mark(x0)) 15.31/4.76 U61(active(x0)) 15.31/4.76 U71(mark(x0), x1) 15.31/4.76 U71(x0, mark(x1)) 15.31/4.76 U71(active(x0), x1) 15.31/4.76 U71(x0, active(x1)) 15.31/4.76 U72(mark(x0)) 15.31/4.76 U72(active(x0)) 15.31/4.76 isPal(mark(x0)) 15.31/4.76 isPal(active(x0)) 15.31/4.76 U81(mark(x0)) 15.31/4.76 U81(active(x0)) 15.31/4.76 isQid(mark(x0)) 15.31/4.76 isQid(active(x0)) 15.31/4.76 isNePal(mark(x0)) 15.31/4.76 isNePal(active(x0)) 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (15) QTRSRRRProof (EQUIVALENT) 15.31/4.76 Used ordering: 15.31/4.76 Polynomial interpretation [POLO]: 15.31/4.76 15.31/4.76 POL(U11(x_1)) = x_1 15.31/4.76 POL(U21(x_1, x_2)) = x_1 + 2*x_2 15.31/4.76 POL(U22(x_1)) = x_1 15.31/4.76 POL(U31(x_1)) = x_1 15.31/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.31/4.76 POL(U42(x_1)) = x_1 15.31/4.76 POL(U51(x_1, x_2)) = 2*x_1 + x_2 15.31/4.76 POL(U52(x_1)) = x_1 15.31/4.76 POL(U61(x_1)) = x_1 15.31/4.76 POL(U71(x_1, x_2)) = x_1 + 2*x_2 15.31/4.76 POL(U72(x_1)) = x_1 15.31/4.76 POL(U81(x_1)) = x_1 15.31/4.76 POL(__(x_1, x_2)) = 2*x_1 + x_2 15.31/4.76 POL(a) = 0 15.31/4.76 POL(active(x_1)) = x_1 15.31/4.76 POL(e) = 0 15.31/4.76 POL(i) = 0 15.31/4.76 POL(isList(x_1)) = 2*x_1 15.31/4.76 POL(isNeList(x_1)) = 2*x_1 15.31/4.76 POL(isNePal(x_1)) = 2*x_1 15.31/4.76 POL(isPal(x_1)) = 2*x_1 15.31/4.76 POL(isQid(x_1)) = 2*x_1 15.31/4.76 POL(mark(x_1)) = x_1 15.31/4.76 POL(nil) = 0 15.31/4.76 POL(o) = 1 15.31/4.76 POL(tt) = 0 15.31/4.76 POL(u) = 0 15.31/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.76 15.31/4.76 active(isQid(o)) -> mark(tt) 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (16) 15.31/4.76 Obligation: 15.31/4.76 Q restricted rewrite system: 15.31/4.76 The TRS R consists of the following rules: 15.31/4.76 15.31/4.76 active(U11(tt)) -> mark(tt) 15.31/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.31/4.76 active(U31(tt)) -> mark(tt) 15.31/4.76 active(U52(tt)) -> mark(tt) 15.31/4.76 active(U61(tt)) -> mark(tt) 15.31/4.76 active(U81(tt)) -> mark(tt) 15.31/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.31/4.76 active(isList(nil)) -> mark(tt) 15.31/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.31/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.31/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.76 active(isQid(a)) -> mark(tt) 15.31/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.31/4.76 mark(nil) -> active(nil) 15.31/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.31/4.76 mark(tt) -> active(tt) 15.31/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.31/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.31/4.76 mark(isList(X)) -> active(isList(X)) 15.31/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.31/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.31/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.31/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.31/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.31/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.31/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.31/4.76 mark(isPal(X)) -> active(isPal(X)) 15.31/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.31/4.76 mark(isQid(X)) -> active(isQid(X)) 15.31/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.31/4.76 mark(a) -> active(a) 15.31/4.76 mark(e) -> active(e) 15.31/4.76 mark(i) -> active(i) 15.31/4.76 mark(o) -> active(o) 15.31/4.76 mark(u) -> active(u) 15.31/4.76 __(mark(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.31/4.76 __(active(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, active(X2)) -> __(X1, X2) 15.31/4.76 U11(mark(X)) -> U11(X) 15.31/4.76 U11(active(X)) -> U11(X) 15.31/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.31/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.31/4.76 U22(mark(X)) -> U22(X) 15.31/4.76 U22(active(X)) -> U22(X) 15.31/4.76 isList(mark(X)) -> isList(X) 15.31/4.76 isList(active(X)) -> isList(X) 15.31/4.76 U31(mark(X)) -> U31(X) 15.31/4.76 U31(active(X)) -> U31(X) 15.31/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.31/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.31/4.76 U42(mark(X)) -> U42(X) 15.31/4.76 U42(active(X)) -> U42(X) 15.31/4.76 isNeList(mark(X)) -> isNeList(X) 15.31/4.76 isNeList(active(X)) -> isNeList(X) 15.31/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.31/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.31/4.76 U52(mark(X)) -> U52(X) 15.31/4.76 U52(active(X)) -> U52(X) 15.31/4.76 U61(mark(X)) -> U61(X) 15.31/4.76 U61(active(X)) -> U61(X) 15.31/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.31/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.31/4.76 U72(mark(X)) -> U72(X) 15.31/4.76 U72(active(X)) -> U72(X) 15.31/4.76 isPal(mark(X)) -> isPal(X) 15.31/4.76 isPal(active(X)) -> isPal(X) 15.31/4.76 U81(mark(X)) -> U81(X) 15.31/4.76 U81(active(X)) -> U81(X) 15.31/4.76 isQid(mark(X)) -> isQid(X) 15.31/4.76 isQid(active(X)) -> isQid(X) 15.31/4.76 isNePal(mark(X)) -> isNePal(X) 15.31/4.76 isNePal(active(X)) -> isNePal(X) 15.31/4.76 15.31/4.76 The set Q consists of the following terms: 15.31/4.76 15.31/4.76 active(__(__(x0, x1), x2)) 15.31/4.76 active(__(x0, nil)) 15.31/4.76 active(__(nil, x0)) 15.31/4.76 active(U11(tt)) 15.31/4.76 active(U21(tt, x0)) 15.31/4.76 active(U22(tt)) 15.31/4.76 active(U31(tt)) 15.31/4.76 active(U41(tt, x0)) 15.31/4.76 active(U42(tt)) 15.31/4.76 active(U51(tt, x0)) 15.31/4.76 active(U52(tt)) 15.31/4.76 active(U61(tt)) 15.31/4.76 active(U71(tt, x0)) 15.31/4.76 active(U72(tt)) 15.31/4.76 active(U81(tt)) 15.31/4.76 active(isList(x0)) 15.31/4.76 active(isNeList(x0)) 15.31/4.76 active(isNePal(x0)) 15.31/4.76 active(isPal(x0)) 15.31/4.76 active(isQid(a)) 15.31/4.76 active(isQid(e)) 15.31/4.76 active(isQid(i)) 15.31/4.76 active(isQid(o)) 15.31/4.76 active(isQid(u)) 15.31/4.76 mark(__(x0, x1)) 15.31/4.76 mark(nil) 15.31/4.76 mark(U11(x0)) 15.31/4.76 mark(tt) 15.31/4.76 mark(U21(x0, x1)) 15.31/4.76 mark(U22(x0)) 15.31/4.76 mark(isList(x0)) 15.31/4.76 mark(U31(x0)) 15.31/4.76 mark(U41(x0, x1)) 15.31/4.76 mark(U42(x0)) 15.31/4.76 mark(isNeList(x0)) 15.31/4.76 mark(U51(x0, x1)) 15.31/4.76 mark(U52(x0)) 15.31/4.76 mark(U61(x0)) 15.31/4.76 mark(U71(x0, x1)) 15.31/4.76 mark(U72(x0)) 15.31/4.76 mark(isPal(x0)) 15.31/4.76 mark(U81(x0)) 15.31/4.76 mark(isQid(x0)) 15.31/4.76 mark(isNePal(x0)) 15.31/4.76 mark(a) 15.31/4.76 mark(e) 15.31/4.76 mark(i) 15.31/4.76 mark(o) 15.31/4.76 mark(u) 15.31/4.76 __(mark(x0), x1) 15.31/4.76 __(x0, mark(x1)) 15.31/4.76 __(active(x0), x1) 15.31/4.76 __(x0, active(x1)) 15.31/4.76 U11(mark(x0)) 15.31/4.76 U11(active(x0)) 15.31/4.76 U21(mark(x0), x1) 15.31/4.76 U21(x0, mark(x1)) 15.31/4.76 U21(active(x0), x1) 15.31/4.76 U21(x0, active(x1)) 15.31/4.76 U22(mark(x0)) 15.31/4.76 U22(active(x0)) 15.31/4.76 isList(mark(x0)) 15.31/4.76 isList(active(x0)) 15.31/4.76 U31(mark(x0)) 15.31/4.76 U31(active(x0)) 15.31/4.76 U41(mark(x0), x1) 15.31/4.76 U41(x0, mark(x1)) 15.31/4.76 U41(active(x0), x1) 15.31/4.76 U41(x0, active(x1)) 15.31/4.76 U42(mark(x0)) 15.31/4.76 U42(active(x0)) 15.31/4.76 isNeList(mark(x0)) 15.31/4.76 isNeList(active(x0)) 15.31/4.76 U51(mark(x0), x1) 15.31/4.76 U51(x0, mark(x1)) 15.31/4.76 U51(active(x0), x1) 15.31/4.76 U51(x0, active(x1)) 15.31/4.76 U52(mark(x0)) 15.31/4.76 U52(active(x0)) 15.31/4.76 U61(mark(x0)) 15.31/4.76 U61(active(x0)) 15.31/4.76 U71(mark(x0), x1) 15.31/4.76 U71(x0, mark(x1)) 15.31/4.76 U71(active(x0), x1) 15.31/4.76 U71(x0, active(x1)) 15.31/4.76 U72(mark(x0)) 15.31/4.76 U72(active(x0)) 15.31/4.76 isPal(mark(x0)) 15.31/4.76 isPal(active(x0)) 15.31/4.76 U81(mark(x0)) 15.31/4.76 U81(active(x0)) 15.31/4.76 isQid(mark(x0)) 15.31/4.76 isQid(active(x0)) 15.31/4.76 isNePal(mark(x0)) 15.31/4.76 isNePal(active(x0)) 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (17) QTRSRRRProof (EQUIVALENT) 15.31/4.76 Used ordering: 15.31/4.76 Polynomial interpretation [POLO]: 15.31/4.76 15.31/4.76 POL(U11(x_1)) = x_1 15.31/4.76 POL(U21(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 15.31/4.76 POL(U22(x_1)) = x_1 15.31/4.76 POL(U31(x_1)) = 2*x_1 15.31/4.76 POL(U41(x_1, x_2)) = x_1 + 2*x_2 15.31/4.76 POL(U42(x_1)) = 2*x_1 15.31/4.76 POL(U51(x_1, x_2)) = x_1 + 2*x_2 15.31/4.76 POL(U52(x_1)) = 2 + x_1 15.31/4.76 POL(U61(x_1)) = x_1 15.31/4.76 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_2 15.31/4.76 POL(U72(x_1)) = x_1 15.31/4.76 POL(U81(x_1)) = 1 + x_1 15.31/4.76 POL(__(x_1, x_2)) = 2 + x_1 + x_2 15.31/4.76 POL(a) = 2 15.31/4.76 POL(active(x_1)) = x_1 15.31/4.76 POL(e) = 0 15.31/4.76 POL(i) = 0 15.31/4.76 POL(isList(x_1)) = 2 + 2*x_1 15.31/4.76 POL(isNeList(x_1)) = 2*x_1 15.31/4.76 POL(isNePal(x_1)) = 2*x_1 15.31/4.76 POL(isPal(x_1)) = 2*x_1 15.31/4.76 POL(isQid(x_1)) = x_1 15.31/4.76 POL(mark(x_1)) = x_1 15.31/4.76 POL(nil) = 0 15.31/4.76 POL(o) = 0 15.31/4.76 POL(tt) = 1 15.31/4.76 POL(u) = 0 15.31/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.76 15.31/4.76 active(U21(tt, V2)) -> mark(U22(isList(V2))) 15.31/4.76 active(U31(tt)) -> mark(tt) 15.31/4.76 active(U52(tt)) -> mark(tt) 15.31/4.76 active(U81(tt)) -> mark(tt) 15.31/4.76 active(isList(V)) -> mark(U11(isNeList(V))) 15.31/4.76 active(isList(nil)) -> mark(tt) 15.31/4.76 active(isNeList(__(V1, V2))) -> mark(U41(isList(V1), V2)) 15.31/4.76 active(isQid(a)) -> mark(tt) 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (18) 15.31/4.76 Obligation: 15.31/4.76 Q restricted rewrite system: 15.31/4.76 The TRS R consists of the following rules: 15.31/4.76 15.31/4.76 active(U11(tt)) -> mark(tt) 15.31/4.76 active(U61(tt)) -> mark(tt) 15.31/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.31/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.31/4.76 mark(nil) -> active(nil) 15.31/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.31/4.76 mark(tt) -> active(tt) 15.31/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.31/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.31/4.76 mark(isList(X)) -> active(isList(X)) 15.31/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.31/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.31/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.31/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.31/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.31/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.31/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.31/4.76 mark(isPal(X)) -> active(isPal(X)) 15.31/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.31/4.76 mark(isQid(X)) -> active(isQid(X)) 15.31/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.31/4.76 mark(a) -> active(a) 15.31/4.76 mark(e) -> active(e) 15.31/4.76 mark(i) -> active(i) 15.31/4.76 mark(o) -> active(o) 15.31/4.76 mark(u) -> active(u) 15.31/4.76 __(mark(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.31/4.76 __(active(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, active(X2)) -> __(X1, X2) 15.31/4.76 U11(mark(X)) -> U11(X) 15.31/4.76 U11(active(X)) -> U11(X) 15.31/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.31/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.31/4.76 U22(mark(X)) -> U22(X) 15.31/4.76 U22(active(X)) -> U22(X) 15.31/4.76 isList(mark(X)) -> isList(X) 15.31/4.76 isList(active(X)) -> isList(X) 15.31/4.76 U31(mark(X)) -> U31(X) 15.31/4.76 U31(active(X)) -> U31(X) 15.31/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.31/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.31/4.76 U42(mark(X)) -> U42(X) 15.31/4.76 U42(active(X)) -> U42(X) 15.31/4.76 isNeList(mark(X)) -> isNeList(X) 15.31/4.76 isNeList(active(X)) -> isNeList(X) 15.31/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.31/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.31/4.76 U52(mark(X)) -> U52(X) 15.31/4.76 U52(active(X)) -> U52(X) 15.31/4.76 U61(mark(X)) -> U61(X) 15.31/4.76 U61(active(X)) -> U61(X) 15.31/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.31/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.31/4.76 U72(mark(X)) -> U72(X) 15.31/4.76 U72(active(X)) -> U72(X) 15.31/4.76 isPal(mark(X)) -> isPal(X) 15.31/4.76 isPal(active(X)) -> isPal(X) 15.31/4.76 U81(mark(X)) -> U81(X) 15.31/4.76 U81(active(X)) -> U81(X) 15.31/4.76 isQid(mark(X)) -> isQid(X) 15.31/4.76 isQid(active(X)) -> isQid(X) 15.31/4.76 isNePal(mark(X)) -> isNePal(X) 15.31/4.76 isNePal(active(X)) -> isNePal(X) 15.31/4.76 15.31/4.76 The set Q consists of the following terms: 15.31/4.76 15.31/4.76 active(__(__(x0, x1), x2)) 15.31/4.76 active(__(x0, nil)) 15.31/4.76 active(__(nil, x0)) 15.31/4.76 active(U11(tt)) 15.31/4.76 active(U21(tt, x0)) 15.31/4.76 active(U22(tt)) 15.31/4.76 active(U31(tt)) 15.31/4.76 active(U41(tt, x0)) 15.31/4.76 active(U42(tt)) 15.31/4.76 active(U51(tt, x0)) 15.31/4.76 active(U52(tt)) 15.31/4.76 active(U61(tt)) 15.31/4.76 active(U71(tt, x0)) 15.31/4.76 active(U72(tt)) 15.31/4.76 active(U81(tt)) 15.31/4.76 active(isList(x0)) 15.31/4.76 active(isNeList(x0)) 15.31/4.76 active(isNePal(x0)) 15.31/4.76 active(isPal(x0)) 15.31/4.76 active(isQid(a)) 15.31/4.76 active(isQid(e)) 15.31/4.76 active(isQid(i)) 15.31/4.76 active(isQid(o)) 15.31/4.76 active(isQid(u)) 15.31/4.76 mark(__(x0, x1)) 15.31/4.76 mark(nil) 15.31/4.76 mark(U11(x0)) 15.31/4.76 mark(tt) 15.31/4.76 mark(U21(x0, x1)) 15.31/4.76 mark(U22(x0)) 15.31/4.76 mark(isList(x0)) 15.31/4.76 mark(U31(x0)) 15.31/4.76 mark(U41(x0, x1)) 15.31/4.76 mark(U42(x0)) 15.31/4.76 mark(isNeList(x0)) 15.31/4.76 mark(U51(x0, x1)) 15.31/4.76 mark(U52(x0)) 15.31/4.76 mark(U61(x0)) 15.31/4.76 mark(U71(x0, x1)) 15.31/4.76 mark(U72(x0)) 15.31/4.76 mark(isPal(x0)) 15.31/4.76 mark(U81(x0)) 15.31/4.76 mark(isQid(x0)) 15.31/4.76 mark(isNePal(x0)) 15.31/4.76 mark(a) 15.31/4.76 mark(e) 15.31/4.76 mark(i) 15.31/4.76 mark(o) 15.31/4.76 mark(u) 15.31/4.76 __(mark(x0), x1) 15.31/4.76 __(x0, mark(x1)) 15.31/4.76 __(active(x0), x1) 15.31/4.76 __(x0, active(x1)) 15.31/4.76 U11(mark(x0)) 15.31/4.76 U11(active(x0)) 15.31/4.76 U21(mark(x0), x1) 15.31/4.76 U21(x0, mark(x1)) 15.31/4.76 U21(active(x0), x1) 15.31/4.76 U21(x0, active(x1)) 15.31/4.76 U22(mark(x0)) 15.31/4.76 U22(active(x0)) 15.31/4.76 isList(mark(x0)) 15.31/4.76 isList(active(x0)) 15.31/4.76 U31(mark(x0)) 15.31/4.76 U31(active(x0)) 15.31/4.76 U41(mark(x0), x1) 15.31/4.76 U41(x0, mark(x1)) 15.31/4.76 U41(active(x0), x1) 15.31/4.76 U41(x0, active(x1)) 15.31/4.76 U42(mark(x0)) 15.31/4.76 U42(active(x0)) 15.31/4.76 isNeList(mark(x0)) 15.31/4.76 isNeList(active(x0)) 15.31/4.76 U51(mark(x0), x1) 15.31/4.76 U51(x0, mark(x1)) 15.31/4.76 U51(active(x0), x1) 15.31/4.76 U51(x0, active(x1)) 15.31/4.76 U52(mark(x0)) 15.31/4.76 U52(active(x0)) 15.31/4.76 U61(mark(x0)) 15.31/4.76 U61(active(x0)) 15.31/4.76 U71(mark(x0), x1) 15.31/4.76 U71(x0, mark(x1)) 15.31/4.76 U71(active(x0), x1) 15.31/4.76 U71(x0, active(x1)) 15.31/4.76 U72(mark(x0)) 15.31/4.76 U72(active(x0)) 15.31/4.76 isPal(mark(x0)) 15.31/4.76 isPal(active(x0)) 15.31/4.76 U81(mark(x0)) 15.31/4.76 U81(active(x0)) 15.31/4.76 isQid(mark(x0)) 15.31/4.76 isQid(active(x0)) 15.31/4.76 isNePal(mark(x0)) 15.31/4.76 isNePal(active(x0)) 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (19) QTRSRRRProof (EQUIVALENT) 15.31/4.76 Used ordering: 15.31/4.76 Polynomial interpretation [POLO]: 15.31/4.76 15.31/4.76 POL(U11(x_1)) = 1 + x_1 15.31/4.76 POL(U21(x_1, x_2)) = 1 + x_1 + 2*x_2 15.31/4.76 POL(U22(x_1)) = 1 + 2*x_1 15.31/4.76 POL(U31(x_1)) = x_1 15.31/4.76 POL(U41(x_1, x_2)) = 1 + x_1 + x_2 15.31/4.76 POL(U42(x_1)) = 1 + x_1 15.31/4.76 POL(U51(x_1, x_2)) = 1 + 2*x_1 + x_2 15.31/4.76 POL(U52(x_1)) = 2*x_1 15.31/4.76 POL(U61(x_1)) = x_1 15.31/4.76 POL(U71(x_1, x_2)) = 1 + x_1 + 2*x_2 15.31/4.76 POL(U72(x_1)) = 1 + x_1 15.31/4.76 POL(U81(x_1)) = 1 + 2*x_1 15.31/4.76 POL(__(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 15.31/4.76 POL(a) = 0 15.31/4.76 POL(active(x_1)) = x_1 15.31/4.76 POL(e) = 0 15.31/4.76 POL(i) = 0 15.31/4.76 POL(isList(x_1)) = 1 + 2*x_1 15.31/4.76 POL(isNeList(x_1)) = 1 + 2*x_1 15.31/4.76 POL(isNePal(x_1)) = 2*x_1 15.31/4.76 POL(isPal(x_1)) = 1 + 2*x_1 15.31/4.76 POL(isQid(x_1)) = x_1 15.31/4.76 POL(mark(x_1)) = 2*x_1 15.31/4.76 POL(nil) = 0 15.31/4.76 POL(o) = 0 15.31/4.76 POL(tt) = 0 15.31/4.76 POL(u) = 1 15.31/4.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.76 15.31/4.76 active(U11(tt)) -> mark(tt) 15.31/4.76 active(isNeList(V)) -> mark(U31(isQid(V))) 15.31/4.76 mark(__(X1, X2)) -> active(__(mark(X1), mark(X2))) 15.31/4.76 mark(U11(X)) -> active(U11(mark(X))) 15.31/4.76 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 15.31/4.76 mark(U22(X)) -> active(U22(mark(X))) 15.31/4.76 mark(isList(X)) -> active(isList(X)) 15.31/4.76 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 15.31/4.76 mark(U42(X)) -> active(U42(mark(X))) 15.31/4.76 mark(isNeList(X)) -> active(isNeList(X)) 15.31/4.76 mark(U51(X1, X2)) -> active(U51(mark(X1), X2)) 15.31/4.76 mark(U71(X1, X2)) -> active(U71(mark(X1), X2)) 15.31/4.76 mark(U72(X)) -> active(U72(mark(X))) 15.31/4.76 mark(isPal(X)) -> active(isPal(X)) 15.31/4.76 mark(U81(X)) -> active(U81(mark(X))) 15.31/4.76 mark(u) -> active(u) 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (20) 15.31/4.76 Obligation: 15.31/4.76 Q restricted rewrite system: 15.31/4.76 The TRS R consists of the following rules: 15.31/4.76 15.31/4.76 active(U61(tt)) -> mark(tt) 15.31/4.76 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.76 mark(nil) -> active(nil) 15.31/4.76 mark(tt) -> active(tt) 15.31/4.76 mark(U31(X)) -> active(U31(mark(X))) 15.31/4.76 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.76 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.76 mark(isQid(X)) -> active(isQid(X)) 15.31/4.76 mark(isNePal(X)) -> active(isNePal(X)) 15.31/4.76 mark(a) -> active(a) 15.31/4.76 mark(e) -> active(e) 15.31/4.76 mark(i) -> active(i) 15.31/4.76 mark(o) -> active(o) 15.31/4.76 __(mark(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, mark(X2)) -> __(X1, X2) 15.31/4.76 __(active(X1), X2) -> __(X1, X2) 15.31/4.76 __(X1, active(X2)) -> __(X1, X2) 15.31/4.76 U11(mark(X)) -> U11(X) 15.31/4.76 U11(active(X)) -> U11(X) 15.31/4.76 U21(mark(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, mark(X2)) -> U21(X1, X2) 15.31/4.76 U21(active(X1), X2) -> U21(X1, X2) 15.31/4.76 U21(X1, active(X2)) -> U21(X1, X2) 15.31/4.76 U22(mark(X)) -> U22(X) 15.31/4.76 U22(active(X)) -> U22(X) 15.31/4.76 isList(mark(X)) -> isList(X) 15.31/4.76 isList(active(X)) -> isList(X) 15.31/4.76 U31(mark(X)) -> U31(X) 15.31/4.76 U31(active(X)) -> U31(X) 15.31/4.76 U41(mark(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, mark(X2)) -> U41(X1, X2) 15.31/4.76 U41(active(X1), X2) -> U41(X1, X2) 15.31/4.76 U41(X1, active(X2)) -> U41(X1, X2) 15.31/4.76 U42(mark(X)) -> U42(X) 15.31/4.76 U42(active(X)) -> U42(X) 15.31/4.76 isNeList(mark(X)) -> isNeList(X) 15.31/4.76 isNeList(active(X)) -> isNeList(X) 15.31/4.76 U51(mark(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, mark(X2)) -> U51(X1, X2) 15.31/4.76 U51(active(X1), X2) -> U51(X1, X2) 15.31/4.76 U51(X1, active(X2)) -> U51(X1, X2) 15.31/4.76 U52(mark(X)) -> U52(X) 15.31/4.76 U52(active(X)) -> U52(X) 15.31/4.76 U61(mark(X)) -> U61(X) 15.31/4.76 U61(active(X)) -> U61(X) 15.31/4.76 U71(mark(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, mark(X2)) -> U71(X1, X2) 15.31/4.76 U71(active(X1), X2) -> U71(X1, X2) 15.31/4.76 U71(X1, active(X2)) -> U71(X1, X2) 15.31/4.76 U72(mark(X)) -> U72(X) 15.31/4.76 U72(active(X)) -> U72(X) 15.31/4.76 isPal(mark(X)) -> isPal(X) 15.31/4.76 isPal(active(X)) -> isPal(X) 15.31/4.76 U81(mark(X)) -> U81(X) 15.31/4.76 U81(active(X)) -> U81(X) 15.31/4.76 isQid(mark(X)) -> isQid(X) 15.31/4.76 isQid(active(X)) -> isQid(X) 15.31/4.76 isNePal(mark(X)) -> isNePal(X) 15.31/4.76 isNePal(active(X)) -> isNePal(X) 15.31/4.76 15.31/4.76 The set Q consists of the following terms: 15.31/4.76 15.31/4.76 active(__(__(x0, x1), x2)) 15.31/4.76 active(__(x0, nil)) 15.31/4.76 active(__(nil, x0)) 15.31/4.76 active(U11(tt)) 15.31/4.76 active(U21(tt, x0)) 15.31/4.76 active(U22(tt)) 15.31/4.76 active(U31(tt)) 15.31/4.76 active(U41(tt, x0)) 15.31/4.76 active(U42(tt)) 15.31/4.76 active(U51(tt, x0)) 15.31/4.76 active(U52(tt)) 15.31/4.76 active(U61(tt)) 15.31/4.76 active(U71(tt, x0)) 15.31/4.76 active(U72(tt)) 15.31/4.76 active(U81(tt)) 15.31/4.76 active(isList(x0)) 15.31/4.76 active(isNeList(x0)) 15.31/4.76 active(isNePal(x0)) 15.31/4.76 active(isPal(x0)) 15.31/4.76 active(isQid(a)) 15.31/4.76 active(isQid(e)) 15.31/4.76 active(isQid(i)) 15.31/4.76 active(isQid(o)) 15.31/4.76 active(isQid(u)) 15.31/4.76 mark(__(x0, x1)) 15.31/4.76 mark(nil) 15.31/4.76 mark(U11(x0)) 15.31/4.76 mark(tt) 15.31/4.76 mark(U21(x0, x1)) 15.31/4.76 mark(U22(x0)) 15.31/4.76 mark(isList(x0)) 15.31/4.76 mark(U31(x0)) 15.31/4.76 mark(U41(x0, x1)) 15.31/4.76 mark(U42(x0)) 15.31/4.76 mark(isNeList(x0)) 15.31/4.76 mark(U51(x0, x1)) 15.31/4.76 mark(U52(x0)) 15.31/4.76 mark(U61(x0)) 15.31/4.76 mark(U71(x0, x1)) 15.31/4.76 mark(U72(x0)) 15.31/4.76 mark(isPal(x0)) 15.31/4.76 mark(U81(x0)) 15.31/4.76 mark(isQid(x0)) 15.31/4.76 mark(isNePal(x0)) 15.31/4.76 mark(a) 15.31/4.76 mark(e) 15.31/4.76 mark(i) 15.31/4.76 mark(o) 15.31/4.76 mark(u) 15.31/4.76 __(mark(x0), x1) 15.31/4.76 __(x0, mark(x1)) 15.31/4.76 __(active(x0), x1) 15.31/4.76 __(x0, active(x1)) 15.31/4.76 U11(mark(x0)) 15.31/4.76 U11(active(x0)) 15.31/4.76 U21(mark(x0), x1) 15.31/4.76 U21(x0, mark(x1)) 15.31/4.76 U21(active(x0), x1) 15.31/4.76 U21(x0, active(x1)) 15.31/4.76 U22(mark(x0)) 15.31/4.76 U22(active(x0)) 15.31/4.76 isList(mark(x0)) 15.31/4.76 isList(active(x0)) 15.31/4.76 U31(mark(x0)) 15.31/4.76 U31(active(x0)) 15.31/4.76 U41(mark(x0), x1) 15.31/4.76 U41(x0, mark(x1)) 15.31/4.76 U41(active(x0), x1) 15.31/4.76 U41(x0, active(x1)) 15.31/4.76 U42(mark(x0)) 15.31/4.76 U42(active(x0)) 15.31/4.76 isNeList(mark(x0)) 15.31/4.76 isNeList(active(x0)) 15.31/4.76 U51(mark(x0), x1) 15.31/4.76 U51(x0, mark(x1)) 15.31/4.76 U51(active(x0), x1) 15.31/4.76 U51(x0, active(x1)) 15.31/4.76 U52(mark(x0)) 15.31/4.76 U52(active(x0)) 15.31/4.76 U61(mark(x0)) 15.31/4.76 U61(active(x0)) 15.31/4.76 U71(mark(x0), x1) 15.31/4.76 U71(x0, mark(x1)) 15.31/4.76 U71(active(x0), x1) 15.31/4.76 U71(x0, active(x1)) 15.31/4.76 U72(mark(x0)) 15.31/4.76 U72(active(x0)) 15.31/4.76 isPal(mark(x0)) 15.31/4.76 isPal(active(x0)) 15.31/4.76 U81(mark(x0)) 15.31/4.76 U81(active(x0)) 15.31/4.76 isQid(mark(x0)) 15.31/4.76 isQid(active(x0)) 15.31/4.76 isNePal(mark(x0)) 15.31/4.76 isNePal(active(x0)) 15.31/4.76 15.31/4.76 15.31/4.76 ---------------------------------------- 15.31/4.76 15.31/4.76 (21) QTRSRRRProof (EQUIVALENT) 15.31/4.76 Used ordering: 15.31/4.76 Polynomial interpretation [POLO]: 15.31/4.76 15.31/4.76 POL(U11(x_1)) = x_1 15.31/4.76 POL(U21(x_1, x_2)) = x_1 + x_2 15.31/4.76 POL(U22(x_1)) = x_1 15.31/4.76 POL(U31(x_1)) = 2 + 2*x_1 15.31/4.76 POL(U41(x_1, x_2)) = x_1 + x_2 15.31/4.77 POL(U42(x_1)) = x_1 15.31/4.77 POL(U51(x_1, x_2)) = x_1 + x_2 15.31/4.77 POL(U52(x_1)) = 1 + x_1 15.31/4.77 POL(U61(x_1)) = 1 + x_1 15.31/4.77 POL(U71(x_1, x_2)) = x_1 + x_2 15.31/4.77 POL(U72(x_1)) = x_1 15.31/4.77 POL(U81(x_1)) = x_1 15.31/4.77 POL(__(x_1, x_2)) = x_1 + x_2 15.31/4.77 POL(a) = 0 15.31/4.77 POL(active(x_1)) = 1 + x_1 15.31/4.77 POL(e) = 1 15.31/4.77 POL(i) = 1 15.31/4.77 POL(isList(x_1)) = x_1 15.31/4.77 POL(isNeList(x_1)) = x_1 15.31/4.77 POL(isNePal(x_1)) = 2 + 2*x_1 15.31/4.77 POL(isPal(x_1)) = x_1 15.31/4.77 POL(isQid(x_1)) = x_1 15.31/4.77 POL(mark(x_1)) = 1 + 2*x_1 15.31/4.77 POL(nil) = 2 15.31/4.77 POL(o) = 1 15.31/4.77 POL(tt) = 0 15.31/4.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.77 15.31/4.77 active(U61(tt)) -> mark(tt) 15.31/4.77 mark(nil) -> active(nil) 15.31/4.77 mark(isNePal(X)) -> active(isNePal(X)) 15.31/4.77 mark(e) -> active(e) 15.31/4.77 mark(i) -> active(i) 15.31/4.77 mark(o) -> active(o) 15.31/4.77 __(mark(X1), X2) -> __(X1, X2) 15.31/4.77 __(X1, mark(X2)) -> __(X1, X2) 15.31/4.77 __(active(X1), X2) -> __(X1, X2) 15.31/4.77 __(X1, active(X2)) -> __(X1, X2) 15.31/4.77 U11(mark(X)) -> U11(X) 15.31/4.77 U11(active(X)) -> U11(X) 15.31/4.77 U21(mark(X1), X2) -> U21(X1, X2) 15.31/4.77 U21(X1, mark(X2)) -> U21(X1, X2) 15.31/4.77 U21(active(X1), X2) -> U21(X1, X2) 15.31/4.77 U21(X1, active(X2)) -> U21(X1, X2) 15.31/4.77 U22(mark(X)) -> U22(X) 15.31/4.77 U22(active(X)) -> U22(X) 15.31/4.77 isList(mark(X)) -> isList(X) 15.31/4.77 isList(active(X)) -> isList(X) 15.31/4.77 U31(mark(X)) -> U31(X) 15.31/4.77 U31(active(X)) -> U31(X) 15.31/4.77 U41(mark(X1), X2) -> U41(X1, X2) 15.31/4.77 U41(X1, mark(X2)) -> U41(X1, X2) 15.31/4.77 U41(active(X1), X2) -> U41(X1, X2) 15.31/4.77 U41(X1, active(X2)) -> U41(X1, X2) 15.31/4.77 U42(mark(X)) -> U42(X) 15.31/4.77 U42(active(X)) -> U42(X) 15.31/4.77 isNeList(mark(X)) -> isNeList(X) 15.31/4.77 isNeList(active(X)) -> isNeList(X) 15.31/4.77 U51(mark(X1), X2) -> U51(X1, X2) 15.31/4.77 U51(X1, mark(X2)) -> U51(X1, X2) 15.31/4.77 U51(active(X1), X2) -> U51(X1, X2) 15.31/4.77 U51(X1, active(X2)) -> U51(X1, X2) 15.31/4.77 U52(mark(X)) -> U52(X) 15.31/4.77 U52(active(X)) -> U52(X) 15.31/4.77 U61(mark(X)) -> U61(X) 15.31/4.77 U61(active(X)) -> U61(X) 15.31/4.77 U71(mark(X1), X2) -> U71(X1, X2) 15.31/4.77 U71(X1, mark(X2)) -> U71(X1, X2) 15.31/4.77 U71(active(X1), X2) -> U71(X1, X2) 15.31/4.77 U71(X1, active(X2)) -> U71(X1, X2) 15.31/4.77 U72(mark(X)) -> U72(X) 15.31/4.77 U72(active(X)) -> U72(X) 15.31/4.77 isPal(mark(X)) -> isPal(X) 15.31/4.77 isPal(active(X)) -> isPal(X) 15.31/4.77 U81(mark(X)) -> U81(X) 15.31/4.77 U81(active(X)) -> U81(X) 15.31/4.77 isQid(mark(X)) -> isQid(X) 15.31/4.77 isQid(active(X)) -> isQid(X) 15.31/4.77 isNePal(mark(X)) -> isNePal(X) 15.31/4.77 isNePal(active(X)) -> isNePal(X) 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (22) 15.31/4.77 Obligation: 15.31/4.77 Q restricted rewrite system: 15.31/4.77 The TRS R consists of the following rules: 15.31/4.77 15.31/4.77 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.77 mark(tt) -> active(tt) 15.31/4.77 mark(U31(X)) -> active(U31(mark(X))) 15.31/4.77 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.77 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.77 mark(isQid(X)) -> active(isQid(X)) 15.31/4.77 mark(a) -> active(a) 15.31/4.77 15.31/4.77 The set Q consists of the following terms: 15.31/4.77 15.31/4.77 active(__(__(x0, x1), x2)) 15.31/4.77 active(__(x0, nil)) 15.31/4.77 active(__(nil, x0)) 15.31/4.77 active(U11(tt)) 15.31/4.77 active(U21(tt, x0)) 15.31/4.77 active(U22(tt)) 15.31/4.77 active(U31(tt)) 15.31/4.77 active(U41(tt, x0)) 15.31/4.77 active(U42(tt)) 15.31/4.77 active(U51(tt, x0)) 15.31/4.77 active(U52(tt)) 15.31/4.77 active(U61(tt)) 15.31/4.77 active(U71(tt, x0)) 15.31/4.77 active(U72(tt)) 15.31/4.77 active(U81(tt)) 15.31/4.77 active(isList(x0)) 15.31/4.77 active(isNeList(x0)) 15.31/4.77 active(isNePal(x0)) 15.31/4.77 active(isPal(x0)) 15.31/4.77 active(isQid(a)) 15.31/4.77 active(isQid(e)) 15.31/4.77 active(isQid(i)) 15.31/4.77 active(isQid(o)) 15.31/4.77 active(isQid(u)) 15.31/4.77 mark(__(x0, x1)) 15.31/4.77 mark(nil) 15.31/4.77 mark(U11(x0)) 15.31/4.77 mark(tt) 15.31/4.77 mark(U21(x0, x1)) 15.31/4.77 mark(U22(x0)) 15.31/4.77 mark(isList(x0)) 15.31/4.77 mark(U31(x0)) 15.31/4.77 mark(U41(x0, x1)) 15.31/4.77 mark(U42(x0)) 15.31/4.77 mark(isNeList(x0)) 15.31/4.77 mark(U51(x0, x1)) 15.31/4.77 mark(U52(x0)) 15.31/4.77 mark(U61(x0)) 15.31/4.77 mark(U71(x0, x1)) 15.31/4.77 mark(U72(x0)) 15.31/4.77 mark(isPal(x0)) 15.31/4.77 mark(U81(x0)) 15.31/4.77 mark(isQid(x0)) 15.31/4.77 mark(isNePal(x0)) 15.31/4.77 mark(a) 15.31/4.77 mark(e) 15.31/4.77 mark(i) 15.31/4.77 mark(o) 15.31/4.77 mark(u) 15.31/4.77 __(mark(x0), x1) 15.31/4.77 __(x0, mark(x1)) 15.31/4.77 __(active(x0), x1) 15.31/4.77 __(x0, active(x1)) 15.31/4.77 U11(mark(x0)) 15.31/4.77 U11(active(x0)) 15.31/4.77 U21(mark(x0), x1) 15.31/4.77 U21(x0, mark(x1)) 15.31/4.77 U21(active(x0), x1) 15.31/4.77 U21(x0, active(x1)) 15.31/4.77 U22(mark(x0)) 15.31/4.77 U22(active(x0)) 15.31/4.77 isList(mark(x0)) 15.31/4.77 isList(active(x0)) 15.31/4.77 U31(mark(x0)) 15.31/4.77 U31(active(x0)) 15.31/4.77 U41(mark(x0), x1) 15.31/4.77 U41(x0, mark(x1)) 15.31/4.77 U41(active(x0), x1) 15.31/4.77 U41(x0, active(x1)) 15.31/4.77 U42(mark(x0)) 15.31/4.77 U42(active(x0)) 15.31/4.77 isNeList(mark(x0)) 15.31/4.77 isNeList(active(x0)) 15.31/4.77 U51(mark(x0), x1) 15.31/4.77 U51(x0, mark(x1)) 15.31/4.77 U51(active(x0), x1) 15.31/4.77 U51(x0, active(x1)) 15.31/4.77 U52(mark(x0)) 15.31/4.77 U52(active(x0)) 15.31/4.77 U61(mark(x0)) 15.31/4.77 U61(active(x0)) 15.31/4.77 U71(mark(x0), x1) 15.31/4.77 U71(x0, mark(x1)) 15.31/4.77 U71(active(x0), x1) 15.31/4.77 U71(x0, active(x1)) 15.31/4.77 U72(mark(x0)) 15.31/4.77 U72(active(x0)) 15.31/4.77 isPal(mark(x0)) 15.31/4.77 isPal(active(x0)) 15.31/4.77 U81(mark(x0)) 15.31/4.77 U81(active(x0)) 15.31/4.77 isQid(mark(x0)) 15.31/4.77 isQid(active(x0)) 15.31/4.77 isNePal(mark(x0)) 15.31/4.77 isNePal(active(x0)) 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (23) QTRSRRRProof (EQUIVALENT) 15.31/4.77 Used ordering: 15.31/4.77 Polynomial interpretation [POLO]: 15.31/4.77 15.31/4.77 POL(U31(x_1)) = 1 + x_1 15.31/4.77 POL(U52(x_1)) = x_1 15.31/4.77 POL(U61(x_1)) = x_1 15.31/4.77 POL(a) = 0 15.31/4.77 POL(active(x_1)) = x_1 15.31/4.77 POL(isNePal(x_1)) = 2*x_1 15.31/4.77 POL(isQid(x_1)) = x_1 15.31/4.77 POL(mark(x_1)) = 2*x_1 15.31/4.77 POL(tt) = 0 15.31/4.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.77 15.31/4.77 mark(U31(X)) -> active(U31(mark(X))) 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (24) 15.31/4.77 Obligation: 15.31/4.77 Q restricted rewrite system: 15.31/4.77 The TRS R consists of the following rules: 15.31/4.77 15.31/4.77 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.77 mark(tt) -> active(tt) 15.31/4.77 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.77 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.77 mark(isQid(X)) -> active(isQid(X)) 15.31/4.77 mark(a) -> active(a) 15.31/4.77 15.31/4.77 The set Q consists of the following terms: 15.31/4.77 15.31/4.77 active(__(__(x0, x1), x2)) 15.31/4.77 active(__(x0, nil)) 15.31/4.77 active(__(nil, x0)) 15.31/4.77 active(U11(tt)) 15.31/4.77 active(U21(tt, x0)) 15.31/4.77 active(U22(tt)) 15.31/4.77 active(U31(tt)) 15.31/4.77 active(U41(tt, x0)) 15.31/4.77 active(U42(tt)) 15.31/4.77 active(U51(tt, x0)) 15.31/4.77 active(U52(tt)) 15.31/4.77 active(U61(tt)) 15.31/4.77 active(U71(tt, x0)) 15.31/4.77 active(U72(tt)) 15.31/4.77 active(U81(tt)) 15.31/4.77 active(isList(x0)) 15.31/4.77 active(isNeList(x0)) 15.31/4.77 active(isNePal(x0)) 15.31/4.77 active(isPal(x0)) 15.31/4.77 active(isQid(a)) 15.31/4.77 active(isQid(e)) 15.31/4.77 active(isQid(i)) 15.31/4.77 active(isQid(o)) 15.31/4.77 active(isQid(u)) 15.31/4.77 mark(__(x0, x1)) 15.31/4.77 mark(nil) 15.31/4.77 mark(U11(x0)) 15.31/4.77 mark(tt) 15.31/4.77 mark(U21(x0, x1)) 15.31/4.77 mark(U22(x0)) 15.31/4.77 mark(isList(x0)) 15.31/4.77 mark(U31(x0)) 15.31/4.77 mark(U41(x0, x1)) 15.31/4.77 mark(U42(x0)) 15.31/4.77 mark(isNeList(x0)) 15.31/4.77 mark(U51(x0, x1)) 15.31/4.77 mark(U52(x0)) 15.31/4.77 mark(U61(x0)) 15.31/4.77 mark(U71(x0, x1)) 15.31/4.77 mark(U72(x0)) 15.31/4.77 mark(isPal(x0)) 15.31/4.77 mark(U81(x0)) 15.31/4.77 mark(isQid(x0)) 15.31/4.77 mark(isNePal(x0)) 15.31/4.77 mark(a) 15.31/4.77 mark(e) 15.31/4.77 mark(i) 15.31/4.77 mark(o) 15.31/4.77 mark(u) 15.31/4.77 __(mark(x0), x1) 15.31/4.77 __(x0, mark(x1)) 15.31/4.77 __(active(x0), x1) 15.31/4.77 __(x0, active(x1)) 15.31/4.77 U11(mark(x0)) 15.31/4.77 U11(active(x0)) 15.31/4.77 U21(mark(x0), x1) 15.31/4.77 U21(x0, mark(x1)) 15.31/4.77 U21(active(x0), x1) 15.31/4.77 U21(x0, active(x1)) 15.31/4.77 U22(mark(x0)) 15.31/4.77 U22(active(x0)) 15.31/4.77 isList(mark(x0)) 15.31/4.77 isList(active(x0)) 15.31/4.77 U31(mark(x0)) 15.31/4.77 U31(active(x0)) 15.31/4.77 U41(mark(x0), x1) 15.31/4.77 U41(x0, mark(x1)) 15.31/4.77 U41(active(x0), x1) 15.31/4.77 U41(x0, active(x1)) 15.31/4.77 U42(mark(x0)) 15.31/4.77 U42(active(x0)) 15.31/4.77 isNeList(mark(x0)) 15.31/4.77 isNeList(active(x0)) 15.31/4.77 U51(mark(x0), x1) 15.31/4.77 U51(x0, mark(x1)) 15.31/4.77 U51(active(x0), x1) 15.31/4.77 U51(x0, active(x1)) 15.31/4.77 U52(mark(x0)) 15.31/4.77 U52(active(x0)) 15.31/4.77 U61(mark(x0)) 15.31/4.77 U61(active(x0)) 15.31/4.77 U71(mark(x0), x1) 15.31/4.77 U71(x0, mark(x1)) 15.31/4.77 U71(active(x0), x1) 15.31/4.77 U71(x0, active(x1)) 15.31/4.77 U72(mark(x0)) 15.31/4.77 U72(active(x0)) 15.31/4.77 isPal(mark(x0)) 15.31/4.77 isPal(active(x0)) 15.31/4.77 U81(mark(x0)) 15.31/4.77 U81(active(x0)) 15.31/4.77 isQid(mark(x0)) 15.31/4.77 isQid(active(x0)) 15.31/4.77 isNePal(mark(x0)) 15.31/4.77 isNePal(active(x0)) 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (25) QTRSRRRProof (EQUIVALENT) 15.31/4.77 Used ordering: 15.31/4.77 Polynomial interpretation [POLO]: 15.31/4.77 15.31/4.77 POL(U52(x_1)) = 1 + x_1 15.31/4.77 POL(U61(x_1)) = x_1 15.31/4.77 POL(a) = 0 15.31/4.77 POL(active(x_1)) = x_1 15.31/4.77 POL(isNePal(x_1)) = 2*x_1 15.31/4.77 POL(isQid(x_1)) = x_1 15.31/4.77 POL(mark(x_1)) = 2*x_1 15.31/4.77 POL(tt) = 1 15.31/4.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.77 15.31/4.77 mark(tt) -> active(tt) 15.31/4.77 mark(U52(X)) -> active(U52(mark(X))) 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (26) 15.31/4.77 Obligation: 15.31/4.77 Q restricted rewrite system: 15.31/4.77 The TRS R consists of the following rules: 15.31/4.77 15.31/4.77 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.77 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.77 mark(isQid(X)) -> active(isQid(X)) 15.31/4.77 mark(a) -> active(a) 15.31/4.77 15.31/4.77 The set Q consists of the following terms: 15.31/4.77 15.31/4.77 active(__(__(x0, x1), x2)) 15.31/4.77 active(__(x0, nil)) 15.31/4.77 active(__(nil, x0)) 15.31/4.77 active(U11(tt)) 15.31/4.77 active(U21(tt, x0)) 15.31/4.77 active(U22(tt)) 15.31/4.77 active(U31(tt)) 15.31/4.77 active(U41(tt, x0)) 15.31/4.77 active(U42(tt)) 15.31/4.77 active(U51(tt, x0)) 15.31/4.77 active(U52(tt)) 15.31/4.77 active(U61(tt)) 15.31/4.77 active(U71(tt, x0)) 15.31/4.77 active(U72(tt)) 15.31/4.77 active(U81(tt)) 15.31/4.77 active(isList(x0)) 15.31/4.77 active(isNeList(x0)) 15.31/4.77 active(isNePal(x0)) 15.31/4.77 active(isPal(x0)) 15.31/4.77 active(isQid(a)) 15.31/4.77 active(isQid(e)) 15.31/4.77 active(isQid(i)) 15.31/4.77 active(isQid(o)) 15.31/4.77 active(isQid(u)) 15.31/4.77 mark(__(x0, x1)) 15.31/4.77 mark(nil) 15.31/4.77 mark(U11(x0)) 15.31/4.77 mark(tt) 15.31/4.77 mark(U21(x0, x1)) 15.31/4.77 mark(U22(x0)) 15.31/4.77 mark(isList(x0)) 15.31/4.77 mark(U31(x0)) 15.31/4.77 mark(U41(x0, x1)) 15.31/4.77 mark(U42(x0)) 15.31/4.77 mark(isNeList(x0)) 15.31/4.77 mark(U51(x0, x1)) 15.31/4.77 mark(U52(x0)) 15.31/4.77 mark(U61(x0)) 15.31/4.77 mark(U71(x0, x1)) 15.31/4.77 mark(U72(x0)) 15.31/4.77 mark(isPal(x0)) 15.31/4.77 mark(U81(x0)) 15.31/4.77 mark(isQid(x0)) 15.31/4.77 mark(isNePal(x0)) 15.31/4.77 mark(a) 15.31/4.77 mark(e) 15.31/4.77 mark(i) 15.31/4.77 mark(o) 15.31/4.77 mark(u) 15.31/4.77 __(mark(x0), x1) 15.31/4.77 __(x0, mark(x1)) 15.31/4.77 __(active(x0), x1) 15.31/4.77 __(x0, active(x1)) 15.31/4.77 U11(mark(x0)) 15.31/4.77 U11(active(x0)) 15.31/4.77 U21(mark(x0), x1) 15.31/4.77 U21(x0, mark(x1)) 15.31/4.77 U21(active(x0), x1) 15.31/4.77 U21(x0, active(x1)) 15.31/4.77 U22(mark(x0)) 15.31/4.77 U22(active(x0)) 15.31/4.77 isList(mark(x0)) 15.31/4.77 isList(active(x0)) 15.31/4.77 U31(mark(x0)) 15.31/4.77 U31(active(x0)) 15.31/4.77 U41(mark(x0), x1) 15.31/4.77 U41(x0, mark(x1)) 15.31/4.77 U41(active(x0), x1) 15.31/4.77 U41(x0, active(x1)) 15.31/4.77 U42(mark(x0)) 15.31/4.77 U42(active(x0)) 15.31/4.77 isNeList(mark(x0)) 15.31/4.77 isNeList(active(x0)) 15.31/4.77 U51(mark(x0), x1) 15.31/4.77 U51(x0, mark(x1)) 15.31/4.77 U51(active(x0), x1) 15.31/4.77 U51(x0, active(x1)) 15.31/4.77 U52(mark(x0)) 15.31/4.77 U52(active(x0)) 15.31/4.77 U61(mark(x0)) 15.31/4.77 U61(active(x0)) 15.31/4.77 U71(mark(x0), x1) 15.31/4.77 U71(x0, mark(x1)) 15.31/4.77 U71(active(x0), x1) 15.31/4.77 U71(x0, active(x1)) 15.31/4.77 U72(mark(x0)) 15.31/4.77 U72(active(x0)) 15.31/4.77 isPal(mark(x0)) 15.31/4.77 isPal(active(x0)) 15.31/4.77 U81(mark(x0)) 15.31/4.77 U81(active(x0)) 15.31/4.77 isQid(mark(x0)) 15.31/4.77 isQid(active(x0)) 15.31/4.77 isNePal(mark(x0)) 15.31/4.77 isNePal(active(x0)) 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (27) QTRSRRRProof (EQUIVALENT) 15.31/4.77 Used ordering: 15.31/4.77 Polynomial interpretation [POLO]: 15.31/4.77 15.31/4.77 POL(U61(x_1)) = 2*x_1 15.31/4.77 POL(a) = 0 15.31/4.77 POL(active(x_1)) = x_1 15.31/4.77 POL(isNePal(x_1)) = 2 + 2*x_1 15.31/4.77 POL(isQid(x_1)) = x_1 15.31/4.77 POL(mark(x_1)) = x_1 15.31/4.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.77 15.31/4.77 active(isNePal(V)) -> mark(U61(isQid(V))) 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (28) 15.31/4.77 Obligation: 15.31/4.77 Q restricted rewrite system: 15.31/4.77 The TRS R consists of the following rules: 15.31/4.77 15.31/4.77 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.77 mark(isQid(X)) -> active(isQid(X)) 15.31/4.77 mark(a) -> active(a) 15.31/4.77 15.31/4.77 The set Q consists of the following terms: 15.31/4.77 15.31/4.77 active(__(__(x0, x1), x2)) 15.31/4.77 active(__(x0, nil)) 15.31/4.77 active(__(nil, x0)) 15.31/4.77 active(U11(tt)) 15.31/4.77 active(U21(tt, x0)) 15.31/4.77 active(U22(tt)) 15.31/4.77 active(U31(tt)) 15.31/4.77 active(U41(tt, x0)) 15.31/4.77 active(U42(tt)) 15.31/4.77 active(U51(tt, x0)) 15.31/4.77 active(U52(tt)) 15.31/4.77 active(U61(tt)) 15.31/4.77 active(U71(tt, x0)) 15.31/4.77 active(U72(tt)) 15.31/4.77 active(U81(tt)) 15.31/4.77 active(isList(x0)) 15.31/4.77 active(isNeList(x0)) 15.31/4.77 active(isNePal(x0)) 15.31/4.77 active(isPal(x0)) 15.31/4.77 active(isQid(a)) 15.31/4.77 active(isQid(e)) 15.31/4.77 active(isQid(i)) 15.31/4.77 active(isQid(o)) 15.31/4.77 active(isQid(u)) 15.31/4.77 mark(__(x0, x1)) 15.31/4.77 mark(nil) 15.31/4.77 mark(U11(x0)) 15.31/4.77 mark(tt) 15.31/4.77 mark(U21(x0, x1)) 15.31/4.77 mark(U22(x0)) 15.31/4.77 mark(isList(x0)) 15.31/4.77 mark(U31(x0)) 15.31/4.77 mark(U41(x0, x1)) 15.31/4.77 mark(U42(x0)) 15.31/4.77 mark(isNeList(x0)) 15.31/4.77 mark(U51(x0, x1)) 15.31/4.77 mark(U52(x0)) 15.31/4.77 mark(U61(x0)) 15.31/4.77 mark(U71(x0, x1)) 15.31/4.77 mark(U72(x0)) 15.31/4.77 mark(isPal(x0)) 15.31/4.77 mark(U81(x0)) 15.31/4.77 mark(isQid(x0)) 15.31/4.77 mark(isNePal(x0)) 15.31/4.77 mark(a) 15.31/4.77 mark(e) 15.31/4.77 mark(i) 15.31/4.77 mark(o) 15.31/4.77 mark(u) 15.31/4.77 __(mark(x0), x1) 15.31/4.77 __(x0, mark(x1)) 15.31/4.77 __(active(x0), x1) 15.31/4.77 __(x0, active(x1)) 15.31/4.77 U11(mark(x0)) 15.31/4.77 U11(active(x0)) 15.31/4.77 U21(mark(x0), x1) 15.31/4.77 U21(x0, mark(x1)) 15.31/4.77 U21(active(x0), x1) 15.31/4.77 U21(x0, active(x1)) 15.31/4.77 U22(mark(x0)) 15.31/4.77 U22(active(x0)) 15.31/4.77 isList(mark(x0)) 15.31/4.77 isList(active(x0)) 15.31/4.77 U31(mark(x0)) 15.31/4.77 U31(active(x0)) 15.31/4.77 U41(mark(x0), x1) 15.31/4.77 U41(x0, mark(x1)) 15.31/4.77 U41(active(x0), x1) 15.31/4.77 U41(x0, active(x1)) 15.31/4.77 U42(mark(x0)) 15.31/4.77 U42(active(x0)) 15.31/4.77 isNeList(mark(x0)) 15.31/4.77 isNeList(active(x0)) 15.31/4.77 U51(mark(x0), x1) 15.31/4.77 U51(x0, mark(x1)) 15.31/4.77 U51(active(x0), x1) 15.31/4.77 U51(x0, active(x1)) 15.31/4.77 U52(mark(x0)) 15.31/4.77 U52(active(x0)) 15.31/4.77 U61(mark(x0)) 15.31/4.77 U61(active(x0)) 15.31/4.77 U71(mark(x0), x1) 15.31/4.77 U71(x0, mark(x1)) 15.31/4.77 U71(active(x0), x1) 15.31/4.77 U71(x0, active(x1)) 15.31/4.77 U72(mark(x0)) 15.31/4.77 U72(active(x0)) 15.31/4.77 isPal(mark(x0)) 15.31/4.77 isPal(active(x0)) 15.31/4.77 U81(mark(x0)) 15.31/4.77 U81(active(x0)) 15.31/4.77 isQid(mark(x0)) 15.31/4.77 isQid(active(x0)) 15.31/4.77 isNePal(mark(x0)) 15.31/4.77 isNePal(active(x0)) 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (29) QTRSRRRProof (EQUIVALENT) 15.31/4.77 Used ordering: 15.31/4.77 Polynomial interpretation [POLO]: 15.31/4.77 15.31/4.77 POL(U61(x_1)) = 1 + x_1 15.31/4.77 POL(a) = 2 15.31/4.77 POL(active(x_1)) = x_1 15.31/4.77 POL(isQid(x_1)) = 2 + 2*x_1 15.31/4.77 POL(mark(x_1)) = 1 + 2*x_1 15.31/4.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 15.31/4.77 15.31/4.77 mark(U61(X)) -> active(U61(mark(X))) 15.31/4.77 mark(isQid(X)) -> active(isQid(X)) 15.31/4.77 mark(a) -> active(a) 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (30) 15.31/4.77 Obligation: 15.31/4.77 Q restricted rewrite system: 15.31/4.77 R is empty. 15.31/4.77 The set Q consists of the following terms: 15.31/4.77 15.31/4.77 active(__(__(x0, x1), x2)) 15.31/4.77 active(__(x0, nil)) 15.31/4.77 active(__(nil, x0)) 15.31/4.77 active(U11(tt)) 15.31/4.77 active(U21(tt, x0)) 15.31/4.77 active(U22(tt)) 15.31/4.77 active(U31(tt)) 15.31/4.77 active(U41(tt, x0)) 15.31/4.77 active(U42(tt)) 15.31/4.77 active(U51(tt, x0)) 15.31/4.77 active(U52(tt)) 15.31/4.77 active(U61(tt)) 15.31/4.77 active(U71(tt, x0)) 15.31/4.77 active(U72(tt)) 15.31/4.77 active(U81(tt)) 15.31/4.77 active(isList(x0)) 15.31/4.77 active(isNeList(x0)) 15.31/4.77 active(isNePal(x0)) 15.31/4.77 active(isPal(x0)) 15.31/4.77 active(isQid(a)) 15.31/4.77 active(isQid(e)) 15.31/4.77 active(isQid(i)) 15.31/4.77 active(isQid(o)) 15.31/4.77 active(isQid(u)) 15.31/4.77 mark(__(x0, x1)) 15.31/4.77 mark(nil) 15.31/4.77 mark(U11(x0)) 15.31/4.77 mark(tt) 15.31/4.77 mark(U21(x0, x1)) 15.31/4.77 mark(U22(x0)) 15.31/4.77 mark(isList(x0)) 15.31/4.77 mark(U31(x0)) 15.31/4.77 mark(U41(x0, x1)) 15.31/4.77 mark(U42(x0)) 15.31/4.77 mark(isNeList(x0)) 15.31/4.77 mark(U51(x0, x1)) 15.31/4.77 mark(U52(x0)) 15.31/4.77 mark(U61(x0)) 15.31/4.77 mark(U71(x0, x1)) 15.31/4.77 mark(U72(x0)) 15.31/4.77 mark(isPal(x0)) 15.31/4.77 mark(U81(x0)) 15.31/4.77 mark(isQid(x0)) 15.31/4.77 mark(isNePal(x0)) 15.31/4.77 mark(a) 15.31/4.77 mark(e) 15.31/4.77 mark(i) 15.31/4.77 mark(o) 15.31/4.77 mark(u) 15.31/4.77 __(mark(x0), x1) 15.31/4.77 __(x0, mark(x1)) 15.31/4.77 __(active(x0), x1) 15.31/4.77 __(x0, active(x1)) 15.31/4.77 U11(mark(x0)) 15.31/4.77 U11(active(x0)) 15.31/4.77 U21(mark(x0), x1) 15.31/4.77 U21(x0, mark(x1)) 15.31/4.77 U21(active(x0), x1) 15.31/4.77 U21(x0, active(x1)) 15.31/4.77 U22(mark(x0)) 15.31/4.77 U22(active(x0)) 15.31/4.77 isList(mark(x0)) 15.31/4.77 isList(active(x0)) 15.31/4.77 U31(mark(x0)) 15.31/4.77 U31(active(x0)) 15.31/4.77 U41(mark(x0), x1) 15.31/4.77 U41(x0, mark(x1)) 15.31/4.77 U41(active(x0), x1) 15.31/4.77 U41(x0, active(x1)) 15.31/4.77 U42(mark(x0)) 15.31/4.77 U42(active(x0)) 15.31/4.77 isNeList(mark(x0)) 15.31/4.77 isNeList(active(x0)) 15.31/4.77 U51(mark(x0), x1) 15.31/4.77 U51(x0, mark(x1)) 15.31/4.77 U51(active(x0), x1) 15.31/4.77 U51(x0, active(x1)) 15.31/4.77 U52(mark(x0)) 15.31/4.77 U52(active(x0)) 15.31/4.77 U61(mark(x0)) 15.31/4.77 U61(active(x0)) 15.31/4.77 U71(mark(x0), x1) 15.31/4.77 U71(x0, mark(x1)) 15.31/4.77 U71(active(x0), x1) 15.31/4.77 U71(x0, active(x1)) 15.31/4.77 U72(mark(x0)) 15.31/4.77 U72(active(x0)) 15.31/4.77 isPal(mark(x0)) 15.31/4.77 isPal(active(x0)) 15.31/4.77 U81(mark(x0)) 15.31/4.77 U81(active(x0)) 15.31/4.77 isQid(mark(x0)) 15.31/4.77 isQid(active(x0)) 15.31/4.77 isNePal(mark(x0)) 15.31/4.77 isNePal(active(x0)) 15.31/4.77 15.31/4.77 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (31) RisEmptyProof (EQUIVALENT) 15.31/4.77 The TRS R is empty. Hence, termination is trivially proven. 15.31/4.77 ---------------------------------------- 15.31/4.77 15.31/4.77 (32) 15.31/4.77 YES 15.35/4.82 EOF