/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), O(n^1))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).

(0) CpxTRS
(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 18 ms]
(2) CpxTRS
    (3) NonCtorToCtorProof [UPPER BOUND(ID), 2 ms]
    (4) CpxRelTRS
    (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxRelTRS
    (7) CpxTrsToCdtProof [UPPER BOUND(ID), 18 ms]
    (8) CdtProblem
    (9) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) CdtProblem
    (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 210 ms]
    (16) CdtProblem
    (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 118 ms]
    (20) CdtProblem
    (21) CdtKnowledgeProof [FINISHED, 0 ms]
    (22) BOUNDS(1, 1)
(23) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(24) CpxTRS
    (25) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (26) typed CpxTrs
    (27) OrderProof [LOWER BOUND(ID), 0 ms]
    (28) typed CpxTrs
    (29) RewriteLemmaProof [LOWER BOUND(ID), 776 ms]
    (30) BEST
        (31) proven lower bound
            (32) LowerBoundPropagationProof [FINISHED, 0 ms]
            (33) BOUNDS(n^1, INF)
        (34) typed CpxTrs
            (35) RewriteLemmaProof [LOWER BOUND(ID), 573 ms]
            (36) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).


The TRS R consists of the following rules:

   __(__(X, Y), Z) -> __(X, __(Y, Z))
   __(X, nil) -> X
   __(nil, X) -> X
   U11(tt) -> tt
   U21(tt, V2) -> U22(isList(activate(V2)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, V2) -> U42(isNeList(activate(V2)))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isList(activate(V2)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, P) -> U72(isPal(activate(P)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(V) -> U11(isNeList(activate(V)))
   isList(n__nil) -> tt
   isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
   isNeList(V) -> U31(isQid(activate(V)))
   isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
   isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
   isNePal(V) -> U61(isQid(activate(V)))
   isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
   isPal(V) -> U81(isNePal(activate(V)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(X1, X2)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
The following defined symbols can occur below the 0th argument of U31: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of isQid: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of activate: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U22: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 0th argument of isList: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U41: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 1th argument of U41: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U42: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 0th argument of isNeList: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U51: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 1th argument of U51: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U72: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of isPal: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U52: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 0th argument of U11: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 0th argument of U21: a, U31, U52, U11, U41, isQid, isPal, U61, __, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U22, U71, o, isNeList, i, U51
The following defined symbols can occur below the 1th argument of U21: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U61: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U81: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of isNePal: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 0th argument of U71: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e
The following defined symbols can occur below the 1th argument of U71: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, U61, __, e

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X

----------------------------------------

(2)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   U11(tt) -> tt
   U21(tt, V2) -> U22(isList(activate(V2)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, V2) -> U42(isNeList(activate(V2)))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isList(activate(V2)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, P) -> U72(isPal(activate(P)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(V) -> U11(isNeList(activate(V)))
   isList(n__nil) -> tt
   isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
   isNeList(V) -> U31(isQid(activate(V)))
   isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
   isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
   isNePal(V) -> U61(isQid(activate(V)))
   isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
   isPal(V) -> U81(isNePal(activate(V)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(X1, X2)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(3) NonCtorToCtorProof (UPPER BOUND(ID))
transformed non-ctor to ctor-system
----------------------------------------

(4)
Obligation:
The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   U11(tt) -> tt
   U21(tt, V2) -> U22(isList(activate(V2)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, V2) -> U42(isNeList(activate(V2)))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isList(activate(V2)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, P) -> U72(isPal(activate(P)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(V) -> U11(isNeList(activate(V)))
   isList(n__nil) -> tt
   isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
   isNeList(V) -> U31(isQid(activate(V)))
   isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
   isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
   isNePal(V) -> U61(isQid(activate(V)))
   isPal(V) -> U81(isNePal(activate(V)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(X1, X2)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X
   isNePal(n____(I, c___(P, I))) -> U71(isQid(activate(I)), activate(P))

The (relative) TRS S consists of the following rules:

   __(x0, x1) -> c___(x0, x1)

Rewrite Strategy: FULL
----------------------------------------

(5) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.
----------------------------------------

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   U11(tt) -> tt
   U21(tt, V2) -> U22(isList(activate(V2)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, V2) -> U42(isNeList(activate(V2)))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isList(activate(V2)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, P) -> U72(isPal(activate(P)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(V) -> U11(isNeList(activate(V)))
   isList(n__nil) -> tt
   isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
   isNeList(V) -> U31(isQid(activate(V)))
   isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
   isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
   isNePal(V) -> U61(isQid(activate(V)))
   isPal(V) -> U81(isNePal(activate(V)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(X1, X2)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X
   isNePal(n____(I, c___(P, I))) -> U71(isQid(activate(I)), activate(P))

The (relative) TRS S consists of the following rules:

   __(x0, x1) -> c___(x0, x1)

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   U11(tt) -> tt
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, z0) -> U72(isPal(activate(z0)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   isNePal(z0) -> U61(isQid(activate(z0)))
   isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1))
   isPal(z0) -> U81(isNePal(activate(z0)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
Tuples:
   __'(z0, z1) -> c
   __'(z0, z1) -> c1
   U11'(tt) -> c2
   U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U22'(tt) -> c4
   U31'(tt) -> c5
   U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   U42'(tt) -> c7
   U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U52'(tt) -> c9
   U61'(tt) -> c10
   U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0))
   U72'(tt) -> c12
   U81'(tt) -> c13
   ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   ISLIST(n__nil) -> c15
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0))
   ISPAL(n__nil) -> c23
   ISQID(n__a) -> c24
   ISQID(n__e) -> c25
   ISQID(n__i) -> c26
   ISQID(n__o) -> c27
   ISQID(n__u) -> c28
   NIL -> c29
   A -> c30
   E -> c31
   I -> c32
   O -> c33
   U -> c34
   ACTIVATE(n__nil) -> c35(NIL)
   ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1))
   ACTIVATE(n__a) -> c37(A)
   ACTIVATE(n__e) -> c38(E)
   ACTIVATE(n__i) -> c39(I)
   ACTIVATE(n__o) -> c40(O)
   ACTIVATE(n__u) -> c41(U)
   ACTIVATE(z0) -> c42
S tuples:
   __'(z0, z1) -> c1
   U11'(tt) -> c2
   U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U22'(tt) -> c4
   U31'(tt) -> c5
   U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   U42'(tt) -> c7
   U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U52'(tt) -> c9
   U61'(tt) -> c10
   U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0))
   U72'(tt) -> c12
   U81'(tt) -> c13
   ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   ISLIST(n__nil) -> c15
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0))
   ISPAL(n__nil) -> c23
   ISQID(n__a) -> c24
   ISQID(n__e) -> c25
   ISQID(n__i) -> c26
   ISQID(n__o) -> c27
   ISQID(n__u) -> c28
   NIL -> c29
   A -> c30
   E -> c31
   I -> c32
   O -> c33
   U -> c34
   ACTIVATE(n__nil) -> c35(NIL)
   ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1))
   ACTIVATE(n__a) -> c37(A)
   ACTIVATE(n__e) -> c38(E)
   ACTIVATE(n__i) -> c39(I)
   ACTIVATE(n__o) -> c40(O)
   ACTIVATE(n__u) -> c41(U)
   ACTIVATE(z0) -> c42
K tuples:none
Defined Rule Symbols:   U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1

Defined Pair Symbols:   __'_2, U11'_1, U21'_2, U22'_1, U31'_1, U41'_2, U42'_1, U51'_2, U52'_1, U61'_1, U71'_2, U72'_1, U81'_1, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1, ISQID_1, NIL, A, E, I, O, U, ACTIVATE_1

Compound Symbols:   c, c1, c2, c3_3, c4, c5, c6_3, c7, c8_3, c9, c10, c11_3, c12, c13, c14_3, c15, c16_4, c17_3, c18_4, c19_4, c20_3, c21_4, c22_3, c23, c24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c41_1, c42


----------------------------------------

(9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 33 trailing nodes:
   E -> c31
   ISQID(n__u) -> c28
   O -> c33
   ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))
   ACTIVATE(n__i) -> c39(I)
   ISPAL(n__nil) -> c23
   U31'(tt) -> c5
   A -> c30
   ACTIVATE(n__nil) -> c35(NIL)
   ISLIST(n__nil) -> c15
   U81'(tt) -> c13
   U52'(tt) -> c9
   ACTIVATE(z0) -> c42
   U11'(tt) -> c2
   __'(z0, z1) -> c
   U -> c34
   U72'(tt) -> c12
   ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1))
   ACTIVATE(n__e) -> c38(E)
   ISQID(n__o) -> c27
   ACTIVATE(n__u) -> c41(U)
   ACTIVATE(n__a) -> c37(A)
   ISQID(n__i) -> c26
   ISQID(n__e) -> c25
   I -> c32
   U61'(tt) -> c10
   __'(z0, z1) -> c1
   U42'(tt) -> c7
   ISQID(n__a) -> c24
   ACTIVATE(n__o) -> c40(O)
   NIL -> c29
   U22'(tt) -> c4
   ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0))

----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   U11(tt) -> tt
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, z0) -> U72(isPal(activate(z0)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   isNePal(z0) -> U61(isQid(activate(z0)))
   isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1))
   isPal(z0) -> U81(isNePal(activate(z0)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
Tuples:
   U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0))
   ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0))
S tuples:
   U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0))
   U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0))
   ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1))
   ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0))
