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