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