25.41/8.01 WORST_CASE(Omega(n^1), O(n^1)) 25.41/8.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 25.41/8.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.41/8.03 25.41/8.03 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.41/8.03 25.41/8.03 (0) CpxTRS 25.41/8.03 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 25.41/8.03 (2) CpxTRS 25.41/8.03 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 25.41/8.03 (4) CpxTRS 25.41/8.03 (5) CpxTrsMatchBoundsTAProof [FINISHED, 112 ms] 25.41/8.03 (6) BOUNDS(1, n^1) 25.41/8.03 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 25.41/8.03 (8) TRS for Loop Detection 25.41/8.03 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 25.41/8.03 (10) BEST 25.41/8.03 (11) proven lower bound 25.41/8.03 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 25.41/8.03 (13) BOUNDS(n^1, INF) 25.41/8.03 (14) TRS for Loop Detection 25.41/8.03 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (0) 25.41/8.03 Obligation: 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 25.41/8.03 active(sqr(0)) -> mark(0) 25.41/8.03 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 25.41/8.03 active(dbl(0)) -> mark(0) 25.41/8.03 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 25.41/8.03 active(add(0, X)) -> mark(X) 25.41/8.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 25.41/8.03 active(first(0, X)) -> mark(nil) 25.41/8.03 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 25.41/8.03 active(terms(X)) -> terms(active(X)) 25.41/8.03 active(cons(X1, X2)) -> cons(active(X1), X2) 25.41/8.03 active(recip(X)) -> recip(active(X)) 25.41/8.03 active(sqr(X)) -> sqr(active(X)) 25.41/8.03 active(add(X1, X2)) -> add(active(X1), X2) 25.41/8.03 active(add(X1, X2)) -> add(X1, active(X2)) 25.41/8.03 active(dbl(X)) -> dbl(active(X)) 25.41/8.03 active(first(X1, X2)) -> first(active(X1), X2) 25.41/8.03 active(first(X1, X2)) -> first(X1, active(X2)) 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(terms(X)) -> terms(proper(X)) 25.41/8.03 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 25.41/8.03 proper(recip(X)) -> recip(proper(X)) 25.41/8.03 proper(sqr(X)) -> sqr(proper(X)) 25.41/8.03 proper(s(X)) -> s(proper(X)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(add(X1, X2)) -> add(proper(X1), proper(X2)) 25.41/8.03 proper(dbl(X)) -> dbl(proper(X)) 25.41/8.03 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 25.41/8.03 The following defined symbols can occur below the 0th argument of top: proper, active 25.41/8.03 The following defined symbols can occur below the 0th argument of proper: proper, active 25.41/8.03 The following defined symbols can occur below the 0th argument of active: proper, active 25.41/8.03 25.41/8.03 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 25.41/8.03 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 25.41/8.03 active(sqr(0)) -> mark(0) 25.41/8.03 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 25.41/8.03 active(dbl(0)) -> mark(0) 25.41/8.03 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 25.41/8.03 active(add(0, X)) -> mark(X) 25.41/8.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 25.41/8.03 active(first(0, X)) -> mark(nil) 25.41/8.03 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 25.41/8.03 active(terms(X)) -> terms(active(X)) 25.41/8.03 active(cons(X1, X2)) -> cons(active(X1), X2) 25.41/8.03 active(recip(X)) -> recip(active(X)) 25.41/8.03 active(sqr(X)) -> sqr(active(X)) 25.41/8.03 active(add(X1, X2)) -> add(active(X1), X2) 25.41/8.03 active(add(X1, X2)) -> add(X1, active(X2)) 25.41/8.03 active(dbl(X)) -> dbl(active(X)) 25.41/8.03 active(first(X1, X2)) -> first(active(X1), X2) 25.41/8.03 active(first(X1, X2)) -> first(X1, active(X2)) 25.41/8.03 proper(terms(X)) -> terms(proper(X)) 25.41/8.03 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 25.41/8.03 proper(recip(X)) -> recip(proper(X)) 25.41/8.03 proper(sqr(X)) -> sqr(proper(X)) 25.41/8.03 proper(s(X)) -> s(proper(X)) 25.41/8.03 proper(add(X1, X2)) -> add(proper(X1), proper(X2)) 25.41/8.03 proper(dbl(X)) -> dbl(proper(X)) 25.41/8.03 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (2) 25.41/8.03 Obligation: 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 25.41/8.03 transformed relative TRS to TRS 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (4) 25.41/8.03 Obligation: 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (5) CpxTrsMatchBoundsTAProof (FINISHED) 25.41/8.03 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 25.41/8.03 25.41/8.03 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 25.41/8.03 final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 25.41/8.03 transitions: 25.41/8.03 mark0(0) -> 0 25.41/8.03 00() -> 0 25.41/8.03 ok0(0) -> 0 25.41/8.03 nil0() -> 0 25.41/8.03 active0(0) -> 0 25.41/8.03 terms0(0) -> 1 25.41/8.03 cons0(0, 0) -> 2 25.41/8.03 recip0(0) -> 3 25.41/8.03 sqr0(0) -> 4 25.41/8.03 add0(0, 0) -> 5 25.41/8.03 dbl0(0) -> 6 25.41/8.03 first0(0, 0) -> 7 25.41/8.03 proper0(0) -> 8 25.41/8.03 s0(0) -> 9 25.41/8.03 top0(0) -> 10 25.41/8.03 terms1(0) -> 11 25.41/8.03 mark1(11) -> 1 25.41/8.03 cons1(0, 0) -> 12 25.41/8.03 mark1(12) -> 2 25.41/8.03 recip1(0) -> 13 25.41/8.03 mark1(13) -> 3 25.41/8.03 sqr1(0) -> 14 25.41/8.03 mark1(14) -> 4 25.41/8.03 add1(0, 0) -> 15 25.41/8.03 mark1(15) -> 5 25.41/8.03 dbl1(0) -> 16 25.41/8.03 mark1(16) -> 6 25.41/8.03 first1(0, 0) -> 17 25.41/8.03 mark1(17) -> 7 25.41/8.03 01() -> 18 25.41/8.03 ok1(18) -> 8 25.41/8.03 nil1() -> 19 25.41/8.03 ok1(19) -> 8 25.41/8.03 terms1(0) -> 20 25.41/8.03 ok1(20) -> 1 25.41/8.03 cons1(0, 0) -> 21 25.41/8.03 ok1(21) -> 2 25.41/8.03 recip1(0) -> 22 25.41/8.03 ok1(22) -> 3 25.41/8.03 sqr1(0) -> 23 25.41/8.03 ok1(23) -> 4 25.41/8.03 s1(0) -> 24 25.41/8.03 ok1(24) -> 9 25.41/8.03 add1(0, 0) -> 25 25.41/8.03 ok1(25) -> 5 25.41/8.03 dbl1(0) -> 26 25.41/8.03 ok1(26) -> 6 25.41/8.03 first1(0, 0) -> 27 25.41/8.03 ok1(27) -> 7 25.41/8.03 proper1(0) -> 28 25.41/8.03 top1(28) -> 10 25.41/8.03 active1(0) -> 29 25.41/8.03 top1(29) -> 10 25.41/8.03 mark1(11) -> 11 25.41/8.03 mark1(11) -> 20 25.41/8.03 mark1(12) -> 12 25.41/8.03 mark1(12) -> 21 25.41/8.03 mark1(13) -> 13 25.41/8.03 mark1(13) -> 22 25.41/8.03 mark1(14) -> 14 25.41/8.03 mark1(14) -> 23 25.41/8.03 mark1(15) -> 15 25.41/8.03 mark1(15) -> 25 25.41/8.03 mark1(16) -> 16 25.41/8.03 mark1(16) -> 26 25.41/8.03 mark1(17) -> 17 25.41/8.03 mark1(17) -> 27 25.41/8.03 ok1(18) -> 28 25.41/8.03 ok1(19) -> 28 25.41/8.03 ok1(20) -> 11 25.41/8.03 ok1(20) -> 20 25.41/8.03 ok1(21) -> 12 25.41/8.03 ok1(21) -> 21 25.41/8.03 ok1(22) -> 13 25.41/8.03 ok1(22) -> 22 25.41/8.03 ok1(23) -> 14 25.41/8.03 ok1(23) -> 23 25.41/8.03 ok1(24) -> 24 25.41/8.03 ok1(25) -> 15 25.41/8.03 ok1(25) -> 25 25.41/8.03 ok1(26) -> 16 25.41/8.03 ok1(26) -> 26 25.41/8.03 ok1(27) -> 17 25.41/8.03 ok1(27) -> 27 25.41/8.03 active2(18) -> 30 25.41/8.03 top2(30) -> 10 25.41/8.03 active2(19) -> 30 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (6) 25.41/8.03 BOUNDS(1, n^1) 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 25.41/8.03 Transformed a relative TRS into a decreasing-loop problem. 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (8) 25.41/8.03 Obligation: 25.41/8.03 Analyzing the following TRS for decreasing loops: 25.41/8.03 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 25.41/8.03 active(sqr(0)) -> mark(0) 25.41/8.03 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 25.41/8.03 active(dbl(0)) -> mark(0) 25.41/8.03 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 25.41/8.03 active(add(0, X)) -> mark(X) 25.41/8.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 25.41/8.03 active(first(0, X)) -> mark(nil) 25.41/8.03 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 25.41/8.03 active(terms(X)) -> terms(active(X)) 25.41/8.03 active(cons(X1, X2)) -> cons(active(X1), X2) 25.41/8.03 active(recip(X)) -> recip(active(X)) 25.41/8.03 active(sqr(X)) -> sqr(active(X)) 25.41/8.03 active(add(X1, X2)) -> add(active(X1), X2) 25.41/8.03 active(add(X1, X2)) -> add(X1, active(X2)) 25.41/8.03 active(dbl(X)) -> dbl(active(X)) 25.41/8.03 active(first(X1, X2)) -> first(active(X1), X2) 25.41/8.03 active(first(X1, X2)) -> first(X1, active(X2)) 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(terms(X)) -> terms(proper(X)) 25.41/8.03 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 25.41/8.03 proper(recip(X)) -> recip(proper(X)) 25.41/8.03 proper(sqr(X)) -> sqr(proper(X)) 25.41/8.03 proper(s(X)) -> s(proper(X)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(add(X1, X2)) -> add(proper(X1), proper(X2)) 25.41/8.03 proper(dbl(X)) -> dbl(proper(X)) 25.41/8.03 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (9) DecreasingLoopProof (LOWER BOUND(ID)) 25.41/8.03 The following loop(s) give(s) rise to the lower bound Omega(n^1): 25.41/8.03 25.41/8.03 The rewrite sequence 25.41/8.03 25.41/8.03 terms(ok(X)) ->^+ ok(terms(X)) 25.41/8.03 25.41/8.03 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 25.41/8.03 25.41/8.03 The pumping substitution is [X / ok(X)]. 25.41/8.03 25.41/8.03 The result substitution is [ ]. 25.41/8.03 25.41/8.03 25.41/8.03 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (10) 25.41/8.03 Complex Obligation (BEST) 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (11) 25.41/8.03 Obligation: 25.41/8.03 Proved the lower bound n^1 for the following obligation: 25.41/8.03 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 25.41/8.03 active(sqr(0)) -> mark(0) 25.41/8.03 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 25.41/8.03 active(dbl(0)) -> mark(0) 25.41/8.03 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 25.41/8.03 active(add(0, X)) -> mark(X) 25.41/8.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 25.41/8.03 active(first(0, X)) -> mark(nil) 25.41/8.03 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 25.41/8.03 active(terms(X)) -> terms(active(X)) 25.41/8.03 active(cons(X1, X2)) -> cons(active(X1), X2) 25.41/8.03 active(recip(X)) -> recip(active(X)) 25.41/8.03 active(sqr(X)) -> sqr(active(X)) 25.41/8.03 active(add(X1, X2)) -> add(active(X1), X2) 25.41/8.03 active(add(X1, X2)) -> add(X1, active(X2)) 25.41/8.03 active(dbl(X)) -> dbl(active(X)) 25.41/8.03 active(first(X1, X2)) -> first(active(X1), X2) 25.41/8.03 active(first(X1, X2)) -> first(X1, active(X2)) 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(terms(X)) -> terms(proper(X)) 25.41/8.03 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 25.41/8.03 proper(recip(X)) -> recip(proper(X)) 25.41/8.03 proper(sqr(X)) -> sqr(proper(X)) 25.41/8.03 proper(s(X)) -> s(proper(X)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(add(X1, X2)) -> add(proper(X1), proper(X2)) 25.41/8.03 proper(dbl(X)) -> dbl(proper(X)) 25.41/8.03 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (12) LowerBoundPropagationProof (FINISHED) 25.41/8.03 Propagated lower bound. 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (13) 25.41/8.03 BOUNDS(n^1, INF) 25.41/8.03 25.41/8.03 ---------------------------------------- 25.41/8.03 25.41/8.03 (14) 25.41/8.03 Obligation: 25.41/8.03 Analyzing the following TRS for decreasing loops: 25.41/8.03 25.41/8.03 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 25.41/8.03 25.41/8.03 25.41/8.03 The TRS R consists of the following rules: 25.41/8.03 25.41/8.03 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 25.41/8.03 active(sqr(0)) -> mark(0) 25.41/8.03 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 25.41/8.03 active(dbl(0)) -> mark(0) 25.41/8.03 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 25.41/8.03 active(add(0, X)) -> mark(X) 25.41/8.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 25.41/8.03 active(first(0, X)) -> mark(nil) 25.41/8.03 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 25.41/8.03 active(terms(X)) -> terms(active(X)) 25.41/8.03 active(cons(X1, X2)) -> cons(active(X1), X2) 25.41/8.03 active(recip(X)) -> recip(active(X)) 25.41/8.03 active(sqr(X)) -> sqr(active(X)) 25.41/8.03 active(add(X1, X2)) -> add(active(X1), X2) 25.41/8.03 active(add(X1, X2)) -> add(X1, active(X2)) 25.41/8.03 active(dbl(X)) -> dbl(active(X)) 25.41/8.03 active(first(X1, X2)) -> first(active(X1), X2) 25.41/8.03 active(first(X1, X2)) -> first(X1, active(X2)) 25.41/8.03 terms(mark(X)) -> mark(terms(X)) 25.41/8.03 cons(mark(X1), X2) -> mark(cons(X1, X2)) 25.41/8.03 recip(mark(X)) -> mark(recip(X)) 25.41/8.03 sqr(mark(X)) -> mark(sqr(X)) 25.41/8.03 add(mark(X1), X2) -> mark(add(X1, X2)) 25.41/8.03 add(X1, mark(X2)) -> mark(add(X1, X2)) 25.41/8.03 dbl(mark(X)) -> mark(dbl(X)) 25.41/8.03 first(mark(X1), X2) -> mark(first(X1, X2)) 25.41/8.03 first(X1, mark(X2)) -> mark(first(X1, X2)) 25.41/8.03 proper(terms(X)) -> terms(proper(X)) 25.41/8.03 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 25.41/8.03 proper(recip(X)) -> recip(proper(X)) 25.41/8.03 proper(sqr(X)) -> sqr(proper(X)) 25.41/8.03 proper(s(X)) -> s(proper(X)) 25.41/8.03 proper(0) -> ok(0) 25.41/8.03 proper(add(X1, X2)) -> add(proper(X1), proper(X2)) 25.41/8.03 proper(dbl(X)) -> dbl(proper(X)) 25.41/8.03 proper(first(X1, X2)) -> first(proper(X1), proper(X2)) 25.41/8.03 proper(nil) -> ok(nil) 25.41/8.03 terms(ok(X)) -> ok(terms(X)) 25.41/8.03 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 25.41/8.03 recip(ok(X)) -> ok(recip(X)) 25.41/8.03 sqr(ok(X)) -> ok(sqr(X)) 25.41/8.03 s(ok(X)) -> ok(s(X)) 25.41/8.03 add(ok(X1), ok(X2)) -> ok(add(X1, X2)) 25.41/8.03 dbl(ok(X)) -> ok(dbl(X)) 25.41/8.03 first(ok(X1), ok(X2)) -> ok(first(X1, X2)) 25.41/8.03 top(mark(X)) -> top(proper(X)) 25.41/8.03 top(ok(X)) -> top(active(X)) 25.41/8.03 25.41/8.03 S is empty. 25.41/8.03 Rewrite Strategy: FULL 25.85/8.08 EOF