317.69/291.46 WORST_CASE(Omega(n^1), ?) 317.69/291.47 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 317.69/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 317.69/291.47 317.69/291.47 317.69/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 317.69/291.47 317.69/291.47 (0) CpxTRS 317.69/291.47 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 317.69/291.47 (2) TRS for Loop Detection 317.69/291.47 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 317.69/291.47 (4) BEST 317.69/291.47 (5) proven lower bound 317.69/291.47 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 317.69/291.47 (7) BOUNDS(n^1, INF) 317.69/291.47 (8) TRS for Loop Detection 317.69/291.47 317.69/291.47 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (0) 317.69/291.47 Obligation: 317.69/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 317.69/291.47 317.69/291.47 317.69/291.47 The TRS R consists of the following rules: 317.69/291.47 317.69/291.47 min(0, y) -> 0 317.69/291.47 min(x, 0) -> 0 317.69/291.47 min(s(x), s(y)) -> s(min(x, y)) 317.69/291.47 max(0, y) -> y 317.69/291.47 max(x, 0) -> x 317.69/291.47 max(s(x), s(y)) -> s(max(x, y)) 317.69/291.47 p(s(x)) -> x 317.69/291.47 f(s(x), s(y), s(z)) -> f(max(s(x), max(s(y), s(z))), p(min(s(x), max(s(y), s(z)))), min(s(x), min(s(y), s(z)))) 317.69/291.47 f(0, y, z) -> max(y, z) 317.69/291.47 f(x, 0, z) -> max(x, z) 317.69/291.47 f(x, y, 0) -> max(x, y) 317.69/291.47 317.69/291.47 S is empty. 317.69/291.47 Rewrite Strategy: FULL 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 317.69/291.47 Transformed a relative TRS into a decreasing-loop problem. 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (2) 317.69/291.47 Obligation: 317.69/291.47 Analyzing the following TRS for decreasing loops: 317.69/291.47 317.69/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 317.69/291.47 317.69/291.47 317.69/291.47 The TRS R consists of the following rules: 317.69/291.47 317.69/291.47 min(0, y) -> 0 317.69/291.47 min(x, 0) -> 0 317.69/291.47 min(s(x), s(y)) -> s(min(x, y)) 317.69/291.47 max(0, y) -> y 317.69/291.47 max(x, 0) -> x 317.69/291.47 max(s(x), s(y)) -> s(max(x, y)) 317.69/291.47 p(s(x)) -> x 317.69/291.47 f(s(x), s(y), s(z)) -> f(max(s(x), max(s(y), s(z))), p(min(s(x), max(s(y), s(z)))), min(s(x), min(s(y), s(z)))) 317.69/291.47 f(0, y, z) -> max(y, z) 317.69/291.47 f(x, 0, z) -> max(x, z) 317.69/291.47 f(x, y, 0) -> max(x, y) 317.69/291.47 317.69/291.47 S is empty. 317.69/291.47 Rewrite Strategy: FULL 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (3) DecreasingLoopProof (LOWER BOUND(ID)) 317.69/291.47 The following loop(s) give(s) rise to the lower bound Omega(n^1): 317.69/291.47 317.69/291.47 The rewrite sequence 317.69/291.47 317.69/291.47 min(s(x), s(y)) ->^+ s(min(x, y)) 317.69/291.47 317.69/291.47 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 317.69/291.47 317.69/291.47 The pumping substitution is [x / s(x), y / s(y)]. 317.69/291.47 317.69/291.47 The result substitution is [ ]. 317.69/291.47 317.69/291.47 317.69/291.47 317.69/291.47 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (4) 317.69/291.47 Complex Obligation (BEST) 317.69/291.47 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (5) 317.69/291.47 Obligation: 317.69/291.47 Proved the lower bound n^1 for the following obligation: 317.69/291.47 317.69/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 317.69/291.47 317.69/291.47 317.69/291.47 The TRS R consists of the following rules: 317.69/291.47 317.69/291.47 min(0, y) -> 0 317.69/291.47 min(x, 0) -> 0 317.69/291.47 min(s(x), s(y)) -> s(min(x, y)) 317.69/291.47 max(0, y) -> y 317.69/291.47 max(x, 0) -> x 317.69/291.47 max(s(x), s(y)) -> s(max(x, y)) 317.69/291.47 p(s(x)) -> x 317.69/291.47 f(s(x), s(y), s(z)) -> f(max(s(x), max(s(y), s(z))), p(min(s(x), max(s(y), s(z)))), min(s(x), min(s(y), s(z)))) 317.69/291.47 f(0, y, z) -> max(y, z) 317.69/291.47 f(x, 0, z) -> max(x, z) 317.69/291.47 f(x, y, 0) -> max(x, y) 317.69/291.47 317.69/291.47 S is empty. 317.69/291.47 Rewrite Strategy: FULL 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (6) LowerBoundPropagationProof (FINISHED) 317.69/291.47 Propagated lower bound. 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (7) 317.69/291.47 BOUNDS(n^1, INF) 317.69/291.47 317.69/291.47 ---------------------------------------- 317.69/291.47 317.69/291.47 (8) 317.69/291.47 Obligation: 317.69/291.47 Analyzing the following TRS for decreasing loops: 317.69/291.47 317.69/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 317.69/291.47 317.69/291.47 317.69/291.47 The TRS R consists of the following rules: 317.69/291.47 317.69/291.47 min(0, y) -> 0 317.69/291.47 min(x, 0) -> 0 317.69/291.47 min(s(x), s(y)) -> s(min(x, y)) 317.69/291.47 max(0, y) -> y 317.69/291.47 max(x, 0) -> x 317.69/291.47 max(s(x), s(y)) -> s(max(x, y)) 317.69/291.47 p(s(x)) -> x 317.69/291.47 f(s(x), s(y), s(z)) -> f(max(s(x), max(s(y), s(z))), p(min(s(x), max(s(y), s(z)))), min(s(x), min(s(y), s(z)))) 317.69/291.47 f(0, y, z) -> max(y, z) 317.69/291.47 f(x, 0, z) -> max(x, z) 317.69/291.47 f(x, y, 0) -> max(x, y) 317.69/291.47 317.69/291.47 S is empty. 317.69/291.47 Rewrite Strategy: FULL 317.72/291.50 EOF