1088.49/291.55 WORST_CASE(Omega(n^1), ?) 1088.49/291.55 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1088.49/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1088.49/291.55 1088.49/291.55 1088.49/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1088.49/291.55 1088.49/291.55 (0) CpxTRS 1088.49/291.55 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1088.49/291.55 (2) TRS for Loop Detection 1088.49/291.55 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1088.49/291.55 (4) BEST 1088.49/291.55 (5) proven lower bound 1088.49/291.55 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1088.49/291.55 (7) BOUNDS(n^1, INF) 1088.49/291.55 (8) TRS for Loop Detection 1088.49/291.55 1088.49/291.55 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (0) 1088.49/291.55 Obligation: 1088.49/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1088.49/291.55 1088.49/291.55 1088.49/291.55 The TRS R consists of the following rules: 1088.49/291.55 1088.49/291.55 qsort(nil) -> nil 1088.49/291.55 qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs))))) 1088.49/291.55 filterlow(n, nil) -> nil 1088.49/291.55 filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs) 1088.49/291.55 if1(true, n, x, xs) -> filterlow(n, xs) 1088.49/291.55 if1(false, n, x, xs) -> cons(x, filterlow(n, xs)) 1088.49/291.55 filterhigh(n, nil) -> nil 1088.49/291.55 filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs) 1088.49/291.55 if2(true, n, x, xs) -> filterhigh(n, xs) 1088.49/291.55 if2(false, n, x, xs) -> cons(x, filterhigh(n, xs)) 1088.49/291.55 ge(x, 0) -> true 1088.49/291.55 ge(0, s(x)) -> false 1088.49/291.55 ge(s(x), s(y)) -> ge(x, y) 1088.49/291.55 append(nil, ys) -> ys 1088.49/291.55 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 1088.49/291.55 1088.49/291.55 S is empty. 1088.49/291.55 Rewrite Strategy: INNERMOST 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1088.49/291.55 Transformed a relative TRS into a decreasing-loop problem. 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (2) 1088.49/291.55 Obligation: 1088.49/291.55 Analyzing the following TRS for decreasing loops: 1088.49/291.55 1088.49/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1088.49/291.55 1088.49/291.55 1088.49/291.55 The TRS R consists of the following rules: 1088.49/291.55 1088.49/291.55 qsort(nil) -> nil 1088.49/291.55 qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs))))) 1088.49/291.55 filterlow(n, nil) -> nil 1088.49/291.55 filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs) 1088.49/291.55 if1(true, n, x, xs) -> filterlow(n, xs) 1088.49/291.55 if1(false, n, x, xs) -> cons(x, filterlow(n, xs)) 1088.49/291.55 filterhigh(n, nil) -> nil 1088.49/291.55 filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs) 1088.49/291.55 if2(true, n, x, xs) -> filterhigh(n, xs) 1088.49/291.55 if2(false, n, x, xs) -> cons(x, filterhigh(n, xs)) 1088.49/291.55 ge(x, 0) -> true 1088.49/291.55 ge(0, s(x)) -> false 1088.49/291.55 ge(s(x), s(y)) -> ge(x, y) 1088.49/291.55 append(nil, ys) -> ys 1088.49/291.55 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 1088.49/291.55 1088.49/291.55 S is empty. 1088.49/291.55 Rewrite Strategy: INNERMOST 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1088.49/291.55 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1088.49/291.55 1088.49/291.55 The rewrite sequence 1088.49/291.55 1088.49/291.55 append(cons(x, xs), ys) ->^+ cons(x, append(xs, ys)) 1088.49/291.55 1088.49/291.55 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 1088.49/291.55 1088.49/291.55 The pumping substitution is [xs / cons(x, xs)]. 1088.49/291.55 1088.49/291.55 The result substitution is [ ]. 1088.49/291.55 1088.49/291.55 1088.49/291.55 1088.49/291.55 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (4) 1088.49/291.55 Complex Obligation (BEST) 1088.49/291.55 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (5) 1088.49/291.55 Obligation: 1088.49/291.55 Proved the lower bound n^1 for the following obligation: 1088.49/291.55 1088.49/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1088.49/291.55 1088.49/291.55 1088.49/291.55 The TRS R consists of the following rules: 1088.49/291.55 1088.49/291.55 qsort(nil) -> nil 1088.49/291.55 qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs))))) 1088.49/291.55 filterlow(n, nil) -> nil 1088.49/291.55 filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs) 1088.49/291.55 if1(true, n, x, xs) -> filterlow(n, xs) 1088.49/291.55 if1(false, n, x, xs) -> cons(x, filterlow(n, xs)) 1088.49/291.55 filterhigh(n, nil) -> nil 1088.49/291.55 filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs) 1088.49/291.55 if2(true, n, x, xs) -> filterhigh(n, xs) 1088.49/291.55 if2(false, n, x, xs) -> cons(x, filterhigh(n, xs)) 1088.49/291.55 ge(x, 0) -> true 1088.49/291.55 ge(0, s(x)) -> false 1088.49/291.55 ge(s(x), s(y)) -> ge(x, y) 1088.49/291.55 append(nil, ys) -> ys 1088.49/291.55 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 1088.49/291.55 1088.49/291.55 S is empty. 1088.49/291.55 Rewrite Strategy: INNERMOST 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (6) LowerBoundPropagationProof (FINISHED) 1088.49/291.55 Propagated lower bound. 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (7) 1088.49/291.55 BOUNDS(n^1, INF) 1088.49/291.55 1088.49/291.55 ---------------------------------------- 1088.49/291.55 1088.49/291.55 (8) 1088.49/291.55 Obligation: 1088.49/291.55 Analyzing the following TRS for decreasing loops: 1088.49/291.55 1088.49/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1088.49/291.55 1088.49/291.55 1088.49/291.55 The TRS R consists of the following rules: 1088.49/291.55 1088.49/291.55 qsort(nil) -> nil 1088.49/291.55 qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs))))) 1088.49/291.55 filterlow(n, nil) -> nil 1088.49/291.55 filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs) 1088.49/291.55 if1(true, n, x, xs) -> filterlow(n, xs) 1088.49/291.55 if1(false, n, x, xs) -> cons(x, filterlow(n, xs)) 1088.49/291.55 filterhigh(n, nil) -> nil 1088.49/291.55 filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs) 1088.49/291.55 if2(true, n, x, xs) -> filterhigh(n, xs) 1088.49/291.55 if2(false, n, x, xs) -> cons(x, filterhigh(n, xs)) 1088.49/291.55 ge(x, 0) -> true 1088.49/291.55 ge(0, s(x)) -> false 1088.49/291.55 ge(s(x), s(y)) -> ge(x, y) 1088.49/291.55 append(nil, ys) -> ys 1088.49/291.55 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 1088.49/291.55 1088.49/291.55 S is empty. 1088.49/291.55 Rewrite Strategy: INNERMOST 1088.65/291.61 EOF