/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), ?) 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, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) typed CpxTrs (5) OrderProof [LOWER BOUND(ID), 0 ms] (6) typed CpxTrs (7) RewriteLemmaProof [LOWER BOUND(ID), 793 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs ---------------------------------------- (0) 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, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) 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, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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 -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt tt :: tt U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPalListKind :: 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 U13 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U21 :: tt -> 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 -> tt U22 :: tt -> 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 -> tt U23 :: tt -> 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 -> tt U24 :: tt -> 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 -> tt U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U26 :: tt -> tt U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U33 :: tt -> tt isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U41 :: tt -> 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 -> tt U42 :: tt -> 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 -> tt U43 :: tt -> 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 -> tt U44 :: tt -> 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 -> tt U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U46 :: tt -> tt U51 :: tt -> 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 -> tt U52 :: tt -> 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 -> tt U53 :: tt -> 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 -> tt U54 :: tt -> 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 -> tt U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U56 :: tt -> tt U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U63 :: tt -> tt U71 :: tt -> 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 -> tt U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U74 :: tt -> tt U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U83 :: tt -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U92 :: 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 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 ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: __, isPalListKind, isNeList, isList, isPal, isNePal They will be analysed ascendingly in the following order: isPalListKind < isNeList isPalListKind < isList isPalListKind < isPal isPalListKind < isNePal isNeList = isList isPal = isNePal ---------------------------------------- (6) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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 -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt tt :: tt U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPalListKind :: 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 U13 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U21 :: tt -> 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 -> tt U22 :: tt -> 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 -> tt U23 :: tt -> 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 -> tt U24 :: tt -> 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 -> tt U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U26 :: tt -> tt U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U33 :: tt -> tt isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U41 :: tt -> 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 -> tt U42 :: tt -> 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 -> tt U43 :: tt -> 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 -> tt U44 :: tt -> 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 -> tt U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U46 :: tt -> tt U51 :: tt -> 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 -> tt U52 :: tt -> 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 -> tt U53 :: tt -> 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 -> tt U54 :: tt -> 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 -> tt U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U56 :: tt -> tt U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U63 :: tt -> tt U71 :: tt -> 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 -> tt U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U74 :: tt -> tt U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U83 :: tt -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U92 :: 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 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: __, isPalListKind, isNeList, isList, isPal, isNePal They will be analysed ascendingly in the following order: isPalListKind < isNeList isPalListKind < isList isPalListKind < isPal isPalListKind < isNePal isNeList = isList isPal = isNePal ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> tt, rt in Omega(1 + n28_0) Induction Base: isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) tt Induction Step: isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n28_0, 1))) ->_R^Omega(1) U91(isPalListKind(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0))), activate(n__nil)) ->_R^Omega(1) U91(isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)), activate(n__nil)) ->_IH U91(tt, activate(n__nil)) ->_R^Omega(1) U91(tt, n__nil) ->_R^Omega(1) U92(isPalListKind(activate(n__nil))) ->_R^Omega(1) U92(isPalListKind(n__nil)) ->_R^Omega(1) U92(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). ---------------------------------------- (8) Complex Obligation (BEST) ---------------------------------------- (9) 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, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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 -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt tt :: tt U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPalListKind :: 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 U13 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U21 :: tt -> 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 -> tt U22 :: tt -> 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 -> tt U23 :: tt -> 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 -> tt U24 :: tt -> 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 -> tt U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U26 :: tt -> tt U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U33 :: tt -> tt isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U41 :: tt -> 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 -> tt U42 :: tt -> 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 -> tt U43 :: tt -> 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 -> tt U44 :: tt -> 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 -> tt U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U46 :: tt -> tt U51 :: tt -> 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 -> tt U52 :: tt -> 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 -> tt U53 :: tt -> 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 -> tt U54 :: tt -> 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 -> tt U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U56 :: tt -> tt U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U63 :: tt -> tt U71 :: tt -> 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 -> tt U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U74 :: tt -> tt U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U83 :: tt -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U92 :: 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 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: isPalListKind, isNeList, isList, isPal, isNePal They will be analysed ascendingly in the following order: isPalListKind < isNeList isPalListKind < isList isPalListKind < isPal isPalListKind < isNePal isNeList = isList isPal = isNePal ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) U12(tt, V) -> U13(isNeList(activate(V))) U13(tt) -> tt U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) U25(tt, V2) -> U26(isList(activate(V2))) U26(tt) -> tt U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) U32(tt, V) -> U33(isQid(activate(V))) U33(tt) -> tt U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) U45(tt, V2) -> U46(isNeList(activate(V2))) U46(tt) -> tt U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) U55(tt, V2) -> U56(isList(activate(V2))) U56(tt) -> tt U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) U62(tt, V) -> U63(isQid(activate(V))) U63(tt) -> tt U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) U72(tt, P) -> U73(isPal(activate(P)), activate(P)) U73(tt, P) -> U74(isPalListKind(activate(P))) U74(tt) -> tt U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) U82(tt, V) -> U83(isNePal(activate(V))) U83(tt) -> tt U91(tt, V2) -> U92(isPalListKind(activate(V2))) U92(tt) -> tt isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 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 -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt tt :: tt U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPalListKind :: 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 U13 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U21 :: tt -> 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 -> tt U22 :: tt -> 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 -> tt U23 :: tt -> 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 -> tt U24 :: tt -> 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 -> tt U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U26 :: tt -> tt U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U33 :: tt -> tt isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U41 :: tt -> 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 -> tt U42 :: tt -> 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 -> tt U43 :: tt -> 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 -> tt U44 :: tt -> 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 -> tt U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U46 :: tt -> tt U51 :: tt -> 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 -> tt U52 :: tt -> 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 -> tt U53 :: tt -> 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 -> tt U54 :: tt -> 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 -> tt U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U56 :: tt -> tt U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U63 :: tt -> tt U71 :: tt -> 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 -> tt U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U74 :: tt -> tt U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U83 :: tt -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U92 :: 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 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: isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> tt, rt in Omega(1 + n28_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: isNePal, isNeList, isList, isPal They will be analysed ascendingly in the following order: isNeList = isList isPal = isNePal