1134.87/291.50 WORST_CASE(Omega(n^1), ?) 1134.87/291.51 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1134.87/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1134.87/291.51 1134.87/291.51 1134.87/291.51 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1134.87/291.51 1134.87/291.51 (0) CpxRelTRS 1134.87/291.51 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 146 ms] 1134.87/291.51 (2) CpxRelTRS 1134.87/291.51 (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1134.87/291.51 (4) CpxRelTRS 1134.87/291.51 (5) SlicingProof [LOWER BOUND(ID), 0 ms] 1134.87/291.51 (6) CpxRelTRS 1134.87/291.51 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1134.87/291.51 (8) typed CpxTrs 1134.87/291.51 (9) OrderProof [LOWER BOUND(ID), 0 ms] 1134.87/291.51 (10) typed CpxTrs 1134.87/291.51 (11) RewriteLemmaProof [LOWER BOUND(ID), 1411 ms] 1134.87/291.51 (12) BEST 1134.87/291.51 (13) proven lower bound 1134.87/291.51 (14) LowerBoundPropagationProof [FINISHED, 0 ms] 1134.87/291.51 (15) BOUNDS(n^1, INF) 1134.87/291.51 (16) typed CpxTrs 1134.87/291.51 (17) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 1134.87/291.51 (18) BOUNDS(1, INF) 1134.87/291.51 1134.87/291.51 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (0) 1134.87/291.51 Obligation: 1134.87/291.51 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1134.87/291.51 1134.87/291.51 1134.87/291.51 The TRS R consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets(Cons(x, xs)) -> subsets[Ite][True][Let](Cons(x, xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil, Nil) 1134.87/291.51 mapconsapp(x', Cons(x, xs), rest) -> Cons(Cons(x', x), mapconsapp(x', xs, rest)) 1134.87/291.51 mapconsapp(x, Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(x, xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 1134.87/291.51 The (relative) TRS S consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets[Ite][True][Let](Cons(x, xs), subs) -> mapconsapp(x, subs, subs) 1134.87/291.51 1134.87/291.51 Rewrite Strategy: INNERMOST 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 1134.87/291.51 proved termination of relative rules 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (2) 1134.87/291.51 Obligation: 1134.87/291.51 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1134.87/291.51 1134.87/291.51 1134.87/291.51 The TRS R consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets(Cons(x, xs)) -> subsets[Ite][True][Let](Cons(x, xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil, Nil) 1134.87/291.51 mapconsapp(x', Cons(x, xs), rest) -> Cons(Cons(x', x), mapconsapp(x', xs, rest)) 1134.87/291.51 mapconsapp(x, Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(x, xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 1134.87/291.51 The (relative) TRS S consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets[Ite][True][Let](Cons(x, xs), subs) -> mapconsapp(x, subs, subs) 1134.87/291.51 1134.87/291.51 Rewrite Strategy: INNERMOST 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (3) RenamingProof (BOTH BOUNDS(ID, ID)) 1134.87/291.51 Renamed function symbols to avoid clashes with predefined symbol. 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (4) 1134.87/291.51 Obligation: 1134.87/291.51 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1134.87/291.51 1134.87/291.51 1134.87/291.51 The TRS R consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets(Cons(x, xs)) -> subsets[Ite][True][Let](Cons(x, xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil, Nil) 1134.87/291.51 mapconsapp(x', Cons(x, xs), rest) -> Cons(Cons(x', x), mapconsapp(x', xs, rest)) 1134.87/291.51 mapconsapp(x, Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(x, xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 1134.87/291.51 The (relative) TRS S consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets[Ite][True][Let](Cons(x, xs), subs) -> mapconsapp(x, subs, subs) 1134.87/291.51 1134.87/291.51 Rewrite Strategy: INNERMOST 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (5) SlicingProof (LOWER BOUND(ID)) 1134.87/291.51 Sliced the following arguments: 1134.87/291.51 Cons/0 1134.87/291.51 mapconsapp/0 1134.87/291.51 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (6) 1134.87/291.51 Obligation: 1134.87/291.51 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 1134.87/291.51 1134.87/291.51 1134.87/291.51 The TRS R consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets(Cons(xs)) -> subsets[Ite][True][Let](Cons(xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil) 1134.87/291.51 mapconsapp(Cons(xs), rest) -> Cons(mapconsapp(xs, rest)) 1134.87/291.51 mapconsapp(Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 1134.87/291.51 The (relative) TRS S consists of the following rules: 1134.87/291.51 1134.87/291.51 subsets[Ite][True][Let](Cons(xs), subs) -> mapconsapp(subs, subs) 1134.87/291.51 1134.87/291.51 Rewrite Strategy: INNERMOST 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1134.87/291.51 Infered types. 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (8) 1134.87/291.51 Obligation: 1134.87/291.51 Innermost TRS: 1134.87/291.51 Rules: 1134.87/291.51 subsets(Cons(xs)) -> subsets[Ite][True][Let](Cons(xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil) 1134.87/291.51 mapconsapp(Cons(xs), rest) -> Cons(mapconsapp(xs, rest)) 1134.87/291.51 mapconsapp(Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 subsets[Ite][True][Let](Cons(xs), subs) -> mapconsapp(subs, subs) 1134.87/291.51 1134.87/291.51 Types: 1134.87/291.51 subsets :: Cons:Nil -> Cons:Nil 1134.87/291.51 Cons :: Cons:Nil -> Cons:Nil 1134.87/291.51 subsets[Ite][True][Let] :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 Nil :: Cons:Nil 1134.87/291.51 mapconsapp :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 notEmpty :: Cons:Nil -> True:False 1134.87/291.51 True :: True:False 1134.87/291.51 False :: True:False 1134.87/291.51 goal :: Cons:Nil -> Cons:Nil 1134.87/291.51 hole_Cons:Nil1_0 :: Cons:Nil 1134.87/291.51 hole_True:False2_0 :: True:False 1134.87/291.51 gen_Cons:Nil3_0 :: Nat -> Cons:Nil 1134.87/291.51 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (9) OrderProof (LOWER BOUND(ID)) 1134.87/291.51 Heuristically decided to analyse the following defined symbols: 1134.87/291.51 subsets, mapconsapp 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (10) 1134.87/291.51 Obligation: 1134.87/291.51 Innermost TRS: 1134.87/291.51 Rules: 1134.87/291.51 subsets(Cons(xs)) -> subsets[Ite][True][Let](Cons(xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil) 1134.87/291.51 mapconsapp(Cons(xs), rest) -> Cons(mapconsapp(xs, rest)) 1134.87/291.51 mapconsapp(Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 subsets[Ite][True][Let](Cons(xs), subs) -> mapconsapp(subs, subs) 1134.87/291.51 1134.87/291.51 Types: 1134.87/291.51 subsets :: Cons:Nil -> Cons:Nil 1134.87/291.51 Cons :: Cons:Nil -> Cons:Nil 1134.87/291.51 subsets[Ite][True][Let] :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 Nil :: Cons:Nil 1134.87/291.51 mapconsapp :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 notEmpty :: Cons:Nil -> True:False 1134.87/291.51 True :: True:False 1134.87/291.51 False :: True:False 1134.87/291.51 goal :: Cons:Nil -> Cons:Nil 1134.87/291.51 hole_Cons:Nil1_0 :: Cons:Nil 1134.87/291.51 hole_True:False2_0 :: True:False 1134.87/291.51 gen_Cons:Nil3_0 :: Nat -> Cons:Nil 1134.87/291.51 1134.87/291.51 1134.87/291.51 Generator Equations: 1134.87/291.51 gen_Cons:Nil3_0(0) <=> Nil 1134.87/291.51 gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x)) 1134.87/291.51 1134.87/291.51 1134.87/291.51 The following defined symbols remain to be analysed: 1134.87/291.51 subsets, mapconsapp 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (11) RewriteLemmaProof (LOWER BOUND(ID)) 1134.87/291.51 Proved the following rewrite lemma: 1134.87/291.51 subsets(gen_Cons:Nil3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0) 1134.87/291.51 1134.87/291.51 Induction Base: 1134.87/291.51 subsets(gen_Cons:Nil3_0(+(1, 0))) 1134.87/291.51 1134.87/291.51 Induction Step: 1134.87/291.51 subsets(gen_Cons:Nil3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 1134.87/291.51 subsets[Ite][True][Let](Cons(gen_Cons:Nil3_0(+(1, n5_0))), subsets(gen_Cons:Nil3_0(+(1, n5_0)))) ->_IH 1134.87/291.51 subsets[Ite][True][Let](Cons(gen_Cons:Nil3_0(+(1, n5_0))), *4_0) 1134.87/291.51 1134.87/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (12) 1134.87/291.51 Complex Obligation (BEST) 1134.87/291.51 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (13) 1134.87/291.51 Obligation: 1134.87/291.51 Proved the lower bound n^1 for the following obligation: 1134.87/291.51 1134.87/291.51 Innermost TRS: 1134.87/291.51 Rules: 1134.87/291.51 subsets(Cons(xs)) -> subsets[Ite][True][Let](Cons(xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil) 1134.87/291.51 mapconsapp(Cons(xs), rest) -> Cons(mapconsapp(xs, rest)) 1134.87/291.51 mapconsapp(Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 subsets[Ite][True][Let](Cons(xs), subs) -> mapconsapp(subs, subs) 1134.87/291.51 1134.87/291.51 Types: 1134.87/291.51 subsets :: Cons:Nil -> Cons:Nil 1134.87/291.51 Cons :: Cons:Nil -> Cons:Nil 1134.87/291.51 subsets[Ite][True][Let] :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 Nil :: Cons:Nil 1134.87/291.51 mapconsapp :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 notEmpty :: Cons:Nil -> True:False 1134.87/291.51 True :: True:False 1134.87/291.51 False :: True:False 1134.87/291.51 goal :: Cons:Nil -> Cons:Nil 1134.87/291.51 hole_Cons:Nil1_0 :: Cons:Nil 1134.87/291.51 hole_True:False2_0 :: True:False 1134.87/291.51 gen_Cons:Nil3_0 :: Nat -> Cons:Nil 1134.87/291.51 1134.87/291.51 1134.87/291.51 Generator Equations: 1134.87/291.51 gen_Cons:Nil3_0(0) <=> Nil 1134.87/291.51 gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x)) 1134.87/291.51 1134.87/291.51 1134.87/291.51 The following defined symbols remain to be analysed: 1134.87/291.51 subsets, mapconsapp 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (14) LowerBoundPropagationProof (FINISHED) 1134.87/291.51 Propagated lower bound. 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (15) 1134.87/291.51 BOUNDS(n^1, INF) 1134.87/291.51 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (16) 1134.87/291.51 Obligation: 1134.87/291.51 Innermost TRS: 1134.87/291.51 Rules: 1134.87/291.51 subsets(Cons(xs)) -> subsets[Ite][True][Let](Cons(xs), subsets(xs)) 1134.87/291.51 subsets(Nil) -> Cons(Nil) 1134.87/291.51 mapconsapp(Cons(xs), rest) -> Cons(mapconsapp(xs, rest)) 1134.87/291.51 mapconsapp(Nil, rest) -> rest 1134.87/291.51 notEmpty(Cons(xs)) -> True 1134.87/291.51 notEmpty(Nil) -> False 1134.87/291.51 goal(xs) -> subsets(xs) 1134.87/291.51 subsets[Ite][True][Let](Cons(xs), subs) -> mapconsapp(subs, subs) 1134.87/291.51 1134.87/291.51 Types: 1134.87/291.51 subsets :: Cons:Nil -> Cons:Nil 1134.87/291.51 Cons :: Cons:Nil -> Cons:Nil 1134.87/291.51 subsets[Ite][True][Let] :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 Nil :: Cons:Nil 1134.87/291.51 mapconsapp :: Cons:Nil -> Cons:Nil -> Cons:Nil 1134.87/291.51 notEmpty :: Cons:Nil -> True:False 1134.87/291.51 True :: True:False 1134.87/291.51 False :: True:False 1134.87/291.51 goal :: Cons:Nil -> Cons:Nil 1134.87/291.51 hole_Cons:Nil1_0 :: Cons:Nil 1134.87/291.51 hole_True:False2_0 :: True:False 1134.87/291.51 gen_Cons:Nil3_0 :: Nat -> Cons:Nil 1134.87/291.51 1134.87/291.51 1134.87/291.51 Lemmas: 1134.87/291.51 subsets(gen_Cons:Nil3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0) 1134.87/291.51 1134.87/291.51 1134.87/291.51 Generator Equations: 1134.87/291.51 gen_Cons:Nil3_0(0) <=> Nil 1134.87/291.51 gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x)) 1134.87/291.51 1134.87/291.51 1134.87/291.51 The following defined symbols remain to be analysed: 1134.87/291.51 mapconsapp 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1134.87/291.51 Proved the following rewrite lemma: 1134.87/291.51 mapconsapp(gen_Cons:Nil3_0(n3634_0), gen_Cons:Nil3_0(b)) -> gen_Cons:Nil3_0(+(n3634_0, b)), rt in Omega(1 + n3634_0) 1134.87/291.51 1134.87/291.51 Induction Base: 1134.87/291.51 mapconsapp(gen_Cons:Nil3_0(0), gen_Cons:Nil3_0(b)) ->_R^Omega(1) 1134.87/291.51 gen_Cons:Nil3_0(b) 1134.87/291.51 1134.87/291.51 Induction Step: 1134.87/291.51 mapconsapp(gen_Cons:Nil3_0(+(n3634_0, 1)), gen_Cons:Nil3_0(b)) ->_R^Omega(1) 1134.87/291.51 Cons(mapconsapp(gen_Cons:Nil3_0(n3634_0), gen_Cons:Nil3_0(b))) ->_IH 1134.87/291.51 Cons(gen_Cons:Nil3_0(+(b, c3635_0))) 1134.87/291.51 1134.87/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1134.87/291.51 ---------------------------------------- 1134.87/291.51 1134.87/291.51 (18) 1134.87/291.51 BOUNDS(1, INF) 1135.01/291.57 EOF