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