NO Termination w.r.t. Q proof of Transformed_CSR_04_PALINDROME_complete-noand_L.ari

Termination w.r.t. Q of the given QTRS could be disproven:

0 QTRS
↳1 QTRSRRRProof (⇔, 83 ms)
↳2 QTRS
↳3 QTRSRRRProof (⇔, 0 ms)
↳4 QTRS
↳5 QTRSRRRProof (⇔, 7 ms)
↳6 QTRS
↳7 DependencyPairsProof (⇔, 0 ms)
↳8 QDP
↳9 DependencyGraphProof (⇔, 0 ms)
↳10 AND
    ↳11 QDP
        ↳12 UsableRulesProof (⇔, 0 ms)
        ↳13 QDP
        ↳14 TransformationProof (⇔, 0 ms)
        ↳15 QDP
        ↳16 NonTerminationLoopProof (⇒, 0 ms)
        ↳17 NO
    ↳18 QDP
        ↳19 UsableRulesProof (⇔, 0 ms)
        ↳20 QDP
        ↳21 TransformationProof (⇔, 0 ms)
        ↳22 QDP
        ↳23 UsableRulesProof (⇔, 0 ms)
        ↳24 QDP
        ↳25 TransformationProof (⇔, 0 ms)
        ↳26 QDP
        ↳27 TransformationProof (⇔, 0 ms)
        ↳28 QDP
        ↳29 TransformationProof (⇔, 0 ms)
        ↳30 QDP
        ↳31 NonTerminationLoopProof (⇒, 0 ms)
        ↳32 NO
    ↳33 QDP
        ↳34 UsableRulesProof (⇔, 0 ms)
        ↳35 QDP
        ↳36 TransformationProof (⇔, 0 ms)
        ↳37 QDP
        ↳38 TransformationProof (⇔, 0 ms)
        ↳39 QDP
        ↳40 TransformationProof (⇔, 0 ms)
        ↳41 QDP
        ↳42 TransformationProof (⇔, 0 ms)
        ↳43 QDP
        ↳44 TransformationProof (⇔, 0 ms)
        ↳45 QDP
        ↳46 TransformationProof (⇔, 0 ms)
        ↳47 QDP
        ↳48 TransformationProof (⇔, 0 ms)
        ↳49 QDP
        ↳50 TransformationProof (⇔, 0 ms)
        ↳51 QDP
        ↳52 TransformationProof (⇔, 0 ms)
        ↳53 QDP
        ↳54 TransformationProof (⇔, 0 ms)
        ↳55 QDP
        ↳56 TransformationProof (⇔, 0 ms)
        ↳57 QDP
        ↳58 TransformationProof (⇔, 0 ms)
        ↳59 QDP
        ↳60 TransformationProof (⇔, 0 ms)
        ↳61 QDP
        ↳62 TransformationProof (⇔, 0 ms)
        ↳63 QDP
        ↳64 TransformationProof (⇔, 0 ms)
        ↳65 QDP
        ↳66 TransformationProof (⇔, 0 ms)
        ↳67 QDP
        ↳68 TransformationProof (⇔, 0 ms)
        ↳69 QDP
        ↳70 NonTerminationLoopProof (⇒, 398 ms)
        ↳71 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 transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = x1   
POL(U12(x1)) = 2·x1   
POL(U13(x1)) = x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = 2·x1   
POL(U23(x1)) = x1   
POL(U24(x1)) = 2·x1   
POL(U25(x1)) = 2·x1   
POL(U26(x1)) = 2·x1   
POL(U31(x1)) = 2·x1   
POL(U32(x1)) = x1   
POL(U33(x1)) = 2·x1   
POL(U41(x1)) = x1   
POL(U42(x1)) = x1   
POL(U43(x1)) = x1   
POL(U44(x1)) = x1   
POL(U45(x1)) = 2·x1   
POL(U46(x1)) = x1   
POL(U51(x1)) = x1   
POL(U52(x1)) = x1   
POL(U53(x1)) = 2·x1   
POL(U54(x1)) = 2·x1   
POL(U55(x1)) = x1   
POL(U56(x1)) = 2·x1   
POL(U61(x1)) = 2·x1   
POL(U62(x1)) = x1   
POL(U63(x1)) = x1   
POL(U71(x1)) = 1 + x1   
POL(U72(x1)) = 1 + 2·x1   
POL(U73(x1)) = x1   
POL(U74(x1)) = x1   
POL(U81(x1)) = 1 + 2·x1   
POL(U82(x1)) = 1 + x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = 2·x1   
POL(U92(x1)) = 2·x1   
POL(__(x1, x2)) = 1 + 2·x1 + x2   
POL(isList) = 0   
POL(isNeList) = 0   
POL(isNePal) = 1   
POL(isPal) = 1   
POL(isPalListKind) = 0   
POL(isQid) = 0   
POL(nil) = 1   
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))
__(X, nil) → X
__(nil, X) → X
isNePal → U61(isPalListKind)
isPal → tt


