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