K tuples:none
Defined Rule Symbols:   U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_3, c6_3, c8_3, c11_3, c14_3, c16_4, c18_4, c19_4, c21_4, c22_3


----------------------------------------

(11) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 21 trailing tuple parts
----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   U11(tt) -> tt
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, z0) -> U72(isPal(activate(z0)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   isNePal(z0) -> U61(isQid(activate(z0)))
   isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1))
   isPal(z0) -> U81(isNePal(activate(z0)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
S tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
K tuples:none
Defined Rule Symbols:   U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1


----------------------------------------

(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   U61(tt) -> tt
   U71(tt, z0) -> U72(isPal(activate(z0)))
   U72(tt) -> tt
   U81(tt) -> tt
   isNePal(z0) -> U61(isQid(activate(z0)))
   isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1))
   isPal(z0) -> U81(isNePal(activate(z0)))
   isPal(n__nil) -> tt

----------------------------------------

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
   nil -> n__nil
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   U11(tt) -> tt
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   U31(tt) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
S tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
K tuples:none
Defined Rule Symbols:   activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1


----------------------------------------

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
We considered the (Usable) Rules:
   activate(n__u) -> u
   __(z0, z1) -> c___(z0, z1)
   activate(n__i) -> i
   activate(z0) -> z0
   i -> n__i
   nil -> n__nil
   u -> n__u
   o -> n__o
   activate(n__nil) -> nil
   __(z0, z1) -> n____(z0, z1)
   activate(n__e) -> e
   e -> n__e
   activate(n__o) -> o
   activate(n__a) -> a
   activate(n____(z0, z1)) -> __(z0, z1)
   a -> n__a
And the Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(ISLIST(x_1)) = 0
   POL(ISNELIST(x_1)) = 0
   POL(ISNEPAL(x_1)) = x_1
   POL(ISPAL(x_1)) = x_1
   POL(U11(x_1)) = [1] + x_1
   POL(U21(x_1, x_2)) = [1] + x_1 + x_2
   POL(U21'(x_1, x_2)) = 0
   POL(U22(x_1)) = [1]
   POL(U31(x_1)) = [1] + x_1
   POL(U41(x_1, x_2)) = [1] + x_1 + x_2
   POL(U41'(x_1, x_2)) = 0
   POL(U42(x_1)) = [1]
   POL(U51(x_1, x_2)) = [1] + x_1 + x_2
   POL(U51'(x_1, x_2)) = 0
   POL(U52(x_1)) = [1]
   POL(U71'(x_1, x_2)) = x_2
   POL(__(x_1, x_2)) = [1] + x_1 + x_2
   POL(a) = [1]
   POL(activate(x_1)) = x_1
   POL(c11(x_1)) = x_1
   POL(c14(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c18(x_1, x_2)) = x_1 + x_2
   POL(c19(x_1, x_2)) = x_1 + x_2
   POL(c21(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c6(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c___(x_1, x_2)) = x_1 + x_2
   POL(e) = [1]
   POL(i) = [1]
   POL(isList(x_1)) = 0
   POL(isNeList(x_1)) = [1]
   POL(isQid(x_1)) = [1]
   POL(n____(x_1, x_2)) = [1] + x_1 + x_2
   POL(n__a) = [1]
   POL(n__e) = [1]
   POL(n__i) = [1]
   POL(n__nil) = [1]
   POL(n__o) = [1]
   POL(n__u) = [1]
   POL(nil) = [1]
   POL(o) = [1]
   POL(tt) = 0
   POL(u) = [1]

----------------------------------------

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
   nil -> n__nil
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   U11(tt) -> tt
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   U31(tt) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
S tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
K tuples:
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
Defined Rule Symbols:   activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1


----------------------------------------

(17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))

----------------------------------------

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
   nil -> n__nil
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   U11(tt) -> tt
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   U31(tt) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
S tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
K tuples:
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
Defined Rule Symbols:   activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1


----------------------------------------

(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
We considered the (Usable) Rules:
   activate(n__u) -> u
   __(z0, z1) -> c___(z0, z1)
   activate(n__i) -> i
   activate(z0) -> z0
   i -> n__i
   nil -> n__nil
   u -> n__u
   o -> n__o
   activate(n__nil) -> nil
   __(z0, z1) -> n____(z0, z1)
   activate(n__e) -> e
   e -> n__e
   activate(n__o) -> o
   activate(n__a) -> a
   activate(n____(z0, z1)) -> __(z0, z1)
   a -> n__a
And the Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(ISLIST(x_1)) = x_1
   POL(ISNELIST(x_1)) = x_1
   POL(ISNEPAL(x_1)) = 0
   POL(ISPAL(x_1)) = 0
   POL(U11(x_1)) = [1] + x_1
   POL(U21(x_1, x_2)) = [1] + x_1 + x_2
   POL(U21'(x_1, x_2)) = x_2
   POL(U22(x_1)) = [1]
   POL(U31(x_1)) = [1] + x_1
   POL(U41(x_1, x_2)) = [1] + x_1 + x_2
   POL(U41'(x_1, x_2)) = x_2
   POL(U42(x_1)) = [1]
   POL(U51(x_1, x_2)) = [1] + x_1 + x_2
   POL(U51'(x_1, x_2)) = x_2
   POL(U52(x_1)) = [1]
   POL(U71'(x_1, x_2)) = 0
   POL(__(x_1, x_2)) = [1] + x_1 + x_2
   POL(a) = [1]
   POL(activate(x_1)) = x_1
   POL(c11(x_1)) = x_1
   POL(c14(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c18(x_1, x_2)) = x_1 + x_2
   POL(c19(x_1, x_2)) = x_1 + x_2
   POL(c21(x_1)) = x_1
   POL(c22(x_1)) = x_1
   POL(c3(x_1)) = x_1
   POL(c6(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c___(x_1, x_2)) = [1] + x_1 + x_2
   POL(e) = [1]
   POL(i) = [1]
   POL(isList(x_1)) = 0
   POL(isNeList(x_1)) = [1]
   POL(isQid(x_1)) = [1]
   POL(n____(x_1, x_2)) = [1] + x_1 + x_2
   POL(n__a) = [1]
   POL(n__e) = [1]
   POL(n__i) = [1]
   POL(n__nil) = [1]
   POL(n__o) = [1]
   POL(n__u) = [1]
   POL(nil) = [1]
   POL(o) = [1]
   POL(tt) = 0
   POL(u) = [1]

----------------------------------------

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   activate(n__nil) -> nil
   activate(n____(z0, z1)) -> __(z0, z1)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(z0) -> z0
   nil -> n__nil
   __(z0, z1) -> c___(z0, z1)
   __(z0, z1) -> n____(z0, z1)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   isList(z0) -> U11(isNeList(activate(z0)))
   isList(n__nil) -> tt
   isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1))
   U11(tt) -> tt
   isNeList(z0) -> U31(isQid(activate(z0)))
   isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1))
   isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1))
   U31(tt) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   U41(tt, z0) -> U42(isNeList(activate(z0)))
   U21(tt, z0) -> U22(isList(activate(z0)))
   U22(tt) -> tt
   U42(tt) -> tt
   U51(tt, z0) -> U52(isList(activate(z0)))
   U52(tt) -> tt
Tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
S tuples:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
K tuples:
   ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)))
   U71'(tt, z0) -> c11(ISPAL(activate(z0)))
   ISPAL(z0) -> c22(ISNEPAL(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
Defined Rule Symbols:   activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1

Defined Pair Symbols:   U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1

Compound Symbols:   c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1


----------------------------------------

(21) CdtKnowledgeProof (FINISHED)
The following tuples could be moved from S to K by knowledge propagation:
   U21'(tt, z0) -> c3(ISLIST(activate(z0)))
   U41'(tt, z0) -> c6(ISNELIST(activate(z0)))
   U51'(tt, z0) -> c8(ISLIST(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
   ISLIST(z0) -> c14(ISNELIST(activate(z0)))
   ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)))
   ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)))
Now S is empty
----------------------------------------

(22)
BOUNDS(1, 1)

----------------------------------------

(23) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(24)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   __(__(X, Y), Z) -> __(X, __(Y, Z))
   __(X, nil) -> X
   __(nil, X) -> X
   U11(tt) -> tt
   U21(tt, V2) -> U22(isList(activate(V2)))
   U22(tt) -> tt
   U31(tt) -> tt
   U41(tt, V2) -> U42(isNeList(activate(V2)))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isList(activate(V2)))
   U52(tt) -> tt
   U61(tt) -> tt
   U71(tt, P) -> U72(isPal(activate(P)))
   U72(tt) -> tt
   U81(tt) -> tt
   isList(V) -> U11(isNeList(activate(V)))
   isList(n__nil) -> tt
   isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
   isNeList(V) -> U31(isQid(activate(V)))
   isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
   isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
   isNePal(V) -> U61(isQid(activate(V)))
   isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
   isPal(V) -> U81(isNePal(activate(V)))
   isPal(n__nil) -> tt
   isQid(n__a) -> tt
   isQid(n__e) -> tt
   isQid(n__i) -> tt
   isQid(n__o) -> tt
   isQid(n__u) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(X1, X2)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(25) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(26)