(2) 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 → U71(isQid)
isPal → U81(isPalListKind)
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt

Q is empty.

(3) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = x1   
POL(U13(x1)) = x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = x1   
POL(U23(x1)) = x1   
POL(U24(x1)) = x1   
POL(U25(x1)) = x1   
POL(U26(x1)) = x1   
POL(U31(x1)) = x1   
POL(U32(x1)) = x1   
POL(U33(x1)) = x1   
POL(U41(x1)) = 2·x1   
POL(U42(x1)) = x1   
POL(U43(x1)) = x1   
POL(U44(x1)) = 2·x1   
POL(U45(x1)) = 2·x1   
POL(U46(x1)) = 2·x1   
POL(U51(x1)) = 2·x1   
POL(U52(x1)) = x1   
POL(U53(x1)) = x1   
POL(U54(x1)) = 2·x1   
POL(U55(x1)) = x1   
POL(U56(x1)) = x1   
POL(U61(x1)) = 2 + 2·x1   
POL(U62(x1)) = 2 + x1   
POL(U63(x1)) = 1 + 2·x1   
POL(U71(x1)) = x1   
POL(U72(x1)) = x1   
POL(U73(x1)) = 2·x1   
POL(U74(x1)) = x1   
POL(U81(x1)) = x1   
POL(U82(x1)) = 2·x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = x1   
POL(U92(x1)) = x1   
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:

U62(tt) → U63(isQid)
U63(tt) → tt


(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)
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.

(5) QTRSRRRProof (EQUIVALENT transformation)

Used ordering:
Polynomial interpretation [POLO]:

POL(U11(x1)) = 2·x1   
POL(U12(x1)) = x1   
POL(U13(x1)) = x1   
POL(U21(x1)) = x1   
POL(U22(x1)) = 2·x1   
POL(U23(x1)) = 2·x1   
POL(U24(x1)) = 2·x1   
POL(U25(x1)) = x1   
POL(U26(x1)) = 2·x1   
POL(U31(x1)) = 2·x1   
POL(U32(x1)) = x1   
POL(U33(x1)) = 2·x1   
POL(U41(x1)) = 2·x1   
POL(U42(x1)) = x1   
POL(U43(x1)) = 2·x1   
POL(U44(x1)) = x1   
POL(U45(x1)) = x1   
POL(U46(x1)) = x1   
POL(U51(x1)) = x1   
POL(U52(x1)) = 2·x1   
POL(U53(x1)) = 2·x1   
POL(U54(x1)) = x1   
POL(U55(x1)) = x1   
POL(U56(x1)) = 2·x1   
POL(U61(x1)) = 1 + x1   
POL(U62(x1)) = 2·x1   
POL(U71(x1)) = x1   
POL(U72(x1)) = 2·x1   
POL(U73(x1)) = x1   
POL(U74(x1)) = 2·x1   
POL(U81(x1)) = 2·x1   
POL(U82(x1)) = x1   
POL(U83(x1)) = x1   
POL(U91(x1)) = x1   
POL(U92(x1)) = 2·x1   
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:

U61(tt) → U62(isPalListKind)


