/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) typed CpxTrs (5) OrderProof [LOWER BOUND(ID), 0 ms] (6) typed CpxTrs (7) RewriteLemmaProof [LOWER BOUND(ID), 1180 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: Innermost TRS: Rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) Types: a__2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons1 :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd mark :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd a__from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd s :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd 2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd hole_cons:cons1:s:from:2nd1_0 :: cons:cons1:s:from:2nd gen_cons:cons1:s:from:2nd2_0 :: Nat -> cons:cons1:s:from:2nd ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: a__2nd, mark, a__from They will be analysed ascendingly in the following order: a__2nd = mark a__2nd = a__from mark = a__from ---------------------------------------- (6) Obligation: Innermost TRS: Rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) Types: a__2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons1 :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd mark :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd a__from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd s :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd 2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd hole_cons:cons1:s:from:2nd1_0 :: cons:cons1:s:from:2nd gen_cons:cons1:s:from:2nd2_0 :: Nat -> cons:cons1:s:from:2nd Generator Equations: gen_cons:cons1:s:from:2nd2_0(0) <=> hole_cons:cons1:s:from:2nd1_0 gen_cons:cons1:s:from:2nd2_0(+(x, 1)) <=> cons1(hole_cons:cons1:s:from:2nd1_0, gen_cons:cons1:s:from:2nd2_0(x)) The following defined symbols remain to be analysed: mark, a__2nd, a__from They will be analysed ascendingly in the following order: a__2nd = mark a__2nd = a__from mark = a__from ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_cons:cons1:s:from:2nd2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) Induction Base: mark(gen_cons:cons1:s:from:2nd2_0(+(1, 0))) Induction Step: mark(gen_cons:cons1:s:from:2nd2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1) cons1(mark(hole_cons:cons1:s:from:2nd1_0), mark(gen_cons:cons1:s:from:2nd2_0(+(1, n4_0)))) ->_IH cons1(mark(hole_cons:cons1:s:from:2nd1_0), *3_0) 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: Innermost TRS: Rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) Types: a__2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons1 :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd mark :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd a__from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd s :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd 2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd hole_cons:cons1:s:from:2nd1_0 :: cons:cons1:s:from:2nd gen_cons:cons1:s:from:2nd2_0 :: Nat -> cons:cons1:s:from:2nd Generator Equations: gen_cons:cons1:s:from:2nd2_0(0) <=> hole_cons:cons1:s:from:2nd1_0 gen_cons:cons1:s:from:2nd2_0(+(x, 1)) <=> cons1(hole_cons:cons1:s:from:2nd1_0, gen_cons:cons1:s:from:2nd2_0(x)) The following defined symbols remain to be analysed: mark, a__2nd, a__from They will be analysed ascendingly in the following order: a__2nd = mark a__2nd = a__from mark = a__from ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: Innermost TRS: Rules: a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) a__from(X) -> cons(mark(X), from(s(X))) mark(2nd(X)) -> a__2nd(mark(X)) mark(from(X)) -> a__from(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) a__2nd(X) -> 2nd(X) a__from(X) -> from(X) Types: a__2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons1 :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd cons :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd mark :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd a__from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd from :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd s :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd 2nd :: cons:cons1:s:from:2nd -> cons:cons1:s:from:2nd hole_cons:cons1:s:from:2nd1_0 :: cons:cons1:s:from:2nd gen_cons:cons1:s:from:2nd2_0 :: Nat -> cons:cons1:s:from:2nd Lemmas: mark(gen_cons:cons1:s:from:2nd2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) Generator Equations: gen_cons:cons1:s:from:2nd2_0(0) <=> hole_cons:cons1:s:from:2nd1_0 gen_cons:cons1:s:from:2nd2_0(+(x, 1)) <=> cons1(hole_cons:cons1:s:from:2nd1_0, gen_cons:cons1:s:from:2nd2_0(x)) The following defined symbols remain to be analysed: a__2nd, a__from They will be analysed ascendingly in the following order: a__2nd = mark a__2nd = a__from mark = a__from