Obligation:
TRS:
Rules:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X
U11(tt) -> tt
U21(tt, V2) -> U22(isList(activate(V2)))
U22(tt) -> tt
U31(tt) -> tt
U41(tt, V2) -> U42(isNeList(activate(V2)))
U42(tt) -> tt
U51(tt, V2) -> U52(isList(activate(V2)))
U52(tt) -> tt
U61(tt) -> tt
U71(tt, P) -> U72(isPal(activate(P)))
U72(tt) -> tt
U81(tt) -> tt
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil) -> tt
isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil) -> tt
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
__(X1, X2) -> n____(X1, X2)
a -> n__a
e -> n__e
i -> n__i
o -> n__o
u -> n__u
activate(n__nil) -> nil
activate(n____(X1, X2)) -> __(X1, X2)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__o) -> o
activate(n__u) -> u
activate(X) -> X

Types:
__ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
U11 :: tt -> tt
tt :: tt
U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U22 :: tt -> tt
isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
U31 :: tt -> tt
U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U42 :: tt -> tt
isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U52 :: tt -> tt
U61 :: tt -> tt
U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U72 :: tt -> tt
isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U81 :: tt -> tt
n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_tt2_0 :: tt
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u

----------------------------------------

(27) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
__, isList, isNeList, isPal, isNePal

