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