/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 126 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 40 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 42 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 26 ms] (8) QTRS (9) QTRSRRRProof [EQUIVALENT, 30 ms] (10) QTRS (11) QTRSRRRProof [EQUIVALENT, 36 ms] (12) QTRS (13) DependencyPairsProof [EQUIVALENT, 25 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) AND (17) QDP (18) UsableRulesProof [EQUIVALENT, 0 ms] (19) QDP (20) TransformationProof [EQUIVALENT, 0 ms] (21) QDP (22) NonTerminationLoopProof [COMPLETE, 0 ms] (23) NO (24) QDP (25) UsableRulesProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) NonTerminationLoopProof [COMPLETE, 11 ms] (38) NO (39) QDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) QDP (42) TransformationProof [EQUIVALENT, 0 ms] (43) QDP (44) TransformationProof [EQUIVALENT, 0 ms] (45) QDP (46) TransformationProof [EQUIVALENT, 0 ms] (47) QDP (48) TransformationProof [EQUIVALENT, 0 ms] (49) QDP (50) TransformationProof [EQUIVALENT, 0 ms] (51) QDP (52) TransformationProof [EQUIVALENT, 0 ms] (53) QDP (54) TransformationProof [EQUIVALENT, 0 ms] (55) QDP (56) TransformationProof [EQUIVALENT, 0 ms] (57) QDP (58) TransformationProof [EQUIVALENT, 0 ms] (59) QDP (60) TransformationProof [EQUIVALENT, 0 ms] (61) QDP (62) TransformationProof [EQUIVALENT, 0 ms] (63) QDP (64) TransformationProof [EQUIVALENT, 0 ms] (65) QDP (66) TransformationProof [EQUIVALENT, 0 ms] (67) QDP (68) TransformationProof [EQUIVALENT, 0 ms] (69) QDP (70) TransformationProof [EQUIVALENT, 0 ms] (71) QDP (72) TransformationProof [EQUIVALENT, 0 ms] (73) QDP (74) TransformationProof [EQUIVALENT, 0 ms] (75) QDP (76) NonTerminationLoopProof [COMPLETE, 1282 ms] (77) NO ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U61(tt) -> U62(isPalListKind) U62(tt) -> U63(isQid) U63(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPal -> tt isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U13(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U22(x_1)) = x_1 POL(U23(x_1)) = x_1 POL(U24(x_1)) = x_1 POL(U25(x_1)) = x_1 POL(U26(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U32(x_1)) = 2*x_1 POL(U33(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(U42(x_1)) = x_1 POL(U43(x_1)) = x_1 POL(U44(x_1)) = x_1 POL(U45(x_1)) = x_1 POL(U46(x_1)) = x_1 POL(U51(x_1)) = x_1 POL(U52(x_1)) = x_1 POL(U53(x_1)) = x_1 POL(U54(x_1)) = x_1 POL(U55(x_1)) = x_1 POL(U56(x_1)) = x_1 POL(U61(x_1)) = x_1 POL(U62(x_1)) = x_1 POL(U63(x_1)) = x_1 POL(U71(x_1)) = x_1 POL(U72(x_1)) = x_1 POL(U73(x_1)) = x_1 POL(U74(x_1)) = x_1 POL(U81(x_1)) = x_1 POL(U82(x_1)) = x_1 POL(U83(x_1)) = x_1 POL(U91(x_1)) = x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 2 + x_1 + x_2 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 0 POL(isPal) = 0 POL(isPalListKind) = 0 POL(isQid) = 0 POL(nil) = 2 POL(tt) = 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: Q restricted rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U61(tt) -> U62(isPalListKind) U62(tt) -> U63(isQid) U63(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPal -> tt isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U13(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U22(x_1)) = 2*x_1 POL(U23(x_1)) = 2*x_1 POL(U24(x_1)) = x_1 POL(U25(x_1)) = x_1 POL(U26(x_1)) = 2*x_1 POL(U31(x_1)) = x_1 POL(U32(x_1)) = 2*x_1 POL(U33(x_1)) = 2*x_1 POL(U41(x_1)) = x_1 POL(U42(x_1)) = x_1 POL(U43(x_1)) = x_1 POL(U44(x_1)) = 2*x_1 POL(U45(x_1)) = 2*x_1 POL(U46(x_1)) = x_1 POL(U51(x_1)) = x_1 POL(U52(x_1)) = 2*x_1 POL(U53(x_1)) = x_1 POL(U54(x_1)) = 2*x_1 POL(U55(x_1)) = 2*x_1 POL(U56(x_1)) = 2*x_1 POL(U61(x_1)) = 2*x_1 POL(U62(x_1)) = x_1 POL(U63(x_1)) = x_1 POL(U71(x_1)) = 2*x_1 POL(U72(x_1)) = x_1 POL(U73(x_1)) = 2*x_1 POL(U74(x_1)) = x_1 POL(U81(x_1)) = x_1 POL(U82(x_1)) = x_1 POL(U83(x_1)) = 2*x_1 POL(U91(x_1)) = 2*x_1 POL(U92(x_1)) = x_1 POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 0 POL(isPal) = 0 POL(isPalListKind) = 0 POL(isQid) = 0 POL(tt) = 0 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)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U61(tt) -> U62(isPalListKind) U62(tt) -> U63(isQid) U63(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPal -> tt isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U13(x_1)) = 2*x_1 POL(U21(x_1)) = 2*x_1 POL(U22(x_1)) = x_1 POL(U23(x_1)) = x_1 POL(U24(x_1)) = 2*x_1 POL(U25(x_1)) = 2*x_1 POL(U26(x_1)) = 2*x_1 POL(U31(x_1)) = 2*x_1 POL(U32(x_1)) = 2*x_1 POL(U33(x_1)) = x_1 POL(U41(x_1)) = 2*x_1 POL(U42(x_1)) = x_1 POL(U43(x_1)) = 2*x_1 POL(U44(x_1)) = 2*x_1 POL(U45(x_1)) = x_1 POL(U46(x_1)) = x_1 POL(U51(x_1)) = x_1 POL(U52(x_1)) = 2*x_1 POL(U53(x_1)) = x_1 POL(U54(x_1)) = x_1 POL(U55(x_1)) = 2*x_1 POL(U56(x_1)) = 2*x_1 POL(U61(x_1)) = 1 + x_1 POL(U62(x_1)) = 1 + 2*x_1 POL(U63(x_1)) = 2*x_1 POL(U71(x_1)) = 1 + 2*x_1 POL(U72(x_1)) = 1 + x_1 POL(U73(x_1)) = x_1 POL(U74(x_1)) = 2*x_1 POL(U81(x_1)) = 1 + 2*x_1 POL(U82(x_1)) = 1 + x_1 POL(U83(x_1)) = x_1 POL(U91(x_1)) = 2*x_1 POL(U92(x_1)) = x_1 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 1 POL(isPal) = 1 POL(isPalListKind) = 0 POL(isQid) = 0 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U62(tt) -> U63(isQid) isPal -> tt ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U61(tt) -> U62(isPalListKind) U63(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U13(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U22(x_1)) = 2*x_1 POL(U23(x_1)) = x_1 POL(U24(x_1)) = x_1 POL(U25(x_1)) = x_1 POL(U26(x_1)) = 2*x_1 POL(U31(x_1)) = x_1 POL(U32(x_1)) = x_1 POL(U33(x_1)) = 2*x_1 POL(U41(x_1)) = x_1 POL(U42(x_1)) = x_1 POL(U43(x_1)) = 2*x_1 POL(U44(x_1)) = x_1 POL(U45(x_1)) = x_1 POL(U46(x_1)) = x_1 POL(U51(x_1)) = 2*x_1 POL(U52(x_1)) = x_1 POL(U53(x_1)) = x_1 POL(U54(x_1)) = x_1 POL(U55(x_1)) = 2*x_1 POL(U56(x_1)) = x_1 POL(U61(x_1)) = 2*x_1 POL(U62(x_1)) = x_1 POL(U63(x_1)) = 1 + 2*x_1 POL(U71(x_1)) = 2*x_1 POL(U72(x_1)) = x_1 POL(U73(x_1)) = 2*x_1 POL(U74(x_1)) = x_1 POL(U81(x_1)) = x_1 POL(U82(x_1)) = x_1 POL(U83(x_1)) = 2*x_1 POL(U91(x_1)) = 2*x_1 POL(U92(x_1)) = 2*x_1 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 0 POL(isPal) = 0 POL(isPalListKind) = 0 POL(isQid) = 0 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U63(tt) -> tt ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U61(tt) -> U62(isPalListKind) U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (9) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U13(x_1)) = 2*x_1 POL(U21(x_1)) = 2*x_1 POL(U22(x_1)) = 2*x_1 POL(U23(x_1)) = 2*x_1 POL(U24(x_1)) = 2*x_1 POL(U25(x_1)) = 2*x_1 POL(U26(x_1)) = 2*x_1 POL(U31(x_1)) = x_1 POL(U32(x_1)) = 2*x_1 POL(U33(x_1)) = x_1 POL(U41(x_1)) = 2*x_1 POL(U42(x_1)) = 2*x_1 POL(U43(x_1)) = x_1 POL(U44(x_1)) = 2*x_1 POL(U45(x_1)) = x_1 POL(U46(x_1)) = 2*x_1 POL(U51(x_1)) = x_1 POL(U52(x_1)) = 2*x_1 POL(U53(x_1)) = 2*x_1 POL(U54(x_1)) = 2*x_1 POL(U55(x_1)) = 2*x_1 POL(U56(x_1)) = 2*x_1 POL(U61(x_1)) = 1 + 2*x_1 POL(U62(x_1)) = 2*x_1 POL(U71(x_1)) = 1 + 2*x_1 POL(U72(x_1)) = 1 + 2*x_1 POL(U73(x_1)) = x_1 POL(U74(x_1)) = 2*x_1 POL(U81(x_1)) = 1 + x_1 POL(U82(x_1)) = 1 + 2*x_1 POL(U83(x_1)) = x_1 POL(U91(x_1)) = 2*x_1 POL(U92(x_1)) = x_1 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 1 POL(isPal) = 1 POL(isPalListKind) = 0 POL(isQid) = 0 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U61(tt) -> U62(isPalListKind) ---------------------------------------- (10) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U61(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (11) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1)) = 2*x_1 POL(U12(x_1)) = 2*x_1 POL(U13(x_1)) = 2*x_1 POL(U21(x_1)) = 2*x_1 POL(U22(x_1)) = 2*x_1 POL(U23(x_1)) = 2*x_1 POL(U24(x_1)) = x_1 POL(U25(x_1)) = 2*x_1 POL(U26(x_1)) = 2*x_1 POL(U31(x_1)) = 2*x_1 POL(U32(x_1)) = 2*x_1 POL(U33(x_1)) = 2*x_1 POL(U41(x_1)) = x_1 POL(U42(x_1)) = 2*x_1 POL(U43(x_1)) = x_1 POL(U44(x_1)) = x_1 POL(U45(x_1)) = 2*x_1 POL(U46(x_1)) = 2*x_1 POL(U51(x_1)) = x_1 POL(U52(x_1)) = x_1 POL(U53(x_1)) = 2*x_1 POL(U54(x_1)) = 2*x_1 POL(U55(x_1)) = 2*x_1 POL(U56(x_1)) = x_1 POL(U61(x_1)) = x_1 POL(U71(x_1)) = 1 + 2*x_1 POL(U72(x_1)) = 1 + x_1 POL(U73(x_1)) = x_1 POL(U74(x_1)) = 2*x_1 POL(U81(x_1)) = 1 + 2*x_1 POL(U82(x_1)) = 1 + x_1 POL(U83(x_1)) = x_1 POL(U91(x_1)) = 2*x_1 POL(U92(x_1)) = 2*x_1 POL(isList) = 0 POL(isNeList) = 0 POL(isNePal) = 1 POL(isPal) = 1 POL(isPalListKind) = 0 POL(isQid) = 0 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNePal -> U61(isPalListKind) ---------------------------------------- (12) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. ---------------------------------------- (13) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt) -> U12^1(isPalListKind) U11^1(tt) -> ISPALLISTKIND U12^1(tt) -> U13^1(isNeList) U12^1(tt) -> ISNELIST U21^1(tt) -> U22^1(isPalListKind) U21^1(tt) -> ISPALLISTKIND U22^1(tt) -> U23^1(isPalListKind) U22^1(tt) -> ISPALLISTKIND U23^1(tt) -> U24^1(isPalListKind) U23^1(tt) -> ISPALLISTKIND U24^1(tt) -> U25^1(isList) U24^1(tt) -> ISLIST U25^1(tt) -> U26^1(isList) U25^1(tt) -> ISLIST U31^1(tt) -> U32^1(isPalListKind) U31^1(tt) -> ISPALLISTKIND U32^1(tt) -> U33^1(isQid) U32^1(tt) -> ISQID U41^1(tt) -> U42^1(isPalListKind) U41^1(tt) -> ISPALLISTKIND U42^1(tt) -> U43^1(isPalListKind) U42^1(tt) -> ISPALLISTKIND U43^1(tt) -> U44^1(isPalListKind) U43^1(tt) -> ISPALLISTKIND U44^1(tt) -> U45^1(isList) U44^1(tt) -> ISLIST U45^1(tt) -> U46^1(isNeList) U45^1(tt) -> ISNELIST U51^1(tt) -> U52^1(isPalListKind) U51^1(tt) -> ISPALLISTKIND U52^1(tt) -> U53^1(isPalListKind) U52^1(tt) -> ISPALLISTKIND U53^1(tt) -> U54^1(isPalListKind) U53^1(tt) -> ISPALLISTKIND U54^1(tt) -> U55^1(isNeList) U54^1(tt) -> ISNELIST U55^1(tt) -> U56^1(isList) U55^1(tt) -> ISLIST U71^1(tt) -> U72^1(isPalListKind) U71^1(tt) -> ISPALLISTKIND U72^1(tt) -> U73^1(isPal) U72^1(tt) -> ISPAL U73^1(tt) -> U74^1(isPalListKind) U73^1(tt) -> ISPALLISTKIND U81^1(tt) -> U82^1(isPalListKind) U81^1(tt) -> ISPALLISTKIND U82^1(tt) -> U83^1(isNePal) U82^1(tt) -> ISNEPAL U91^1(tt) -> U92^1(isPalListKind) U91^1(tt) -> ISPALLISTKIND ISLIST -> U11^1(isPalListKind) ISLIST -> ISPALLISTKIND ISLIST -> U21^1(isPalListKind) ISNELIST -> U31^1(isPalListKind) ISNELIST -> ISPALLISTKIND ISNELIST -> U41^1(isPalListKind) ISNELIST -> U51^1(isPalListKind) ISNEPAL -> U71^1(isQid) ISNEPAL -> ISQID ISPAL -> U81^1(isPalListKind) ISPAL -> ISPALLISTKIND ISPALLISTKIND -> U91^1(isPalListKind) ISPALLISTKIND -> ISPALLISTKIND The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 30 less nodes. ---------------------------------------- (16) Complex Obligation (AND) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: U91^1(tt) -> ISPALLISTKIND ISPALLISTKIND -> U91^1(isPalListKind) ISPALLISTKIND -> ISPALLISTKIND The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: U91^1(tt) -> ISPALLISTKIND ISPALLISTKIND -> U91^1(isPalListKind) ISPALLISTKIND -> ISPALLISTKIND The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISPALLISTKIND -> U91^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISPALLISTKIND -> U91^1(tt),ISPALLISTKIND -> U91^1(tt)) (ISPALLISTKIND -> U91^1(U91(isPalListKind)),ISPALLISTKIND -> U91^1(U91(isPalListKind))) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: U91^1(tt) -> ISPALLISTKIND ISPALLISTKIND -> ISPALLISTKIND ISPALLISTKIND -> U91^1(tt) ISPALLISTKIND -> U91^1(U91(isPalListKind)) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = ISPALLISTKIND evaluates to t =ISPALLISTKIND Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from ISPALLISTKIND to ISPALLISTKIND. ---------------------------------------- (23) NO ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL ISPAL -> U81^1(isPalListKind) U81^1(tt) -> U82^1(isPalListKind) U82^1(tt) -> ISNEPAL ISNEPAL -> U71^1(isQid) U71^1(tt) -> U72^1(isPalListKind) The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL ISPAL -> U81^1(isPalListKind) U81^1(tt) -> U82^1(isPalListKind) U82^1(tt) -> ISNEPAL ISNEPAL -> U71^1(isQid) U71^1(tt) -> U72^1(isPalListKind) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISNEPAL -> U71^1(isQid) at position [0] we obtained the following new rules [LPAR04]: (ISNEPAL -> U71^1(tt),ISNEPAL -> U71^1(tt)) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL ISPAL -> U81^1(isPalListKind) U81^1(tt) -> U82^1(isPalListKind) U82^1(tt) -> ISNEPAL U71^1(tt) -> U72^1(isPalListKind) ISNEPAL -> U71^1(tt) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL ISPAL -> U81^1(isPalListKind) U81^1(tt) -> U82^1(isPalListKind) U82^1(tt) -> ISNEPAL U71^1(tt) -> U72^1(isPalListKind) ISNEPAL -> U71^1(tt) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISPAL -> U81^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISPAL -> U81^1(tt),ISPAL -> U81^1(tt)) (ISPAL -> U81^1(U91(isPalListKind)),ISPAL -> U81^1(U91(isPalListKind))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL U81^1(tt) -> U82^1(isPalListKind) U82^1(tt) -> ISNEPAL U71^1(tt) -> U72^1(isPalListKind) ISNEPAL -> U71^1(tt) ISPAL -> U81^1(tt) ISPAL -> U81^1(U91(isPalListKind)) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U81^1(tt) -> U82^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U81^1(tt) -> U82^1(tt),U81^1(tt) -> U82^1(tt)) (U81^1(tt) -> U82^1(U91(isPalListKind)),U81^1(tt) -> U82^1(U91(isPalListKind))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL U82^1(tt) -> ISNEPAL U71^1(tt) -> U72^1(isPalListKind) ISNEPAL -> U71^1(tt) ISPAL -> U81^1(tt) ISPAL -> U81^1(U91(isPalListKind)) U81^1(tt) -> U82^1(tt) U81^1(tt) -> U82^1(U91(isPalListKind)) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U71^1(tt) -> U72^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U71^1(tt) -> U72^1(tt),U71^1(tt) -> U72^1(tt)) (U71^1(tt) -> U72^1(U91(isPalListKind)),U71^1(tt) -> U72^1(U91(isPalListKind))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: U72^1(tt) -> ISPAL U82^1(tt) -> ISNEPAL ISNEPAL -> U71^1(tt) ISPAL -> U81^1(tt) ISPAL -> U81^1(U91(isPalListKind)) U81^1(tt) -> U82^1(tt) U81^1(tt) -> U82^1(U91(isPalListKind)) U71^1(tt) -> U72^1(tt) U71^1(tt) -> U72^1(U91(isPalListKind)) The TRS R consists of the following rules: isPalListKind -> tt isPalListKind -> U91(isPalListKind) U91(tt) -> U92(isPalListKind) U92(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = ISPAL evaluates to t =ISPAL Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence ISPAL -> U81^1(tt) with rule ISPAL -> U81^1(tt) at position [] and matcher [ ] U81^1(tt) -> U82^1(tt) with rule U81^1(tt) -> U82^1(tt) at position [] and matcher [ ] U82^1(tt) -> ISNEPAL with rule U82^1(tt) -> ISNEPAL at position [] and matcher [ ] ISNEPAL -> U71^1(tt) with rule ISNEPAL -> U71^1(tt) at position [] and matcher [ ] U71^1(tt) -> U72^1(tt) with rule U71^1(tt) -> U72^1(tt) at position [] and matcher [ ] U72^1(tt) -> ISPAL with rule U72^1(tt) -> ISPAL Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (38) NO ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST ISNELIST -> U41^1(isPalListKind) U41^1(tt) -> U42^1(isPalListKind) U42^1(tt) -> U43^1(isPalListKind) U43^1(tt) -> U44^1(isPalListKind) U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST The TRS R consists of the following rules: U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) U13(tt) -> tt U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) U33(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U71(tt) -> U72(isPalListKind) U72(tt) -> U73(isPal) U73(tt) -> U74(isPalListKind) U74(tt) -> tt U81(tt) -> U82(isPalListKind) U82(tt) -> U83(isNePal) U83(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) isNePal -> U71(isQid) isPal -> U81(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) isQid -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST ISNELIST -> U41^1(isPalListKind) U41^1(tt) -> U42^1(isPalListKind) U42^1(tt) -> U43^1(isPalListKind) U43^1(tt) -> U44^1(isPalListKind) U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISNELIST -> U41^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISNELIST -> U41^1(tt),ISNELIST -> U41^1(tt)) (ISNELIST -> U41^1(U91(isPalListKind)),ISNELIST -> U41^1(U91(isPalListKind))) ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U41^1(tt) -> U42^1(isPalListKind) U42^1(tt) -> U43^1(isPalListKind) U43^1(tt) -> U44^1(isPalListKind) U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U41^1(tt) -> U42^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U41^1(tt) -> U42^1(tt),U41^1(tt) -> U42^1(tt)) (U41^1(tt) -> U42^1(U91(isPalListKind)),U41^1(tt) -> U42^1(U91(isPalListKind))) ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U42^1(tt) -> U43^1(isPalListKind) U43^1(tt) -> U44^1(isPalListKind) U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U42^1(tt) -> U43^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U42^1(tt) -> U43^1(tt),U42^1(tt) -> U43^1(tt)) (U42^1(tt) -> U43^1(U91(isPalListKind)),U42^1(tt) -> U43^1(U91(isPalListKind))) ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U43^1(tt) -> U44^1(isPalListKind) U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U43^1(tt) -> U44^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U43^1(tt) -> U44^1(tt),U43^1(tt) -> U44^1(tt)) (U43^1(tt) -> U44^1(U91(isPalListKind)),U43^1(tt) -> U44^1(U91(isPalListKind))) ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U44^1(tt) -> U45^1(isList) U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U44^1(tt) -> U45^1(isList) at position [0] we obtained the following new rules [LPAR04]: (U44^1(tt) -> U45^1(U11(isPalListKind)),U44^1(tt) -> U45^1(U11(isPalListKind))) (U44^1(tt) -> U45^1(tt),U44^1(tt) -> U45^1(tt)) (U44^1(tt) -> U45^1(U21(isPalListKind)),U44^1(tt) -> U45^1(U21(isPalListKind))) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST ISNELIST -> U51^1(isPalListKind) U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISNELIST -> U51^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISNELIST -> U51^1(tt),ISNELIST -> U51^1(tt)) (ISNELIST -> U51^1(U91(isPalListKind)),ISNELIST -> U51^1(U91(isPalListKind))) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U51^1(tt) -> U52^1(isPalListKind) U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U51^1(tt) -> U52^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U51^1(tt) -> U52^1(tt),U51^1(tt) -> U52^1(tt)) (U51^1(tt) -> U52^1(U91(isPalListKind)),U51^1(tt) -> U52^1(U91(isPalListKind))) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U52^1(tt) -> U53^1(isPalListKind) U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U52^1(tt) -> U53^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U52^1(tt) -> U53^1(tt),U52^1(tt) -> U53^1(tt)) (U52^1(tt) -> U53^1(U91(isPalListKind)),U52^1(tt) -> U53^1(U91(isPalListKind))) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U53^1(tt) -> U54^1(isPalListKind) U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U53^1(tt) -> U54^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U53^1(tt) -> U54^1(tt),U53^1(tt) -> U54^1(tt)) (U53^1(tt) -> U54^1(U91(isPalListKind)),U53^1(tt) -> U54^1(U91(isPalListKind))) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U54^1(tt) -> U55^1(isNeList) U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U54^1(tt) -> U55^1(isNeList) at position [0] we obtained the following new rules [LPAR04]: (U54^1(tt) -> U55^1(U31(isPalListKind)),U54^1(tt) -> U55^1(U31(isPalListKind))) (U54^1(tt) -> U55^1(U41(isPalListKind)),U54^1(tt) -> U55^1(U41(isPalListKind))) (U54^1(tt) -> U55^1(U51(isPalListKind)),U54^1(tt) -> U55^1(U51(isPalListKind))) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST ISLIST -> U11^1(isPalListKind) U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISLIST -> U11^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISLIST -> U11^1(tt),ISLIST -> U11^1(tt)) (ISLIST -> U11^1(U91(isPalListKind)),ISLIST -> U11^1(U91(isPalListKind))) ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U11^1(tt) -> U12^1(isPalListKind) ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U11^1(tt) -> U12^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U11^1(tt) -> U12^1(tt),U11^1(tt) -> U12^1(tt)) (U11^1(tt) -> U12^1(U91(isPalListKind)),U11^1(tt) -> U12^1(U91(isPalListKind))) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST ISLIST -> U21^1(isPalListKind) U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule ISLIST -> U21^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (ISLIST -> U21^1(tt),ISLIST -> U21^1(tt)) (ISLIST -> U21^1(U91(isPalListKind)),ISLIST -> U21^1(U91(isPalListKind))) ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U21^1(tt) -> U22^1(isPalListKind) U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) ISLIST -> U21^1(tt) ISLIST -> U21^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U21^1(tt) -> U22^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U21^1(tt) -> U22^1(tt),U21^1(tt) -> U22^1(tt)) (U21^1(tt) -> U22^1(U91(isPalListKind)),U21^1(tt) -> U22^1(U91(isPalListKind))) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U22^1(tt) -> U23^1(isPalListKind) U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) ISLIST -> U21^1(tt) ISLIST -> U21^1(U91(isPalListKind)) U21^1(tt) -> U22^1(tt) U21^1(tt) -> U22^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U22^1(tt) -> U23^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U22^1(tt) -> U23^1(tt),U22^1(tt) -> U23^1(tt)) (U22^1(tt) -> U23^1(U91(isPalListKind)),U22^1(tt) -> U23^1(U91(isPalListKind))) ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U23^1(tt) -> U24^1(isPalListKind) U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) ISLIST -> U21^1(tt) ISLIST -> U21^1(U91(isPalListKind)) U21^1(tt) -> U22^1(tt) U21^1(tt) -> U22^1(U91(isPalListKind)) U22^1(tt) -> U23^1(tt) U22^1(tt) -> U23^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U23^1(tt) -> U24^1(isPalListKind) at position [0] we obtained the following new rules [LPAR04]: (U23^1(tt) -> U24^1(tt),U23^1(tt) -> U24^1(tt)) (U23^1(tt) -> U24^1(U91(isPalListKind)),U23^1(tt) -> U24^1(U91(isPalListKind))) ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U24^1(tt) -> U25^1(isList) U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) ISLIST -> U21^1(tt) ISLIST -> U21^1(U91(isPalListKind)) U21^1(tt) -> U22^1(tt) U21^1(tt) -> U22^1(U91(isPalListKind)) U22^1(tt) -> U23^1(tt) U22^1(tt) -> U23^1(U91(isPalListKind)) U23^1(tt) -> U24^1(tt) U23^1(tt) -> U24^1(U91(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule U24^1(tt) -> U25^1(isList) at position [0] we obtained the following new rules [LPAR04]: (U24^1(tt) -> U25^1(U11(isPalListKind)),U24^1(tt) -> U25^1(U11(isPalListKind))) (U24^1(tt) -> U25^1(tt),U24^1(tt) -> U25^1(tt)) (U24^1(tt) -> U25^1(U21(isPalListKind)),U24^1(tt) -> U25^1(U21(isPalListKind))) ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(tt) -> ISNELIST U45^1(tt) -> ISNELIST U55^1(tt) -> ISLIST U25^1(tt) -> ISLIST U24^1(tt) -> ISLIST U54^1(tt) -> ISNELIST U44^1(tt) -> ISLIST ISNELIST -> U41^1(tt) ISNELIST -> U41^1(U91(isPalListKind)) U41^1(tt) -> U42^1(tt) U41^1(tt) -> U42^1(U91(isPalListKind)) U42^1(tt) -> U43^1(tt) U42^1(tt) -> U43^1(U91(isPalListKind)) U43^1(tt) -> U44^1(tt) U43^1(tt) -> U44^1(U91(isPalListKind)) U44^1(tt) -> U45^1(U11(isPalListKind)) U44^1(tt) -> U45^1(tt) U44^1(tt) -> U45^1(U21(isPalListKind)) ISNELIST -> U51^1(tt) ISNELIST -> U51^1(U91(isPalListKind)) U51^1(tt) -> U52^1(tt) U51^1(tt) -> U52^1(U91(isPalListKind)) U52^1(tt) -> U53^1(tt) U52^1(tt) -> U53^1(U91(isPalListKind)) U53^1(tt) -> U54^1(tt) U53^1(tt) -> U54^1(U91(isPalListKind)) U54^1(tt) -> U55^1(U31(isPalListKind)) U54^1(tt) -> U55^1(U41(isPalListKind)) U54^1(tt) -> U55^1(U51(isPalListKind)) ISLIST -> U11^1(tt) ISLIST -> U11^1(U91(isPalListKind)) U11^1(tt) -> U12^1(tt) U11^1(tt) -> U12^1(U91(isPalListKind)) ISLIST -> U21^1(tt) ISLIST -> U21^1(U91(isPalListKind)) U21^1(tt) -> U22^1(tt) U21^1(tt) -> U22^1(U91(isPalListKind)) U22^1(tt) -> U23^1(tt) U22^1(tt) -> U23^1(U91(isPalListKind)) U23^1(tt) -> U24^1(tt) U23^1(tt) -> U24^1(U91(isPalListKind)) U24^1(tt) -> U25^1(U11(isPalListKind)) U24^1(tt) -> U25^1(tt) U24^1(tt) -> U25^1(U21(isPalListKind)) The TRS R consists of the following rules: isList -> U11(isPalListKind) isList -> tt isList -> U21(isPalListKind) isPalListKind -> tt isPalListKind -> U91(isPalListKind) U21(tt) -> U22(isPalListKind) U22(tt) -> U23(isPalListKind) U23(tt) -> U24(isPalListKind) U24(tt) -> U25(isList) U25(tt) -> U26(isList) U26(tt) -> tt U91(tt) -> U92(isPalListKind) U92(tt) -> tt U11(tt) -> U12(isPalListKind) U12(tt) -> U13(isNeList) isNeList -> U31(isPalListKind) isNeList -> U41(isPalListKind) isNeList -> U51(isPalListKind) U13(tt) -> tt U51(tt) -> U52(isPalListKind) U52(tt) -> U53(isPalListKind) U53(tt) -> U54(isPalListKind) U54(tt) -> U55(isNeList) U55(tt) -> U56(isList) U56(tt) -> tt U41(tt) -> U42(isPalListKind) U42(tt) -> U43(isPalListKind) U43(tt) -> U44(isPalListKind) U44(tt) -> U45(isList) U45(tt) -> U46(isNeList) U46(tt) -> tt U31(tt) -> U32(isPalListKind) U32(tt) -> U33(isQid) isQid -> tt U33(tt) -> tt Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = ISLIST evaluates to t =ISLIST Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence ISLIST -> U21^1(tt) with rule ISLIST -> U21^1(tt) at position [] and matcher [ ] U21^1(tt) -> U22^1(tt) with rule U21^1(tt) -> U22^1(tt) at position [] and matcher [ ] U22^1(tt) -> U23^1(tt) with rule U22^1(tt) -> U23^1(tt) at position [] and matcher [ ] U23^1(tt) -> U24^1(tt) with rule U23^1(tt) -> U24^1(tt) at position [] and matcher [ ] U24^1(tt) -> ISLIST with rule U24^1(tt) -> ISLIST Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (77) NO