(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
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.

(7) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(8) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U111(tt) → U121(isPalListKind)
U111(tt) → ISPALLISTKIND
U121(tt) → U131(isNeList)
U121(tt) → ISNELIST
U211(tt) → U221(isPalListKind)
U211(tt) → ISPALLISTKIND
U221(tt) → U231(isPalListKind)
U221(tt) → ISPALLISTKIND
U231(tt) → U241(isPalListKind)
U231(tt) → ISPALLISTKIND
U241(tt) → U251(isList)
U241(tt) → ISLIST
U251(tt) → U261(isList)
U251(tt) → ISLIST
U311(tt) → U321(isPalListKind)
U311(tt) → ISPALLISTKIND
U321(tt) → U331(isQid)
U321(tt) → ISQID
U411(tt) → U421(isPalListKind)
U411(tt) → ISPALLISTKIND
U421(tt) → U431(isPalListKind)
U421(tt) → ISPALLISTKIND
U431(tt) → U441(isPalListKind)
U431(tt) → ISPALLISTKIND
U441(tt) → U451(isList)
U441(tt) → ISLIST
U451(tt) → U461(isNeList)
U451(tt) → ISNELIST
U511(tt) → U521(isPalListKind)
U511(tt) → ISPALLISTKIND
U521(tt) → U531(isPalListKind)
U521(tt) → ISPALLISTKIND
U531(tt) → U541(isPalListKind)
U531(tt) → ISPALLISTKIND
U541(tt) → U551(isNeList)
U541(tt) → ISNELIST
U551(tt) → U561(isList)
U551(tt) → ISLIST
U711(tt) → U721(isPalListKind)
U711(tt) → ISPALLISTKIND
U721(tt) → U731(isPal)
U721(tt) → ISPAL
U731(tt) → U741(isPalListKind)
U731(tt) → ISPALLISTKIND
U811(tt) → U821(isPalListKind)
U811(tt) → ISPALLISTKIND
U821(tt) → U831(isNePal)
U821(tt) → ISNEPAL
U911(tt) → U921(isPalListKind)
U911(tt) → ISPALLISTKIND
ISLIST → U111(isPalListKind)
ISLIST → ISPALLISTKIND
ISLIST → U211(isPalListKind)
ISNELIST → U311(isPalListKind)
ISNELIST → ISPALLISTKIND
ISNELIST → U411(isPalListKind)
ISNELIST → U511(isPalListKind)
ISNEPAL → U711(isQid)
ISNEPAL → ISQID
ISPAL → U811(isPalListKind)
ISPAL → ISPALLISTKIND
ISPALLISTKIND → U911(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.

(9) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 30 less nodes.

(10) Complex Obligation (AND)

(11) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKIND → U911(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.

(12) UsableRulesProof (EQUIVALENT transformation)

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.

(13) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKIND → U911(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.

(14) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISPALLISTKIND → U911(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISPALLISTKIND → U911(tt) → ISPALLISTKIND → U911(tt)
ISPALLISTKIND → U911(U91(isPalListKind)) → ISPALLISTKIND → U911(U91(isPalListKind))

(15) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U911(tt) → ISPALLISTKIND
ISPALLISTKIND → ISPALLISTKIND
ISPALLISTKIND → U911(tt)
ISPALLISTKIND → U911(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.

(16) NonTerminationLoopProof (COMPLETE transformation)

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.



(17) NO

(18) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPAL → U811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
ISNEPAL → U711(isQid)
U711(tt) → U721(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.

(19) UsableRulesProof (EQUIVALENT transformation)

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.

(20) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPAL → U811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
ISNEPAL → U711(isQid)
U711(tt) → U721(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.

(21) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNEPAL → U711(isQid) at position [0] we obtained the following new rules [LPAR04]:

ISNEPAL → U711(tt) → ISNEPAL → U711(tt)

(22) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPAL → U811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPAL → U711(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.

(23) UsableRulesProof (EQUIVALENT transformation)

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.

(24) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
ISPAL → U811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPAL → U711(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.

(25) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISPAL → U811(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISPAL → U811(tt) → ISPAL → U811(tt)
ISPAL → U811(U91(isPalListKind)) → ISPAL → U811(U91(isPalListKind))

(26) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPAL → U711(tt)
ISPAL → U811(tt)
ISPAL → U811(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.

(27) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U811(tt) → U821(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U811(tt) → U821(tt) → U811(tt) → U821(tt)
U811(tt) → U821(U91(isPalListKind)) → U811(tt) → U821(U91(isPalListKind))

(28) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
ISNEPAL → U711(tt)
ISPAL → U811(tt)
ISPAL → U811(U91(isPalListKind))
U811(tt) → U821(tt)
U811(tt) → U821(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.

(29) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U711(tt) → U721(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U711(tt) → U721(tt) → U711(tt) → U721(tt)
U711(tt) → U721(U91(isPalListKind)) → U711(tt) → U721(U91(isPalListKind))

(30) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U721(tt) → ISPAL
U821(tt) → ISNEPAL
ISNEPAL → U711(tt)
ISPAL → U811(tt)
ISPAL → U811(U91(isPalListKind))
U811(tt) → U821(tt)
U811(tt) → U821(U91(isPalListKind))
U711(tt) → U721(tt)
U711(tt) → U721(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.

(31) NonTerminationLoopProof (COMPLETE transformation)

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 → U811(tt)
with rule ISPAL → U811(tt) at position [] and matcher [ ]

U811(tt) → U821(tt)
with rule U811(tt) → U821(tt) at position [] and matcher [ ]

U821(tt) → ISNEPAL
with rule U821(tt) → ISNEPAL at position [] and matcher [ ]

ISNEPAL → U711(tt)
with rule ISNEPAL → U711(tt) at position [] and matcher [ ]

U711(tt) → U721(tt)
with rule U711(tt) → U721(tt) at position [] and matcher [ ]

U721(tt) → ISPAL
with rule U721(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.



(32) NO

(33) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
ISNELIST → U411(isPalListKind)
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(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.

(34) UsableRulesProof (EQUIVALENT transformation)

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.

(35) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
ISNELIST → U411(isPalListKind)
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(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.

(36) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNELIST → U411(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISNELIST → U411(tt) → ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind)) → ISNELIST → U411(U91(isPalListKind))

(37) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(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.

(38) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U411(tt) → U421(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U411(tt) → U421(tt) → U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind)) → U411(tt) → U421(U91(isPalListKind))

(39) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(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.

(40) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U421(tt) → U431(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U421(tt) → U431(tt) → U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind)) → U421(tt) → U431(U91(isPalListKind))

(41) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(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.

(42) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U431(tt) → U441(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U431(tt) → U441(tt) → U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind)) → U431(tt) → U441(U91(isPalListKind))

(43) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(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 transformation)

By narrowing [LPAR04] the rule U441(tt) → U451(isList) at position [0] we obtained the following new rules [LPAR04]:

U441(tt) → U451(U11(isPalListKind)) → U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt) → U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind)) → U441(tt) → U451(U21(isPalListKind))

(45) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
ISNELIST → U511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(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.

(46) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISNELIST → U511(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISNELIST → U511(tt) → ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind)) → ISNELIST → U511(U91(isPalListKind))

(47) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(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 transformation)

By narrowing [LPAR04] the rule U511(tt) → U521(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U511(tt) → U521(tt) → U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind)) → U511(tt) → U521(U91(isPalListKind))

(49) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(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 transformation)

By narrowing [LPAR04] the rule U521(tt) → U531(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U521(tt) → U531(tt) → U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind)) → U521(tt) → U531(U91(isPalListKind))

(51) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(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.

(52) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U531(tt) → U541(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U531(tt) → U541(tt) → U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind)) → U531(tt) → U541(U91(isPalListKind))

(53) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(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 transformation)

By narrowing [LPAR04] the rule U541(tt) → U551(isNeList) at position [0] we obtained the following new rules [LPAR04]:

U541(tt) → U551(U31(isPalListKind)) → U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind)) → U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind)) → U541(tt) → U551(U51(isPalListKind))

(55) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
ISLIST → U111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(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.

(56) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule ISLIST → U111(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISLIST → U111(tt) → ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind)) → ISLIST → U111(U91(isPalListKind))

(57) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U111(tt) → U121(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(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 transformation)

By narrowing [LPAR04] the rule U111(tt) → U121(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U111(tt) → U121(tt) → U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind)) → U111(tt) → U121(U91(isPalListKind))

(59) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
ISLIST → U211(isPalListKind)
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(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 transformation)

By narrowing [LPAR04] the rule ISLIST → U211(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

ISLIST → U211(tt) → ISLIST → U211(tt)
ISLIST → U211(U91(isPalListKind)) → ISLIST → U211(U91(isPalListKind))

(61) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U211(tt) → U221(isPalListKind)
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLIST → U211(tt)
ISLIST → U211(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.

(62) TransformationProof (EQUIVALENT transformation)

By narrowing [LPAR04] the rule U211(tt) → U221(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U211(tt) → U221(tt) → U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind)) → U211(tt) → U221(U91(isPalListKind))

(63) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U221(tt) → U231(isPalListKind)
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLIST → U211(tt)
ISLIST → U211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(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 transformation)

By narrowing [LPAR04] the rule U221(tt) → U231(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U221(tt) → U231(tt) → U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind)) → U221(tt) → U231(U91(isPalListKind))

(65) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U231(tt) → U241(isPalListKind)
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLIST → U211(tt)
ISLIST → U211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(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 transformation)

By narrowing [LPAR04] the rule U231(tt) → U241(isPalListKind) at position [0] we obtained the following new rules [LPAR04]:

U231(tt) → U241(tt) → U231(tt) → U241(tt)
U231(tt) → U241(U91(isPalListKind)) → U231(tt) → U241(U91(isPalListKind))

(67) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U241(tt) → U251(isList)
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLIST → U211(tt)
ISLIST → U211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))
U231(tt) → U241(tt)
U231(tt) → U241(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 transformation)

By narrowing [LPAR04] the rule U241(tt) → U251(isList) at position [0] we obtained the following new rules [LPAR04]:

U241(tt) → U251(U11(isPalListKind)) → U241(tt) → U251(U11(isPalListKind))
U241(tt) → U251(tt) → U241(tt) → U251(tt)
U241(tt) → U251(U21(isPalListKind)) → U241(tt) → U251(U21(isPalListKind))

(69) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U121(tt) → ISNELIST
U451(tt) → ISNELIST
U551(tt) → ISLIST
U251(tt) → ISLIST
U241(tt) → ISLIST
U541(tt) → ISNELIST
U441(tt) → ISLIST
ISNELIST → U411(tt)
ISNELIST → U411(U91(isPalListKind))
U411(tt) → U421(tt)
U411(tt) → U421(U91(isPalListKind))
U421(tt) → U431(tt)
U421(tt) → U431(U91(isPalListKind))
U431(tt) → U441(tt)
U431(tt) → U441(U91(isPalListKind))
U441(tt) → U451(U11(isPalListKind))
U441(tt) → U451(tt)
U441(tt) → U451(U21(isPalListKind))
ISNELIST → U511(tt)
ISNELIST → U511(U91(isPalListKind))
U511(tt) → U521(tt)
U511(tt) → U521(U91(isPalListKind))
U521(tt) → U531(tt)
U521(tt) → U531(U91(isPalListKind))
U531(tt) → U541(tt)
U531(tt) → U541(U91(isPalListKind))
U541(tt) → U551(U31(isPalListKind))
U541(tt) → U551(U41(isPalListKind))
U541(tt) → U551(U51(isPalListKind))
ISLIST → U111(tt)
ISLIST → U111(U91(isPalListKind))
U111(tt) → U121(tt)
U111(tt) → U121(U91(isPalListKind))
ISLIST → U211(tt)
ISLIST → U211(U91(isPalListKind))
U211(tt) → U221(tt)
U211(tt) → U221(U91(isPalListKind))
U221(tt) → U231(tt)
U221(tt) → U231(U91(isPalListKind))
U231(tt) → U241(tt)
U231(tt) → U241(U91(isPalListKind))
U241(tt) → U251(U11(isPalListKind))
U241(tt) → U251(tt)
U241(tt) → U251(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.

(70) NonTerminationLoopProof (COMPLETE transformation)

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 → U211(tt)
with rule ISLIST → U211(tt) at position [] and matcher [ ]

U211(tt) → U221(tt)
with rule U211(tt) → U221(tt) at position [] and matcher [ ]

U221(tt) → U231(tt)
with rule U221(tt) → U231(tt) at position [] and matcher [ ]

U231(tt) → U241(tt)
with rule U231(tt) → U241(tt) at position [] and matcher [ ]

U241(tt) → ISLIST
with rule U241(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.



(71) NO