/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), 549 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), 1203 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), 4922 ms] (20) typed CpxTrs ---------------------------------------- (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 U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: __, isList, activate, isNeList, isPal, isNePal They will be analysed ascendingly in the following order: __ < activate activate < isList isList = isNeList activate < isNeList activate < isPal activate < isNePal isPal = isNePal ---------------------------------------- (6) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: __, isList, activate, isNeList, isPal, isNePal They will be analysed ascendingly in the following order: __ < activate activate < isList isList = isNeList activate < isNeList activate < isPal activate < isNePal isPal = isNePal ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: 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) Induction Base: activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) Induction Step: activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n28_0, 1))) ->_R^Omega(1) __(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)), activate(n__nil)) ->_IH __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(c29_0), activate(n__nil)) ->_R^Omega(1) __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), n__nil) ->_R^Omega(1) n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_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 U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: activate, isList, isNeList, isPal, isNePal They will be analysed ascendingly in the following order: activate < isList isList = isNeList activate < isNeList activate < isPal activate < isNePal isPal = isNePal ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Lemmas: 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) Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: isNePal, isList, isNeList, isPal They will be analysed ascendingly in the following order: isList = isNeList isPal = isNePal ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) Induction Base: isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) Induction Step: isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n9819_0, 1))) ->_R^Omega(1) U51(isNeList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0))), activate(n__nil)) ->_L^Omega(1 + n9819_0) U51(isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)), activate(n__nil)) ->_IH U51(*4_0, activate(n__nil)) ->_L^Omega(1) U51(*4_0, gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) 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 U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Lemmas: 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) Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: isNeList, isList They will be analysed ascendingly in the following order: isList = isNeList ---------------------------------------- (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 U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Lemmas: 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) isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: isList They will be analysed ascendingly in the following order: isList = isNeList ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)) -> tt, rt in Omega(1 + n25345_0 + n25345_0^2) Induction Base: isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) tt Induction Step: isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n25345_0, 1))) ->_R^Omega(1) U21(isList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0))), activate(n__nil)) ->_L^Omega(1 + n25345_0) U21(isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)), activate(n__nil)) ->_IH U21(tt, activate(n__nil)) ->_L^Omega(1) U21(tt, gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) U22(isList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)))) ->_L^Omega(1) U22(isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0))) ->_R^Omega(1) U22(tt) ->_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). ---------------------------------------- (20) Obligation: TRS: Rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt) -> tt U21(tt, V2) -> U22(isList(activate(V2))) U22(tt) -> tt U31(tt) -> tt U41(tt, V2) -> U42(isNeList(activate(V2))) U42(tt) -> tt U51(tt, V2) -> U52(isList(activate(V2))) U52(tt) -> tt U61(tt) -> tt U71(tt, P) -> U72(isPal(activate(P))) U72(tt) -> tt U81(tt) -> tt isList(V) -> U11(isNeList(activate(V))) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) isNeList(V) -> U31(isQid(activate(V))) isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) isNePal(V) -> U61(isQid(activate(V))) isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) isPal(V) -> U81(isNePal(activate(V))) isPal(n__nil) -> tt isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Types: __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u U11 :: tt -> tt tt :: tt U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U22 :: tt -> tt isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u U31 :: tt -> tt U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U42 :: tt -> tt isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U52 :: tt -> tt U61 :: tt -> tt U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U72 :: tt -> tt isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt U81 :: tt -> tt n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u hole_tt2_0 :: tt gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u Lemmas: 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) isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)) -> tt, rt in Omega(1 + n25345_0 + n25345_0^2) Generator Equations: gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) The following defined symbols remain to be analysed: isNeList They will be analysed ascendingly in the following order: isList = isNeList