1022.98/291.51 WORST_CASE(Omega(n^1), ?) 1022.98/291.52 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1022.98/291.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1022.98/291.52 1022.98/291.52 1022.98/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1022.98/291.52 1022.98/291.52 (0) CpxTRS 1022.98/291.52 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1022.98/291.52 (2) CpxTRS 1022.98/291.52 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1022.98/291.52 (4) typed CpxTrs 1022.98/291.52 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1022.98/291.52 (6) typed CpxTrs 1022.98/291.52 (7) RewriteLemmaProof [LOWER BOUND(ID), 507 ms] 1022.98/291.52 (8) proven lower bound 1022.98/291.52 (9) LowerBoundPropagationProof [FINISHED, 0 ms] 1022.98/291.52 (10) BOUNDS(n^1, INF) 1022.98/291.52 1022.98/291.52 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (0) 1022.98/291.52 Obligation: 1022.98/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1022.98/291.52 1022.98/291.52 1022.98/291.52 The TRS R consists of the following rules: 1022.98/291.52 1022.98/291.52 f(x, a(b(y))) -> f(a(a(b(x))), y) 1022.98/291.52 f(a(x), y) -> f(x, a(y)) 1022.98/291.52 f(b(x), y) -> f(x, b(y)) 1022.98/291.52 1022.98/291.52 S is empty. 1022.98/291.52 Rewrite Strategy: INNERMOST 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1022.98/291.52 Renamed function symbols to avoid clashes with predefined symbol. 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (2) 1022.98/291.52 Obligation: 1022.98/291.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1022.98/291.52 1022.98/291.52 1022.98/291.52 The TRS R consists of the following rules: 1022.98/291.52 1022.98/291.52 f(x, a(b(y))) -> f(a(a(b(x))), y) 1022.98/291.52 f(a(x), y) -> f(x, a(y)) 1022.98/291.52 f(b(x), y) -> f(x, b(y)) 1022.98/291.52 1022.98/291.52 S is empty. 1022.98/291.52 Rewrite Strategy: INNERMOST 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1022.98/291.52 Infered types. 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (4) 1022.98/291.52 Obligation: 1022.98/291.52 Innermost TRS: 1022.98/291.52 Rules: 1022.98/291.52 f(x, a(b(y))) -> f(a(a(b(x))), y) 1022.98/291.52 f(a(x), y) -> f(x, a(y)) 1022.98/291.52 f(b(x), y) -> f(x, b(y)) 1022.98/291.52 1022.98/291.52 Types: 1022.98/291.52 f :: b:a -> b:a -> f 1022.98/291.52 a :: b:a -> b:a 1022.98/291.52 b :: b:a -> b:a 1022.98/291.52 hole_f1_0 :: f 1022.98/291.52 hole_b:a2_0 :: b:a 1022.98/291.52 gen_b:a3_0 :: Nat -> b:a 1022.98/291.52 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (5) OrderProof (LOWER BOUND(ID)) 1022.98/291.52 Heuristically decided to analyse the following defined symbols: 1022.98/291.52 f 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (6) 1022.98/291.52 Obligation: 1022.98/291.52 Innermost TRS: 1022.98/291.52 Rules: 1022.98/291.52 f(x, a(b(y))) -> f(a(a(b(x))), y) 1022.98/291.52 f(a(x), y) -> f(x, a(y)) 1022.98/291.52 f(b(x), y) -> f(x, b(y)) 1022.98/291.52 1022.98/291.52 Types: 1022.98/291.52 f :: b:a -> b:a -> f 1022.98/291.52 a :: b:a -> b:a 1022.98/291.52 b :: b:a -> b:a 1022.98/291.52 hole_f1_0 :: f 1022.98/291.52 hole_b:a2_0 :: b:a 1022.98/291.52 gen_b:a3_0 :: Nat -> b:a 1022.98/291.52 1022.98/291.52 1022.98/291.52 Generator Equations: 1022.98/291.52 gen_b:a3_0(0) <=> hole_b:a2_0 1022.98/291.52 gen_b:a3_0(+(x, 1)) <=> a(gen_b:a3_0(x)) 1022.98/291.52 1022.98/291.52 1022.98/291.52 The following defined symbols remain to be analysed: 1022.98/291.52 f 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1022.98/291.52 Proved the following rewrite lemma: 1022.98/291.52 f(gen_b:a3_0(+(1, n5_0)), gen_b:a3_0(b)) -> *4_0, rt in Omega(n5_0) 1022.98/291.52 1022.98/291.52 Induction Base: 1022.98/291.52 f(gen_b:a3_0(+(1, 0)), gen_b:a3_0(b)) 1022.98/291.52 1022.98/291.52 Induction Step: 1022.98/291.52 f(gen_b:a3_0(+(1, +(n5_0, 1))), gen_b:a3_0(b)) ->_R^Omega(1) 1022.98/291.52 f(gen_b:a3_0(+(1, n5_0)), a(gen_b:a3_0(b))) ->_IH 1022.98/291.52 *4_0 1022.98/291.52 1022.98/291.52 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (8) 1022.98/291.52 Obligation: 1022.98/291.52 Proved the lower bound n^1 for the following obligation: 1022.98/291.52 1022.98/291.52 Innermost TRS: 1022.98/291.52 Rules: 1022.98/291.52 f(x, a(b(y))) -> f(a(a(b(x))), y) 1022.98/291.52 f(a(x), y) -> f(x, a(y)) 1022.98/291.52 f(b(x), y) -> f(x, b(y)) 1022.98/291.52 1022.98/291.52 Types: 1022.98/291.52 f :: b:a -> b:a -> f 1022.98/291.52 a :: b:a -> b:a 1022.98/291.52 b :: b:a -> b:a 1022.98/291.52 hole_f1_0 :: f 1022.98/291.52 hole_b:a2_0 :: b:a 1022.98/291.52 gen_b:a3_0 :: Nat -> b:a 1022.98/291.52 1022.98/291.52 1022.98/291.52 Generator Equations: 1022.98/291.52 gen_b:a3_0(0) <=> hole_b:a2_0 1022.98/291.52 gen_b:a3_0(+(x, 1)) <=> a(gen_b:a3_0(x)) 1022.98/291.52 1022.98/291.52 1022.98/291.52 The following defined symbols remain to be analysed: 1022.98/291.52 f 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (9) LowerBoundPropagationProof (FINISHED) 1022.98/291.52 Propagated lower bound. 1022.98/291.52 ---------------------------------------- 1022.98/291.52 1022.98/291.52 (10) 1022.98/291.52 BOUNDS(n^1, INF) 1023.27/291.59 EOF