376.15/291.51 WORST_CASE(Omega(n^1), ?) 378.16/292.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 378.16/292.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 378.16/292.03 378.16/292.03 378.16/292.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 378.16/292.03 378.16/292.03 (0) CpxTRS 378.16/292.03 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 378.16/292.03 (2) CpxTRS 378.16/292.03 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 378.16/292.03 (4) typed CpxTrs 378.16/292.03 (5) OrderProof [LOWER BOUND(ID), 0 ms] 378.16/292.03 (6) typed CpxTrs 378.16/292.03 (7) RewriteLemmaProof [LOWER BOUND(ID), 641 ms] 378.16/292.03 (8) BEST 378.16/292.03 (9) proven lower bound 378.16/292.03 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 378.16/292.03 (11) BOUNDS(n^1, INF) 378.16/292.03 (12) typed CpxTrs 378.16/292.03 (13) RewriteLemmaProof [LOWER BOUND(ID), 286 ms] 378.16/292.03 (14) BOUNDS(1, INF) 378.16/292.03 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (0) 378.16/292.03 Obligation: 378.16/292.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 378.16/292.03 378.16/292.03 378.16/292.03 The TRS R consists of the following rules: 378.16/292.03 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 S is empty. 378.16/292.03 Rewrite Strategy: FULL 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 378.16/292.03 Renamed function symbols to avoid clashes with predefined symbol. 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (2) 378.16/292.03 Obligation: 378.16/292.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 378.16/292.03 378.16/292.03 378.16/292.03 The TRS R consists of the following rules: 378.16/292.03 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 S is empty. 378.16/292.03 Rewrite Strategy: FULL 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 378.16/292.03 Infered types. 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (4) 378.16/292.03 Obligation: 378.16/292.03 TRS: 378.16/292.03 Rules: 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 Types: 378.16/292.03 not :: or -> or 378.16/292.03 and :: or -> or -> or 378.16/292.03 or :: or -> or -> or 378.16/292.03 hole_or1_0 :: or 378.16/292.03 gen_or2_0 :: Nat -> or 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (5) OrderProof (LOWER BOUND(ID)) 378.16/292.03 Heuristically decided to analyse the following defined symbols: 378.16/292.03 not, and 378.16/292.03 378.16/292.03 They will be analysed ascendingly in the following order: 378.16/292.03 and < not 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (6) 378.16/292.03 Obligation: 378.16/292.03 TRS: 378.16/292.03 Rules: 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 Types: 378.16/292.03 not :: or -> or 378.16/292.03 and :: or -> or -> or 378.16/292.03 or :: or -> or -> or 378.16/292.03 hole_or1_0 :: or 378.16/292.03 gen_or2_0 :: Nat -> or 378.16/292.03 378.16/292.03 378.16/292.03 Generator Equations: 378.16/292.03 gen_or2_0(0) <=> hole_or1_0 378.16/292.03 gen_or2_0(+(x, 1)) <=> or(hole_or1_0, gen_or2_0(x)) 378.16/292.03 378.16/292.03 378.16/292.03 The following defined symbols remain to be analysed: 378.16/292.03 and, not 378.16/292.03 378.16/292.03 They will be analysed ascendingly in the following order: 378.16/292.03 and < not 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (7) RewriteLemmaProof (LOWER BOUND(ID)) 378.16/292.03 Proved the following rewrite lemma: 378.16/292.03 and(gen_or2_0(a), gen_or2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) 378.16/292.03 378.16/292.03 Induction Base: 378.16/292.03 and(gen_or2_0(a), gen_or2_0(+(1, 0))) 378.16/292.03 378.16/292.03 Induction Step: 378.16/292.03 and(gen_or2_0(a), gen_or2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1) 378.16/292.03 or(and(gen_or2_0(a), hole_or1_0), and(gen_or2_0(a), gen_or2_0(+(1, n4_0)))) ->_IH 378.16/292.03 or(and(gen_or2_0(a), hole_or1_0), *3_0) 378.16/292.03 378.16/292.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (8) 378.16/292.03 Complex Obligation (BEST) 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (9) 378.16/292.03 Obligation: 378.16/292.03 Proved the lower bound n^1 for the following obligation: 378.16/292.03 378.16/292.03 TRS: 378.16/292.03 Rules: 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 Types: 378.16/292.03 not :: or -> or 378.16/292.03 and :: or -> or -> or 378.16/292.03 or :: or -> or -> or 378.16/292.03 hole_or1_0 :: or 378.16/292.03 gen_or2_0 :: Nat -> or 378.16/292.03 378.16/292.03 378.16/292.03 Generator Equations: 378.16/292.03 gen_or2_0(0) <=> hole_or1_0 378.16/292.03 gen_or2_0(+(x, 1)) <=> or(hole_or1_0, gen_or2_0(x)) 378.16/292.03 378.16/292.03 378.16/292.03 The following defined symbols remain to be analysed: 378.16/292.03 and, not 378.16/292.03 378.16/292.03 They will be analysed ascendingly in the following order: 378.16/292.03 and < not 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (10) LowerBoundPropagationProof (FINISHED) 378.16/292.03 Propagated lower bound. 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (11) 378.16/292.03 BOUNDS(n^1, INF) 378.16/292.03 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (12) 378.16/292.03 Obligation: 378.16/292.03 TRS: 378.16/292.03 Rules: 378.16/292.03 not(and(x, y)) -> or(not(x), not(y)) 378.16/292.03 not(or(x, y)) -> and(not(x), not(y)) 378.16/292.03 and(x, or(y, z)) -> or(and(x, y), and(x, z)) 378.16/292.03 378.16/292.03 Types: 378.16/292.03 not :: or -> or 378.16/292.03 and :: or -> or -> or 378.16/292.03 or :: or -> or -> or 378.16/292.03 hole_or1_0 :: or 378.16/292.03 gen_or2_0 :: Nat -> or 378.16/292.03 378.16/292.03 378.16/292.03 Lemmas: 378.16/292.03 and(gen_or2_0(a), gen_or2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0) 378.16/292.03 378.16/292.03 378.16/292.03 Generator Equations: 378.16/292.03 gen_or2_0(0) <=> hole_or1_0 378.16/292.03 gen_or2_0(+(x, 1)) <=> or(hole_or1_0, gen_or2_0(x)) 378.16/292.03 378.16/292.03 378.16/292.03 The following defined symbols remain to be analysed: 378.16/292.03 not 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (13) RewriteLemmaProof (LOWER BOUND(ID)) 378.16/292.03 Proved the following rewrite lemma: 378.16/292.03 not(gen_or2_0(+(1, n3893_0))) -> *3_0, rt in Omega(n3893_0) 378.16/292.03 378.16/292.03 Induction Base: 378.16/292.03 not(gen_or2_0(+(1, 0))) 378.16/292.03 378.16/292.03 Induction Step: 378.16/292.03 not(gen_or2_0(+(1, +(n3893_0, 1)))) ->_R^Omega(1) 378.16/292.03 and(not(hole_or1_0), not(gen_or2_0(+(1, n3893_0)))) ->_IH 378.16/292.03 and(not(hole_or1_0), *3_0) 378.16/292.03 378.16/292.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 378.16/292.03 ---------------------------------------- 378.16/292.03 378.16/292.03 (14) 378.16/292.03 BOUNDS(1, INF) 378.16/292.08 EOF