20.99/7.00 WORST_CASE(Omega(n^1), O(n^1)) 20.99/7.01 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 20.99/7.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.99/7.01 20.99/7.01 20.99/7.01 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.99/7.01 20.99/7.01 (0) CpxTRS 20.99/7.01 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 20.99/7.01 (2) CpxTRS 20.99/7.01 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 20.99/7.01 (4) CpxTRS 20.99/7.01 (5) CpxTrsMatchBoundsProof [FINISHED, 1 ms] 20.99/7.01 (6) BOUNDS(1, n^1) 20.99/7.01 (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 20.99/7.01 (8) CpxTRS 20.99/7.01 (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 20.99/7.01 (10) typed CpxTrs 20.99/7.01 (11) OrderProof [LOWER BOUND(ID), 0 ms] 20.99/7.01 (12) typed CpxTrs 20.99/7.01 (13) RewriteLemmaProof [LOWER BOUND(ID), 469 ms] 20.99/7.01 (14) BEST 20.99/7.01 (15) proven lower bound 20.99/7.01 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 20.99/7.01 (17) BOUNDS(n^1, INF) 20.99/7.01 (18) typed CpxTrs 20.99/7.01 (19) RewriteLemmaProof [LOWER BOUND(ID), 94 ms] 20.99/7.01 (20) typed CpxTrs 20.99/7.01 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (0) 20.99/7.01 Obligation: 20.99/7.01 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.99/7.01 20.99/7.01 20.99/7.01 The TRS R consists of the following rules: 20.99/7.01 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 S is empty. 20.99/7.01 Rewrite Strategy: FULL 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 20.99/7.01 The following defined symbols can occur below the 0th argument of top: proper, active 20.99/7.01 The following defined symbols can occur below the 0th argument of proper: proper, active 20.99/7.01 The following defined symbols can occur below the 0th argument of active: proper, active 20.99/7.01 20.99/7.01 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (2) 20.99/7.01 Obligation: 20.99/7.01 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 20.99/7.01 20.99/7.01 20.99/7.01 The TRS R consists of the following rules: 20.99/7.01 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 S is empty. 20.99/7.01 Rewrite Strategy: FULL 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 20.99/7.01 transformed relative TRS to TRS 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (4) 20.99/7.01 Obligation: 20.99/7.01 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 20.99/7.01 20.99/7.01 20.99/7.01 The TRS R consists of the following rules: 20.99/7.01 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 S is empty. 20.99/7.01 Rewrite Strategy: FULL 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (5) CpxTrsMatchBoundsProof (FINISHED) 20.99/7.01 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. 20.99/7.01 The certificate found is represented by the following graph. 20.99/7.01 20.99/7.01 "[23, 24, 25, 26, 27, 28, 29, 30, 31] 20.99/7.01 {(23,24,[f_1|0, h_1|0, g_1|0, top_1|0]), (23,25,[mark_1|1]), (23,26,[ok_1|1]), (23,27,[mark_1|1]), (23,28,[ok_1|1]), (23,29,[ok_1|1]), (23,30,[top_1|1]), (23,31,[top_1|1]), (24,24,[mark_1|0, ok_1|0, proper_1|0, active_1|0]), (25,24,[f_1|1]), (25,25,[mark_1|1]), (25,26,[ok_1|1]), (26,24,[f_1|1]), (26,25,[mark_1|1]), (26,26,[ok_1|1]), (27,24,[h_1|1]), (27,27,[mark_1|1]), (27,28,[ok_1|1]), (28,24,[h_1|1]), (28,27,[mark_1|1]), (28,28,[ok_1|1]), (29,24,[g_1|1]), (29,29,[ok_1|1]), (30,24,[proper_1|1]), (31,24,[active_1|1])}" 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (6) 20.99/7.01 BOUNDS(1, n^1) 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (7) RenamingProof (BOTH BOUNDS(ID, ID)) 20.99/7.01 Renamed function symbols to avoid clashes with predefined symbol. 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (8) 20.99/7.01 Obligation: 20.99/7.01 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 20.99/7.01 20.99/7.01 20.99/7.01 The TRS R consists of the following rules: 20.99/7.01 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 S is empty. 20.99/7.01 Rewrite Strategy: FULL 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 20.99/7.01 Infered types. 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (10) 20.99/7.01 Obligation: 20.99/7.01 TRS: 20.99/7.01 Rules: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 Types: 20.99/7.01 active :: mark:ok -> mark:ok 20.99/7.01 f :: mark:ok -> mark:ok 20.99/7.01 mark :: mark:ok -> mark:ok 20.99/7.01 g :: mark:ok -> mark:ok 20.99/7.01 h :: mark:ok -> mark:ok 20.99/7.01 proper :: mark:ok -> mark:ok 20.99/7.01 ok :: mark:ok -> mark:ok 20.99/7.01 top :: mark:ok -> top 20.99/7.01 hole_mark:ok1_0 :: mark:ok 20.99/7.01 hole_top2_0 :: top 20.99/7.01 gen_mark:ok3_0 :: Nat -> mark:ok 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (11) OrderProof (LOWER BOUND(ID)) 20.99/7.01 Heuristically decided to analyse the following defined symbols: 20.99/7.01 active, g, h, f, proper, top 20.99/7.01 20.99/7.01 They will be analysed ascendingly in the following order: 20.99/7.01 g < active 20.99/7.01 h < active 20.99/7.01 f < active 20.99/7.01 active < top 20.99/7.01 g < proper 20.99/7.01 h < proper 20.99/7.01 f < proper 20.99/7.01 proper < top 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (12) 20.99/7.01 Obligation: 20.99/7.01 TRS: 20.99/7.01 Rules: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 Types: 20.99/7.01 active :: mark:ok -> mark:ok 20.99/7.01 f :: mark:ok -> mark:ok 20.99/7.01 mark :: mark:ok -> mark:ok 20.99/7.01 g :: mark:ok -> mark:ok 20.99/7.01 h :: mark:ok -> mark:ok 20.99/7.01 proper :: mark:ok -> mark:ok 20.99/7.01 ok :: mark:ok -> mark:ok 20.99/7.01 top :: mark:ok -> top 20.99/7.01 hole_mark:ok1_0 :: mark:ok 20.99/7.01 hole_top2_0 :: top 20.99/7.01 gen_mark:ok3_0 :: Nat -> mark:ok 20.99/7.01 20.99/7.01 20.99/7.01 Generator Equations: 20.99/7.01 gen_mark:ok3_0(0) <=> hole_mark:ok1_0 20.99/7.01 gen_mark:ok3_0(+(x, 1)) <=> mark(gen_mark:ok3_0(x)) 20.99/7.01 20.99/7.01 20.99/7.01 The following defined symbols remain to be analysed: 20.99/7.01 g, active, h, f, proper, top 20.99/7.01 20.99/7.01 They will be analysed ascendingly in the following order: 20.99/7.01 g < active 20.99/7.01 h < active 20.99/7.01 f < active 20.99/7.01 active < top 20.99/7.01 g < proper 20.99/7.01 h < proper 20.99/7.01 f < proper 20.99/7.01 proper < top 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (13) RewriteLemmaProof (LOWER BOUND(ID)) 20.99/7.01 Proved the following rewrite lemma: 20.99/7.01 h(gen_mark:ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) 20.99/7.01 20.99/7.01 Induction Base: 20.99/7.01 h(gen_mark:ok3_0(+(1, 0))) 20.99/7.01 20.99/7.01 Induction Step: 20.99/7.01 h(gen_mark:ok3_0(+(1, +(n9_0, 1)))) ->_R^Omega(1) 20.99/7.01 mark(h(gen_mark:ok3_0(+(1, n9_0)))) ->_IH 20.99/7.01 mark(*4_0) 20.99/7.01 20.99/7.01 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (14) 20.99/7.01 Complex Obligation (BEST) 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (15) 20.99/7.01 Obligation: 20.99/7.01 Proved the lower bound n^1 for the following obligation: 20.99/7.01 20.99/7.01 TRS: 20.99/7.01 Rules: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 Types: 20.99/7.01 active :: mark:ok -> mark:ok 20.99/7.01 f :: mark:ok -> mark:ok 20.99/7.01 mark :: mark:ok -> mark:ok 20.99/7.01 g :: mark:ok -> mark:ok 20.99/7.01 h :: mark:ok -> mark:ok 20.99/7.01 proper :: mark:ok -> mark:ok 20.99/7.01 ok :: mark:ok -> mark:ok 20.99/7.01 top :: mark:ok -> top 20.99/7.01 hole_mark:ok1_0 :: mark:ok 20.99/7.01 hole_top2_0 :: top 20.99/7.01 gen_mark:ok3_0 :: Nat -> mark:ok 20.99/7.01 20.99/7.01 20.99/7.01 Generator Equations: 20.99/7.01 gen_mark:ok3_0(0) <=> hole_mark:ok1_0 20.99/7.01 gen_mark:ok3_0(+(x, 1)) <=> mark(gen_mark:ok3_0(x)) 20.99/7.01 20.99/7.01 20.99/7.01 The following defined symbols remain to be analysed: 20.99/7.01 h, active, f, proper, top 20.99/7.01 20.99/7.01 They will be analysed ascendingly in the following order: 20.99/7.01 h < active 20.99/7.01 f < active 20.99/7.01 active < top 20.99/7.01 h < proper 20.99/7.01 f < proper 20.99/7.01 proper < top 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (16) LowerBoundPropagationProof (FINISHED) 20.99/7.01 Propagated lower bound. 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (17) 20.99/7.01 BOUNDS(n^1, INF) 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (18) 20.99/7.01 Obligation: 20.99/7.01 TRS: 20.99/7.01 Rules: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 Types: 20.99/7.01 active :: mark:ok -> mark:ok 20.99/7.01 f :: mark:ok -> mark:ok 20.99/7.01 mark :: mark:ok -> mark:ok 20.99/7.01 g :: mark:ok -> mark:ok 20.99/7.01 h :: mark:ok -> mark:ok 20.99/7.01 proper :: mark:ok -> mark:ok 20.99/7.01 ok :: mark:ok -> mark:ok 20.99/7.01 top :: mark:ok -> top 20.99/7.01 hole_mark:ok1_0 :: mark:ok 20.99/7.01 hole_top2_0 :: top 20.99/7.01 gen_mark:ok3_0 :: Nat -> mark:ok 20.99/7.01 20.99/7.01 20.99/7.01 Lemmas: 20.99/7.01 h(gen_mark:ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) 20.99/7.01 20.99/7.01 20.99/7.01 Generator Equations: 20.99/7.01 gen_mark:ok3_0(0) <=> hole_mark:ok1_0 20.99/7.01 gen_mark:ok3_0(+(x, 1)) <=> mark(gen_mark:ok3_0(x)) 20.99/7.01 20.99/7.01 20.99/7.01 The following defined symbols remain to be analysed: 20.99/7.01 f, active, proper, top 20.99/7.01 20.99/7.01 They will be analysed ascendingly in the following order: 20.99/7.01 f < active 20.99/7.01 active < top 20.99/7.01 f < proper 20.99/7.01 proper < top 20.99/7.01 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (19) RewriteLemmaProof (LOWER BOUND(ID)) 20.99/7.01 Proved the following rewrite lemma: 20.99/7.01 f(gen_mark:ok3_0(+(1, n315_0))) -> *4_0, rt in Omega(n315_0) 20.99/7.01 20.99/7.01 Induction Base: 20.99/7.01 f(gen_mark:ok3_0(+(1, 0))) 20.99/7.01 20.99/7.01 Induction Step: 20.99/7.01 f(gen_mark:ok3_0(+(1, +(n315_0, 1)))) ->_R^Omega(1) 20.99/7.01 mark(f(gen_mark:ok3_0(+(1, n315_0)))) ->_IH 20.99/7.01 mark(*4_0) 20.99/7.01 20.99/7.01 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 20.99/7.01 ---------------------------------------- 20.99/7.01 20.99/7.01 (20) 20.99/7.01 Obligation: 20.99/7.01 TRS: 20.99/7.01 Rules: 20.99/7.01 active(f(X)) -> mark(g(h(f(X)))) 20.99/7.01 active(f(X)) -> f(active(X)) 20.99/7.01 active(h(X)) -> h(active(X)) 20.99/7.01 f(mark(X)) -> mark(f(X)) 20.99/7.01 h(mark(X)) -> mark(h(X)) 20.99/7.01 proper(f(X)) -> f(proper(X)) 20.99/7.01 proper(g(X)) -> g(proper(X)) 20.99/7.01 proper(h(X)) -> h(proper(X)) 20.99/7.01 f(ok(X)) -> ok(f(X)) 20.99/7.01 g(ok(X)) -> ok(g(X)) 20.99/7.01 h(ok(X)) -> ok(h(X)) 20.99/7.01 top(mark(X)) -> top(proper(X)) 20.99/7.01 top(ok(X)) -> top(active(X)) 20.99/7.01 20.99/7.01 Types: 20.99/7.01 active :: mark:ok -> mark:ok 20.99/7.01 f :: mark:ok -> mark:ok 20.99/7.01 mark :: mark:ok -> mark:ok 20.99/7.01 g :: mark:ok -> mark:ok 20.99/7.01 h :: mark:ok -> mark:ok 20.99/7.01 proper :: mark:ok -> mark:ok 20.99/7.01 ok :: mark:ok -> mark:ok 20.99/7.01 top :: mark:ok -> top 20.99/7.01 hole_mark:ok1_0 :: mark:ok 20.99/7.01 hole_top2_0 :: top 20.99/7.01 gen_mark:ok3_0 :: Nat -> mark:ok 20.99/7.01 20.99/7.01 20.99/7.01 Lemmas: 20.99/7.01 h(gen_mark:ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) 20.99/7.01 f(gen_mark:ok3_0(+(1, n315_0))) -> *4_0, rt in Omega(n315_0) 20.99/7.01 20.99/7.01 20.99/7.01 Generator Equations: 20.99/7.01 gen_mark:ok3_0(0) <=> hole_mark:ok1_0 20.99/7.01 gen_mark:ok3_0(+(x, 1)) <=> mark(gen_mark:ok3_0(x)) 20.99/7.01 20.99/7.01 20.99/7.01 The following defined symbols remain to be analysed: 20.99/7.01 active, proper, top 20.99/7.01 20.99/7.01 They will be analysed ascendingly in the following order: 20.99/7.01 active < top 20.99/7.01 proper < top 21.25/10.59 EOF