They will be analysed ascendingly in the following order:
isList = isNeList
isPal = isNePal

----------------------------------------

(28)
Obligation:
TRS:
Rules:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X
U11(tt) -> tt
U21(tt, V2) -> U22(isList(activate(V2)))
U22(tt) -> tt
U31(tt) -> tt
U41(tt, V2) -> U42(isNeList(activate(V2)))
U42(tt) -> tt
U51(tt, V2) -> U52(isList(activate(V2)))
U52(tt) -> tt
U61(tt) -> tt
U71(tt, P) -> U72(isPal(activate(P)))
U72(tt) -> tt
U81(tt) -> tt
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil) -> tt
isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil) -> tt
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
__(X1, X2) -> n____(X1, X2)
a -> n__a
e -> n__e
i -> n__i
o -> n__o
u -> n__u
activate(n__nil) -> nil
activate(n____(X1, X2)) -> __(X1, X2)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__o) -> o
activate(n__u) -> u
activate(X) -> X

Types:
__ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
U11 :: tt -> tt
tt :: tt
U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U22 :: tt -> tt
isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
U31 :: tt -> tt
U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U42 :: tt -> tt
isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U52 :: tt -> tt
U61 :: tt -> tt
U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U72 :: tt -> tt
isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U81 :: tt -> tt
n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_tt2_0 :: tt
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u


