/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), ?) 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^2, 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), 1426 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 4201 ms] (14) BEST (15) proven lower bound (16) LowerBoundPropagationProof [FINISHED, 0 ms] (17) BOUNDS(n^2, INF) (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 808 ms] (20) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) 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^2, INF). The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) 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 and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: __, and, activate, isList, isNeList, isNePal, isPal They will be analysed ascendingly in the following order: __ < activate and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (6) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u Generator Equations: gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) The following defined symbols remain to be analysed: __, and, activate, isList, isNeList, isNePal, isPal They will be analysed ascendingly in the following order: __ < activate and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) Induction Base: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) Induction Step: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n27_0, 1))) ->_R^Omega(1) __(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)), activate(n__nil)) ->_IH __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(c28_0), activate(n__nil)) ->_R^Omega(1) __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), n__nil) ->_R^Omega(1) n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), n__nil) 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 and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u Generator Equations: gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) The following defined symbols remain to be analysed: activate, and, isList, isNeList, isNePal, isPal They will be analysed ascendingly in the following order: and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (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 and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u Lemmas: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) Generator Equations: gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) The following defined symbols remain to be analysed: isList, and, isNeList, isNePal, isPal They will be analysed ascendingly in the following order: and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)) -> tt, rt in Omega(1 + n65578_0 + n65578_0^2) Induction Base: isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) tt Induction Step: isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n65578_0, 1))) ->_R^Omega(1) and(isList(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0))), n__isList(activate(n__nil))) ->_L^Omega(1 + n65578_0) and(isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)), n__isList(activate(n__nil))) ->_IH and(tt, n__isList(activate(n__nil))) ->_L^Omega(1) and(tt, n__isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0))) ->_R^Omega(1) activate(n__isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0))) ->_R^Omega(1) isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) tt We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). ---------------------------------------- (14) Complex Obligation (BEST) ---------------------------------------- (15) Obligation: Proved the lower bound n^2 for the following obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u Lemmas: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) Generator Equations: gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) The following defined symbols remain to be analysed: isList, and, isNeList, isNePal, isPal They will be analysed ascendingly in the following order: and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (16) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (17) BOUNDS(n^2, INF) ---------------------------------------- (18) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X and(tt, X) -> activate(X) isList(V) -> isNeList(activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) isNeList(V) -> isQid(activate(V)) isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) isNePal(V) -> isQid(activate(V)) isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) isPal(V) -> isNePal(activate(V)) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isList(X) -> n__isList(X) isNeList(X) -> n__isNeList(X) isPal(X) -> n__isPal(X) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__isList(X)) -> isList(X) activate(n__isNeList(X)) -> isNeList(X) activate(n__isPal(X)) -> isPal(X) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u Lemmas: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)) -> tt, rt in Omega(1 + n65578_0 + n65578_0^2) Generator Equations: gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) The following defined symbols remain to be analysed: isNeList, and, activate, isNePal, isPal They will be analysed ascendingly in the following order: and = activate and = isList and = isNeList and = isNePal and = isPal activate = isList activate = isNeList activate = isNePal activate = isPal isList = isNeList isList = isNePal isList = isPal isNeList = isNePal isNeList = isPal isNePal = isPal ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), rt in Omega(1 + n153552_0) Induction Base: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) Induction Step: activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n153552_0, 1))) ->_R^Omega(1) __(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0)), activate(n__nil)) ->_IH __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(c153553_0), activate(n__nil)) ->_R^Omega(1) __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), n__nil) ->_R^Omega(1) n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), n__nil) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (20) BOUNDS(1, INF)