7.24/2.77 YES 7.57/2.80 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.57/2.80 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.57/2.80 7.57/2.80 7.57/2.80 Termination w.r.t. Q of the given QTRS could be proven: 7.57/2.80 7.57/2.80 (0) QTRS 7.57/2.80 (1) QTRSToCSRProof [SOUND, 0 ms] 7.57/2.80 (2) CSR 7.57/2.80 (3) CSRRRRProof [EQUIVALENT, 107 ms] 7.57/2.80 (4) CSR 7.57/2.80 (5) CSRRRRProof [EQUIVALENT, 51 ms] 7.57/2.80 (6) CSR 7.57/2.80 (7) CSRRRRProof [EQUIVALENT, 32 ms] 7.57/2.80 (8) CSR 7.57/2.80 (9) CSRRRRProof [EQUIVALENT, 13 ms] 7.57/2.80 (10) CSR 7.57/2.80 (11) CSRRRRProof [EQUIVALENT, 15 ms] 7.57/2.80 (12) CSR 7.57/2.80 (13) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (14) CSR 7.57/2.80 (15) CSRRRRProof [EQUIVALENT, 7 ms] 7.57/2.80 (16) CSR 7.57/2.80 (17) CSRRRRProof [EQUIVALENT, 12 ms] 7.57/2.80 (18) CSR 7.57/2.80 (19) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (20) CSR 7.57/2.80 (21) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (22) CSR 7.57/2.80 (23) CSRRRRProof [EQUIVALENT, 9 ms] 7.57/2.80 (24) CSR 7.57/2.80 (25) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (26) CSR 7.57/2.80 (27) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (28) CSR 7.57/2.80 (29) CSRRRRProof [EQUIVALENT, 0 ms] 7.57/2.80 (30) CSR 7.57/2.80 (31) RisEmptyProof [EQUIVALENT, 0 ms] 7.57/2.80 (32) YES 7.57/2.80 7.57/2.80 7.57/2.80 ---------------------------------------- 7.57/2.80 7.57/2.80 (0) 7.57/2.80 Obligation: 7.57/2.80 Q restricted rewrite system: 7.57/2.80 The TRS R consists of the following rules: 7.57/2.80 7.57/2.80 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 7.57/2.80 active(__(X, nil)) -> mark(X) 7.57/2.80 active(__(nil, X)) -> mark(X) 7.57/2.80 active(U11(tt, V)) -> mark(U12(isPalListKind(V), V)) 7.57/2.80 active(U12(tt, V)) -> mark(U13(isNeList(V))) 7.57/2.80 active(U13(tt)) -> mark(tt) 7.57/2.80 active(U21(tt, V1, V2)) -> mark(U22(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U22(tt, V1, V2)) -> mark(U23(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U23(tt, V1, V2)) -> mark(U24(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U24(tt, V1, V2)) -> mark(U25(isList(V1), V2)) 7.57/2.80 active(U25(tt, V2)) -> mark(U26(isList(V2))) 7.57/2.80 active(U26(tt)) -> mark(tt) 7.57/2.80 active(U31(tt, V)) -> mark(U32(isPalListKind(V), V)) 7.57/2.80 active(U32(tt, V)) -> mark(U33(isQid(V))) 7.57/2.80 active(U33(tt)) -> mark(tt) 7.57/2.80 active(U41(tt, V1, V2)) -> mark(U42(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U42(tt, V1, V2)) -> mark(U43(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U43(tt, V1, V2)) -> mark(U44(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U44(tt, V1, V2)) -> mark(U45(isList(V1), V2)) 7.57/2.80 active(U45(tt, V2)) -> mark(U46(isNeList(V2))) 7.57/2.80 active(U46(tt)) -> mark(tt) 7.57/2.80 active(U51(tt, V1, V2)) -> mark(U52(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U52(tt, V1, V2)) -> mark(U53(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U53(tt, V1, V2)) -> mark(U54(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U54(tt, V1, V2)) -> mark(U55(isNeList(V1), V2)) 7.57/2.80 active(U55(tt, V2)) -> mark(U56(isList(V2))) 7.57/2.80 active(U56(tt)) -> mark(tt) 7.57/2.80 active(U61(tt, V)) -> mark(U62(isPalListKind(V), V)) 7.57/2.80 active(U62(tt, V)) -> mark(U63(isQid(V))) 7.57/2.80 active(U63(tt)) -> mark(tt) 7.57/2.80 active(U71(tt, I, P)) -> mark(U72(isPalListKind(I), P)) 7.57/2.80 active(U72(tt, P)) -> mark(U73(isPal(P), P)) 7.57/2.80 active(U73(tt, P)) -> mark(U74(isPalListKind(P))) 7.57/2.80 active(U74(tt)) -> mark(tt) 7.57/2.80 active(U81(tt, V)) -> mark(U82(isPalListKind(V), V)) 7.57/2.80 active(U82(tt, V)) -> mark(U83(isNePal(V))) 7.57/2.80 active(U83(tt)) -> mark(tt) 7.57/2.80 active(U91(tt, V2)) -> mark(U92(isPalListKind(V2))) 7.57/2.80 active(U92(tt)) -> mark(tt) 7.57/2.80 active(isList(V)) -> mark(U11(isPalListKind(V), V)) 7.57/2.80 active(isList(nil)) -> mark(tt) 7.57/2.80 active(isList(__(V1, V2))) -> mark(U21(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNeList(V)) -> mark(U31(isPalListKind(V), V)) 7.57/2.80 active(isNeList(__(V1, V2))) -> mark(U41(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNeList(__(V1, V2))) -> mark(U51(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNePal(V)) -> mark(U61(isPalListKind(V), V)) 7.57/2.80 active(isNePal(__(I, __(P, I)))) -> mark(U71(isQid(I), I, P)) 7.57/2.80 active(isPal(V)) -> mark(U81(isPalListKind(V), V)) 7.57/2.80 active(isPal(nil)) -> mark(tt) 7.57/2.80 active(isPalListKind(a)) -> mark(tt) 7.57/2.80 active(isPalListKind(e)) -> mark(tt) 7.57/2.80 active(isPalListKind(i)) -> mark(tt) 7.57/2.80 active(isPalListKind(nil)) -> mark(tt) 7.57/2.80 active(isPalListKind(o)) -> mark(tt) 7.57/2.80 active(isPalListKind(u)) -> mark(tt) 7.57/2.80 active(isPalListKind(__(V1, V2))) -> mark(U91(isPalListKind(V1), V2)) 7.57/2.80 active(isQid(a)) -> mark(tt) 7.57/2.80 active(isQid(e)) -> mark(tt) 7.57/2.80 active(isQid(i)) -> mark(tt) 7.57/2.80 active(isQid(o)) -> mark(tt) 7.57/2.80 active(isQid(u)) -> mark(tt) 7.57/2.80 active(__(X1, X2)) -> __(active(X1), X2) 7.57/2.80 active(__(X1, X2)) -> __(X1, active(X2)) 7.57/2.80 active(U11(X1, X2)) -> U11(active(X1), X2) 7.57/2.80 active(U12(X1, X2)) -> U12(active(X1), X2) 7.57/2.80 active(U13(X)) -> U13(active(X)) 7.57/2.80 active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3) 7.57/2.80 active(U22(X1, X2, X3)) -> U22(active(X1), X2, X3) 7.57/2.80 active(U23(X1, X2, X3)) -> U23(active(X1), X2, X3) 7.57/2.80 active(U24(X1, X2, X3)) -> U24(active(X1), X2, X3) 7.57/2.80 active(U25(X1, X2)) -> U25(active(X1), X2) 7.57/2.80 active(U26(X)) -> U26(active(X)) 7.57/2.80 active(U31(X1, X2)) -> U31(active(X1), X2) 7.57/2.80 active(U32(X1, X2)) -> U32(active(X1), X2) 7.57/2.80 active(U33(X)) -> U33(active(X)) 7.57/2.80 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 7.57/2.80 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 7.57/2.80 active(U43(X1, X2, X3)) -> U43(active(X1), X2, X3) 7.57/2.80 active(U44(X1, X2, X3)) -> U44(active(X1), X2, X3) 7.57/2.80 active(U45(X1, X2)) -> U45(active(X1), X2) 7.57/2.80 active(U46(X)) -> U46(active(X)) 7.57/2.80 active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) 7.57/2.80 active(U52(X1, X2, X3)) -> U52(active(X1), X2, X3) 7.57/2.80 active(U53(X1, X2, X3)) -> U53(active(X1), X2, X3) 7.57/2.80 active(U54(X1, X2, X3)) -> U54(active(X1), X2, X3) 7.57/2.80 active(U55(X1, X2)) -> U55(active(X1), X2) 7.57/2.80 active(U56(X)) -> U56(active(X)) 7.57/2.80 active(U61(X1, X2)) -> U61(active(X1), X2) 7.57/2.80 active(U62(X1, X2)) -> U62(active(X1), X2) 7.57/2.80 active(U63(X)) -> U63(active(X)) 7.57/2.80 active(U71(X1, X2, X3)) -> U71(active(X1), X2, X3) 7.57/2.80 active(U72(X1, X2)) -> U72(active(X1), X2) 7.57/2.80 active(U73(X1, X2)) -> U73(active(X1), X2) 7.57/2.80 active(U74(X)) -> U74(active(X)) 7.57/2.80 active(U81(X1, X2)) -> U81(active(X1), X2) 7.57/2.80 active(U82(X1, X2)) -> U82(active(X1), X2) 7.57/2.80 active(U83(X)) -> U83(active(X)) 7.57/2.80 active(U91(X1, X2)) -> U91(active(X1), X2) 7.57/2.80 active(U92(X)) -> U92(active(X)) 7.57/2.80 __(mark(X1), X2) -> mark(__(X1, X2)) 7.57/2.80 __(X1, mark(X2)) -> mark(__(X1, X2)) 7.57/2.80 U11(mark(X1), X2) -> mark(U11(X1, X2)) 7.57/2.80 U12(mark(X1), X2) -> mark(U12(X1, X2)) 7.57/2.80 U13(mark(X)) -> mark(U13(X)) 7.57/2.80 U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3)) 7.57/2.80 U22(mark(X1), X2, X3) -> mark(U22(X1, X2, X3)) 7.57/2.80 U23(mark(X1), X2, X3) -> mark(U23(X1, X2, X3)) 7.57/2.80 U24(mark(X1), X2, X3) -> mark(U24(X1, X2, X3)) 7.57/2.80 U25(mark(X1), X2) -> mark(U25(X1, X2)) 7.57/2.80 U26(mark(X)) -> mark(U26(X)) 7.57/2.80 U31(mark(X1), X2) -> mark(U31(X1, X2)) 7.57/2.80 U32(mark(X1), X2) -> mark(U32(X1, X2)) 7.57/2.80 U33(mark(X)) -> mark(U33(X)) 7.57/2.80 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 7.57/2.80 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 7.57/2.80 U43(mark(X1), X2, X3) -> mark(U43(X1, X2, X3)) 7.57/2.80 U44(mark(X1), X2, X3) -> mark(U44(X1, X2, X3)) 7.57/2.80 U45(mark(X1), X2) -> mark(U45(X1, X2)) 7.57/2.80 U46(mark(X)) -> mark(U46(X)) 7.57/2.80 U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) 7.57/2.80 U52(mark(X1), X2, X3) -> mark(U52(X1, X2, X3)) 7.57/2.80 U53(mark(X1), X2, X3) -> mark(U53(X1, X2, X3)) 7.57/2.80 U54(mark(X1), X2, X3) -> mark(U54(X1, X2, X3)) 7.57/2.80 U55(mark(X1), X2) -> mark(U55(X1, X2)) 7.57/2.80 U56(mark(X)) -> mark(U56(X)) 7.57/2.80 U61(mark(X1), X2) -> mark(U61(X1, X2)) 7.57/2.80 U62(mark(X1), X2) -> mark(U62(X1, X2)) 7.57/2.80 U63(mark(X)) -> mark(U63(X)) 7.57/2.80 U71(mark(X1), X2, X3) -> mark(U71(X1, X2, X3)) 7.57/2.80 U72(mark(X1), X2) -> mark(U72(X1, X2)) 7.57/2.80 U73(mark(X1), X2) -> mark(U73(X1, X2)) 7.57/2.80 U74(mark(X)) -> mark(U74(X)) 7.57/2.80 U81(mark(X1), X2) -> mark(U81(X1, X2)) 7.57/2.80 U82(mark(X1), X2) -> mark(U82(X1, X2)) 7.57/2.80 U83(mark(X)) -> mark(U83(X)) 7.57/2.80 U91(mark(X1), X2) -> mark(U91(X1, X2)) 7.57/2.80 U92(mark(X)) -> mark(U92(X)) 7.57/2.80 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 7.57/2.80 proper(nil) -> ok(nil) 7.57/2.80 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 7.57/2.80 proper(tt) -> ok(tt) 7.57/2.80 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 7.57/2.80 proper(isPalListKind(X)) -> isPalListKind(proper(X)) 7.57/2.80 proper(U13(X)) -> U13(proper(X)) 7.57/2.80 proper(isNeList(X)) -> isNeList(proper(X)) 7.57/2.80 proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U22(X1, X2, X3)) -> U22(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U23(X1, X2, X3)) -> U23(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U24(X1, X2, X3)) -> U24(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U25(X1, X2)) -> U25(proper(X1), proper(X2)) 7.57/2.80 proper(isList(X)) -> isList(proper(X)) 7.57/2.80 proper(U26(X)) -> U26(proper(X)) 7.57/2.80 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 7.57/2.80 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 7.57/2.80 proper(U33(X)) -> U33(proper(X)) 7.57/2.80 proper(isQid(X)) -> isQid(proper(X)) 7.57/2.80 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U43(X1, X2, X3)) -> U43(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U44(X1, X2, X3)) -> U44(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U45(X1, X2)) -> U45(proper(X1), proper(X2)) 7.57/2.80 proper(U46(X)) -> U46(proper(X)) 7.57/2.80 proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U52(X1, X2, X3)) -> U52(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U53(X1, X2, X3)) -> U53(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U54(X1, X2, X3)) -> U54(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U55(X1, X2)) -> U55(proper(X1), proper(X2)) 7.57/2.80 proper(U56(X)) -> U56(proper(X)) 7.57/2.80 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 7.57/2.80 proper(U62(X1, X2)) -> U62(proper(X1), proper(X2)) 7.57/2.80 proper(U63(X)) -> U63(proper(X)) 7.57/2.80 proper(U71(X1, X2, X3)) -> U71(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 7.57/2.80 proper(U73(X1, X2)) -> U73(proper(X1), proper(X2)) 7.57/2.80 proper(isPal(X)) -> isPal(proper(X)) 7.57/2.80 proper(U74(X)) -> U74(proper(X)) 7.57/2.80 proper(U81(X1, X2)) -> U81(proper(X1), proper(X2)) 7.57/2.80 proper(U82(X1, X2)) -> U82(proper(X1), proper(X2)) 7.57/2.80 proper(U83(X)) -> U83(proper(X)) 7.57/2.80 proper(isNePal(X)) -> isNePal(proper(X)) 7.57/2.80 proper(U91(X1, X2)) -> U91(proper(X1), proper(X2)) 7.57/2.80 proper(U92(X)) -> U92(proper(X)) 7.57/2.80 proper(a) -> ok(a) 7.57/2.80 proper(e) -> ok(e) 7.57/2.80 proper(i) -> ok(i) 7.57/2.80 proper(o) -> ok(o) 7.57/2.80 proper(u) -> ok(u) 7.57/2.80 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 7.57/2.80 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 7.57/2.80 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 7.57/2.80 isPalListKind(ok(X)) -> ok(isPalListKind(X)) 7.57/2.80 U13(ok(X)) -> ok(U13(X)) 7.57/2.80 isNeList(ok(X)) -> ok(isNeList(X)) 7.57/2.80 U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3)) 7.57/2.80 U22(ok(X1), ok(X2), ok(X3)) -> ok(U22(X1, X2, X3)) 7.57/2.80 U23(ok(X1), ok(X2), ok(X3)) -> ok(U23(X1, X2, X3)) 7.57/2.80 U24(ok(X1), ok(X2), ok(X3)) -> ok(U24(X1, X2, X3)) 7.57/2.80 U25(ok(X1), ok(X2)) -> ok(U25(X1, X2)) 7.57/2.80 isList(ok(X)) -> ok(isList(X)) 7.57/2.80 U26(ok(X)) -> ok(U26(X)) 7.57/2.80 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 7.57/2.80 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 7.57/2.80 U33(ok(X)) -> ok(U33(X)) 7.57/2.80 isQid(ok(X)) -> ok(isQid(X)) 7.57/2.80 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 7.57/2.80 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 7.57/2.80 U43(ok(X1), ok(X2), ok(X3)) -> ok(U43(X1, X2, X3)) 7.57/2.80 U44(ok(X1), ok(X2), ok(X3)) -> ok(U44(X1, X2, X3)) 7.57/2.80 U45(ok(X1), ok(X2)) -> ok(U45(X1, X2)) 7.57/2.80 U46(ok(X)) -> ok(U46(X)) 7.57/2.80 U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) 7.57/2.80 U52(ok(X1), ok(X2), ok(X3)) -> ok(U52(X1, X2, X3)) 7.57/2.80 U53(ok(X1), ok(X2), ok(X3)) -> ok(U53(X1, X2, X3)) 7.57/2.80 U54(ok(X1), ok(X2), ok(X3)) -> ok(U54(X1, X2, X3)) 7.57/2.80 U55(ok(X1), ok(X2)) -> ok(U55(X1, X2)) 7.57/2.80 U56(ok(X)) -> ok(U56(X)) 7.57/2.80 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 7.57/2.80 U62(ok(X1), ok(X2)) -> ok(U62(X1, X2)) 7.57/2.80 U63(ok(X)) -> ok(U63(X)) 7.57/2.80 U71(ok(X1), ok(X2), ok(X3)) -> ok(U71(X1, X2, X3)) 7.57/2.80 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 7.57/2.80 U73(ok(X1), ok(X2)) -> ok(U73(X1, X2)) 7.57/2.80 isPal(ok(X)) -> ok(isPal(X)) 7.57/2.80 U74(ok(X)) -> ok(U74(X)) 7.57/2.80 U81(ok(X1), ok(X2)) -> ok(U81(X1, X2)) 7.57/2.80 U82(ok(X1), ok(X2)) -> ok(U82(X1, X2)) 7.57/2.80 U83(ok(X)) -> ok(U83(X)) 7.57/2.80 isNePal(ok(X)) -> ok(isNePal(X)) 7.57/2.80 U91(ok(X1), ok(X2)) -> ok(U91(X1, X2)) 7.57/2.80 U92(ok(X)) -> ok(U92(X)) 7.57/2.80 top(mark(X)) -> top(proper(X)) 7.57/2.80 top(ok(X)) -> top(active(X)) 7.57/2.80 7.57/2.80 The set Q consists of the following terms: 7.57/2.80 7.57/2.80 active(isList(x0)) 7.57/2.80 active(isNeList(x0)) 7.57/2.80 active(isNePal(x0)) 7.57/2.80 active(isPal(x0)) 7.57/2.80 active(isPalListKind(a)) 7.57/2.80 active(isPalListKind(e)) 7.57/2.80 active(isPalListKind(i)) 7.57/2.80 active(isPalListKind(nil)) 7.57/2.80 active(isPalListKind(o)) 7.57/2.80 active(isPalListKind(u)) 7.57/2.80 active(isPalListKind(__(x0, x1))) 7.57/2.80 active(isQid(a)) 7.57/2.80 active(isQid(e)) 7.57/2.80 active(isQid(i)) 7.57/2.80 active(isQid(o)) 7.57/2.80 active(isQid(u)) 7.57/2.80 active(__(x0, x1)) 7.57/2.80 active(U11(x0, x1)) 7.57/2.80 active(U12(x0, x1)) 7.57/2.80 active(U13(x0)) 7.57/2.80 active(U21(x0, x1, x2)) 7.57/2.80 active(U22(x0, x1, x2)) 7.57/2.80 active(U23(x0, x1, x2)) 7.57/2.80 active(U24(x0, x1, x2)) 7.57/2.80 active(U25(x0, x1)) 7.57/2.80 active(U26(x0)) 7.57/2.80 active(U31(x0, x1)) 7.57/2.80 active(U32(x0, x1)) 7.57/2.80 active(U33(x0)) 7.57/2.80 active(U41(x0, x1, x2)) 7.57/2.80 active(U42(x0, x1, x2)) 7.57/2.80 active(U43(x0, x1, x2)) 7.57/2.80 active(U44(x0, x1, x2)) 7.57/2.80 active(U45(x0, x1)) 7.57/2.80 active(U46(x0)) 7.57/2.80 active(U51(x0, x1, x2)) 7.57/2.80 active(U52(x0, x1, x2)) 7.57/2.80 active(U53(x0, x1, x2)) 7.57/2.80 active(U54(x0, x1, x2)) 7.57/2.80 active(U55(x0, x1)) 7.57/2.80 active(U56(x0)) 7.57/2.80 active(U61(x0, x1)) 7.57/2.80 active(U62(x0, x1)) 7.57/2.80 active(U63(x0)) 7.57/2.80 active(U71(x0, x1, x2)) 7.57/2.80 active(U72(x0, x1)) 7.57/2.80 active(U73(x0, x1)) 7.57/2.80 active(U74(x0)) 7.57/2.80 active(U81(x0, x1)) 7.57/2.80 active(U82(x0, x1)) 7.57/2.80 active(U83(x0)) 7.57/2.80 active(U91(x0, x1)) 7.57/2.80 active(U92(x0)) 7.57/2.80 __(mark(x0), x1) 7.57/2.80 __(x0, mark(x1)) 7.57/2.80 U11(mark(x0), x1) 7.57/2.80 U12(mark(x0), x1) 7.57/2.80 U13(mark(x0)) 7.57/2.80 U21(mark(x0), x1, x2) 7.57/2.80 U22(mark(x0), x1, x2) 7.57/2.80 U23(mark(x0), x1, x2) 7.57/2.80 U24(mark(x0), x1, x2) 7.57/2.80 U25(mark(x0), x1) 7.57/2.80 U26(mark(x0)) 7.57/2.80 U31(mark(x0), x1) 7.57/2.80 U32(mark(x0), x1) 7.57/2.80 U33(mark(x0)) 7.57/2.80 U41(mark(x0), x1, x2) 7.57/2.80 U42(mark(x0), x1, x2) 7.57/2.80 U43(mark(x0), x1, x2) 7.57/2.80 U44(mark(x0), x1, x2) 7.57/2.80 U45(mark(x0), x1) 7.57/2.80 U46(mark(x0)) 7.57/2.80 U51(mark(x0), x1, x2) 7.57/2.80 U52(mark(x0), x1, x2) 7.57/2.80 U53(mark(x0), x1, x2) 7.57/2.80 U54(mark(x0), x1, x2) 7.57/2.80 U55(mark(x0), x1) 7.57/2.80 U56(mark(x0)) 7.57/2.80 U61(mark(x0), x1) 7.57/2.80 U62(mark(x0), x1) 7.57/2.80 U63(mark(x0)) 7.57/2.80 U71(mark(x0), x1, x2) 7.57/2.80 U72(mark(x0), x1) 7.57/2.80 U73(mark(x0), x1) 7.57/2.80 U74(mark(x0)) 7.57/2.80 U81(mark(x0), x1) 7.57/2.80 U82(mark(x0), x1) 7.57/2.80 U83(mark(x0)) 7.57/2.80 U91(mark(x0), x1) 7.57/2.80 U92(mark(x0)) 7.57/2.80 proper(__(x0, x1)) 7.57/2.80 proper(nil) 7.57/2.80 proper(U11(x0, x1)) 7.57/2.80 proper(tt) 7.57/2.80 proper(U12(x0, x1)) 7.57/2.80 proper(isPalListKind(x0)) 7.57/2.80 proper(U13(x0)) 7.57/2.80 proper(isNeList(x0)) 7.57/2.80 proper(U21(x0, x1, x2)) 7.57/2.80 proper(U22(x0, x1, x2)) 7.57/2.80 proper(U23(x0, x1, x2)) 7.57/2.80 proper(U24(x0, x1, x2)) 7.57/2.80 proper(U25(x0, x1)) 7.57/2.80 proper(isList(x0)) 7.57/2.80 proper(U26(x0)) 7.57/2.80 proper(U31(x0, x1)) 7.57/2.80 proper(U32(x0, x1)) 7.57/2.80 proper(U33(x0)) 7.57/2.80 proper(isQid(x0)) 7.57/2.80 proper(U41(x0, x1, x2)) 7.57/2.80 proper(U42(x0, x1, x2)) 7.57/2.80 proper(U43(x0, x1, x2)) 7.57/2.80 proper(U44(x0, x1, x2)) 7.57/2.80 proper(U45(x0, x1)) 7.57/2.80 proper(U46(x0)) 7.57/2.80 proper(U51(x0, x1, x2)) 7.57/2.80 proper(U52(x0, x1, x2)) 7.57/2.80 proper(U53(x0, x1, x2)) 7.57/2.80 proper(U54(x0, x1, x2)) 7.57/2.80 proper(U55(x0, x1)) 7.57/2.80 proper(U56(x0)) 7.57/2.80 proper(U61(x0, x1)) 7.57/2.80 proper(U62(x0, x1)) 7.57/2.80 proper(U63(x0)) 7.57/2.80 proper(U71(x0, x1, x2)) 7.57/2.80 proper(U72(x0, x1)) 7.57/2.80 proper(U73(x0, x1)) 7.57/2.80 proper(isPal(x0)) 7.57/2.80 proper(U74(x0)) 7.57/2.80 proper(U81(x0, x1)) 7.57/2.80 proper(U82(x0, x1)) 7.57/2.80 proper(U83(x0)) 7.57/2.80 proper(isNePal(x0)) 7.57/2.80 proper(U91(x0, x1)) 7.57/2.80 proper(U92(x0)) 7.57/2.80 proper(a) 7.57/2.80 proper(e) 7.57/2.80 proper(i) 7.57/2.80 proper(o) 7.57/2.80 proper(u) 7.57/2.80 __(ok(x0), ok(x1)) 7.57/2.80 U11(ok(x0), ok(x1)) 7.57/2.80 U12(ok(x0), ok(x1)) 7.57/2.80 isPalListKind(ok(x0)) 7.57/2.80 U13(ok(x0)) 7.57/2.80 isNeList(ok(x0)) 7.57/2.80 U21(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U22(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U23(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U24(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U25(ok(x0), ok(x1)) 7.57/2.80 isList(ok(x0)) 7.57/2.80 U26(ok(x0)) 7.57/2.80 U31(ok(x0), ok(x1)) 7.57/2.80 U32(ok(x0), ok(x1)) 7.57/2.80 U33(ok(x0)) 7.57/2.80 isQid(ok(x0)) 7.57/2.80 U41(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U42(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U43(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U44(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U45(ok(x0), ok(x1)) 7.57/2.80 U46(ok(x0)) 7.57/2.80 U51(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U52(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U53(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U54(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U55(ok(x0), ok(x1)) 7.57/2.80 U56(ok(x0)) 7.57/2.80 U61(ok(x0), ok(x1)) 7.57/2.80 U62(ok(x0), ok(x1)) 7.57/2.80 U63(ok(x0)) 7.57/2.80 U71(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U72(ok(x0), ok(x1)) 7.57/2.80 U73(ok(x0), ok(x1)) 7.57/2.80 isPal(ok(x0)) 7.57/2.80 U74(ok(x0)) 7.57/2.80 U81(ok(x0), ok(x1)) 7.57/2.80 U82(ok(x0), ok(x1)) 7.57/2.80 U83(ok(x0)) 7.57/2.80 isNePal(ok(x0)) 7.57/2.80 U91(ok(x0), ok(x1)) 7.57/2.80 U92(ok(x0)) 7.57/2.80 top(mark(x0)) 7.57/2.80 top(ok(x0)) 7.57/2.80 7.57/2.80 7.57/2.80 ---------------------------------------- 7.57/2.80 7.57/2.80 (1) QTRSToCSRProof (SOUND) 7.57/2.80 The following Q TRS is given: Q restricted rewrite system: 7.57/2.80 The TRS R consists of the following rules: 7.57/2.80 7.57/2.80 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 7.57/2.80 active(__(X, nil)) -> mark(X) 7.57/2.80 active(__(nil, X)) -> mark(X) 7.57/2.80 active(U11(tt, V)) -> mark(U12(isPalListKind(V), V)) 7.57/2.80 active(U12(tt, V)) -> mark(U13(isNeList(V))) 7.57/2.80 active(U13(tt)) -> mark(tt) 7.57/2.80 active(U21(tt, V1, V2)) -> mark(U22(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U22(tt, V1, V2)) -> mark(U23(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U23(tt, V1, V2)) -> mark(U24(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U24(tt, V1, V2)) -> mark(U25(isList(V1), V2)) 7.57/2.80 active(U25(tt, V2)) -> mark(U26(isList(V2))) 7.57/2.80 active(U26(tt)) -> mark(tt) 7.57/2.80 active(U31(tt, V)) -> mark(U32(isPalListKind(V), V)) 7.57/2.80 active(U32(tt, V)) -> mark(U33(isQid(V))) 7.57/2.80 active(U33(tt)) -> mark(tt) 7.57/2.80 active(U41(tt, V1, V2)) -> mark(U42(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U42(tt, V1, V2)) -> mark(U43(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U43(tt, V1, V2)) -> mark(U44(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U44(tt, V1, V2)) -> mark(U45(isList(V1), V2)) 7.57/2.80 active(U45(tt, V2)) -> mark(U46(isNeList(V2))) 7.57/2.80 active(U46(tt)) -> mark(tt) 7.57/2.80 active(U51(tt, V1, V2)) -> mark(U52(isPalListKind(V1), V1, V2)) 7.57/2.80 active(U52(tt, V1, V2)) -> mark(U53(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U53(tt, V1, V2)) -> mark(U54(isPalListKind(V2), V1, V2)) 7.57/2.80 active(U54(tt, V1, V2)) -> mark(U55(isNeList(V1), V2)) 7.57/2.80 active(U55(tt, V2)) -> mark(U56(isList(V2))) 7.57/2.80 active(U56(tt)) -> mark(tt) 7.57/2.80 active(U61(tt, V)) -> mark(U62(isPalListKind(V), V)) 7.57/2.80 active(U62(tt, V)) -> mark(U63(isQid(V))) 7.57/2.80 active(U63(tt)) -> mark(tt) 7.57/2.80 active(U71(tt, I, P)) -> mark(U72(isPalListKind(I), P)) 7.57/2.80 active(U72(tt, P)) -> mark(U73(isPal(P), P)) 7.57/2.80 active(U73(tt, P)) -> mark(U74(isPalListKind(P))) 7.57/2.80 active(U74(tt)) -> mark(tt) 7.57/2.80 active(U81(tt, V)) -> mark(U82(isPalListKind(V), V)) 7.57/2.80 active(U82(tt, V)) -> mark(U83(isNePal(V))) 7.57/2.80 active(U83(tt)) -> mark(tt) 7.57/2.80 active(U91(tt, V2)) -> mark(U92(isPalListKind(V2))) 7.57/2.80 active(U92(tt)) -> mark(tt) 7.57/2.80 active(isList(V)) -> mark(U11(isPalListKind(V), V)) 7.57/2.80 active(isList(nil)) -> mark(tt) 7.57/2.80 active(isList(__(V1, V2))) -> mark(U21(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNeList(V)) -> mark(U31(isPalListKind(V), V)) 7.57/2.80 active(isNeList(__(V1, V2))) -> mark(U41(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNeList(__(V1, V2))) -> mark(U51(isPalListKind(V1), V1, V2)) 7.57/2.80 active(isNePal(V)) -> mark(U61(isPalListKind(V), V)) 7.57/2.80 active(isNePal(__(I, __(P, I)))) -> mark(U71(isQid(I), I, P)) 7.57/2.80 active(isPal(V)) -> mark(U81(isPalListKind(V), V)) 7.57/2.80 active(isPal(nil)) -> mark(tt) 7.57/2.80 active(isPalListKind(a)) -> mark(tt) 7.57/2.80 active(isPalListKind(e)) -> mark(tt) 7.57/2.80 active(isPalListKind(i)) -> mark(tt) 7.57/2.80 active(isPalListKind(nil)) -> mark(tt) 7.57/2.80 active(isPalListKind(o)) -> mark(tt) 7.57/2.80 active(isPalListKind(u)) -> mark(tt) 7.57/2.80 active(isPalListKind(__(V1, V2))) -> mark(U91(isPalListKind(V1), V2)) 7.57/2.80 active(isQid(a)) -> mark(tt) 7.57/2.80 active(isQid(e)) -> mark(tt) 7.57/2.80 active(isQid(i)) -> mark(tt) 7.57/2.80 active(isQid(o)) -> mark(tt) 7.57/2.80 active(isQid(u)) -> mark(tt) 7.57/2.80 active(__(X1, X2)) -> __(active(X1), X2) 7.57/2.80 active(__(X1, X2)) -> __(X1, active(X2)) 7.57/2.80 active(U11(X1, X2)) -> U11(active(X1), X2) 7.57/2.80 active(U12(X1, X2)) -> U12(active(X1), X2) 7.57/2.80 active(U13(X)) -> U13(active(X)) 7.57/2.80 active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3) 7.57/2.80 active(U22(X1, X2, X3)) -> U22(active(X1), X2, X3) 7.57/2.80 active(U23(X1, X2, X3)) -> U23(active(X1), X2, X3) 7.57/2.80 active(U24(X1, X2, X3)) -> U24(active(X1), X2, X3) 7.57/2.80 active(U25(X1, X2)) -> U25(active(X1), X2) 7.57/2.80 active(U26(X)) -> U26(active(X)) 7.57/2.80 active(U31(X1, X2)) -> U31(active(X1), X2) 7.57/2.80 active(U32(X1, X2)) -> U32(active(X1), X2) 7.57/2.80 active(U33(X)) -> U33(active(X)) 7.57/2.80 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 7.57/2.80 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 7.57/2.80 active(U43(X1, X2, X3)) -> U43(active(X1), X2, X3) 7.57/2.80 active(U44(X1, X2, X3)) -> U44(active(X1), X2, X3) 7.57/2.80 active(U45(X1, X2)) -> U45(active(X1), X2) 7.57/2.80 active(U46(X)) -> U46(active(X)) 7.57/2.80 active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) 7.57/2.80 active(U52(X1, X2, X3)) -> U52(active(X1), X2, X3) 7.57/2.80 active(U53(X1, X2, X3)) -> U53(active(X1), X2, X3) 7.57/2.80 active(U54(X1, X2, X3)) -> U54(active(X1), X2, X3) 7.57/2.80 active(U55(X1, X2)) -> U55(active(X1), X2) 7.57/2.80 active(U56(X)) -> U56(active(X)) 7.57/2.80 active(U61(X1, X2)) -> U61(active(X1), X2) 7.57/2.80 active(U62(X1, X2)) -> U62(active(X1), X2) 7.57/2.80 active(U63(X)) -> U63(active(X)) 7.57/2.80 active(U71(X1, X2, X3)) -> U71(active(X1), X2, X3) 7.57/2.80 active(U72(X1, X2)) -> U72(active(X1), X2) 7.57/2.80 active(U73(X1, X2)) -> U73(active(X1), X2) 7.57/2.80 active(U74(X)) -> U74(active(X)) 7.57/2.80 active(U81(X1, X2)) -> U81(active(X1), X2) 7.57/2.80 active(U82(X1, X2)) -> U82(active(X1), X2) 7.57/2.80 active(U83(X)) -> U83(active(X)) 7.57/2.80 active(U91(X1, X2)) -> U91(active(X1), X2) 7.57/2.80 active(U92(X)) -> U92(active(X)) 7.57/2.80 __(mark(X1), X2) -> mark(__(X1, X2)) 7.57/2.80 __(X1, mark(X2)) -> mark(__(X1, X2)) 7.57/2.80 U11(mark(X1), X2) -> mark(U11(X1, X2)) 7.57/2.80 U12(mark(X1), X2) -> mark(U12(X1, X2)) 7.57/2.80 U13(mark(X)) -> mark(U13(X)) 7.57/2.80 U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3)) 7.57/2.80 U22(mark(X1), X2, X3) -> mark(U22(X1, X2, X3)) 7.57/2.80 U23(mark(X1), X2, X3) -> mark(U23(X1, X2, X3)) 7.57/2.80 U24(mark(X1), X2, X3) -> mark(U24(X1, X2, X3)) 7.57/2.80 U25(mark(X1), X2) -> mark(U25(X1, X2)) 7.57/2.80 U26(mark(X)) -> mark(U26(X)) 7.57/2.80 U31(mark(X1), X2) -> mark(U31(X1, X2)) 7.57/2.80 U32(mark(X1), X2) -> mark(U32(X1, X2)) 7.57/2.80 U33(mark(X)) -> mark(U33(X)) 7.57/2.80 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 7.57/2.80 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 7.57/2.80 U43(mark(X1), X2, X3) -> mark(U43(X1, X2, X3)) 7.57/2.80 U44(mark(X1), X2, X3) -> mark(U44(X1, X2, X3)) 7.57/2.80 U45(mark(X1), X2) -> mark(U45(X1, X2)) 7.57/2.80 U46(mark(X)) -> mark(U46(X)) 7.57/2.80 U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) 7.57/2.80 U52(mark(X1), X2, X3) -> mark(U52(X1, X2, X3)) 7.57/2.80 U53(mark(X1), X2, X3) -> mark(U53(X1, X2, X3)) 7.57/2.80 U54(mark(X1), X2, X3) -> mark(U54(X1, X2, X3)) 7.57/2.80 U55(mark(X1), X2) -> mark(U55(X1, X2)) 7.57/2.80 U56(mark(X)) -> mark(U56(X)) 7.57/2.80 U61(mark(X1), X2) -> mark(U61(X1, X2)) 7.57/2.80 U62(mark(X1), X2) -> mark(U62(X1, X2)) 7.57/2.80 U63(mark(X)) -> mark(U63(X)) 7.57/2.80 U71(mark(X1), X2, X3) -> mark(U71(X1, X2, X3)) 7.57/2.80 U72(mark(X1), X2) -> mark(U72(X1, X2)) 7.57/2.80 U73(mark(X1), X2) -> mark(U73(X1, X2)) 7.57/2.80 U74(mark(X)) -> mark(U74(X)) 7.57/2.80 U81(mark(X1), X2) -> mark(U81(X1, X2)) 7.57/2.80 U82(mark(X1), X2) -> mark(U82(X1, X2)) 7.57/2.80 U83(mark(X)) -> mark(U83(X)) 7.57/2.80 U91(mark(X1), X2) -> mark(U91(X1, X2)) 7.57/2.80 U92(mark(X)) -> mark(U92(X)) 7.57/2.80 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 7.57/2.80 proper(nil) -> ok(nil) 7.57/2.80 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 7.57/2.80 proper(tt) -> ok(tt) 7.57/2.80 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 7.57/2.80 proper(isPalListKind(X)) -> isPalListKind(proper(X)) 7.57/2.80 proper(U13(X)) -> U13(proper(X)) 7.57/2.80 proper(isNeList(X)) -> isNeList(proper(X)) 7.57/2.80 proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U22(X1, X2, X3)) -> U22(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U23(X1, X2, X3)) -> U23(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U24(X1, X2, X3)) -> U24(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U25(X1, X2)) -> U25(proper(X1), proper(X2)) 7.57/2.80 proper(isList(X)) -> isList(proper(X)) 7.57/2.80 proper(U26(X)) -> U26(proper(X)) 7.57/2.80 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 7.57/2.80 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 7.57/2.80 proper(U33(X)) -> U33(proper(X)) 7.57/2.80 proper(isQid(X)) -> isQid(proper(X)) 7.57/2.80 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U43(X1, X2, X3)) -> U43(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U44(X1, X2, X3)) -> U44(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U45(X1, X2)) -> U45(proper(X1), proper(X2)) 7.57/2.80 proper(U46(X)) -> U46(proper(X)) 7.57/2.80 proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U52(X1, X2, X3)) -> U52(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U53(X1, X2, X3)) -> U53(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U54(X1, X2, X3)) -> U54(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U55(X1, X2)) -> U55(proper(X1), proper(X2)) 7.57/2.80 proper(U56(X)) -> U56(proper(X)) 7.57/2.80 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 7.57/2.80 proper(U62(X1, X2)) -> U62(proper(X1), proper(X2)) 7.57/2.80 proper(U63(X)) -> U63(proper(X)) 7.57/2.80 proper(U71(X1, X2, X3)) -> U71(proper(X1), proper(X2), proper(X3)) 7.57/2.80 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 7.57/2.80 proper(U73(X1, X2)) -> U73(proper(X1), proper(X2)) 7.57/2.80 proper(isPal(X)) -> isPal(proper(X)) 7.57/2.80 proper(U74(X)) -> U74(proper(X)) 7.57/2.80 proper(U81(X1, X2)) -> U81(proper(X1), proper(X2)) 7.57/2.80 proper(U82(X1, X2)) -> U82(proper(X1), proper(X2)) 7.57/2.80 proper(U83(X)) -> U83(proper(X)) 7.57/2.80 proper(isNePal(X)) -> isNePal(proper(X)) 7.57/2.80 proper(U91(X1, X2)) -> U91(proper(X1), proper(X2)) 7.57/2.80 proper(U92(X)) -> U92(proper(X)) 7.57/2.80 proper(a) -> ok(a) 7.57/2.80 proper(e) -> ok(e) 7.57/2.80 proper(i) -> ok(i) 7.57/2.80 proper(o) -> ok(o) 7.57/2.80 proper(u) -> ok(u) 7.57/2.80 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 7.57/2.80 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 7.57/2.80 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 7.57/2.80 isPalListKind(ok(X)) -> ok(isPalListKind(X)) 7.57/2.80 U13(ok(X)) -> ok(U13(X)) 7.57/2.80 isNeList(ok(X)) -> ok(isNeList(X)) 7.57/2.80 U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3)) 7.57/2.80 U22(ok(X1), ok(X2), ok(X3)) -> ok(U22(X1, X2, X3)) 7.57/2.80 U23(ok(X1), ok(X2), ok(X3)) -> ok(U23(X1, X2, X3)) 7.57/2.80 U24(ok(X1), ok(X2), ok(X3)) -> ok(U24(X1, X2, X3)) 7.57/2.80 U25(ok(X1), ok(X2)) -> ok(U25(X1, X2)) 7.57/2.80 isList(ok(X)) -> ok(isList(X)) 7.57/2.80 U26(ok(X)) -> ok(U26(X)) 7.57/2.80 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 7.57/2.80 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 7.57/2.80 U33(ok(X)) -> ok(U33(X)) 7.57/2.80 isQid(ok(X)) -> ok(isQid(X)) 7.57/2.80 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 7.57/2.80 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 7.57/2.80 U43(ok(X1), ok(X2), ok(X3)) -> ok(U43(X1, X2, X3)) 7.57/2.80 U44(ok(X1), ok(X2), ok(X3)) -> ok(U44(X1, X2, X3)) 7.57/2.80 U45(ok(X1), ok(X2)) -> ok(U45(X1, X2)) 7.57/2.80 U46(ok(X)) -> ok(U46(X)) 7.57/2.80 U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) 7.57/2.80 U52(ok(X1), ok(X2), ok(X3)) -> ok(U52(X1, X2, X3)) 7.57/2.80 U53(ok(X1), ok(X2), ok(X3)) -> ok(U53(X1, X2, X3)) 7.57/2.80 U54(ok(X1), ok(X2), ok(X3)) -> ok(U54(X1, X2, X3)) 7.57/2.80 U55(ok(X1), ok(X2)) -> ok(U55(X1, X2)) 7.57/2.80 U56(ok(X)) -> ok(U56(X)) 7.57/2.80 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 7.57/2.80 U62(ok(X1), ok(X2)) -> ok(U62(X1, X2)) 7.57/2.80 U63(ok(X)) -> ok(U63(X)) 7.57/2.80 U71(ok(X1), ok(X2), ok(X3)) -> ok(U71(X1, X2, X3)) 7.57/2.80 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 7.57/2.80 U73(ok(X1), ok(X2)) -> ok(U73(X1, X2)) 7.57/2.80 isPal(ok(X)) -> ok(isPal(X)) 7.57/2.80 U74(ok(X)) -> ok(U74(X)) 7.57/2.80 U81(ok(X1), ok(X2)) -> ok(U81(X1, X2)) 7.57/2.80 U82(ok(X1), ok(X2)) -> ok(U82(X1, X2)) 7.57/2.80 U83(ok(X)) -> ok(U83(X)) 7.57/2.80 isNePal(ok(X)) -> ok(isNePal(X)) 7.57/2.80 U91(ok(X1), ok(X2)) -> ok(U91(X1, X2)) 7.57/2.80 U92(ok(X)) -> ok(U92(X)) 7.57/2.80 top(mark(X)) -> top(proper(X)) 7.57/2.80 top(ok(X)) -> top(active(X)) 7.57/2.80 7.57/2.80 The set Q consists of the following terms: 7.57/2.80 7.57/2.80 active(isList(x0)) 7.57/2.80 active(isNeList(x0)) 7.57/2.80 active(isNePal(x0)) 7.57/2.80 active(isPal(x0)) 7.57/2.80 active(isPalListKind(a)) 7.57/2.80 active(isPalListKind(e)) 7.57/2.80 active(isPalListKind(i)) 7.57/2.80 active(isPalListKind(nil)) 7.57/2.80 active(isPalListKind(o)) 7.57/2.80 active(isPalListKind(u)) 7.57/2.80 active(isPalListKind(__(x0, x1))) 7.57/2.80 active(isQid(a)) 7.57/2.80 active(isQid(e)) 7.57/2.80 active(isQid(i)) 7.57/2.80 active(isQid(o)) 7.57/2.80 active(isQid(u)) 7.57/2.80 active(__(x0, x1)) 7.57/2.80 active(U11(x0, x1)) 7.57/2.80 active(U12(x0, x1)) 7.57/2.80 active(U13(x0)) 7.57/2.80 active(U21(x0, x1, x2)) 7.57/2.80 active(U22(x0, x1, x2)) 7.57/2.80 active(U23(x0, x1, x2)) 7.57/2.80 active(U24(x0, x1, x2)) 7.57/2.80 active(U25(x0, x1)) 7.57/2.80 active(U26(x0)) 7.57/2.80 active(U31(x0, x1)) 7.57/2.80 active(U32(x0, x1)) 7.57/2.80 active(U33(x0)) 7.57/2.80 active(U41(x0, x1, x2)) 7.57/2.80 active(U42(x0, x1, x2)) 7.57/2.80 active(U43(x0, x1, x2)) 7.57/2.80 active(U44(x0, x1, x2)) 7.57/2.80 active(U45(x0, x1)) 7.57/2.80 active(U46(x0)) 7.57/2.80 active(U51(x0, x1, x2)) 7.57/2.80 active(U52(x0, x1, x2)) 7.57/2.80 active(U53(x0, x1, x2)) 7.57/2.80 active(U54(x0, x1, x2)) 7.57/2.80 active(U55(x0, x1)) 7.57/2.80 active(U56(x0)) 7.57/2.80 active(U61(x0, x1)) 7.57/2.80 active(U62(x0, x1)) 7.57/2.80 active(U63(x0)) 7.57/2.80 active(U71(x0, x1, x2)) 7.57/2.80 active(U72(x0, x1)) 7.57/2.80 active(U73(x0, x1)) 7.57/2.80 active(U74(x0)) 7.57/2.80 active(U81(x0, x1)) 7.57/2.80 active(U82(x0, x1)) 7.57/2.80 active(U83(x0)) 7.57/2.80 active(U91(x0, x1)) 7.57/2.80 active(U92(x0)) 7.57/2.80 __(mark(x0), x1) 7.57/2.80 __(x0, mark(x1)) 7.57/2.80 U11(mark(x0), x1) 7.57/2.80 U12(mark(x0), x1) 7.57/2.80 U13(mark(x0)) 7.57/2.80 U21(mark(x0), x1, x2) 7.57/2.80 U22(mark(x0), x1, x2) 7.57/2.80 U23(mark(x0), x1, x2) 7.57/2.80 U24(mark(x0), x1, x2) 7.57/2.80 U25(mark(x0), x1) 7.57/2.80 U26(mark(x0)) 7.57/2.80 U31(mark(x0), x1) 7.57/2.80 U32(mark(x0), x1) 7.57/2.80 U33(mark(x0)) 7.57/2.80 U41(mark(x0), x1, x2) 7.57/2.80 U42(mark(x0), x1, x2) 7.57/2.80 U43(mark(x0), x1, x2) 7.57/2.80 U44(mark(x0), x1, x2) 7.57/2.80 U45(mark(x0), x1) 7.57/2.80 U46(mark(x0)) 7.57/2.80 U51(mark(x0), x1, x2) 7.57/2.80 U52(mark(x0), x1, x2) 7.57/2.80 U53(mark(x0), x1, x2) 7.57/2.80 U54(mark(x0), x1, x2) 7.57/2.80 U55(mark(x0), x1) 7.57/2.80 U56(mark(x0)) 7.57/2.80 U61(mark(x0), x1) 7.57/2.80 U62(mark(x0), x1) 7.57/2.80 U63(mark(x0)) 7.57/2.80 U71(mark(x0), x1, x2) 7.57/2.80 U72(mark(x0), x1) 7.57/2.80 U73(mark(x0), x1) 7.57/2.80 U74(mark(x0)) 7.57/2.80 U81(mark(x0), x1) 7.57/2.80 U82(mark(x0), x1) 7.57/2.80 U83(mark(x0)) 7.57/2.80 U91(mark(x0), x1) 7.57/2.80 U92(mark(x0)) 7.57/2.80 proper(__(x0, x1)) 7.57/2.80 proper(nil) 7.57/2.80 proper(U11(x0, x1)) 7.57/2.80 proper(tt) 7.57/2.80 proper(U12(x0, x1)) 7.57/2.80 proper(isPalListKind(x0)) 7.57/2.80 proper(U13(x0)) 7.57/2.80 proper(isNeList(x0)) 7.57/2.80 proper(U21(x0, x1, x2)) 7.57/2.80 proper(U22(x0, x1, x2)) 7.57/2.80 proper(U23(x0, x1, x2)) 7.57/2.80 proper(U24(x0, x1, x2)) 7.57/2.80 proper(U25(x0, x1)) 7.57/2.80 proper(isList(x0)) 7.57/2.80 proper(U26(x0)) 7.57/2.80 proper(U31(x0, x1)) 7.57/2.80 proper(U32(x0, x1)) 7.57/2.80 proper(U33(x0)) 7.57/2.80 proper(isQid(x0)) 7.57/2.80 proper(U41(x0, x1, x2)) 7.57/2.80 proper(U42(x0, x1, x2)) 7.57/2.80 proper(U43(x0, x1, x2)) 7.57/2.80 proper(U44(x0, x1, x2)) 7.57/2.80 proper(U45(x0, x1)) 7.57/2.80 proper(U46(x0)) 7.57/2.80 proper(U51(x0, x1, x2)) 7.57/2.80 proper(U52(x0, x1, x2)) 7.57/2.80 proper(U53(x0, x1, x2)) 7.57/2.80 proper(U54(x0, x1, x2)) 7.57/2.80 proper(U55(x0, x1)) 7.57/2.80 proper(U56(x0)) 7.57/2.80 proper(U61(x0, x1)) 7.57/2.80 proper(U62(x0, x1)) 7.57/2.80 proper(U63(x0)) 7.57/2.80 proper(U71(x0, x1, x2)) 7.57/2.80 proper(U72(x0, x1)) 7.57/2.80 proper(U73(x0, x1)) 7.57/2.80 proper(isPal(x0)) 7.57/2.80 proper(U74(x0)) 7.57/2.80 proper(U81(x0, x1)) 7.57/2.80 proper(U82(x0, x1)) 7.57/2.80 proper(U83(x0)) 7.57/2.80 proper(isNePal(x0)) 7.57/2.80 proper(U91(x0, x1)) 7.57/2.80 proper(U92(x0)) 7.57/2.80 proper(a) 7.57/2.80 proper(e) 7.57/2.80 proper(i) 7.57/2.80 proper(o) 7.57/2.80 proper(u) 7.57/2.80 __(ok(x0), ok(x1)) 7.57/2.80 U11(ok(x0), ok(x1)) 7.57/2.80 U12(ok(x0), ok(x1)) 7.57/2.80 isPalListKind(ok(x0)) 7.57/2.80 U13(ok(x0)) 7.57/2.80 isNeList(ok(x0)) 7.57/2.80 U21(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U22(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U23(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U24(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U25(ok(x0), ok(x1)) 7.57/2.80 isList(ok(x0)) 7.57/2.80 U26(ok(x0)) 7.57/2.80 U31(ok(x0), ok(x1)) 7.57/2.80 U32(ok(x0), ok(x1)) 7.57/2.80 U33(ok(x0)) 7.57/2.80 isQid(ok(x0)) 7.57/2.80 U41(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U42(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U43(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U44(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U45(ok(x0), ok(x1)) 7.57/2.80 U46(ok(x0)) 7.57/2.80 U51(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U52(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U53(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U54(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U55(ok(x0), ok(x1)) 7.57/2.80 U56(ok(x0)) 7.57/2.80 U61(ok(x0), ok(x1)) 7.57/2.80 U62(ok(x0), ok(x1)) 7.57/2.80 U63(ok(x0)) 7.57/2.80 U71(ok(x0), ok(x1), ok(x2)) 7.57/2.80 U72(ok(x0), ok(x1)) 7.57/2.80 U73(ok(x0), ok(x1)) 7.57/2.80 isPal(ok(x0)) 7.57/2.80 U74(ok(x0)) 7.57/2.80 U81(ok(x0), ok(x1)) 7.57/2.80 U82(ok(x0), ok(x1)) 7.57/2.80 U83(ok(x0)) 7.57/2.80 isNePal(ok(x0)) 7.57/2.80 U91(ok(x0), ok(x1)) 7.57/2.80 U92(ok(x0)) 7.57/2.80 top(mark(x0)) 7.57/2.80 top(ok(x0)) 7.57/2.80 7.57/2.80 Special symbols used for the transformation (see [GM04]): 7.57/2.80 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 7.57/2.80 The replacement map contains the following entries: 7.57/2.80 7.57/2.80 __: {1, 2} 7.57/2.80 nil: empty set 7.57/2.80 U11: {1} 7.57/2.80 tt: empty set 7.57/2.80 U12: {1} 7.57/2.80 isPalListKind: empty set 7.57/2.80 U13: {1} 7.57/2.80 isNeList: empty set 7.57/2.80 U21: {1} 7.57/2.80 U22: {1} 7.57/2.80 U23: {1} 7.57/2.80 U24: {1} 7.57/2.80 U25: {1} 7.57/2.80 isList: empty set 7.57/2.80 U26: {1} 7.57/2.80 U31: {1} 7.57/2.80 U32: {1} 7.57/2.80 U33: {1} 7.57/2.80 isQid: empty set 7.57/2.80 U41: {1} 7.57/2.80 U42: {1} 7.57/2.80 U43: {1} 7.57/2.80 U44: {1} 7.57/2.80 U45: {1} 7.57/2.80 U46: {1} 7.57/2.80 U51: {1} 7.57/2.80 U52: {1} 7.57/2.80 U53: {1} 7.57/2.80 U54: {1} 7.57/2.80 U55: {1} 7.57/2.80 U56: {1} 7.57/2.80 U61: {1} 7.57/2.80 U62: {1} 7.57/2.80 U63: {1} 7.57/2.80 U71: {1} 7.57/2.80 U72: {1} 7.57/2.80 U73: {1} 7.57/2.80 isPal: empty set 7.57/2.80 U74: {1} 7.57/2.80 U81: {1} 7.57/2.80 U82: {1} 7.57/2.80 U83: {1} 7.57/2.80 isNePal: empty set 7.57/2.80 U91: {1} 7.57/2.80 U92: {1} 7.57/2.80 a: empty set 7.57/2.80 e: empty set 7.57/2.80 i: empty set 7.57/2.80 o: empty set 7.57/2.80 u: empty set 7.57/2.80 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 7.57/2.80 ---------------------------------------- 7.57/2.80 7.57/2.80 (2) 7.57/2.80 Obligation: 7.57/2.80 Context-sensitive rewrite system: 7.57/2.80 The TRS R consists of the following rules: 7.57/2.80 7.57/2.80 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.80 __(X, nil) -> X 7.57/2.80 __(nil, X) -> X 7.57/2.80 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.80 U12(tt, V) -> U13(isNeList(V)) 7.57/2.80 U13(tt) -> tt 7.57/2.80 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.80 U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) 7.57/2.80 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.80 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.80 U25(tt, V2) -> U26(isList(V2)) 7.57/2.80 U26(tt) -> tt 7.57/2.80 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.80 U32(tt, V) -> U33(isQid(V)) 7.57/2.80 U33(tt) -> tt 7.57/2.80 U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) 7.57/2.80 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U55(tt, V2) -> U56(isList(V2)) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U71(tt, I, P) -> U72(isPalListKind(I), P) 7.57/2.81 U72(tt, P) -> U73(isPal(P), P) 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(nil) -> tt 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPal(nil) -> tt 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 isQid(a) -> tt 7.57/2.81 isQid(e) -> tt 7.57/2.81 isQid(i) -> tt 7.57/2.81 isQid(o) -> tt 7.57/2.81 isQid(u) -> tt 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U41: {1} 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U71: {1} 7.57/2.81 U72: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (3) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 __(X, nil) -> X 7.57/2.81 __(nil, X) -> X 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U25(tt, V2) -> U26(isList(V2)) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U55(tt, V2) -> U56(isList(V2)) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U71(tt, I, P) -> U72(isPalListKind(I), P) 7.57/2.81 U72(tt, P) -> U73(isPal(P), P) 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(nil) -> tt 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPal(nil) -> tt 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 isQid(a) -> tt 7.57/2.81 isQid(e) -> tt 7.57/2.81 isQid(i) -> tt 7.57/2.81 isQid(o) -> tt 7.57/2.81 isQid(u) -> tt 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U41: {1} 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U71: {1} 7.57/2.81 U72: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U22(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U23(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U24(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U25(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U26(x_1)) = x_1 7.57/2.81 POL(U31(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U45(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U55(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U56(x_1)) = x_1 7.57/2.81 POL(U61(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + x_3 7.57/2.81 POL(U72(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U73(x_1, x_2)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U81(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U82(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = x_1 7.57/2.81 POL(isNeList(x_1)) = x_1 7.57/2.81 POL(isNePal(x_1)) = x_1 7.57/2.81 POL(isPal(x_1)) = x_1 7.57/2.81 POL(isPalListKind(x_1)) = 0 7.57/2.81 POL(isQid(x_1)) = x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 0 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 __(X, nil) -> X 7.57/2.81 __(nil, X) -> X 7.57/2.81 U25(tt, V2) -> U26(isList(V2)) 7.57/2.81 U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) 7.57/2.81 U71(tt, I, P) -> U72(isPalListKind(I), P) 7.57/2.81 isList(nil) -> tt 7.57/2.81 isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) 7.57/2.81 isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) 7.57/2.81 isPal(nil) -> tt 7.57/2.81 isQid(a) -> tt 7.57/2.81 isQid(e) -> tt 7.57/2.81 isQid(i) -> tt 7.57/2.81 isQid(o) -> tt 7.57/2.81 isQid(u) -> tt 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (4) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U55(tt, V2) -> U56(isList(V2)) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U72(tt, P) -> U73(isPal(P), P) 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U41: {1} 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U72: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (5) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U55(tt, V2) -> U56(isList(V2)) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U72(tt, P) -> U73(isPal(P), P) 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U41: {1} 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U72: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U22(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U23(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U24(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U25(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U26(x_1)) = x_1 7.57/2.81 POL(U31(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U43(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U45(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U55(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U56(x_1)) = x_1 7.57/2.81 POL(U61(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U72(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U73(x_1, x_2)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U81(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U82(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = 1 + x_1 7.57/2.81 POL(isNeList(x_1)) = 1 + x_1 7.57/2.81 POL(isNePal(x_1)) = 1 + x_1 7.57/2.81 POL(isPal(x_1)) = 1 + x_1 7.57/2.81 POL(isPalListKind(x_1)) = 1 7.57/2.81 POL(isQid(x_1)) = 1 + x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 1 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) 7.57/2.81 U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) 7.57/2.81 U55(tt, V2) -> U56(isList(V2)) 7.57/2.81 U72(tt, P) -> U73(isPal(P), P) 7.57/2.81 isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (6) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (7) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U56(tt) -> tt 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U21: {1} 7.57/2.81 U22: {1} 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U26: {1} 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U56: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U73: {1} 7.57/2.81 isPal: empty set 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = 2 + x_1 7.57/2.81 POL(U12(x_1, x_2)) = 2 + x_1 7.57/2.81 POL(U13(x_1)) = 2*x_1 7.57/2.81 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U22(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 7.57/2.81 POL(U23(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U24(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U25(x_1, x_2)) = x_1 + 2*x_2 7.57/2.81 POL(U26(x_1)) = 1 + 2*x_1 7.57/2.81 POL(U31(x_1, x_2)) = 2*x_1 7.57/2.81 POL(U32(x_1, x_2)) = x_1 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U42(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U43(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U44(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U45(x_1, x_2)) = x_1 + 2*x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = x_1 + 2*x_2 7.57/2.81 POL(U54(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 7.57/2.81 POL(U55(x_1, x_2)) = 2*x_1 7.57/2.81 POL(U56(x_1)) = 1 + 2*x_1 7.57/2.81 POL(U61(x_1, x_2)) = 2*x_1 7.57/2.81 POL(U62(x_1, x_2)) = x_1 7.57/2.81 POL(U63(x_1)) = 2*x_1 7.57/2.81 POL(U73(x_1, x_2)) = 1 + x_1 + 2*x_2 7.57/2.81 POL(U74(x_1)) = 2*x_1 7.57/2.81 POL(U81(x_1, x_2)) = 2*x_1 7.57/2.81 POL(U82(x_1, x_2)) = 2*x_1 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = 2*x_1 7.57/2.81 POL(__(x_1, x_2)) = 2*x_1 + x_2 7.57/2.81 POL(a) = 2 7.57/2.81 POL(e) = 2 7.57/2.81 POL(i) = 2 7.57/2.81 POL(isList(x_1)) = 2 + 2*x_1 7.57/2.81 POL(isNeList(x_1)) = 0 7.57/2.81 POL(isNePal(x_1)) = 0 7.57/2.81 POL(isPal(x_1)) = 2 + 2*x_1 7.57/2.81 POL(isPalListKind(x_1)) = 0 7.57/2.81 POL(isQid(x_1)) = 0 7.57/2.81 POL(nil) = 2 7.57/2.81 POL(o) = 2 7.57/2.81 POL(tt) = 0 7.57/2.81 POL(u) = 2 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U12(tt, V) -> U13(isNeList(V)) 7.57/2.81 U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) 7.57/2.81 U26(tt) -> tt 7.57/2.81 U56(tt) -> tt 7.57/2.81 U73(tt, P) -> U74(isPalListKind(P)) 7.57/2.81 isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) 7.57/2.81 isPal(V) -> U81(isPalListKind(V), V) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (8) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (9) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U23: {1} 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U42: {1} 7.57/2.81 U43: {1} 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U23(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U24(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U25(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U45(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U55(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U82(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = x_1 7.57/2.81 POL(isNeList(x_1)) = 1 + x_1 7.57/2.81 POL(isNePal(x_1)) = 1 + x_1 7.57/2.81 POL(isPalListKind(x_1)) = 0 7.57/2.81 POL(isQid(x_1)) = 1 + x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 0 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) 7.57/2.81 U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (10) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (11) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 U24: {1} 7.57/2.81 U25: {1} 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U55: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U24(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U25(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U31(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U45(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U55(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U61(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U82(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = 1 + x_1 7.57/2.81 POL(isNeList(x_1)) = 1 + x_1 7.57/2.81 POL(isNePal(x_1)) = 1 + x_1 7.57/2.81 POL(isPalListKind(x_1)) = 1 7.57/2.81 POL(isQid(x_1)) = 1 + x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 1 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U24(tt, V1, V2) -> U25(isList(V1), V2) 7.57/2.81 U45(tt, V2) -> U46(isNeList(V2)) 7.57/2.81 U54(tt, V1, V2) -> U55(isNeList(V1), V2) 7.57/2.81 U82(tt, V) -> U83(isNePal(V)) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (12) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (13) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U44: {1} 7.57/2.81 U45: {1} 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U81: {1} 7.57/2.81 U82: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U31(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U45(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U61(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(U82(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = 1 + x_1 7.57/2.81 POL(isNeList(x_1)) = 1 + x_1 7.57/2.81 POL(isNePal(x_1)) = 1 + x_1 7.57/2.81 POL(isPalListKind(x_1)) = 1 7.57/2.81 POL(isQid(x_1)) = 1 + x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 1 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U44(tt, V1, V2) -> U45(isList(V1), V2) 7.57/2.81 U81(tt, V) -> U82(isPalListKind(V), V) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (14) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (15) CSRRRRProof (EQUIVALENT) 7.57/2.81 The following CSR is given: Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.57/2.81 U63(tt) -> tt 7.57/2.81 U74(tt) -> tt 7.57/2.81 U83(tt) -> tt 7.57/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.57/2.81 U92(tt) -> tt 7.57/2.81 isList(V) -> U11(isPalListKind(V), V) 7.57/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.57/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.57/2.81 isPalListKind(a) -> tt 7.57/2.81 isPalListKind(e) -> tt 7.57/2.81 isPalListKind(i) -> tt 7.57/2.81 isPalListKind(nil) -> tt 7.57/2.81 isPalListKind(o) -> tt 7.57/2.81 isPalListKind(u) -> tt 7.57/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.57/2.81 7.57/2.81 The replacement map contains the following entries: 7.57/2.81 7.57/2.81 __: {1, 2} 7.57/2.81 nil: empty set 7.57/2.81 U11: {1} 7.57/2.81 tt: empty set 7.57/2.81 U12: {1} 7.57/2.81 isPalListKind: empty set 7.57/2.81 U13: {1} 7.57/2.81 isNeList: empty set 7.57/2.81 isList: empty set 7.57/2.81 U31: {1} 7.57/2.81 U32: {1} 7.57/2.81 U33: {1} 7.57/2.81 isQid: empty set 7.57/2.81 U46: {1} 7.57/2.81 U51: {1} 7.57/2.81 U52: {1} 7.57/2.81 U53: {1} 7.57/2.81 U54: {1} 7.57/2.81 U61: {1} 7.57/2.81 U62: {1} 7.57/2.81 U63: {1} 7.57/2.81 U74: {1} 7.57/2.81 U83: {1} 7.57/2.81 isNePal: empty set 7.57/2.81 U91: {1} 7.57/2.81 U92: {1} 7.57/2.81 a: empty set 7.57/2.81 e: empty set 7.57/2.81 i: empty set 7.57/2.81 o: empty set 7.57/2.81 u: empty set 7.57/2.81 Used ordering: 7.57/2.81 Polynomial interpretation [POLO]: 7.57/2.81 7.57/2.81 POL(U11(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U12(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U13(x_1)) = x_1 7.57/2.81 POL(U31(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U32(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U33(x_1)) = x_1 7.57/2.81 POL(U46(x_1)) = x_1 7.57/2.81 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.57/2.81 POL(U53(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.57/2.81 POL(U61(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U62(x_1, x_2)) = x_1 + x_2 7.57/2.81 POL(U63(x_1)) = x_1 7.57/2.81 POL(U74(x_1)) = x_1 7.57/2.81 POL(U83(x_1)) = x_1 7.57/2.81 POL(U91(x_1, x_2)) = x_1 7.57/2.81 POL(U92(x_1)) = x_1 7.57/2.81 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.57/2.81 POL(a) = 1 7.57/2.81 POL(e) = 1 7.57/2.81 POL(i) = 1 7.57/2.81 POL(isList(x_1)) = 1 + x_1 7.57/2.81 POL(isNeList(x_1)) = 1 + x_1 7.57/2.81 POL(isNePal(x_1)) = 1 + x_1 7.57/2.81 POL(isPalListKind(x_1)) = 1 7.57/2.81 POL(isQid(x_1)) = 1 + x_1 7.57/2.81 POL(nil) = 1 7.57/2.81 POL(o) = 1 7.57/2.81 POL(tt) = 1 7.57/2.81 POL(u) = 1 7.57/2.81 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.57/2.81 7.57/2.81 U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 7.57/2.81 ---------------------------------------- 7.57/2.81 7.57/2.81 (16) 7.57/2.81 Obligation: 7.57/2.81 Context-sensitive rewrite system: 7.57/2.81 The TRS R consists of the following rules: 7.57/2.81 7.57/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.57/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.57/2.81 U13(tt) -> tt 7.57/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.57/2.81 U32(tt, V) -> U33(isQid(V)) 7.57/2.81 U33(tt) -> tt 7.57/2.81 U46(tt) -> tt 7.57/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.57/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.57/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.57/2.81 U62(tt, V) -> U63(isQid(V)) 7.65/2.81 U63(tt) -> tt 7.65/2.81 U74(tt) -> tt 7.65/2.81 U83(tt) -> tt 7.65/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.81 U92(tt) -> tt 7.65/2.81 isList(V) -> U11(isPalListKind(V), V) 7.65/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.81 isPalListKind(a) -> tt 7.65/2.81 isPalListKind(e) -> tt 7.65/2.81 isPalListKind(i) -> tt 7.65/2.81 isPalListKind(nil) -> tt 7.65/2.81 isPalListKind(o) -> tt 7.65/2.81 isPalListKind(u) -> tt 7.65/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.81 7.65/2.81 The replacement map contains the following entries: 7.65/2.81 7.65/2.81 __: {1, 2} 7.65/2.81 nil: empty set 7.65/2.81 U11: {1} 7.65/2.81 tt: empty set 7.65/2.81 U12: {1} 7.65/2.81 isPalListKind: empty set 7.65/2.81 U13: {1} 7.65/2.81 isNeList: empty set 7.65/2.81 isList: empty set 7.65/2.81 U31: {1} 7.65/2.81 U32: {1} 7.65/2.81 U33: {1} 7.65/2.81 isQid: empty set 7.65/2.81 U46: {1} 7.65/2.81 U51: {1} 7.65/2.81 U52: {1} 7.65/2.81 U53: {1} 7.65/2.81 U54: {1} 7.65/2.81 U61: {1} 7.65/2.81 U62: {1} 7.65/2.81 U63: {1} 7.65/2.81 U74: {1} 7.65/2.81 U83: {1} 7.65/2.81 isNePal: empty set 7.65/2.81 U91: {1} 7.65/2.81 U92: {1} 7.65/2.81 a: empty set 7.65/2.81 e: empty set 7.65/2.81 i: empty set 7.65/2.81 o: empty set 7.65/2.81 u: empty set 7.65/2.81 7.65/2.81 ---------------------------------------- 7.65/2.81 7.65/2.81 (17) CSRRRRProof (EQUIVALENT) 7.65/2.81 The following CSR is given: Context-sensitive rewrite system: 7.65/2.81 The TRS R consists of the following rules: 7.65/2.81 7.65/2.81 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.81 U11(tt, V) -> U12(isPalListKind(V), V) 7.65/2.81 U13(tt) -> tt 7.65/2.81 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.81 U32(tt, V) -> U33(isQid(V)) 7.65/2.81 U33(tt) -> tt 7.65/2.81 U46(tt) -> tt 7.65/2.81 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.65/2.81 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.65/2.81 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.81 U62(tt, V) -> U63(isQid(V)) 7.65/2.81 U63(tt) -> tt 7.65/2.81 U74(tt) -> tt 7.65/2.81 U83(tt) -> tt 7.65/2.81 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.81 U92(tt) -> tt 7.65/2.81 isList(V) -> U11(isPalListKind(V), V) 7.65/2.81 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.81 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.81 isPalListKind(a) -> tt 7.65/2.81 isPalListKind(e) -> tt 7.65/2.81 isPalListKind(i) -> tt 7.65/2.81 isPalListKind(nil) -> tt 7.65/2.81 isPalListKind(o) -> tt 7.65/2.81 isPalListKind(u) -> tt 7.65/2.81 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.81 7.65/2.81 The replacement map contains the following entries: 7.65/2.81 7.65/2.81 __: {1, 2} 7.65/2.81 nil: empty set 7.65/2.81 U11: {1} 7.65/2.81 tt: empty set 7.65/2.81 U12: {1} 7.65/2.81 isPalListKind: empty set 7.65/2.81 U13: {1} 7.65/2.81 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U33: {1} 7.65/2.82 isQid: empty set 7.65/2.82 U46: {1} 7.65/2.82 U51: {1} 7.65/2.82 U52: {1} 7.65/2.82 U53: {1} 7.65/2.82 U54: {1} 7.65/2.82 U61: {1} 7.65/2.82 U62: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U11(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U12(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U13(x_1)) = x_1 7.65/2.82 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U32(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U33(x_1)) = 1 + x_1 7.65/2.82 POL(U46(x_1)) = x_1 7.65/2.82 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.65/2.82 POL(U52(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.65/2.82 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.65/2.82 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.65/2.82 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U62(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U63(x_1)) = x_1 7.65/2.82 POL(U74(x_1)) = x_1 7.65/2.82 POL(U83(x_1)) = x_1 7.65/2.82 POL(U91(x_1, x_2)) = x_1 7.65/2.82 POL(U92(x_1)) = x_1 7.65/2.82 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(a) = 1 7.65/2.82 POL(e) = 1 7.65/2.82 POL(i) = 1 7.65/2.82 POL(isList(x_1)) = 1 + x_1 7.65/2.82 POL(isNeList(x_1)) = 1 + x_1 7.65/2.82 POL(isNePal(x_1)) = 1 + x_1 7.65/2.82 POL(isPalListKind(x_1)) = 0 7.65/2.82 POL(isQid(x_1)) = x_1 7.65/2.82 POL(nil) = 1 7.65/2.82 POL(o) = 1 7.65/2.82 POL(tt) = 0 7.65/2.82 POL(u) = 1 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 U11(tt, V) -> U12(isPalListKind(V), V) 7.65/2.82 U33(tt) -> tt 7.65/2.82 U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) 7.65/2.82 U62(tt, V) -> U63(isQid(V)) 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (18) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U13(tt) -> tt 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U32(tt, V) -> U33(isQid(V)) 7.65/2.82 U46(tt) -> tt 7.65/2.82 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.65/2.82 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U13: {1} 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U33: {1} 7.65/2.82 isQid: empty set 7.65/2.82 U46: {1} 7.65/2.82 U53: {1} 7.65/2.82 U54: {1} 7.65/2.82 U61: {1} 7.65/2.82 U62: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (19) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U13(tt) -> tt 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U32(tt, V) -> U33(isQid(V)) 7.65/2.82 U46(tt) -> tt 7.65/2.82 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.65/2.82 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U13: {1} 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U33: {1} 7.65/2.82 isQid: empty set 7.65/2.82 U46: {1} 7.65/2.82 U53: {1} 7.65/2.82 U54: {1} 7.65/2.82 U61: {1} 7.65/2.82 U62: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U11(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U13(x_1)) = x_1 7.65/2.82 POL(U31(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U32(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U33(x_1)) = x_1 7.65/2.82 POL(U46(x_1)) = 1 + x_1 7.65/2.82 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 7.65/2.82 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 7.65/2.82 POL(U61(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U62(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U63(x_1)) = x_1 7.65/2.82 POL(U74(x_1)) = x_1 7.65/2.82 POL(U83(x_1)) = x_1 7.65/2.82 POL(U91(x_1, x_2)) = x_1 7.65/2.82 POL(U92(x_1)) = x_1 7.65/2.82 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(a) = 1 7.65/2.82 POL(e) = 1 7.65/2.82 POL(i) = 1 7.65/2.82 POL(isList(x_1)) = 1 + x_1 7.65/2.82 POL(isNeList(x_1)) = 1 + x_1 7.65/2.82 POL(isNePal(x_1)) = 1 + x_1 7.65/2.82 POL(isPalListKind(x_1)) = 1 7.65/2.82 POL(isQid(x_1)) = x_1 7.65/2.82 POL(nil) = 1 7.65/2.82 POL(o) = 1 7.65/2.82 POL(tt) = 1 7.65/2.82 POL(u) = 1 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 U32(tt, V) -> U33(isQid(V)) 7.65/2.82 U46(tt) -> tt 7.65/2.82 U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (20) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U13(tt) -> tt 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U13: {1} 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U61: {1} 7.65/2.82 U62: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (21) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U13(tt) -> tt 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U13: {1} 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U61: {1} 7.65/2.82 U62: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U11(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U13(x_1)) = 1 + x_1 7.65/2.82 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U32(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(U62(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U63(x_1)) = x_1 7.65/2.82 POL(U74(x_1)) = x_1 7.65/2.82 POL(U83(x_1)) = x_1 7.65/2.82 POL(U91(x_1, x_2)) = x_1 7.65/2.82 POL(U92(x_1)) = x_1 7.65/2.82 POL(__(x_1, x_2)) = 1 + x_1 + x_2 7.65/2.82 POL(a) = 1 7.65/2.82 POL(e) = 1 7.65/2.82 POL(i) = 1 7.65/2.82 POL(isList(x_1)) = 1 + x_1 7.65/2.82 POL(isNeList(x_1)) = 1 + x_1 7.65/2.82 POL(isNePal(x_1)) = 1 + x_1 7.65/2.82 POL(isPalListKind(x_1)) = 0 7.65/2.82 POL(nil) = 1 7.65/2.82 POL(o) = 1 7.65/2.82 POL(tt) = 0 7.65/2.82 POL(u) = 1 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 U13(tt) -> tt 7.65/2.82 U61(tt, V) -> U62(isPalListKind(V), V) 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (22) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U61: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (23) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 __: {1, 2} 7.65/2.82 nil: empty set 7.65/2.82 U11: {1} 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 isNeList: empty set 7.65/2.82 isList: empty set 7.65/2.82 U31: {1} 7.65/2.82 U32: {1} 7.65/2.82 U61: {1} 7.65/2.82 U63: {1} 7.65/2.82 U74: {1} 7.65/2.82 U83: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 U91: {1} 7.65/2.82 U92: {1} 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U11(x_1, x_2)) = 2*x_1 7.65/2.82 POL(U31(x_1, x_2)) = x_1 + x_2 7.65/2.82 POL(U32(x_1, x_2)) = x_1 7.65/2.82 POL(U61(x_1, x_2)) = 2 + x_1 + x_2 7.65/2.82 POL(U63(x_1)) = 1 + x_1 7.65/2.82 POL(U74(x_1)) = 2*x_1 7.65/2.82 POL(U83(x_1)) = 1 + 2*x_1 7.65/2.82 POL(U91(x_1, x_2)) = 1 + 2*x_1 + x_2 7.65/2.82 POL(U92(x_1)) = 1 + x_1 7.65/2.82 POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 7.65/2.82 POL(a) = 2 7.65/2.82 POL(e) = 2 7.65/2.82 POL(i) = 2 7.65/2.82 POL(isList(x_1)) = 2 + 2*x_1 7.65/2.82 POL(isNeList(x_1)) = 2 + 2*x_1 7.65/2.82 POL(isNePal(x_1)) = 2 + 2*x_1 7.65/2.82 POL(isPalListKind(x_1)) = x_1 7.65/2.82 POL(nil) = 2 7.65/2.82 POL(o) = 2 7.65/2.82 POL(tt) = 2 7.65/2.82 POL(u) = 2 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 __(__(X, Y), Z) -> __(X, __(Y, Z)) 7.65/2.82 U31(tt, V) -> U32(isPalListKind(V), V) 7.65/2.82 U63(tt) -> tt 7.65/2.82 U74(tt) -> tt 7.65/2.82 U83(tt) -> tt 7.65/2.82 U91(tt, V2) -> U92(isPalListKind(V2)) 7.65/2.82 U92(tt) -> tt 7.65/2.82 isList(V) -> U11(isPalListKind(V), V) 7.65/2.82 isNeList(V) -> U31(isPalListKind(V), V) 7.65/2.82 isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (24) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 nil: empty set 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (25) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 nil: empty set 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 a: empty set 7.65/2.82 e: empty set 7.65/2.82 i: empty set 7.65/2.82 o: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U61(x_1, x_2)) = x_1 7.65/2.82 POL(a) = 1 7.65/2.82 POL(e) = 1 7.65/2.82 POL(i) = 1 7.65/2.82 POL(isNePal(x_1)) = 1 + x_1 7.65/2.82 POL(isPalListKind(x_1)) = 1 + x_1 7.65/2.82 POL(nil) = 1 7.65/2.82 POL(o) = 1 7.65/2.82 POL(tt) = 1 7.65/2.82 POL(u) = 0 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 isPalListKind(a) -> tt 7.65/2.82 isPalListKind(e) -> tt 7.65/2.82 isPalListKind(i) -> tt 7.65/2.82 isPalListKind(nil) -> tt 7.65/2.82 isPalListKind(o) -> tt 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (26) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 u: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (27) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 tt: empty set 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 u: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U61(x_1, x_2)) = x_1 7.65/2.82 POL(isNePal(x_1)) = 2 + 2*x_1 7.65/2.82 POL(isPalListKind(x_1)) = 2 + 2*x_1 7.65/2.82 POL(tt) = 0 7.65/2.82 POL(u) = 1 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 isPalListKind(u) -> tt 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (28) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (29) CSRRRRProof (EQUIVALENT) 7.65/2.82 The following CSR is given: Context-sensitive rewrite system: 7.65/2.82 The TRS R consists of the following rules: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 7.65/2.82 The replacement map contains the following entries: 7.65/2.82 7.65/2.82 isPalListKind: empty set 7.65/2.82 U61: {1} 7.65/2.82 isNePal: empty set 7.65/2.82 Used ordering: 7.65/2.82 Polynomial interpretation [POLO]: 7.65/2.82 7.65/2.82 POL(U61(x_1, x_2)) = 1 + 2*x_1 7.65/2.82 POL(isNePal(x_1)) = 2 + 2*x_1 7.65/2.82 POL(isPalListKind(x_1)) = x_1 7.65/2.82 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.65/2.82 7.65/2.82 isNePal(V) -> U61(isPalListKind(V), V) 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (30) 7.65/2.82 Obligation: 7.65/2.82 Context-sensitive rewrite system: 7.65/2.82 R is empty. 7.65/2.82 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (31) RisEmptyProof (EQUIVALENT) 7.65/2.82 The CSR R is empty. Hence, termination is trivially proven. 7.65/2.82 ---------------------------------------- 7.65/2.82 7.65/2.82 (32) 7.65/2.82 YES 7.67/2.87 EOF