/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination of the given CSR could be proven: (0) CSR (1) CSRRRRProof [EQUIVALENT, 175 ms] (2) CSR (3) CSRRRRProof [EQUIVALENT, 29 ms] (4) CSR (5) CSRRRRProof [EQUIVALENT, 8 ms] (6) CSR (7) CSRRRRProof [EQUIVALENT, 0 ms] (8) CSR (9) CSRRRRProof [EQUIVALENT, 9 ms] (10) CSR (11) CSRRRRProof [EQUIVALENT, 10 ms] (12) CSR (13) CSRRRRProof [EQUIVALENT, 12 ms] (14) CSR (15) CSRRRRProof [EQUIVALENT, 26 ms] (16) CSR (17) CSRRRRProof [EQUIVALENT, 0 ms] (18) CSR (19) CSRRRRProof [EQUIVALENT, 0 ms] (20) CSR (21) CSRRRRProof [EQUIVALENT, 3 ms] (22) CSR (23) CSRRRRProof [EQUIVALENT, 0 ms] (24) CSR (25) RisEmptyProof [EQUIVALENT, 0 ms] (26) YES ---------------------------------------- (0) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (1) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 2*x_1 POL(U12(x_1, x_2)) = x_1 POL(U13(x_1)) = x_1 POL(U21(x_1, x_2, x_3)) = 2*x_1 POL(U22(x_1, x_2, x_3)) = x_1 POL(U23(x_1, x_2, x_3)) = 2*x_1 POL(U24(x_1, x_2, x_3)) = 2*x_1 POL(U25(x_1, x_2)) = 2*x_1 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1, x_2)) = x_1 POL(U33(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = 2*x_1 POL(U42(x_1, x_2, x_3)) = 2*x_1 POL(U43(x_1, x_2, x_3)) = 2*x_1 POL(U44(x_1, x_2, x_3)) = 2*x_1 POL(U45(x_1, x_2)) = x_1 POL(U46(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = 2*x_1 POL(U52(x_1, x_2, x_3)) = 2*x_1 POL(U53(x_1, x_2, x_3)) = 2*x_1 POL(U54(x_1, x_2, x_3)) = 2*x_1 POL(U55(x_1, x_2)) = x_1 POL(U56(x_1)) = x_1 POL(U61(x_1, x_2)) = 2*x_1 POL(U62(x_1, x_2)) = x_1 POL(U63(x_1)) = x_1 POL(U71(x_1, x_2, x_3)) = 2*x_1 POL(U72(x_1, x_2)) = 2*x_1 POL(U73(x_1, x_2)) = 2*x_1 POL(U74(x_1)) = 2*x_1 POL(U81(x_1, x_2)) = x_1 POL(U82(x_1, x_2)) = 2*x_1 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = 2*x_1 POL(U92(x_1)) = 2*x_1 POL(__(x_1, x_2)) = x_1 + x_2 POL(a) = 0 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = 0 POL(isNeList(x_1)) = 0 POL(isNePal(x_1)) = 0 POL(isPal(x_1)) = 0 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = 0 POL(nil) = 2 POL(o) = 0 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: __(X, nil) -> X __(nil, X) -> X ---------------------------------------- (2) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (3) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U22(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U23(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U24(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U25(x_1, x_2)) = x_1 + x_2 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U33(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U52(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U53(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U55(x_1, x_2)) = x_1 + x_2 POL(U56(x_1)) = x_1 POL(U61(x_1, x_2)) = x_1 POL(U62(x_1, x_2)) = x_1 POL(U63(x_1)) = x_1 POL(U71(x_1, x_2, x_3)) = x_1 POL(U72(x_1, x_2)) = x_1 POL(U73(x_1, x_2)) = x_1 POL(U74(x_1)) = x_1 POL(U81(x_1, x_2)) = x_1 POL(U82(x_1, x_2)) = x_1 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(e) = 1 POL(i) = 1 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = 0 POL(isPal(x_1)) = 0 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = 0 POL(nil) = 0 POL(o) = 1 POL(tt) = 0 POL(u) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U22(tt, V1, V2) -> U23(isPalListKind(V2), V1, V2) U51(tt, V1, V2) -> U52(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U41(isPalListKind(V1), V1, V2) ---------------------------------------- (4) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (5) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(I), P) U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(V) -> U31(isPalListKind(V), V) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(V) -> U61(isPalListKind(V), V) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(a) -> tt isQid(e) -> tt isQid(i) -> tt isQid(o) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U23: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U51: {1} U52: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U71: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U21(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U22(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U23(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U24(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U25(x_1, x_2)) = x_1 + x_2 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U33(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U52(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U53(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U55(x_1, x_2)) = x_1 + x_2 POL(U56(x_1)) = x_1 POL(U61(x_1, x_2)) = x_1 + x_2 POL(U62(x_1, x_2)) = x_1 + x_2 POL(U63(x_1)) = x_1 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U72(x_1, x_2)) = x_1 + x_2 POL(U73(x_1, x_2)) = x_1 POL(U74(x_1)) = x_1 POL(U81(x_1, x_2)) = x_1 + x_2 POL(U82(x_1, x_2)) = x_1 + x_2 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = x_1 POL(isPal(x_1)) = x_1 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = x_1 POL(nil) = 0 POL(o) = 1 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U23(tt, V1, V2) -> U24(isPalListKind(V2), V1, V2) U52(tt, V1, V2) -> U53(isPalListKind(V2), V1, V2) U71(tt, I, P) -> U72(isPalListKind(I), P) isList(__(V1, V2)) -> U21(isPalListKind(V1), V1, V2) isNeList(__(V1, V2)) -> U51(isPalListKind(V1), V1, V2) isNePal(__(I, __(P, I))) -> U71(isQid(I), I, P) isQid(a) -> tt isQid(o) -> tt ---------------------------------------- (6) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (7) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(V), V) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isList(nil) -> tt isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPal(nil) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U21: {1} U22: {1} U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U41: {1} U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U53: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U22(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U24(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U25(x_1, x_2)) = x_1 + x_2 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U33(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U53(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U54(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U55(x_1, x_2)) = x_1 + x_2 POL(U56(x_1)) = x_1 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 POL(U62(x_1, x_2)) = x_1 + x_2 POL(U63(x_1)) = x_1 POL(U72(x_1, x_2)) = 1 + x_1 + x_2 POL(U73(x_1, x_2)) = x_1 POL(U74(x_1)) = x_1 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 POL(U82(x_1, x_2)) = 1 + x_1 + x_2 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(e) = 1 POL(i) = 1 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPal(x_1)) = 1 + x_1 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = 0 POL(nil) = 1 POL(o) = 1 POL(tt) = 0 POL(u) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U21(tt, V1, V2) -> U22(isPalListKind(V1), V1, V2) U41(tt, V1, V2) -> U42(isPalListKind(V1), V1, V2) U53(tt, V1, V2) -> U54(isPalListKind(V2), V1, V2) U61(tt, V) -> U62(isPalListKind(V), V) isList(nil) -> tt isPal(nil) -> tt ---------------------------------------- (8) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (9) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U54(tt, V1, V2) -> U55(isNeList(V1), V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set U24: {1} U25: {1} isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U42: {1} U43: {1} U44: {1} U45: {1} U46: {1} U54: {1} U55: {1} U56: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 2*x_1 POL(U12(x_1, x_2)) = x_1 POL(U13(x_1)) = x_1 POL(U24(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 POL(U25(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1, x_2)) = 2*x_1 POL(U33(x_1)) = x_1 POL(U42(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(U43(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 POL(U44(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 POL(U45(x_1, x_2)) = x_1 POL(U46(x_1)) = x_1 POL(U54(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(U55(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U56(x_1)) = 1 + x_1 POL(U61(x_1, x_2)) = 2*x_1 POL(U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U63(x_1)) = 2*x_1 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U73(x_1, x_2)) = x_1 + 2*x_2 POL(U74(x_1)) = 2*x_1 POL(U81(x_1, x_2)) = 2*x_1 POL(U82(x_1, x_2)) = x_1 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = 2*x_1 POL(U92(x_1)) = 2*x_1 POL(__(x_1, x_2)) = 2*x_1 + x_2 POL(a) = 2 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = 0 POL(isNePal(x_1)) = 0 POL(isPal(x_1)) = 0 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = 0 POL(nil) = 2 POL(o) = 2 POL(tt) = 0 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U24(tt, V1, V2) -> U25(isList(V1), V2) U25(tt, V2) -> U26(isList(V2)) U42(tt, V1, V2) -> U43(isPalListKind(V2), V1, V2) U43(tt, V1, V2) -> U44(isPalListKind(V2), V1, V2) U55(tt, V2) -> U56(isList(V2)) U56(tt) -> tt ---------------------------------------- (10) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U54(tt, V1, V2) -> U55(isNeList(V1), V2) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U54: {1} U55: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (11) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U54(tt, V1, V2) -> U55(isNeList(V1), V2) U62(tt, V) -> U63(isQid(V)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U73(tt, P) -> U74(isPalListKind(P)) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U54: {1} U55: {1} U61: {1} U62: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U33(x_1)) = x_1 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U54(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U55(x_1, x_2)) = x_1 + x_2 POL(U61(x_1, x_2)) = x_1 + x_2 POL(U62(x_1, x_2)) = 1 + x_1 + x_2 POL(U63(x_1)) = x_1 POL(U72(x_1, x_2)) = 1 + x_1 + x_2 POL(U73(x_1, x_2)) = 1 + x_1 POL(U74(x_1)) = x_1 POL(U81(x_1, x_2)) = x_1 + x_2 POL(U82(x_1, x_2)) = x_1 + x_2 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(e) = 0 POL(i) = 0 POL(isList(x_1)) = 1 + x_1 POL(isNeList(x_1)) = 1 + x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPal(x_1)) = 1 + x_1 POL(isPalListKind(x_1)) = 1 POL(isQid(x_1)) = 1 + x_1 POL(nil) = 1 POL(o) = 1 POL(tt) = 1 POL(u) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U54(tt, V1, V2) -> U55(isNeList(V1), V2) U62(tt, V) -> U63(isQid(V)) U73(tt, P) -> U74(isPalListKind(P)) ---------------------------------------- (12) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U61: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (13) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt, V) -> U12(isPalListKind(V), V) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(V), V) U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U61: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 1 + x_1 + x_2 POL(U12(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U26(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U33(x_1)) = x_1 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U61(x_1, x_2)) = x_1 POL(U63(x_1)) = x_1 POL(U72(x_1, x_2)) = 1 + x_1 + x_2 POL(U73(x_1, x_2)) = x_1 + x_2 POL(U74(x_1)) = x_1 POL(U81(x_1, x_2)) = 1 + x_1 POL(U82(x_1, x_2)) = x_1 POL(U83(x_1)) = x_1 POL(U91(x_1, x_2)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(e) = 1 POL(i) = 1 POL(isList(x_1)) = 1 + x_1 POL(isNeList(x_1)) = x_1 POL(isNePal(x_1)) = 0 POL(isPal(x_1)) = 1 POL(isPalListKind(x_1)) = 0 POL(isQid(x_1)) = x_1 POL(nil) = 1 POL(o) = 1 POL(tt) = 0 POL(u) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U11(tt, V) -> U12(isPalListKind(V), V) U81(tt, V) -> U82(isPalListKind(V), V) isQid(e) -> tt isQid(i) -> tt isQid(u) -> tt ---------------------------------------- (14) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U74(tt) -> tt U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U61: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set ---------------------------------------- (15) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U12(tt, V) -> U13(isNeList(V)) U13(tt) -> tt U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U44(tt, V1, V2) -> U45(isList(V1), V2) U45(tt, V2) -> U46(isNeList(V2)) U46(tt) -> tt U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U74(tt) -> tt U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) U92(tt) -> tt isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) The replacement map contains the following entries: __: {1, 2} nil: empty set U11: {1} tt: empty set U12: {1} isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U26: {1} U31: {1} U32: {1} U33: {1} isQid: empty set U44: {1} U45: {1} U46: {1} U61: {1} U63: {1} U72: {1} U73: {1} isPal: empty set U74: {1} U81: {1} U82: {1} U83: {1} isNePal: empty set U91: {1} U92: {1} a: empty set e: empty set i: empty set o: empty set u: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 POL(U12(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U13(x_1)) = x_1 POL(U26(x_1)) = 1 + x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U32(x_1, x_2)) = x_1 POL(U33(x_1)) = 2*x_1 POL(U44(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(U45(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U46(x_1)) = x_1 POL(U61(x_1, x_2)) = x_1 POL(U63(x_1)) = 1 + x_1 POL(U72(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U73(x_1, x_2)) = x_1 POL(U74(x_1)) = 1 + 2*x_1 POL(U81(x_1, x_2)) = x_1 + x_2 POL(U82(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U83(x_1)) = 1 + 2*x_1 POL(U91(x_1, x_2)) = 1 + x_1 + x_2 POL(U92(x_1)) = 1 + x_1 POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(a) = 2 POL(e) = 2 POL(i) = 2 POL(isList(x_1)) = 2 + x_1 POL(isNeList(x_1)) = 2 + 2*x_1 POL(isNePal(x_1)) = 2 + x_1 POL(isPal(x_1)) = 2 + 2*x_1 POL(isPalListKind(x_1)) = 2 + x_1 POL(isQid(x_1)) = 0 POL(nil) = 2 POL(o) = 2 POL(tt) = 2 POL(u) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: __(__(X, Y), Z) -> __(X, __(Y, Z)) U12(tt, V) -> U13(isNeList(V)) U26(tt) -> tt U32(tt, V) -> U33(isQid(V)) U33(tt) -> tt U45(tt, V2) -> U46(isNeList(V2)) U63(tt) -> tt U72(tt, P) -> U73(isPal(P), P) U74(tt) -> tt U82(tt, V) -> U83(isNePal(V)) U83(tt) -> tt U92(tt) -> tt isPalListKind(a) -> tt isPalListKind(e) -> tt isPalListKind(i) -> tt isPalListKind(nil) -> tt isPalListKind(o) -> tt isPalListKind(u) -> tt isPalListKind(__(V1, V2)) -> U91(isPalListKind(V1), V2) ---------------------------------------- (16) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U44(tt, V1, V2) -> U45(isList(V1), V2) U46(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} tt: empty set isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U31: {1} U32: {1} U44: {1} U45: {1} U46: {1} U61: {1} isPal: empty set U81: {1} isNePal: empty set U91: {1} U92: {1} ---------------------------------------- (17) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt) -> tt U31(tt, V) -> U32(isPalListKind(V), V) U44(tt, V1, V2) -> U45(isList(V1), V2) U46(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} tt: empty set isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U31: {1} U32: {1} U44: {1} U45: {1} U46: {1} U61: {1} isPal: empty set U81: {1} isNePal: empty set U91: {1} U92: {1} Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(U13(x_1)) = x_1 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 POL(U32(x_1, x_2)) = x_1 + x_2 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U45(x_1, x_2)) = x_1 + x_2 POL(U46(x_1)) = x_1 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 POL(U91(x_1, x_2)) = 1 + x_1 POL(U92(x_1)) = 1 + x_1 POL(isList(x_1)) = x_1 POL(isNeList(x_1)) = 1 + x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPal(x_1)) = 1 + x_1 POL(isPalListKind(x_1)) = 0 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U31(tt, V) -> U32(isPalListKind(V), V) U44(tt, V1, V2) -> U45(isList(V1), V2) ---------------------------------------- (18) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt) -> tt U46(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} tt: empty set isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U31: {1} U46: {1} U61: {1} isPal: empty set U81: {1} isNePal: empty set U91: {1} U92: {1} ---------------------------------------- (19) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt) -> tt U46(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) isList(V) -> U11(isPalListKind(V), V) isNeList(V) -> U31(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} tt: empty set isPalListKind: empty set U13: {1} isNeList: empty set isList: empty set U31: {1} U46: {1} U61: {1} isPal: empty set U81: {1} isNePal: empty set U91: {1} U92: {1} Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 2 + x_1 + x_2 POL(U13(x_1)) = 2*x_1 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 POL(U46(x_1)) = 2*x_1 POL(U61(x_1, x_2)) = 2 + x_1 + x_2 POL(U81(x_1, x_2)) = 1 + x_1 + x_2 POL(U91(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(U92(x_1)) = 2*x_1 POL(isList(x_1)) = 2 + 2*x_1 POL(isNeList(x_1)) = 2 + 2*x_1 POL(isNePal(x_1)) = 2 + 2*x_1 POL(isPal(x_1)) = 2 + 2*x_1 POL(isPalListKind(x_1)) = x_1 POL(tt) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U13(tt) -> tt U46(tt) -> tt U91(tt, V2) -> U92(isPalListKind(V2)) isNeList(V) -> U31(isPalListKind(V), V) isPal(V) -> U81(isPalListKind(V), V) ---------------------------------------- (20) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: isList(V) -> U11(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} isPalListKind: empty set isList: empty set U61: {1} isNePal: empty set ---------------------------------------- (21) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: isList(V) -> U11(isPalListKind(V), V) isNePal(V) -> U61(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} isPalListKind: empty set isList: empty set U61: {1} isNePal: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 1 + x_1 + x_2 POL(U61(x_1, x_2)) = x_1 + x_2 POL(isList(x_1)) = 1 + x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPalListKind(x_1)) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNePal(V) -> U61(isPalListKind(V), V) ---------------------------------------- (22) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: isList(V) -> U11(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} isPalListKind: empty set isList: empty set ---------------------------------------- (23) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: isList(V) -> U11(isPalListKind(V), V) The replacement map contains the following entries: U11: {1} isPalListKind: empty set isList: empty set Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = x_1 + x_2 POL(isList(x_1)) = 1 + x_1 POL(isPalListKind(x_1)) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isList(V) -> U11(isPalListKind(V), V) ---------------------------------------- (24) Obligation: Context-sensitive rewrite system: R is empty. ---------------------------------------- (25) RisEmptyProof (EQUIVALENT) The CSR R is empty. Hence, termination is trivially proven. ---------------------------------------- (26) YES