21.52/7.46 WORST_CASE(Omega(n^1), O(n^1)) 21.52/7.47 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 21.52/7.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.52/7.47 21.52/7.47 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.52/7.47 21.52/7.47 (0) CpxTRS 21.52/7.47 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 21.52/7.47 (2) CpxTRS 21.52/7.47 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 21.52/7.47 (4) CpxTRS 21.52/7.47 (5) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 21.52/7.47 (6) BOUNDS(1, n^1) 21.52/7.47 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 21.52/7.47 (8) TRS for Loop Detection 21.52/7.47 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 21.52/7.47 (10) BEST 21.52/7.47 (11) proven lower bound 21.52/7.47 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 21.52/7.47 (13) BOUNDS(n^1, INF) 21.52/7.47 (14) TRS for Loop Detection 21.52/7.47 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (0) 21.52/7.47 Obligation: 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(g(X)) -> mark(h(X)) 21.52/7.47 active(c) -> mark(d) 21.52/7.47 active(h(d)) -> mark(g(c)) 21.52/7.47 proper(g(X)) -> g(proper(X)) 21.52/7.47 proper(h(X)) -> h(proper(X)) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 21.52/7.47 The following defined symbols can occur below the 0th argument of top: proper, active 21.52/7.47 The following defined symbols can occur below the 0th argument of proper: proper, active 21.52/7.47 The following defined symbols can occur below the 0th argument of active: proper, active 21.52/7.47 21.52/7.47 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 21.52/7.47 active(g(X)) -> mark(h(X)) 21.52/7.47 active(h(d)) -> mark(g(c)) 21.52/7.47 proper(g(X)) -> g(proper(X)) 21.52/7.47 proper(h(X)) -> h(proper(X)) 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (2) 21.52/7.47 Obligation: 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(c) -> mark(d) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 21.52/7.47 transformed relative TRS to TRS 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (4) 21.52/7.47 Obligation: 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(c) -> mark(d) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (5) CpxTrsMatchBoundsProof (FINISHED) 21.52/7.47 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4. 21.52/7.47 The certificate found is represented by the following graph. 21.52/7.47 21.52/7.47 "[16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32] 21.52/7.47 {(16,17,[active_1|0, proper_1|0, g_1|0, h_1|0, top_1|0]), (16,18,[mark_1|1]), (16,19,[ok_1|1]), (16,20,[ok_1|1]), (16,21,[ok_1|1]), (16,22,[ok_1|1]), (16,23,[top_1|1]), (16,24,[top_1|1]), (16,25,[top_1|2]), (16,26,[top_1|2]), (16,29,[top_1|3]), (16,30,[top_1|3]), (16,32,[top_1|4]), (17,17,[c|0, mark_1|0, d|0, ok_1|0]), (18,17,[d|1]), (19,17,[c|1]), (20,17,[d|1]), (21,17,[g_1|1]), (21,21,[ok_1|1]), (22,17,[h_1|1]), (22,22,[ok_1|1]), (23,17,[proper_1|1]), (23,19,[ok_1|1]), (23,20,[ok_1|1]), (24,17,[active_1|1]), (24,18,[mark_1|1]), (25,19,[active_1|2]), (25,20,[active_1|2]), (25,27,[mark_1|2]), (26,18,[proper_1|2]), (26,28,[ok_1|2]), (27,17,[d|2]), (28,17,[d|2]), (29,27,[proper_1|3]), (29,31,[ok_1|3]), (30,28,[active_1|3]), (31,17,[d|3]), (32,31,[active_1|4])}" 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (6) 21.52/7.47 BOUNDS(1, n^1) 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 21.52/7.47 Transformed a relative TRS into a decreasing-loop problem. 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (8) 21.52/7.47 Obligation: 21.52/7.47 Analyzing the following TRS for decreasing loops: 21.52/7.47 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(g(X)) -> mark(h(X)) 21.52/7.47 active(c) -> mark(d) 21.52/7.47 active(h(d)) -> mark(g(c)) 21.52/7.47 proper(g(X)) -> g(proper(X)) 21.52/7.47 proper(h(X)) -> h(proper(X)) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (9) DecreasingLoopProof (LOWER BOUND(ID)) 21.52/7.47 The following loop(s) give(s) rise to the lower bound Omega(n^1): 21.52/7.47 21.52/7.47 The rewrite sequence 21.52/7.47 21.52/7.47 g(ok(X)) ->^+ ok(g(X)) 21.52/7.47 21.52/7.47 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 21.52/7.47 21.52/7.47 The pumping substitution is [X / ok(X)]. 21.52/7.47 21.52/7.47 The result substitution is [ ]. 21.52/7.47 21.52/7.47 21.52/7.47 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (10) 21.52/7.47 Complex Obligation (BEST) 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (11) 21.52/7.47 Obligation: 21.52/7.47 Proved the lower bound n^1 for the following obligation: 21.52/7.47 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(g(X)) -> mark(h(X)) 21.52/7.47 active(c) -> mark(d) 21.52/7.47 active(h(d)) -> mark(g(c)) 21.52/7.47 proper(g(X)) -> g(proper(X)) 21.52/7.47 proper(h(X)) -> h(proper(X)) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (12) LowerBoundPropagationProof (FINISHED) 21.52/7.47 Propagated lower bound. 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (13) 21.52/7.47 BOUNDS(n^1, INF) 21.52/7.47 21.52/7.47 ---------------------------------------- 21.52/7.47 21.52/7.47 (14) 21.52/7.47 Obligation: 21.52/7.47 Analyzing the following TRS for decreasing loops: 21.52/7.47 21.52/7.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 21.52/7.47 21.52/7.47 21.52/7.47 The TRS R consists of the following rules: 21.52/7.47 21.52/7.47 active(g(X)) -> mark(h(X)) 21.52/7.47 active(c) -> mark(d) 21.52/7.47 active(h(d)) -> mark(g(c)) 21.52/7.47 proper(g(X)) -> g(proper(X)) 21.52/7.47 proper(h(X)) -> h(proper(X)) 21.52/7.47 proper(c) -> ok(c) 21.52/7.47 proper(d) -> ok(d) 21.52/7.47 g(ok(X)) -> ok(g(X)) 21.52/7.47 h(ok(X)) -> ok(h(X)) 21.52/7.47 top(mark(X)) -> top(proper(X)) 21.52/7.47 top(ok(X)) -> top(active(X)) 21.52/7.47 21.52/7.47 S is empty. 21.52/7.47 Rewrite Strategy: FULL 21.93/8.96 EOF