8.21/3.00 WORST_CASE(Omega(n^1), O(n^1)) 8.21/3.00 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.21/3.00 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.21/3.00 8.21/3.00 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.21/3.00 8.21/3.00 (0) CpxTRS 8.21/3.00 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 8.21/3.00 (2) CpxTRS 8.21/3.00 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 8.21/3.00 (4) CpxTRS 8.21/3.00 (5) CpxTrsMatchBoundsProof [FINISHED, 0 ms] 8.21/3.00 (6) BOUNDS(1, n^1) 8.21/3.00 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 8.21/3.00 (8) TRS for Loop Detection 8.21/3.00 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 8.21/3.00 (10) BEST 8.21/3.00 (11) proven lower bound 8.21/3.00 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 8.21/3.00 (13) BOUNDS(n^1, INF) 8.21/3.00 (14) TRS for Loop Detection 8.21/3.00 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (0) 8.21/3.00 Obligation: 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 b(w(x)) -> w(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 8.21/3.00 The TRS does not nest defined symbols. 8.21/3.00 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 8.21/3.00 b(w(x)) -> w(b(x)) 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (2) 8.21/3.00 Obligation: 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 8.21/3.00 transformed relative TRS to TRS 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (4) 8.21/3.00 Obligation: 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (5) CpxTrsMatchBoundsProof (FINISHED) 8.21/3.00 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. 8.21/3.00 The certificate found is represented by the following graph. 8.21/3.00 8.21/3.00 "[7, 8, 9, 10] 8.21/3.00 {(7,8,[w_1|0, b_1|0]), (7,9,[r_1|1]), (7,10,[r_1|1]), (8,8,[r_1|0]), (9,8,[w_1|1]), (9,9,[r_1|1]), (10,8,[b_1|1]), (10,10,[r_1|1])}" 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (6) 8.21/3.00 BOUNDS(1, n^1) 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 8.21/3.00 Transformed a relative TRS into a decreasing-loop problem. 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (8) 8.21/3.00 Obligation: 8.21/3.00 Analyzing the following TRS for decreasing loops: 8.21/3.00 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 b(w(x)) -> w(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (9) DecreasingLoopProof (LOWER BOUND(ID)) 8.21/3.00 The following loop(s) give(s) rise to the lower bound Omega(n^1): 8.21/3.00 8.21/3.00 The rewrite sequence 8.21/3.00 8.21/3.00 b(r(x)) ->^+ r(b(x)) 8.21/3.00 8.21/3.00 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 8.21/3.00 8.21/3.00 The pumping substitution is [x / r(x)]. 8.21/3.00 8.21/3.00 The result substitution is [ ]. 8.21/3.00 8.21/3.00 8.21/3.00 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (10) 8.21/3.00 Complex Obligation (BEST) 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (11) 8.21/3.00 Obligation: 8.21/3.00 Proved the lower bound n^1 for the following obligation: 8.21/3.00 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 b(w(x)) -> w(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (12) LowerBoundPropagationProof (FINISHED) 8.21/3.00 Propagated lower bound. 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (13) 8.21/3.00 BOUNDS(n^1, INF) 8.21/3.00 8.21/3.00 ---------------------------------------- 8.21/3.00 8.21/3.00 (14) 8.21/3.00 Obligation: 8.21/3.00 Analyzing the following TRS for decreasing loops: 8.21/3.00 8.21/3.00 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 8.21/3.00 8.21/3.00 8.21/3.00 The TRS R consists of the following rules: 8.21/3.00 8.21/3.00 w(r(x)) -> r(w(x)) 8.21/3.00 b(r(x)) -> r(b(x)) 8.21/3.00 b(w(x)) -> w(b(x)) 8.21/3.00 8.21/3.00 S is empty. 8.21/3.00 Rewrite Strategy: FULL 8.58/3.12 EOF