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