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