317.89/291.65 WORST_CASE(Omega(n^2), ?) 318.09/291.73 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 318.09/291.73 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 318.09/291.73 318.09/291.73 318.09/291.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 318.09/291.73 318.09/291.73 (0) CpxTRS 318.09/291.73 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 318.09/291.73 (2) CpxTRS 318.09/291.73 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 318.09/291.73 (4) typed CpxTrs 318.09/291.73 (5) OrderProof [LOWER BOUND(ID), 0 ms] 318.09/291.73 (6) typed CpxTrs 318.09/291.73 (7) RewriteLemmaProof [LOWER BOUND(ID), 661 ms] 318.09/291.73 (8) BEST 318.09/291.73 (9) proven lower bound 318.09/291.73 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 318.09/291.73 (11) BOUNDS(n^1, INF) 318.09/291.73 (12) typed CpxTrs 318.09/291.73 (13) RewriteLemmaProof [LOWER BOUND(ID), 270 ms] 318.09/291.73 (14) BEST 318.09/291.73 (15) proven lower bound 318.09/291.73 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 318.09/291.73 (17) BOUNDS(n^2, INF) 318.09/291.73 (18) typed CpxTrs 318.09/291.73 318.09/291.73 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (0) 318.09/291.73 Obligation: 318.09/291.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 318.09/291.73 318.09/291.73 318.09/291.73 The TRS R consists of the following rules: 318.09/291.73 318.09/291.73 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.73 __(X, nil) -> X 318.09/291.73 __(nil, X) -> X 318.09/291.73 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.73 U13(tt) -> tt 318.09/291.73 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.73 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.73 U26(tt) -> tt 318.09/291.73 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.73 U33(tt) -> tt 318.09/291.73 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.73 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.73 U46(tt) -> tt 318.09/291.73 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.73 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.73 U56(tt) -> tt 318.09/291.73 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.73 U63(tt) -> tt 318.09/291.73 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.73 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.73 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.73 U74(tt) -> tt 318.09/291.73 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.73 U83(tt) -> tt 318.09/291.73 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.73 U92(tt) -> tt 318.09/291.73 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isList(n__nil) -> tt 318.09/291.73 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.73 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isPal(n__nil) -> tt 318.09/291.73 isPalListKind(n__a) -> tt 318.09/291.73 isPalListKind(n__e) -> tt 318.09/291.73 isPalListKind(n__i) -> tt 318.09/291.73 isPalListKind(n__nil) -> tt 318.09/291.73 isPalListKind(n__o) -> tt 318.09/291.73 isPalListKind(n__u) -> tt 318.09/291.73 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.73 isQid(n__a) -> tt 318.09/291.73 isQid(n__e) -> tt 318.09/291.73 isQid(n__i) -> tt 318.09/291.73 isQid(n__o) -> tt 318.09/291.73 isQid(n__u) -> tt 318.09/291.73 nil -> n__nil 318.09/291.73 __(X1, X2) -> n____(X1, X2) 318.09/291.73 a -> n__a 318.09/291.73 e -> n__e 318.09/291.73 i -> n__i 318.09/291.73 o -> n__o 318.09/291.73 u -> n__u 318.09/291.73 activate(n__nil) -> nil 318.09/291.73 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.73 activate(n__a) -> a 318.09/291.73 activate(n__e) -> e 318.09/291.73 activate(n__i) -> i 318.09/291.73 activate(n__o) -> o 318.09/291.73 activate(n__u) -> u 318.09/291.73 activate(X) -> X 318.09/291.73 318.09/291.73 S is empty. 318.09/291.73 Rewrite Strategy: FULL 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 318.09/291.73 Renamed function symbols to avoid clashes with predefined symbol. 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (2) 318.09/291.73 Obligation: 318.09/291.73 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 318.09/291.73 318.09/291.73 318.09/291.73 The TRS R consists of the following rules: 318.09/291.73 318.09/291.73 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.73 __(X, nil) -> X 318.09/291.73 __(nil, X) -> X 318.09/291.73 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.73 U13(tt) -> tt 318.09/291.73 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.73 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.73 U26(tt) -> tt 318.09/291.73 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.73 U33(tt) -> tt 318.09/291.73 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.73 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.73 U46(tt) -> tt 318.09/291.73 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.73 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.73 U56(tt) -> tt 318.09/291.73 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.73 U63(tt) -> tt 318.09/291.73 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.73 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.73 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.73 U74(tt) -> tt 318.09/291.73 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.73 U83(tt) -> tt 318.09/291.73 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.73 U92(tt) -> tt 318.09/291.73 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isList(n__nil) -> tt 318.09/291.73 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.73 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isPal(n__nil) -> tt 318.09/291.73 isPalListKind(n__a) -> tt 318.09/291.73 isPalListKind(n__e) -> tt 318.09/291.73 isPalListKind(n__i) -> tt 318.09/291.73 isPalListKind(n__nil) -> tt 318.09/291.73 isPalListKind(n__o) -> tt 318.09/291.73 isPalListKind(n__u) -> tt 318.09/291.73 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.73 isQid(n__a) -> tt 318.09/291.73 isQid(n__e) -> tt 318.09/291.73 isQid(n__i) -> tt 318.09/291.73 isQid(n__o) -> tt 318.09/291.73 isQid(n__u) -> tt 318.09/291.73 nil -> n__nil 318.09/291.73 __(X1, X2) -> n____(X1, X2) 318.09/291.73 a -> n__a 318.09/291.73 e -> n__e 318.09/291.73 i -> n__i 318.09/291.73 o -> n__o 318.09/291.73 u -> n__u 318.09/291.73 activate(n__nil) -> nil 318.09/291.73 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.73 activate(n__a) -> a 318.09/291.73 activate(n__e) -> e 318.09/291.73 activate(n__i) -> i 318.09/291.73 activate(n__o) -> o 318.09/291.73 activate(n__u) -> u 318.09/291.73 activate(X) -> X 318.09/291.73 318.09/291.73 S is empty. 318.09/291.73 Rewrite Strategy: FULL 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 318.09/291.73 Infered types. 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (4) 318.09/291.73 Obligation: 318.09/291.73 TRS: 318.09/291.73 Rules: 318.09/291.73 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.73 __(X, nil) -> X 318.09/291.73 __(nil, X) -> X 318.09/291.73 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.73 U13(tt) -> tt 318.09/291.73 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.73 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.73 U26(tt) -> tt 318.09/291.73 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.73 U33(tt) -> tt 318.09/291.73 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.73 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.73 U46(tt) -> tt 318.09/291.73 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.73 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.73 U56(tt) -> tt 318.09/291.73 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.73 U63(tt) -> tt 318.09/291.73 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.73 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.73 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.73 U74(tt) -> tt 318.09/291.73 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.73 U83(tt) -> tt 318.09/291.73 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.73 U92(tt) -> tt 318.09/291.73 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isList(n__nil) -> tt 318.09/291.73 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.73 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isPal(n__nil) -> tt 318.09/291.73 isPalListKind(n__a) -> tt 318.09/291.73 isPalListKind(n__e) -> tt 318.09/291.73 isPalListKind(n__i) -> tt 318.09/291.73 isPalListKind(n__nil) -> tt 318.09/291.73 isPalListKind(n__o) -> tt 318.09/291.73 isPalListKind(n__u) -> tt 318.09/291.73 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.73 isQid(n__a) -> tt 318.09/291.73 isQid(n__e) -> tt 318.09/291.73 isQid(n__i) -> tt 318.09/291.73 isQid(n__o) -> tt 318.09/291.73 isQid(n__u) -> tt 318.09/291.73 nil -> n__nil 318.09/291.73 __(X1, X2) -> n____(X1, X2) 318.09/291.73 a -> n__a 318.09/291.73 e -> n__e 318.09/291.73 i -> n__i 318.09/291.73 o -> n__o 318.09/291.73 u -> n__u 318.09/291.73 activate(n__nil) -> nil 318.09/291.73 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.73 activate(n__a) -> a 318.09/291.73 activate(n__e) -> e 318.09/291.73 activate(n__i) -> i 318.09/291.73 activate(n__o) -> o 318.09/291.73 activate(n__u) -> u 318.09/291.73 activate(X) -> X 318.09/291.73 318.09/291.73 Types: 318.09/291.73 __ :: 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 318.09/291.73 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 tt :: tt 318.09/291.73 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 U13 :: tt -> tt 318.09/291.73 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U26 :: tt -> tt 318.09/291.73 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U33 :: tt -> tt 318.09/291.73 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U46 :: tt -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U56 :: tt -> tt 318.09/291.73 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U63 :: tt -> tt 318.09/291.73 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 318.09/291.73 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U74 :: tt -> tt 318.09/291.73 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U83 :: tt -> tt 318.09/291.73 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U92 :: tt -> tt 318.09/291.73 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 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 318.09/291.73 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 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 318.09/291.73 hole_tt2_0 :: tt 318.09/291.73 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 318.09/291.73 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (5) OrderProof (LOWER BOUND(ID)) 318.09/291.73 Heuristically decided to analyse the following defined symbols: 318.09/291.73 __, isPalListKind, activate, isNeList, isList, isPal, isNePal 318.09/291.73 318.09/291.73 They will be analysed ascendingly in the following order: 318.09/291.73 __ < activate 318.09/291.73 activate < isPalListKind 318.09/291.73 isPalListKind < isNeList 318.09/291.73 isPalListKind < isList 318.09/291.73 isPalListKind < isPal 318.09/291.73 isPalListKind < isNePal 318.09/291.73 activate < isNeList 318.09/291.73 activate < isList 318.09/291.73 activate < isPal 318.09/291.73 activate < isNePal 318.09/291.73 isNeList = isList 318.09/291.73 isPal = isNePal 318.09/291.73 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (6) 318.09/291.73 Obligation: 318.09/291.73 TRS: 318.09/291.73 Rules: 318.09/291.73 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.73 __(X, nil) -> X 318.09/291.73 __(nil, X) -> X 318.09/291.73 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.73 U13(tt) -> tt 318.09/291.73 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.73 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.73 U26(tt) -> tt 318.09/291.73 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.73 U33(tt) -> tt 318.09/291.73 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.73 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.73 U46(tt) -> tt 318.09/291.73 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.73 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.73 U56(tt) -> tt 318.09/291.73 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.73 U63(tt) -> tt 318.09/291.73 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.73 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.73 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.73 U74(tt) -> tt 318.09/291.73 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.73 U83(tt) -> tt 318.09/291.73 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.73 U92(tt) -> tt 318.09/291.73 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isList(n__nil) -> tt 318.09/291.73 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.73 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.73 isPal(n__nil) -> tt 318.09/291.73 isPalListKind(n__a) -> tt 318.09/291.73 isPalListKind(n__e) -> tt 318.09/291.73 isPalListKind(n__i) -> tt 318.09/291.73 isPalListKind(n__nil) -> tt 318.09/291.73 isPalListKind(n__o) -> tt 318.09/291.73 isPalListKind(n__u) -> tt 318.09/291.73 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.73 isQid(n__a) -> tt 318.09/291.73 isQid(n__e) -> tt 318.09/291.73 isQid(n__i) -> tt 318.09/291.73 isQid(n__o) -> tt 318.09/291.73 isQid(n__u) -> tt 318.09/291.73 nil -> n__nil 318.09/291.73 __(X1, X2) -> n____(X1, X2) 318.09/291.73 a -> n__a 318.09/291.73 e -> n__e 318.09/291.73 i -> n__i 318.09/291.73 o -> n__o 318.09/291.73 u -> n__u 318.09/291.73 activate(n__nil) -> nil 318.09/291.73 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.73 activate(n__a) -> a 318.09/291.73 activate(n__e) -> e 318.09/291.73 activate(n__i) -> i 318.09/291.73 activate(n__o) -> o 318.09/291.73 activate(n__u) -> u 318.09/291.73 activate(X) -> X 318.09/291.73 318.09/291.73 Types: 318.09/291.73 __ :: 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 318.09/291.73 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 tt :: tt 318.09/291.73 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 U13 :: tt -> tt 318.09/291.73 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U26 :: tt -> tt 318.09/291.73 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U33 :: tt -> tt 318.09/291.73 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U46 :: tt -> tt 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 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 318.09/291.73 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U56 :: tt -> tt 318.09/291.73 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U63 :: tt -> tt 318.09/291.73 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 318.09/291.73 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U74 :: tt -> tt 318.09/291.73 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U83 :: tt -> tt 318.09/291.73 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.73 U92 :: tt -> tt 318.09/291.73 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 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 318.09/291.73 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.73 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 318.09/291.73 hole_tt2_0 :: tt 318.09/291.73 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 318.09/291.73 318.09/291.73 318.09/291.73 Generator Equations: 318.09/291.73 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 318.09/291.73 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) 318.09/291.73 318.09/291.73 318.09/291.73 The following defined symbols remain to be analysed: 318.09/291.73 __, isPalListKind, activate, isNeList, isList, isPal, isNePal 318.09/291.73 318.09/291.73 They will be analysed ascendingly in the following order: 318.09/291.73 __ < activate 318.09/291.73 activate < isPalListKind 318.09/291.73 isPalListKind < isNeList 318.09/291.73 isPalListKind < isList 318.09/291.73 isPalListKind < isPal 318.09/291.73 isPalListKind < isNePal 318.09/291.73 activate < isNeList 318.09/291.73 activate < isList 318.09/291.73 activate < isPal 318.09/291.73 activate < isNePal 318.09/291.73 isNeList = isList 318.09/291.73 isPal = isNePal 318.09/291.73 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (7) RewriteLemmaProof (LOWER BOUND(ID)) 318.09/291.73 Proved the following rewrite lemma: 318.09/291.73 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 318.09/291.73 318.09/291.73 Induction Base: 318.09/291.73 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 318.09/291.73 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) 318.09/291.73 318.09/291.73 Induction Step: 318.09/291.73 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n28_0, 1))) ->_R^Omega(1) 318.09/291.73 __(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)), activate(n__nil)) ->_IH 318.09/291.73 __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(c29_0), activate(n__nil)) ->_R^Omega(1) 318.09/291.73 __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), n__nil) ->_R^Omega(1) 318.09/291.73 n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), n__nil) 318.09/291.73 318.09/291.73 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (8) 318.09/291.73 Complex Obligation (BEST) 318.09/291.73 318.09/291.73 ---------------------------------------- 318.09/291.73 318.09/291.73 (9) 318.09/291.73 Obligation: 318.09/291.73 Proved the lower bound n^1 for the following obligation: 318.09/291.73 318.09/291.73 TRS: 318.09/291.73 Rules: 318.09/291.73 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.73 __(X, nil) -> X 318.09/291.73 __(nil, X) -> X 318.09/291.73 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.73 U13(tt) -> tt 318.09/291.73 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.73 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.73 U26(tt) -> tt 318.09/291.73 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.73 U33(tt) -> tt 318.09/291.73 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.73 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.73 U46(tt) -> tt 318.09/291.73 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.73 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.73 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.73 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.73 U56(tt) -> tt 318.09/291.73 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.73 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.73 U63(tt) -> tt 318.09/291.73 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.73 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.73 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.73 U74(tt) -> tt 318.09/291.73 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.74 U83(tt) -> tt 318.09/291.74 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.74 U92(tt) -> tt 318.09/291.74 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isList(n__nil) -> tt 318.09/291.74 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.74 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isPal(n__nil) -> tt 318.09/291.74 isPalListKind(n__a) -> tt 318.09/291.74 isPalListKind(n__e) -> tt 318.09/291.74 isPalListKind(n__i) -> tt 318.09/291.74 isPalListKind(n__nil) -> tt 318.09/291.74 isPalListKind(n__o) -> tt 318.09/291.74 isPalListKind(n__u) -> tt 318.09/291.74 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.74 isQid(n__a) -> tt 318.09/291.74 isQid(n__e) -> tt 318.09/291.74 isQid(n__i) -> tt 318.09/291.74 isQid(n__o) -> tt 318.09/291.74 isQid(n__u) -> tt 318.09/291.74 nil -> n__nil 318.09/291.74 __(X1, X2) -> n____(X1, X2) 318.09/291.74 a -> n__a 318.09/291.74 e -> n__e 318.09/291.74 i -> n__i 318.09/291.74 o -> n__o 318.09/291.74 u -> n__u 318.09/291.74 activate(n__nil) -> nil 318.09/291.74 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.74 activate(n__a) -> a 318.09/291.74 activate(n__e) -> e 318.09/291.74 activate(n__i) -> i 318.09/291.74 activate(n__o) -> o 318.09/291.74 activate(n__u) -> u 318.09/291.74 activate(X) -> X 318.09/291.74 318.09/291.74 Types: 318.09/291.74 __ :: 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 318.09/291.74 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 tt :: tt 318.09/291.74 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 U13 :: tt -> tt 318.09/291.74 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U26 :: tt -> tt 318.09/291.74 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U33 :: tt -> tt 318.09/291.74 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U46 :: tt -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U56 :: tt -> tt 318.09/291.74 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U63 :: tt -> tt 318.09/291.74 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 318.09/291.74 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U74 :: tt -> tt 318.09/291.74 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U83 :: tt -> tt 318.09/291.74 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U92 :: tt -> tt 318.09/291.74 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 hole_tt2_0 :: tt 318.09/291.74 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 318.09/291.74 318.09/291.74 318.09/291.74 Generator Equations: 318.09/291.74 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 318.09/291.74 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) 318.09/291.74 318.09/291.74 318.09/291.74 The following defined symbols remain to be analysed: 318.09/291.74 activate, isPalListKind, isNeList, isList, isPal, isNePal 318.09/291.74 318.09/291.74 They will be analysed ascendingly in the following order: 318.09/291.74 activate < isPalListKind 318.09/291.74 isPalListKind < isNeList 318.09/291.74 isPalListKind < isList 318.09/291.74 isPalListKind < isPal 318.09/291.74 isPalListKind < isNePal 318.09/291.74 activate < isNeList 318.09/291.74 activate < isList 318.09/291.74 activate < isPal 318.09/291.74 activate < isNePal 318.09/291.74 isNeList = isList 318.09/291.74 isPal = isNePal 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (10) LowerBoundPropagationProof (FINISHED) 318.09/291.74 Propagated lower bound. 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (11) 318.09/291.74 BOUNDS(n^1, INF) 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (12) 318.09/291.74 Obligation: 318.09/291.74 TRS: 318.09/291.74 Rules: 318.09/291.74 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.74 __(X, nil) -> X 318.09/291.74 __(nil, X) -> X 318.09/291.74 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.74 U13(tt) -> tt 318.09/291.74 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.74 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.74 U26(tt) -> tt 318.09/291.74 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.74 U33(tt) -> tt 318.09/291.74 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.74 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.74 U46(tt) -> tt 318.09/291.74 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.74 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.74 U56(tt) -> tt 318.09/291.74 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.74 U63(tt) -> tt 318.09/291.74 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.74 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.74 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.74 U74(tt) -> tt 318.09/291.74 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.74 U83(tt) -> tt 318.09/291.74 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.74 U92(tt) -> tt 318.09/291.74 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isList(n__nil) -> tt 318.09/291.74 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.74 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isPal(n__nil) -> tt 318.09/291.74 isPalListKind(n__a) -> tt 318.09/291.74 isPalListKind(n__e) -> tt 318.09/291.74 isPalListKind(n__i) -> tt 318.09/291.74 isPalListKind(n__nil) -> tt 318.09/291.74 isPalListKind(n__o) -> tt 318.09/291.74 isPalListKind(n__u) -> tt 318.09/291.74 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.74 isQid(n__a) -> tt 318.09/291.74 isQid(n__e) -> tt 318.09/291.74 isQid(n__i) -> tt 318.09/291.74 isQid(n__o) -> tt 318.09/291.74 isQid(n__u) -> tt 318.09/291.74 nil -> n__nil 318.09/291.74 __(X1, X2) -> n____(X1, X2) 318.09/291.74 a -> n__a 318.09/291.74 e -> n__e 318.09/291.74 i -> n__i 318.09/291.74 o -> n__o 318.09/291.74 u -> n__u 318.09/291.74 activate(n__nil) -> nil 318.09/291.74 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.74 activate(n__a) -> a 318.09/291.74 activate(n__e) -> e 318.09/291.74 activate(n__i) -> i 318.09/291.74 activate(n__o) -> o 318.09/291.74 activate(n__u) -> u 318.09/291.74 activate(X) -> X 318.09/291.74 318.09/291.74 Types: 318.09/291.74 __ :: 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 318.09/291.74 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 tt :: tt 318.09/291.74 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 U13 :: tt -> tt 318.09/291.74 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U26 :: tt -> tt 318.09/291.74 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U33 :: tt -> tt 318.09/291.74 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U46 :: tt -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U56 :: tt -> tt 318.09/291.74 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U63 :: tt -> tt 318.09/291.74 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 318.09/291.74 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U74 :: tt -> tt 318.09/291.74 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U83 :: tt -> tt 318.09/291.74 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U92 :: tt -> tt 318.09/291.74 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 hole_tt2_0 :: tt 318.09/291.74 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 318.09/291.74 318.09/291.74 318.09/291.74 Lemmas: 318.09/291.74 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 318.09/291.74 318.09/291.74 318.09/291.74 Generator Equations: 318.09/291.74 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 318.09/291.74 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) 318.09/291.74 318.09/291.74 318.09/291.74 The following defined symbols remain to be analysed: 318.09/291.74 isPalListKind, isNeList, isList, isPal, isNePal 318.09/291.74 318.09/291.74 They will be analysed ascendingly in the following order: 318.09/291.74 isPalListKind < isNeList 318.09/291.74 isPalListKind < isList 318.09/291.74 isPalListKind < isPal 318.09/291.74 isPalListKind < isNePal 318.09/291.74 isNeList = isList 318.09/291.74 isPal = isNePal 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (13) RewriteLemmaProof (LOWER BOUND(ID)) 318.09/291.74 Proved the following rewrite lemma: 318.09/291.74 isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n10528_0)) -> tt, rt in Omega(1 + n10528_0 + n10528_0^2) 318.09/291.74 318.09/291.74 Induction Base: 318.09/291.74 isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 318.09/291.74 tt 318.09/291.74 318.09/291.74 Induction Step: 318.09/291.74 isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n10528_0, 1))) ->_R^Omega(1) 318.09/291.74 U91(isPalListKind(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n10528_0))), activate(n__nil)) ->_L^Omega(1 + n10528_0) 318.09/291.74 U91(isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n10528_0)), activate(n__nil)) ->_IH 318.09/291.74 U91(tt, activate(n__nil)) ->_L^Omega(1) 318.09/291.74 U91(tt, gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 318.09/291.74 U92(isPalListKind(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)))) ->_L^Omega(1) 318.09/291.74 U92(isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0))) ->_R^Omega(1) 318.09/291.74 U92(tt) ->_R^Omega(1) 318.09/291.74 tt 318.09/291.74 318.09/291.74 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (14) 318.09/291.74 Complex Obligation (BEST) 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (15) 318.09/291.74 Obligation: 318.09/291.74 Proved the lower bound n^2 for the following obligation: 318.09/291.74 318.09/291.74 TRS: 318.09/291.74 Rules: 318.09/291.74 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.74 __(X, nil) -> X 318.09/291.74 __(nil, X) -> X 318.09/291.74 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.74 U13(tt) -> tt 318.09/291.74 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.74 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.74 U26(tt) -> tt 318.09/291.74 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.74 U33(tt) -> tt 318.09/291.74 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.74 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.74 U46(tt) -> tt 318.09/291.74 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.74 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.74 U56(tt) -> tt 318.09/291.74 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.74 U63(tt) -> tt 318.09/291.74 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.74 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.74 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.74 U74(tt) -> tt 318.09/291.74 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.74 U83(tt) -> tt 318.09/291.74 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.74 U92(tt) -> tt 318.09/291.74 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isList(n__nil) -> tt 318.09/291.74 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.74 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isPal(n__nil) -> tt 318.09/291.74 isPalListKind(n__a) -> tt 318.09/291.74 isPalListKind(n__e) -> tt 318.09/291.74 isPalListKind(n__i) -> tt 318.09/291.74 isPalListKind(n__nil) -> tt 318.09/291.74 isPalListKind(n__o) -> tt 318.09/291.74 isPalListKind(n__u) -> tt 318.09/291.74 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.74 isQid(n__a) -> tt 318.09/291.74 isQid(n__e) -> tt 318.09/291.74 isQid(n__i) -> tt 318.09/291.74 isQid(n__o) -> tt 318.09/291.74 isQid(n__u) -> tt 318.09/291.74 nil -> n__nil 318.09/291.74 __(X1, X2) -> n____(X1, X2) 318.09/291.74 a -> n__a 318.09/291.74 e -> n__e 318.09/291.74 i -> n__i 318.09/291.74 o -> n__o 318.09/291.74 u -> n__u 318.09/291.74 activate(n__nil) -> nil 318.09/291.74 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.74 activate(n__a) -> a 318.09/291.74 activate(n__e) -> e 318.09/291.74 activate(n__i) -> i 318.09/291.74 activate(n__o) -> o 318.09/291.74 activate(n__u) -> u 318.09/291.74 activate(X) -> X 318.09/291.74 318.09/291.74 Types: 318.09/291.74 __ :: 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 318.09/291.74 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 tt :: tt 318.09/291.74 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 U13 :: tt -> tt 318.09/291.74 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U26 :: tt -> tt 318.09/291.74 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U33 :: tt -> tt 318.09/291.74 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U46 :: tt -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U56 :: tt -> tt 318.09/291.74 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U63 :: tt -> tt 318.09/291.74 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 318.09/291.74 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U74 :: tt -> tt 318.09/291.74 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U83 :: tt -> tt 318.09/291.74 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U92 :: tt -> tt 318.09/291.74 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 hole_tt2_0 :: tt 318.09/291.74 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 318.09/291.74 318.09/291.74 318.09/291.74 Lemmas: 318.09/291.74 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 318.09/291.74 318.09/291.74 318.09/291.74 Generator Equations: 318.09/291.74 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 318.09/291.74 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) 318.09/291.74 318.09/291.74 318.09/291.74 The following defined symbols remain to be analysed: 318.09/291.74 isPalListKind, isNeList, isList, isPal, isNePal 318.09/291.74 318.09/291.74 They will be analysed ascendingly in the following order: 318.09/291.74 isPalListKind < isNeList 318.09/291.74 isPalListKind < isList 318.09/291.74 isPalListKind < isPal 318.09/291.74 isPalListKind < isNePal 318.09/291.74 isNeList = isList 318.09/291.74 isPal = isNePal 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (16) LowerBoundPropagationProof (FINISHED) 318.09/291.74 Propagated lower bound. 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (17) 318.09/291.74 BOUNDS(n^2, INF) 318.09/291.74 318.09/291.74 ---------------------------------------- 318.09/291.74 318.09/291.74 (18) 318.09/291.74 Obligation: 318.09/291.74 TRS: 318.09/291.74 Rules: 318.09/291.74 __(__(X, Y), Z) -> __(X, __(Y, Z)) 318.09/291.74 __(X, nil) -> X 318.09/291.74 __(nil, X) -> X 318.09/291.74 U11(tt, V) -> U12(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U12(tt, V) -> U13(isNeList(activate(V))) 318.09/291.74 U13(tt) -> tt 318.09/291.74 U21(tt, V1, V2) -> U22(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U22(tt, V1, V2) -> U23(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U23(tt, V1, V2) -> U24(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U24(tt, V1, V2) -> U25(isList(activate(V1)), activate(V2)) 318.09/291.74 U25(tt, V2) -> U26(isList(activate(V2))) 318.09/291.74 U26(tt) -> tt 318.09/291.74 U31(tt, V) -> U32(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U32(tt, V) -> U33(isQid(activate(V))) 318.09/291.74 U33(tt) -> tt 318.09/291.74 U41(tt, V1, V2) -> U42(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U42(tt, V1, V2) -> U43(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U43(tt, V1, V2) -> U44(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U44(tt, V1, V2) -> U45(isList(activate(V1)), activate(V2)) 318.09/291.74 U45(tt, V2) -> U46(isNeList(activate(V2))) 318.09/291.74 U46(tt) -> tt 318.09/291.74 U51(tt, V1, V2) -> U52(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 U52(tt, V1, V2) -> U53(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U53(tt, V1, V2) -> U54(isPalListKind(activate(V2)), activate(V1), activate(V2)) 318.09/291.74 U54(tt, V1, V2) -> U55(isNeList(activate(V1)), activate(V2)) 318.09/291.74 U55(tt, V2) -> U56(isList(activate(V2))) 318.09/291.74 U56(tt) -> tt 318.09/291.74 U61(tt, V) -> U62(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U62(tt, V) -> U63(isQid(activate(V))) 318.09/291.74 U63(tt) -> tt 318.09/291.74 U71(tt, I, P) -> U72(isPalListKind(activate(I)), activate(P)) 318.09/291.74 U72(tt, P) -> U73(isPal(activate(P)), activate(P)) 318.09/291.74 U73(tt, P) -> U74(isPalListKind(activate(P))) 318.09/291.74 U74(tt) -> tt 318.09/291.74 U81(tt, V) -> U82(isPalListKind(activate(V)), activate(V)) 318.09/291.74 U82(tt, V) -> U83(isNePal(activate(V))) 318.09/291.74 U83(tt) -> tt 318.09/291.74 U91(tt, V2) -> U92(isPalListKind(activate(V2))) 318.09/291.74 U92(tt) -> tt 318.09/291.74 isList(V) -> U11(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isList(n__nil) -> tt 318.09/291.74 isList(n____(V1, V2)) -> U21(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNeList(n____(V1, V2)) -> U41(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNeList(n____(V1, V2)) -> U51(isPalListKind(activate(V1)), activate(V1), activate(V2)) 318.09/291.74 isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(I), activate(P)) 318.09/291.74 isPal(V) -> U81(isPalListKind(activate(V)), activate(V)) 318.09/291.74 isPal(n__nil) -> tt 318.09/291.74 isPalListKind(n__a) -> tt 318.09/291.74 isPalListKind(n__e) -> tt 318.09/291.74 isPalListKind(n__i) -> tt 318.09/291.74 isPalListKind(n__nil) -> tt 318.09/291.74 isPalListKind(n__o) -> tt 318.09/291.74 isPalListKind(n__u) -> tt 318.09/291.74 isPalListKind(n____(V1, V2)) -> U91(isPalListKind(activate(V1)), activate(V2)) 318.09/291.74 isQid(n__a) -> tt 318.09/291.74 isQid(n__e) -> tt 318.09/291.74 isQid(n__i) -> tt 318.09/291.74 isQid(n__o) -> tt 318.09/291.74 isQid(n__u) -> tt 318.09/291.74 nil -> n__nil 318.09/291.74 __(X1, X2) -> n____(X1, X2) 318.09/291.74 a -> n__a 318.09/291.74 e -> n__e 318.09/291.74 i -> n__i 318.09/291.74 o -> n__o 318.09/291.74 u -> n__u 318.09/291.74 activate(n__nil) -> nil 318.09/291.74 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 318.09/291.74 activate(n__a) -> a 318.09/291.74 activate(n__e) -> e 318.09/291.74 activate(n__i) -> i 318.09/291.74 activate(n__o) -> o 318.09/291.74 activate(n__u) -> u 318.09/291.74 activate(X) -> X 318.09/291.74 318.09/291.74 Types: 318.09/291.74 __ :: 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 318.09/291.74 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 U11 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 tt :: tt 318.09/291.74 U12 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPalListKind :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 U13 :: tt -> tt 318.09/291.74 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U25 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U26 :: tt -> tt 318.09/291.74 U31 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U32 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U33 :: tt -> tt 318.09/291.74 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U45 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U46 :: tt -> tt 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 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 318.09/291.74 U55 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U56 :: tt -> tt 318.09/291.74 U61 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U62 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U63 :: tt -> tt 318.09/291.74 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 318.09/291.74 U72 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U73 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U74 :: tt -> tt 318.09/291.74 U81 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U82 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U83 :: tt -> tt 318.09/291.74 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U91 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 318.09/291.74 U92 :: tt -> tt 318.09/291.74 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 318.09/291.74 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 318.09/291.74 hole_tt2_0 :: tt 318.09/291.74 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 318.09/291.74 318.09/291.74 318.09/291.74 Lemmas: 318.09/291.74 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 318.09/291.74 isPalListKind(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n10528_0)) -> tt, rt in Omega(1 + n10528_0 + n10528_0^2) 318.09/291.74 318.09/291.74 318.09/291.74 Generator Equations: 318.09/291.74 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 318.09/291.74 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) 318.09/291.74 318.09/291.74 318.09/291.74 The following defined symbols remain to be analysed: 318.09/291.74 isNePal, isNeList, isList, isPal 318.09/291.74 318.09/291.74 They will be analysed ascendingly in the following order: 318.09/291.74 isNeList = isList 318.09/291.74 isPal = isNePal 318.09/291.76 EOF