(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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.

(1) DependencyPairsProof (EQUIVALENT transformation)

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

(2) Obligation:

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

__1(__(X, Y), Z) → __1(X, __(Y, Z))
__1(__(X, Y), Z) → __1(Y, Z)
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
U611(tt) → U621(isPalListKind)
U611(tt) → ISPALLISTKIND
U621(tt) → U631(isQid)
U621(tt) → ISQID
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
ISLISTU111(isPalListKind)
ISLISTISPALLISTKIND
ISLISTU211(isPalListKind)
ISNELISTU311(isPalListKind)
ISNELISTISPALLISTKIND
ISNELISTU411(isPalListKind)
ISNELISTU511(isPalListKind)
ISNEPALU611(isPalListKind)
ISNEPALISPALLISTKIND
ISNEPALU711(isQid)
ISNEPALISQID
ISPALU811(isPalListKind)
ISPALISPALLISTKIND
ISPALLISTKINDU911(isPalListKind)
ISPALLISTKINDISPALLISTKIND

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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(3) DependencyGraphProof (EQUIVALENT transformation)

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

(4) Complex Obligation (AND)

(5) Obligation:

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

U911(tt) → ISPALLISTKIND
ISPALLISTKINDU911(isPalListKind)
ISPALLISTKINDISPALLISTKIND

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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(6) Obligation:

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

ISNEPALU711(isQid)
U711(tt) → U721(isPalListKind)
U721(tt) → ISPAL
ISPALU811(isPalListKind)
U811(tt) → U821(isPalListKind)
U821(tt) → ISNEPAL

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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(7) Obligation:

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

U121(tt) → ISNELIST
ISNELISTU411(isPalListKind)
U411(tt) → U421(isPalListKind)
U421(tt) → U431(isPalListKind)
U431(tt) → U441(isPalListKind)
U441(tt) → U451(isList)
U451(tt) → ISNELIST
ISNELISTU511(isPalListKind)
U511(tt) → U521(isPalListKind)
U521(tt) → U531(isPalListKind)
U531(tt) → U541(isPalListKind)
U541(tt) → U551(isNeList)
U551(tt) → ISLIST
ISLISTU111(isPalListKind)
U111(tt) → U121(isPalListKind)
ISLISTU211(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:

__(__(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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(8) Obligation:

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

__1(__(X, Y), Z) → __1(Y, Z)
__1(__(X, Y), Z) → __1(X, __(Y, Z))

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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(9) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


__1(__(X, Y), Z) → __1(Y, Z)
__1(__(X, Y), Z) → __1(X, __(Y, Z))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
__1(x1, x2)  =  __1(x1)
__(x1, x2)  =  __(x1, x2)
nil  =  nil
U11(x1)  =  U11(x1)
tt  =  tt
U12(x1)  =  U12(x1)
isPalListKind  =  isPalListKind
U13(x1)  =  U13
isNeList  =  isNeList
U21(x1)  =  U21(x1)
U22(x1)  =  U22
U23(x1)  =  U23
U24(x1)  =  U24
U25(x1)  =  U25
isList  =  isList
U26(x1)  =  U26
U31(x1)  =  U31(x1)
U32(x1)  =  U32
U33(x1)  =  U33
isQid  =  isQid
U41(x1)  =  U41(x1)
U42(x1)  =  U42
U43(x1)  =  U43(x1)
U44(x1)  =  U44
U45(x1)  =  U45
U46(x1)  =  U46
U51(x1)  =  U51(x1)
U52(x1)  =  U52
U53(x1)  =  U53
U54(x1)  =  U54
U55(x1)  =  U55
U56(x1)  =  U56
U61(x1)  =  U61(x1)
U62(x1)  =  U62
U63(x1)  =  U63
U71(x1)  =  U71(x1)
U72(x1)  =  U72
U73(x1)  =  U73
isPal  =  isPal
U74(x1)  =  x1
U81(x1)  =  U81(x1)
U82(x1)  =  U82(x1)
U83(x1)  =  U83
isNePal  =  isNePal
U91(x1)  =  U91
U92(x1)  =  U92

Recursive path order with status [RPO].
Precedence:
isNeList > U311 > U32 > U33 > tt
isNeList > U411 > U42 > isPalListKind > U91 > U92 > tt
isNeList > U411 > U42 > U431 > U44 > U45 > U46 > tt
isNeList > U511 > U52 > U53 > U54 > U55 > U56 > tt
isList > U111 > U121 > U13 > tt
isList > U111 > isPalListKind > U91 > U92 > tt
isList > U211 > U22 > U23 > isPalListKind > U91 > U92 > tt
isList > U211 > U22 > U23 > U24 > U25 > U26 > tt
isPal > U811 > isPalListKind > U91 > U92 > tt
isPal > U811 > U821 > U83 > tt
isNePal > isQid > tt
isNePal > U611 > U62 > U63 > tt
isNePal > U711 > U72 > U73 > isPalListKind > U91 > U92 > tt

Status:
_^11: multiset
_2: [1,2]
nil: multiset
U111: multiset
tt: multiset
U121: multiset
isPalListKind: multiset
U13: multiset
isNeList: multiset
U211: multiset
U22: multiset
U23: multiset
U24: multiset
U25: multiset
isList: multiset
U26: multiset
U311: multiset
U32: multiset
U33: multiset
isQid: multiset
U411: multiset
U42: multiset
U431: multiset
U44: multiset
U45: multiset
U46: multiset
U511: multiset
U52: multiset
U53: multiset
U54: multiset
U55: multiset
U56: multiset
U611: multiset
U62: multiset
U63: multiset
U711: multiset
U72: multiset
U73: multiset
isPal: multiset
U811: multiset
U821: multiset
U83: multiset
isNePal: multiset
U91: multiset
U92: multiset

The following usable rules [FROCOS05] were oriented:

__(__(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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

(10) Obligation:

Q DP problem:
P is empty.
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
isListU11(isPalListKind)
isListtt
isListU21(isPalListKind)
isNeListU31(isPalListKind)
isNeListU41(isPalListKind)
isNeListU51(isPalListKind)
isNePalU61(isPalListKind)
isNePalU71(isQid)
isPalU81(isPalListKind)
isPaltt
isPalListKindtt
isPalListKindU91(isPalListKind)
isQidtt

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(11) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(12) TRUE