Generator Equations:
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil)


The following defined symbols remain to be analysed:
__, isList, isNeList, isPal, isNePal

They will be analysed ascendingly in the following order:
isList = isNeList
isPal = isNePal

----------------------------------------

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n707_0)) -> *4_0, rt in Omega(n707_0)

Induction Base:
isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0))

Induction Step:
isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n707_0, 1))) ->_R^Omega(1)
U51(isNeList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n707_0))), activate(n__nil)) ->_R^Omega(1)
U51(isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n707_0)), activate(n__nil)) ->_IH
U51(*4_0, activate(n__nil)) ->_R^Omega(1)
U51(*4_0, n__nil)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(30)
Complex Obligation (BEST)

----------------------------------------

(31)
Obligation:
Proved the lower bound n^1 for the following obligation:

TRS:
Rules:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X
U11(tt) -> tt
U21(tt, V2) -> U22(isList(activate(V2)))
U22(tt) -> tt
U31(tt) -> tt
U41(tt, V2) -> U42(isNeList(activate(V2)))
U42(tt) -> tt
U51(tt, V2) -> U52(isList(activate(V2)))
U52(tt) -> tt
U61(tt) -> tt
U71(tt, P) -> U72(isPal(activate(P)))
U72(tt) -> tt
U81(tt) -> tt
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil) -> tt
isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil) -> tt
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
__(X1, X2) -> n____(X1, X2)
a -> n__a
e -> n__e
i -> n__i
o -> n__o
u -> n__u
activate(n__nil) -> nil
activate(n____(X1, X2)) -> __(X1, X2)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__o) -> o
activate(n__u) -> u
activate(X) -> X

