1123.10/294.49 WORST_CASE(Omega(n^1), ?) 1125.18/294.99 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1125.18/294.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1125.18/294.99 1125.18/294.99 1125.18/294.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1125.18/294.99 1125.18/294.99 (0) CpxTRS 1125.18/294.99 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1125.18/294.99 (2) TRS for Loop Detection 1125.18/294.99 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1125.18/294.99 (4) BEST 1125.18/294.99 (5) proven lower bound 1125.18/294.99 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1125.18/294.99 (7) BOUNDS(n^1, INF) 1125.18/294.99 (8) TRS for Loop Detection 1125.18/294.99 1125.18/294.99 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (0) 1125.18/294.99 Obligation: 1125.18/294.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1125.18/294.99 1125.18/294.99 1125.18/294.99 The TRS R consists of the following rules: 1125.18/294.99 1125.18/294.99 isEmpty(cons(x, xs)) -> false 1125.18/294.99 isEmpty(nil) -> true 1125.18/294.99 isZero(0) -> true 1125.18/294.99 isZero(s(x)) -> false 1125.18/294.99 head(cons(x, xs)) -> x 1125.18/294.99 tail(cons(x, xs)) -> xs 1125.18/294.99 tail(nil) -> nil 1125.18/294.99 append(nil, x) -> cons(x, nil) 1125.18/294.99 append(cons(y, ys), x) -> cons(y, append(ys, x)) 1125.18/294.99 p(s(s(x))) -> s(p(s(x))) 1125.18/294.99 p(s(0)) -> 0 1125.18/294.99 p(0) -> 0 1125.18/294.99 inc(s(x)) -> s(inc(x)) 1125.18/294.99 inc(0) -> s(0) 1125.18/294.99 addLists(xs, ys, zs) -> if(isEmpty(xs), isEmpty(ys), isZero(head(xs)), tail(xs), tail(ys), cons(p(head(xs)), tail(xs)), cons(inc(head(ys)), tail(ys)), zs, append(zs, head(ys))) 1125.18/294.99 if(true, true, b, xs, ys, xs2, ys2, zs, zs2) -> zs 1125.18/294.99 if(true, false, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, true, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, false, false, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs2, ys2, zs) 1125.18/294.99 if(false, false, true, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs, ys, zs2) 1125.18/294.99 addList(xs, ys) -> addLists(xs, ys, nil) 1125.18/294.99 1125.18/294.99 S is empty. 1125.18/294.99 Rewrite Strategy: INNERMOST 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1125.18/294.99 Transformed a relative TRS into a decreasing-loop problem. 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (2) 1125.18/294.99 Obligation: 1125.18/294.99 Analyzing the following TRS for decreasing loops: 1125.18/294.99 1125.18/294.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1125.18/294.99 1125.18/294.99 1125.18/294.99 The TRS R consists of the following rules: 1125.18/294.99 1125.18/294.99 isEmpty(cons(x, xs)) -> false 1125.18/294.99 isEmpty(nil) -> true 1125.18/294.99 isZero(0) -> true 1125.18/294.99 isZero(s(x)) -> false 1125.18/294.99 head(cons(x, xs)) -> x 1125.18/294.99 tail(cons(x, xs)) -> xs 1125.18/294.99 tail(nil) -> nil 1125.18/294.99 append(nil, x) -> cons(x, nil) 1125.18/294.99 append(cons(y, ys), x) -> cons(y, append(ys, x)) 1125.18/294.99 p(s(s(x))) -> s(p(s(x))) 1125.18/294.99 p(s(0)) -> 0 1125.18/294.99 p(0) -> 0 1125.18/294.99 inc(s(x)) -> s(inc(x)) 1125.18/294.99 inc(0) -> s(0) 1125.18/294.99 addLists(xs, ys, zs) -> if(isEmpty(xs), isEmpty(ys), isZero(head(xs)), tail(xs), tail(ys), cons(p(head(xs)), tail(xs)), cons(inc(head(ys)), tail(ys)), zs, append(zs, head(ys))) 1125.18/294.99 if(true, true, b, xs, ys, xs2, ys2, zs, zs2) -> zs 1125.18/294.99 if(true, false, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, true, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, false, false, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs2, ys2, zs) 1125.18/294.99 if(false, false, true, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs, ys, zs2) 1125.18/294.99 addList(xs, ys) -> addLists(xs, ys, nil) 1125.18/294.99 1125.18/294.99 S is empty. 1125.18/294.99 Rewrite Strategy: INNERMOST 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1125.18/294.99 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1125.18/294.99 1125.18/294.99 The rewrite sequence 1125.18/294.99 1125.18/294.99 append(cons(y, ys), x) ->^+ cons(y, append(ys, x)) 1125.18/294.99 1125.18/294.99 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 1125.18/294.99 1125.18/294.99 The pumping substitution is [ys / cons(y, ys)]. 1125.18/294.99 1125.18/294.99 The result substitution is [ ]. 1125.18/294.99 1125.18/294.99 1125.18/294.99 1125.18/294.99 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (4) 1125.18/294.99 Complex Obligation (BEST) 1125.18/294.99 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (5) 1125.18/294.99 Obligation: 1125.18/294.99 Proved the lower bound n^1 for the following obligation: 1125.18/294.99 1125.18/294.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1125.18/294.99 1125.18/294.99 1125.18/294.99 The TRS R consists of the following rules: 1125.18/294.99 1125.18/294.99 isEmpty(cons(x, xs)) -> false 1125.18/294.99 isEmpty(nil) -> true 1125.18/294.99 isZero(0) -> true 1125.18/294.99 isZero(s(x)) -> false 1125.18/294.99 head(cons(x, xs)) -> x 1125.18/294.99 tail(cons(x, xs)) -> xs 1125.18/294.99 tail(nil) -> nil 1125.18/294.99 append(nil, x) -> cons(x, nil) 1125.18/294.99 append(cons(y, ys), x) -> cons(y, append(ys, x)) 1125.18/294.99 p(s(s(x))) -> s(p(s(x))) 1125.18/294.99 p(s(0)) -> 0 1125.18/294.99 p(0) -> 0 1125.18/294.99 inc(s(x)) -> s(inc(x)) 1125.18/294.99 inc(0) -> s(0) 1125.18/294.99 addLists(xs, ys, zs) -> if(isEmpty(xs), isEmpty(ys), isZero(head(xs)), tail(xs), tail(ys), cons(p(head(xs)), tail(xs)), cons(inc(head(ys)), tail(ys)), zs, append(zs, head(ys))) 1125.18/294.99 if(true, true, b, xs, ys, xs2, ys2, zs, zs2) -> zs 1125.18/294.99 if(true, false, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, true, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, false, false, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs2, ys2, zs) 1125.18/294.99 if(false, false, true, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs, ys, zs2) 1125.18/294.99 addList(xs, ys) -> addLists(xs, ys, nil) 1125.18/294.99 1125.18/294.99 S is empty. 1125.18/294.99 Rewrite Strategy: INNERMOST 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (6) LowerBoundPropagationProof (FINISHED) 1125.18/294.99 Propagated lower bound. 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (7) 1125.18/294.99 BOUNDS(n^1, INF) 1125.18/294.99 1125.18/294.99 ---------------------------------------- 1125.18/294.99 1125.18/294.99 (8) 1125.18/294.99 Obligation: 1125.18/294.99 Analyzing the following TRS for decreasing loops: 1125.18/294.99 1125.18/294.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1125.18/294.99 1125.18/294.99 1125.18/294.99 The TRS R consists of the following rules: 1125.18/294.99 1125.18/294.99 isEmpty(cons(x, xs)) -> false 1125.18/294.99 isEmpty(nil) -> true 1125.18/294.99 isZero(0) -> true 1125.18/294.99 isZero(s(x)) -> false 1125.18/294.99 head(cons(x, xs)) -> x 1125.18/294.99 tail(cons(x, xs)) -> xs 1125.18/294.99 tail(nil) -> nil 1125.18/294.99 append(nil, x) -> cons(x, nil) 1125.18/294.99 append(cons(y, ys), x) -> cons(y, append(ys, x)) 1125.18/294.99 p(s(s(x))) -> s(p(s(x))) 1125.18/294.99 p(s(0)) -> 0 1125.18/294.99 p(0) -> 0 1125.18/294.99 inc(s(x)) -> s(inc(x)) 1125.18/294.99 inc(0) -> s(0) 1125.18/294.99 addLists(xs, ys, zs) -> if(isEmpty(xs), isEmpty(ys), isZero(head(xs)), tail(xs), tail(ys), cons(p(head(xs)), tail(xs)), cons(inc(head(ys)), tail(ys)), zs, append(zs, head(ys))) 1125.18/294.99 if(true, true, b, xs, ys, xs2, ys2, zs, zs2) -> zs 1125.18/294.99 if(true, false, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, true, b, xs, ys, xs2, ys2, zs, zs2) -> differentLengthError 1125.18/294.99 if(false, false, false, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs2, ys2, zs) 1125.18/294.99 if(false, false, true, xs, ys, xs2, ys2, zs, zs2) -> addLists(xs, ys, zs2) 1125.18/294.99 addList(xs, ys) -> addLists(xs, ys, nil) 1125.18/294.99 1125.18/294.99 S is empty. 1125.18/294.99 Rewrite Strategy: INNERMOST 1125.34/295.11 EOF