344.77/291.52 WORST_CASE(Omega(n^1), ?) 344.77/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 344.77/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 344.77/291.53 344.77/291.53 344.77/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 344.77/291.53 344.77/291.53 (0) CpxRelTRS 344.77/291.53 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 254 ms] 344.77/291.53 (2) CpxRelTRS 344.77/291.53 (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 344.77/291.53 (4) CpxRelTRS 344.77/291.53 (5) SlicingProof [LOWER BOUND(ID), 0 ms] 344.77/291.53 (6) CpxRelTRS 344.77/291.53 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 344.77/291.53 (8) typed CpxTrs 344.77/291.53 (9) OrderProof [LOWER BOUND(ID), 0 ms] 344.77/291.53 (10) typed CpxTrs 344.77/291.53 (11) RewriteLemmaProof [LOWER BOUND(ID), 228 ms] 344.77/291.53 (12) BEST 344.77/291.53 (13) proven lower bound 344.77/291.53 (14) LowerBoundPropagationProof [FINISHED, 0 ms] 344.77/291.53 (15) BOUNDS(n^1, INF) 344.77/291.53 (16) typed CpxTrs 344.77/291.53 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (0) 344.77/291.53 Obligation: 344.77/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 344.77/291.53 344.77/291.53 344.77/291.53 The TRS R consists of the following rules: 344.77/291.53 344.77/291.53 rw(Val(n), c) -> Op(Val(n), rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val(n)) -> Val(n) 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val(n)) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val(n)) -> Val(n) 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 344.77/291.53 The (relative) TRS S consists of the following rules: 344.77/291.53 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](Op(x, y), c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](ab, c, a1, b1) -> rw[Let][Let][Let](c, a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](c, a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Rewrite Strategy: INNERMOST 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 344.77/291.53 proved termination of relative rules 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (2) 344.77/291.53 Obligation: 344.77/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 344.77/291.53 344.77/291.53 344.77/291.53 The TRS R consists of the following rules: 344.77/291.53 344.77/291.53 rw(Val(n), c) -> Op(Val(n), rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val(n)) -> Val(n) 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val(n)) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val(n)) -> Val(n) 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 344.77/291.53 The (relative) TRS S consists of the following rules: 344.77/291.53 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](Op(x, y), c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](ab, c, a1, b1) -> rw[Let][Let][Let](c, a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](c, a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Rewrite Strategy: INNERMOST 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (3) RenamingProof (BOTH BOUNDS(ID, ID)) 344.77/291.53 Renamed function symbols to avoid clashes with predefined symbol. 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (4) 344.77/291.53 Obligation: 344.77/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 344.77/291.53 344.77/291.53 344.77/291.53 The TRS R consists of the following rules: 344.77/291.53 344.77/291.53 rw(Val(n), c) -> Op(Val(n), rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val(n)) -> Val(n) 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val(n)) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val(n)) -> Val(n) 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 344.77/291.53 The (relative) TRS S consists of the following rules: 344.77/291.53 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](Op(x, y), c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](ab, c, a1, b1) -> rw[Let][Let][Let](c, a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](c, a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Rewrite Strategy: INNERMOST 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (5) SlicingProof (LOWER BOUND(ID)) 344.77/291.53 Sliced the following arguments: 344.77/291.53 Val/0 344.77/291.53 rw[Let][Let]/0 344.77/291.53 rw[Let][Let][Let]/0 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (6) 344.77/291.53 Obligation: 344.77/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 344.77/291.53 344.77/291.53 344.77/291.53 The TRS R consists of the following rules: 344.77/291.53 344.77/291.53 rw(Val, c) -> Op(Val, rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val) -> Val 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val) -> Val 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 344.77/291.53 The (relative) TRS S consists of the following rules: 344.77/291.53 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](c, a1, b1) -> rw[Let][Let][Let](a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Rewrite Strategy: INNERMOST 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 344.77/291.53 Infered types. 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (8) 344.77/291.53 Obligation: 344.77/291.53 Innermost TRS: 344.77/291.53 Rules: 344.77/291.53 rw(Val, c) -> Op(Val, rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val) -> Val 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val) -> Val 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](c, a1, b1) -> rw[Let][Let][Let](a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Types: 344.77/291.53 rw :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 Val :: Val:Op 344.77/291.53 Op :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 rewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 second :: Val:Op -> Val:Op 344.77/291.53 isOp :: Val:Op -> False:True 344.77/291.53 False :: False:True 344.77/291.53 True :: False:True 344.77/291.53 first :: Val:Op -> Val:Op 344.77/291.53 assrewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 rw[Let][Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 hole_Val:Op1_0 :: Val:Op 344.77/291.53 hole_False:True2_0 :: False:True 344.77/291.53 gen_Val:Op3_0 :: Nat -> Val:Op 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (9) OrderProof (LOWER BOUND(ID)) 344.77/291.53 Heuristically decided to analyse the following defined symbols: 344.77/291.53 rw, rewrite 344.77/291.53 344.77/291.53 They will be analysed ascendingly in the following order: 344.77/291.53 rw = rewrite 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (10) 344.77/291.53 Obligation: 344.77/291.53 Innermost TRS: 344.77/291.53 Rules: 344.77/291.53 rw(Val, c) -> Op(Val, rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val) -> Val 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val) -> Val 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](c, a1, b1) -> rw[Let][Let][Let](a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Types: 344.77/291.53 rw :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 Val :: Val:Op 344.77/291.53 Op :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 rewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 second :: Val:Op -> Val:Op 344.77/291.53 isOp :: Val:Op -> False:True 344.77/291.53 False :: False:True 344.77/291.53 True :: False:True 344.77/291.53 first :: Val:Op -> Val:Op 344.77/291.53 assrewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 rw[Let][Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 hole_Val:Op1_0 :: Val:Op 344.77/291.53 hole_False:True2_0 :: False:True 344.77/291.53 gen_Val:Op3_0 :: Nat -> Val:Op 344.77/291.53 344.77/291.53 344.77/291.53 Generator Equations: 344.77/291.53 gen_Val:Op3_0(0) <=> Val 344.77/291.53 gen_Val:Op3_0(+(x, 1)) <=> Op(Val, gen_Val:Op3_0(x)) 344.77/291.53 344.77/291.53 344.77/291.53 The following defined symbols remain to be analysed: 344.77/291.53 rewrite, rw 344.77/291.53 344.77/291.53 They will be analysed ascendingly in the following order: 344.77/291.53 rw = rewrite 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (11) RewriteLemmaProof (LOWER BOUND(ID)) 344.77/291.53 Proved the following rewrite lemma: 344.77/291.53 rewrite(gen_Val:Op3_0(n5_0)) -> gen_Val:Op3_0(n5_0), rt in Omega(1 + n5_0) 344.77/291.53 344.77/291.53 Induction Base: 344.77/291.53 rewrite(gen_Val:Op3_0(0)) ->_R^Omega(1) 344.77/291.53 Val 344.77/291.53 344.77/291.53 Induction Step: 344.77/291.53 rewrite(gen_Val:Op3_0(+(n5_0, 1))) ->_R^Omega(1) 344.77/291.53 rw(Val, gen_Val:Op3_0(n5_0)) ->_R^Omega(1) 344.77/291.53 Op(Val, rewrite(gen_Val:Op3_0(n5_0))) ->_IH 344.77/291.53 Op(Val, gen_Val:Op3_0(c6_0)) 344.77/291.53 344.77/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (12) 344.77/291.53 Complex Obligation (BEST) 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (13) 344.77/291.53 Obligation: 344.77/291.53 Proved the lower bound n^1 for the following obligation: 344.77/291.53 344.77/291.53 Innermost TRS: 344.77/291.53 Rules: 344.77/291.53 rw(Val, c) -> Op(Val, rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val) -> Val 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val) -> Val 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](c, a1, b1) -> rw[Let][Let][Let](a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Types: 344.77/291.53 rw :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 Val :: Val:Op 344.77/291.53 Op :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 rewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 second :: Val:Op -> Val:Op 344.77/291.53 isOp :: Val:Op -> False:True 344.77/291.53 False :: False:True 344.77/291.53 True :: False:True 344.77/291.53 first :: Val:Op -> Val:Op 344.77/291.53 assrewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 rw[Let][Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 hole_Val:Op1_0 :: Val:Op 344.77/291.53 hole_False:True2_0 :: False:True 344.77/291.53 gen_Val:Op3_0 :: Nat -> Val:Op 344.77/291.53 344.77/291.53 344.77/291.53 Generator Equations: 344.77/291.53 gen_Val:Op3_0(0) <=> Val 344.77/291.53 gen_Val:Op3_0(+(x, 1)) <=> Op(Val, gen_Val:Op3_0(x)) 344.77/291.53 344.77/291.53 344.77/291.53 The following defined symbols remain to be analysed: 344.77/291.53 rewrite, rw 344.77/291.53 344.77/291.53 They will be analysed ascendingly in the following order: 344.77/291.53 rw = rewrite 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (14) LowerBoundPropagationProof (FINISHED) 344.77/291.53 Propagated lower bound. 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (15) 344.77/291.53 BOUNDS(n^1, INF) 344.77/291.53 344.77/291.53 ---------------------------------------- 344.77/291.53 344.77/291.53 (16) 344.77/291.53 Obligation: 344.77/291.53 Innermost TRS: 344.77/291.53 Rules: 344.77/291.53 rw(Val, c) -> Op(Val, rewrite(c)) 344.77/291.53 rewrite(Op(x, y)) -> rw(x, y) 344.77/291.53 rw(Op(x, y), c) -> rw[Let](Op(x, y), c, rewrite(x)) 344.77/291.53 rewrite(Val) -> Val 344.77/291.53 second(Op(x, y)) -> y 344.77/291.53 isOp(Val) -> False 344.77/291.53 isOp(Op(x, y)) -> True 344.77/291.53 first(Val) -> Val 344.77/291.53 first(Op(x, y)) -> x 344.77/291.53 assrewrite(exp) -> rewrite(exp) 344.77/291.53 rw[Let](Op(x, y), c, a1) -> rw[Let][Let](c, a1, rewrite(y)) 344.77/291.53 rw[Let][Let](c, a1, b1) -> rw[Let][Let][Let](a1, b1, rewrite(c)) 344.77/291.53 rw[Let][Let][Let](a1, b1, c1) -> rw(a1, Op(b1, c1)) 344.77/291.53 344.77/291.53 Types: 344.77/291.53 rw :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 Val :: Val:Op 344.77/291.53 Op :: Val:Op -> Val:Op -> Val:Op 344.77/291.53 rewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 second :: Val:Op -> Val:Op 344.77/291.53 isOp :: Val:Op -> False:True 344.77/291.53 False :: False:True 344.77/291.53 True :: False:True 344.77/291.53 first :: Val:Op -> Val:Op 344.77/291.53 assrewrite :: Val:Op -> Val:Op 344.77/291.53 rw[Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 rw[Let][Let][Let] :: Val:Op -> Val:Op -> Val:Op -> Val:Op 344.77/291.53 hole_Val:Op1_0 :: Val:Op 344.77/291.53 hole_False:True2_0 :: False:True 344.77/291.53 gen_Val:Op3_0 :: Nat -> Val:Op 344.77/291.53 344.77/291.53 344.77/291.53 Lemmas: 344.77/291.53 rewrite(gen_Val:Op3_0(n5_0)) -> gen_Val:Op3_0(n5_0), rt in Omega(1 + n5_0) 344.77/291.53 344.77/291.53 344.77/291.53 Generator Equations: 344.77/291.53 gen_Val:Op3_0(0) <=> Val 344.77/291.53 gen_Val:Op3_0(+(x, 1)) <=> Op(Val, gen_Val:Op3_0(x)) 344.77/291.53 344.77/291.53 344.77/291.53 The following defined symbols remain to be analysed: 344.77/291.53 rw 344.77/291.53 344.77/291.53 They will be analysed ascendingly in the following order: 344.77/291.53 rw = rewrite 344.88/291.57 EOF