22.16/7.62 WORST_CASE(Omega(n^1), O(n^1)) 22.16/7.63 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 22.16/7.63 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 22.16/7.63 22.16/7.63 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.16/7.63 22.16/7.63 (0) CpxTRS 22.16/7.63 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 22.16/7.63 (2) CpxTRS 22.16/7.63 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 22.16/7.63 (4) CpxTRS 22.16/7.63 (5) CpxTrsMatchBoundsTAProof [FINISHED, 177 ms] 22.16/7.63 (6) BOUNDS(1, n^1) 22.16/7.63 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 22.16/7.63 (8) TRS for Loop Detection 22.16/7.63 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 22.16/7.63 (10) BEST 22.16/7.63 (11) proven lower bound 22.16/7.63 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 22.16/7.63 (13) BOUNDS(n^1, INF) 22.16/7.63 (14) TRS for Loop Detection 22.16/7.63 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (0) 22.16/7.63 Obligation: 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(f(b, c, x)) -> mark(f(x, x, x)) 22.16/7.63 active(f(x, y, z)) -> f(x, y, active(z)) 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 proper(f(x, y, z)) -> f(proper(x), proper(y), proper(z)) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 22.16/7.63 The following defined symbols can occur below the 0th argument of top: active, proper 22.16/7.63 The following defined symbols can occur below the 0th argument of active: active, proper 22.16/7.63 The following defined symbols can occur below the 0th argument of proper: active, proper 22.16/7.63 22.16/7.63 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 22.16/7.63 active(f(b, c, x)) -> mark(f(x, x, x)) 22.16/7.63 active(f(x, y, z)) -> f(x, y, active(z)) 22.16/7.63 proper(f(x, y, z)) -> f(proper(x), proper(y), proper(z)) 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (2) 22.16/7.63 Obligation: 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 22.16/7.63 transformed relative TRS to TRS 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (4) 22.16/7.63 Obligation: 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (5) CpxTrsMatchBoundsTAProof (FINISHED) 22.16/7.63 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 4. 22.16/7.63 22.16/7.63 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 22.16/7.63 final states : [1, 2, 3, 4] 22.16/7.63 transitions: 22.16/7.63 d0() -> 0 22.16/7.63 m0(0) -> 0 22.16/7.63 b0() -> 0 22.16/7.63 mark0(0) -> 0 22.16/7.63 c0() -> 0 22.16/7.63 ok0(0) -> 0 22.16/7.63 active0(0) -> 1 22.16/7.63 f0(0, 0, 0) -> 2 22.16/7.63 proper0(0) -> 3 22.16/7.63 top0(0) -> 4 22.16/7.63 b1() -> 5 22.16/7.63 m1(5) -> 1 22.16/7.63 f1(0, 0, 0) -> 6 22.16/7.63 mark1(6) -> 2 22.16/7.63 c1() -> 7 22.16/7.63 mark1(7) -> 1 22.16/7.63 b1() -> 8 22.16/7.63 ok1(8) -> 3 22.16/7.63 c1() -> 9 22.16/7.63 ok1(9) -> 3 22.16/7.63 d1() -> 10 22.16/7.63 ok1(10) -> 3 22.16/7.63 f1(0, 0, 0) -> 11 22.16/7.63 ok1(11) -> 2 22.16/7.63 proper1(0) -> 12 22.16/7.63 top1(12) -> 4 22.16/7.63 active1(0) -> 13 22.16/7.63 top1(13) -> 4 22.16/7.63 m1(5) -> 13 22.16/7.63 mark1(6) -> 6 22.16/7.63 mark1(6) -> 11 22.16/7.63 mark1(7) -> 13 22.16/7.63 ok1(8) -> 12 22.16/7.63 ok1(9) -> 12 22.16/7.63 ok1(10) -> 12 22.16/7.63 ok1(11) -> 6 22.16/7.63 ok1(11) -> 11 22.16/7.63 proper2(7) -> 14 22.16/7.63 top2(14) -> 4 22.16/7.63 active2(8) -> 15 22.16/7.63 top2(15) -> 4 22.16/7.63 active2(9) -> 15 22.16/7.63 active2(10) -> 15 22.16/7.63 b2() -> 16 22.16/7.63 m2(16) -> 15 22.16/7.63 c2() -> 17 22.16/7.63 mark2(17) -> 15 22.16/7.63 c2() -> 18 22.16/7.63 ok2(18) -> 14 22.16/7.63 proper3(17) -> 19 22.16/7.63 top3(19) -> 4 22.16/7.63 active3(18) -> 20 22.16/7.63 top3(20) -> 4 22.16/7.63 c3() -> 21 22.16/7.63 ok3(21) -> 19 22.16/7.63 active4(21) -> 22 22.16/7.63 top4(22) -> 4 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (6) 22.16/7.63 BOUNDS(1, n^1) 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 22.16/7.63 Transformed a relative TRS into a decreasing-loop problem. 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (8) 22.16/7.63 Obligation: 22.16/7.63 Analyzing the following TRS for decreasing loops: 22.16/7.63 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(f(b, c, x)) -> mark(f(x, x, x)) 22.16/7.63 active(f(x, y, z)) -> f(x, y, active(z)) 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 proper(f(x, y, z)) -> f(proper(x), proper(y), proper(z)) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (9) DecreasingLoopProof (LOWER BOUND(ID)) 22.16/7.63 The following loop(s) give(s) rise to the lower bound Omega(n^1): 22.16/7.63 22.16/7.63 The rewrite sequence 22.16/7.63 22.16/7.63 f(ok(x), ok(y), ok(z)) ->^+ ok(f(x, y, z)) 22.16/7.63 22.16/7.63 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 22.16/7.63 22.16/7.63 The pumping substitution is [x / ok(x), y / ok(y), z / ok(z)]. 22.16/7.63 22.16/7.63 The result substitution is [ ]. 22.16/7.63 22.16/7.63 22.16/7.63 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (10) 22.16/7.63 Complex Obligation (BEST) 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (11) 22.16/7.63 Obligation: 22.16/7.63 Proved the lower bound n^1 for the following obligation: 22.16/7.63 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(f(b, c, x)) -> mark(f(x, x, x)) 22.16/7.63 active(f(x, y, z)) -> f(x, y, active(z)) 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 proper(f(x, y, z)) -> f(proper(x), proper(y), proper(z)) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (12) LowerBoundPropagationProof (FINISHED) 22.16/7.63 Propagated lower bound. 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (13) 22.16/7.63 BOUNDS(n^1, INF) 22.16/7.63 22.16/7.63 ---------------------------------------- 22.16/7.63 22.16/7.63 (14) 22.16/7.63 Obligation: 22.16/7.63 Analyzing the following TRS for decreasing loops: 22.16/7.63 22.16/7.63 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 22.16/7.63 22.16/7.63 22.16/7.63 The TRS R consists of the following rules: 22.16/7.63 22.16/7.63 active(f(b, c, x)) -> mark(f(x, x, x)) 22.16/7.63 active(f(x, y, z)) -> f(x, y, active(z)) 22.16/7.63 active(d) -> m(b) 22.16/7.63 f(x, y, mark(z)) -> mark(f(x, y, z)) 22.16/7.63 active(d) -> mark(c) 22.16/7.63 proper(b) -> ok(b) 22.16/7.63 proper(c) -> ok(c) 22.16/7.63 proper(d) -> ok(d) 22.16/7.63 proper(f(x, y, z)) -> f(proper(x), proper(y), proper(z)) 22.16/7.63 f(ok(x), ok(y), ok(z)) -> ok(f(x, y, z)) 22.16/7.63 top(mark(x)) -> top(proper(x)) 22.16/7.63 top(ok(x)) -> top(active(x)) 22.16/7.63 22.16/7.63 S is empty. 22.16/7.63 Rewrite Strategy: FULL 22.21/7.66 EOF