Termination w.r.t. Q proof of /tmp/tmpY4TCWY/PALINDROME_complete-noand

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

0 QTRS

↳1 DependencyPairsProof (⇔)

↳2 QDP

↳3 DependencyGraphProof (⇔)

↳4 AND

  ↳5 QDP

  ↳6 QDP

  ↳7 QDP

  ↳8 QDP

    ↳9 QDPOrderProof (⇔)

    ↳10 QDP

    ↳11 PisEmptyProof (⇔)

    ↳12 TRUE

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

__¹(__(X, Y), Z) → __¹(X, __(Y, Z))
__¹(__(X, Y), Z) → __¹(Y, Z)
U11¹(tt) → U12¹(isPalListKind)
U11¹(tt) → ISPALLISTKIND
U12¹(tt) → U13¹(isNeList)
U12¹(tt) → ISNELIST
U21¹(tt) → U22¹(isPalListKind)
U21¹(tt) → ISPALLISTKIND
U22¹(tt) → U23¹(isPalListKind)
U22¹(tt) → ISPALLISTKIND
U23¹(tt) → U24¹(isPalListKind)
U23¹(tt) → ISPALLISTKIND
U24¹(tt) → U25¹(isList)
U24¹(tt) → ISLIST
U25¹(tt) → U26¹(isList)
U25¹(tt) → ISLIST
U31¹(tt) → U32¹(isPalListKind)
U31¹(tt) → ISPALLISTKIND
U32¹(tt) → U33¹(isQid)
U32¹(tt) → ISQID
U41¹(tt) → U42¹(isPalListKind)
U41¹(tt) → ISPALLISTKIND
U42¹(tt) → U43¹(isPalListKind)
U42¹(tt) → ISPALLISTKIND
U43¹(tt) → U44¹(isPalListKind)
U43¹(tt) → ISPALLISTKIND
U44¹(tt) → U45¹(isList)
U44¹(tt) → ISLIST
U45¹(tt) → U46¹(isNeList)
U45¹(tt) → ISNELIST
U51¹(tt) → U52¹(isPalListKind)
U51¹(tt) → ISPALLISTKIND
U52¹(tt) → U53¹(isPalListKind)
U52¹(tt) → ISPALLISTKIND
U53¹(tt) → U54¹(isPalListKind)
U53¹(tt) → ISPALLISTKIND
U54¹(tt) → U55¹(isNeList)
U54¹(tt) → ISNELIST
U55¹(tt) → U56¹(isList)
U55¹(tt) → ISLIST
U61¹(tt) → U62¹(isPalListKind)
U61¹(tt) → ISPALLISTKIND
U62¹(tt) → U63¹(isQid)
U62¹(tt) → ISQID
U71¹(tt) → U72¹(isPalListKind)
U71¹(tt) → ISPALLISTKIND
U72¹(tt) → U73¹(isPal)
U72¹(tt) → ISPAL
U73¹(tt) → U74¹(isPalListKind)
U73¹(tt) → ISPALLISTKIND
U81¹(tt) → U82¹(isPalListKind)
U81¹(tt) → ISPALLISTKIND
U82¹(tt) → U83¹(isNePal)
U82¹(tt) → ISNEPAL
U91¹(tt) → U92¹(isPalListKind)
U91¹(tt) → ISPALLISTKIND
ISLIST → U11¹(isPalListKind)
ISLIST → ISPALLISTKIND
ISLIST → U21¹(isPalListKind)
ISNELIST → U31¹(isPalListKind)
ISNELIST → ISPALLISTKIND
ISNELIST → U41¹(isPalListKind)
ISNELIST → U51¹(isPalListKind)
ISNEPAL → U61¹(isPalListKind)
ISNEPAL → ISPALLISTKIND
ISNEPAL → U71¹(isQid)
ISNEPAL → ISQID
ISPAL → U81¹(isPalListKind)
ISPAL → ISPALLISTKIND
ISPALLISTKIND → U91¹(isPalListKind)
ISPALLISTKIND → ISPALLISTKIND

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

U91¹(tt) → ISPALLISTKIND
ISPALLISTKIND → U91¹(isPalListKind)
ISPALLISTKIND → ISPALLISTKIND

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.
We have to consider all minimal (P,Q,R)-chains.

(6) Obligation:

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

ISNEPAL → U71¹(isQid)
U71¹(tt) → U72¹(isPalListKind)
U72¹(tt) → ISPAL
ISPAL → U81¹(isPalListKind)
U81¹(tt) → U82¹(isPalListKind)
U82¹(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
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.
We have to consider all minimal (P,Q,R)-chains.

(7) Obligation:

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

U12¹(tt) → ISNELIST
ISNELIST → U41¹(isPalListKind)
U41¹(tt) → U42¹(isPalListKind)
U42¹(tt) → U43¹(isPalListKind)
U43¹(tt) → U44¹(isPalListKind)
U44¹(tt) → U45¹(isList)
U45¹(tt) → ISNELIST
ISNELIST → U51¹(isPalListKind)
U51¹(tt) → U52¹(isPalListKind)
U52¹(tt) → U53¹(isPalListKind)
U53¹(tt) → U54¹(isPalListKind)
U54¹(tt) → U55¹(isNeList)
U55¹(tt) → ISLIST
ISLIST → U11¹(isPalListKind)
U11¹(tt) → U12¹(isPalListKind)
ISLIST → U21¹(isPalListKind)
U21¹(tt) → U22¹(isPalListKind)
U22¹(tt) → U23¹(isPalListKind)
U23¹(tt) → U24¹(isPalListKind)
U24¹(tt) → U25¹(isList)
U25¹(tt) → ISLIST
U24¹(tt) → ISLIST
U54¹(tt) → ISNELIST
U44¹(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
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.
We have to consider all minimal (P,Q,R)-chains.

(8) Obligation:

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

__¹(__(X, Y), Z) → __¹(Y, Z)
__¹(__(X, Y), Z) → __¹(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
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.
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.

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

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
__¹(x1, x2) = __¹(x1)
__(x1, x2) = __(x1, x2)
nil = nil

Lexicographic path order with status [LPO].
Precedence:

__₂ > __^1₁
nil > __^1₁

Status:

__^1₁: [1]
__₂: [1,2]
nil: []

The following usable rules [FROCOS05] were oriented: none

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

(0) Obligation:

(1) DependencyPairsProof (EQUIVALENT transformation)

(2) Obligation:

(3) DependencyGraphProof (EQUIVALENT transformation)

(4) Complex Obligation (AND)

(5) Obligation:

(6) Obligation:

(7) Obligation:

(8) Obligation:

(9) QDPOrderProof (EQUIVALENT transformation)

(10) Obligation:

(11) PisEmptyProof (EQUIVALENT transformation)

(12) TRUE