Types:
__ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
U11 :: tt -> tt
tt :: tt
U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U22 :: tt -> tt
isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
U31 :: tt -> tt
U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U42 :: tt -> tt
isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U52 :: tt -> tt
U61 :: tt -> tt
U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U72 :: tt -> tt
isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U81 :: tt -> tt
n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_tt2_0 :: tt
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u


Generator Equations:
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil)


The following defined symbols remain to be analysed:
isNeList, isList

They will be analysed ascendingly in the following order:
isList = isNeList

----------------------------------------

(32) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(33)
BOUNDS(n^1, INF)

----------------------------------------

(34)
Obligation:
TRS:
Rules:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X
U11(tt) -> tt
U21(tt, V2) -> U22(isList(activate(V2)))
U22(tt) -> tt
U31(tt) -> tt
U41(tt, V2) -> U42(isNeList(activate(V2)))
U42(tt) -> tt
U51(tt, V2) -> U52(isList(activate(V2)))
U52(tt) -> tt
U61(tt) -> tt
U71(tt, P) -> U72(isPal(activate(P)))
U72(tt) -> tt
U81(tt) -> tt
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil) -> tt
isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil) -> tt
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
__(X1, X2) -> n____(X1, X2)
a -> n__a
e -> n__e
i -> n__i
o -> n__o
u -> n__u
activate(n__nil) -> nil
activate(n____(X1, X2)) -> __(X1, X2)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__o) -> o
activate(n__u) -> u
activate(X) -> X

