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