Types:
__ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
U11 :: tt -> tt
tt :: tt
U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U22 :: tt -> tt
isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
U31 :: tt -> tt
U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U42 :: tt -> tt
isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U52 :: tt -> tt
U61 :: tt -> tt
U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U72 :: tt -> tt
isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U81 :: tt -> tt
n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_tt2_0 :: tt
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u


Lemmas:
isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n707_0)) -> *4_0, rt in Omega(n707_0)


Generator Equations:
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil)


The following defined symbols remain to be analysed:
isList

They will be analysed ascendingly in the following order:
isList = isNeList

----------------------------------------

(35) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n17483_0)) -> tt, rt in Omega(1 + n17483_0)

Induction Base:
isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1)
tt

Induction Step:
isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n17483_0, 1))) ->_R^Omega(1)
U21(isList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n17483_0))), activate(n__nil)) ->_R^Omega(1)
U21(isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n17483_0)), activate(n__nil)) ->_IH
U21(tt, activate(n__nil)) ->_R^Omega(1)
U21(tt, n__nil) ->_R^Omega(1)
U22(isList(activate(n__nil))) ->_R^Omega(1)
U22(isList(n__nil)) ->_R^Omega(1)
U22(tt) ->_R^Omega(1)
tt

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(36)
Obligation:
TRS:
Rules:
__(__(X, Y), Z) -> __(X, __(Y, Z))
__(X, nil) -> X
__(nil, X) -> X
U11(tt) -> tt
U21(tt, V2) -> U22(isList(activate(V2)))
U22(tt) -> tt
U31(tt) -> tt
U41(tt, V2) -> U42(isNeList(activate(V2)))
U42(tt) -> tt
U51(tt, V2) -> U52(isList(activate(V2)))
U52(tt) -> tt
U61(tt) -> tt
U71(tt, P) -> U72(isPal(activate(P)))
U72(tt) -> tt
U81(tt) -> tt
isList(V) -> U11(isNeList(activate(V)))
isList(n__nil) -> tt
isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2))
isNeList(V) -> U31(isQid(activate(V)))
isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2))
isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2))
isNePal(V) -> U61(isQid(activate(V)))
isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P))
isPal(V) -> U81(isNePal(activate(V)))
isPal(n__nil) -> tt
isQid(n__a) -> tt
isQid(n__e) -> tt
isQid(n__i) -> tt
isQid(n__o) -> tt
isQid(n__u) -> tt
nil -> n__nil
__(X1, X2) -> n____(X1, X2)
a -> n__a
e -> n__e
i -> n__i
o -> n__o
u -> n__u
activate(n__nil) -> nil
activate(n____(X1, X2)) -> __(X1, X2)
activate(n__a) -> a
activate(n__e) -> e
activate(n__i) -> i
activate(n__o) -> o
activate(n__u) -> u
activate(X) -> X

Types:
__ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
U11 :: tt -> tt
tt :: tt
U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U22 :: tt -> tt
isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
U31 :: tt -> tt
U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U42 :: tt -> tt
isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U52 :: tt -> tt
U61 :: tt -> tt
U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U72 :: tt -> tt
isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
U81 :: tt -> tt
n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u
isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt
n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u
hole_tt2_0 :: tt
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u


Lemmas:
isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n707_0)) -> *4_0, rt in Omega(n707_0)
isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n17483_0)) -> tt, rt in Omega(1 + n17483_0)


Generator Equations:
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil
gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil)


The following defined symbols remain to be analysed:
isNeList

They will be analysed ascendingly in the following order:
isList = isNeList