3.69/2.06 WORST_CASE(NON_POLY, ?) 3.69/2.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.69/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.69/2.07 3.69/2.07 3.69/2.07 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.69/2.07 3.69/2.07 (0) CpxTRS 3.69/2.07 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 3.69/2.07 (2) TRS for Loop Detection 3.69/2.07 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 3.69/2.07 (4) BEST 3.69/2.07 (5) proven lower bound 3.69/2.07 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 3.69/2.07 (7) BOUNDS(n^1, INF) 3.69/2.07 (8) TRS for Loop Detection 3.69/2.07 (9) DecreasingLoopProof [FINISHED, 72 ms] 3.69/2.07 (10) BOUNDS(EXP, INF) 3.69/2.07 3.69/2.07 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (0) 3.69/2.07 Obligation: 3.69/2.07 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.69/2.07 3.69/2.07 3.69/2.07 The TRS R consists of the following rules: 3.69/2.07 3.69/2.07 dbl(0) -> 0 3.69/2.07 dbl(s(X)) -> s(n__s(n__dbl(activate(X)))) 3.69/2.07 dbls(nil) -> nil 3.69/2.07 dbls(cons(X, Y)) -> cons(n__dbl(activate(X)), n__dbls(activate(Y))) 3.69/2.07 sel(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z)) 3.69/2.07 indx(nil, X) -> nil 3.69/2.07 indx(cons(X, Y), Z) -> cons(n__sel(activate(X), activate(Z)), n__indx(activate(Y), activate(Z))) 3.69/2.07 from(X) -> cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 dbl1(0) -> 01 3.69/2.07 dbl1(s(X)) -> s1(s1(dbl1(activate(X)))) 3.69/2.07 sel1(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel1(s(X), cons(Y, Z)) -> sel1(activate(X), activate(Z)) 3.69/2.07 quote(0) -> 01 3.69/2.07 quote(s(X)) -> s1(quote(activate(X))) 3.69/2.07 quote(dbl(X)) -> dbl1(X) 3.69/2.07 quote(sel(X, Y)) -> sel1(X, Y) 3.69/2.07 s(X) -> n__s(X) 3.69/2.07 dbl(X) -> n__dbl(X) 3.69/2.07 dbls(X) -> n__dbls(X) 3.69/2.07 sel(X1, X2) -> n__sel(X1, X2) 3.69/2.07 indx(X1, X2) -> n__indx(X1, X2) 3.69/2.07 from(X) -> n__from(X) 3.69/2.07 activate(n__s(X)) -> s(X) 3.69/2.07 activate(n__dbl(X)) -> dbl(activate(X)) 3.69/2.07 activate(n__dbls(X)) -> dbls(activate(X)) 3.69/2.07 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 3.69/2.07 activate(n__indx(X1, X2)) -> indx(activate(X1), X2) 3.69/2.07 activate(n__from(X)) -> from(X) 3.69/2.07 activate(X) -> X 3.69/2.07 3.69/2.07 S is empty. 3.69/2.07 Rewrite Strategy: FULL 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 3.69/2.07 Transformed a relative TRS into a decreasing-loop problem. 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (2) 3.69/2.07 Obligation: 3.69/2.07 Analyzing the following TRS for decreasing loops: 3.69/2.07 3.69/2.07 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.69/2.07 3.69/2.07 3.69/2.07 The TRS R consists of the following rules: 3.69/2.07 3.69/2.07 dbl(0) -> 0 3.69/2.07 dbl(s(X)) -> s(n__s(n__dbl(activate(X)))) 3.69/2.07 dbls(nil) -> nil 3.69/2.07 dbls(cons(X, Y)) -> cons(n__dbl(activate(X)), n__dbls(activate(Y))) 3.69/2.07 sel(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z)) 3.69/2.07 indx(nil, X) -> nil 3.69/2.07 indx(cons(X, Y), Z) -> cons(n__sel(activate(X), activate(Z)), n__indx(activate(Y), activate(Z))) 3.69/2.07 from(X) -> cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 dbl1(0) -> 01 3.69/2.07 dbl1(s(X)) -> s1(s1(dbl1(activate(X)))) 3.69/2.07 sel1(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel1(s(X), cons(Y, Z)) -> sel1(activate(X), activate(Z)) 3.69/2.07 quote(0) -> 01 3.69/2.07 quote(s(X)) -> s1(quote(activate(X))) 3.69/2.07 quote(dbl(X)) -> dbl1(X) 3.69/2.07 quote(sel(X, Y)) -> sel1(X, Y) 3.69/2.07 s(X) -> n__s(X) 3.69/2.07 dbl(X) -> n__dbl(X) 3.69/2.07 dbls(X) -> n__dbls(X) 3.69/2.07 sel(X1, X2) -> n__sel(X1, X2) 3.69/2.07 indx(X1, X2) -> n__indx(X1, X2) 3.69/2.07 from(X) -> n__from(X) 3.69/2.07 activate(n__s(X)) -> s(X) 3.69/2.07 activate(n__dbl(X)) -> dbl(activate(X)) 3.69/2.07 activate(n__dbls(X)) -> dbls(activate(X)) 3.69/2.07 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 3.69/2.07 activate(n__indx(X1, X2)) -> indx(activate(X1), X2) 3.69/2.07 activate(n__from(X)) -> from(X) 3.69/2.07 activate(X) -> X 3.69/2.07 3.69/2.07 S is empty. 3.69/2.07 Rewrite Strategy: FULL 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (3) DecreasingLoopProof (LOWER BOUND(ID)) 3.69/2.07 The following loop(s) give(s) rise to the lower bound Omega(n^1): 3.69/2.07 3.69/2.07 The rewrite sequence 3.69/2.07 3.69/2.07 activate(n__indx(X1, X2)) ->^+ indx(activate(X1), X2) 3.69/2.07 3.69/2.07 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 3.69/2.07 3.69/2.07 The pumping substitution is [X1 / n__indx(X1, X2)]. 3.69/2.07 3.69/2.07 The result substitution is [ ]. 3.69/2.07 3.69/2.07 3.69/2.07 3.69/2.07 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (4) 3.69/2.07 Complex Obligation (BEST) 3.69/2.07 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (5) 3.69/2.07 Obligation: 3.69/2.07 Proved the lower bound n^1 for the following obligation: 3.69/2.07 3.69/2.07 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.69/2.07 3.69/2.07 3.69/2.07 The TRS R consists of the following rules: 3.69/2.07 3.69/2.07 dbl(0) -> 0 3.69/2.07 dbl(s(X)) -> s(n__s(n__dbl(activate(X)))) 3.69/2.07 dbls(nil) -> nil 3.69/2.07 dbls(cons(X, Y)) -> cons(n__dbl(activate(X)), n__dbls(activate(Y))) 3.69/2.07 sel(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z)) 3.69/2.07 indx(nil, X) -> nil 3.69/2.07 indx(cons(X, Y), Z) -> cons(n__sel(activate(X), activate(Z)), n__indx(activate(Y), activate(Z))) 3.69/2.07 from(X) -> cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 dbl1(0) -> 01 3.69/2.07 dbl1(s(X)) -> s1(s1(dbl1(activate(X)))) 3.69/2.07 sel1(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel1(s(X), cons(Y, Z)) -> sel1(activate(X), activate(Z)) 3.69/2.07 quote(0) -> 01 3.69/2.07 quote(s(X)) -> s1(quote(activate(X))) 3.69/2.07 quote(dbl(X)) -> dbl1(X) 3.69/2.07 quote(sel(X, Y)) -> sel1(X, Y) 3.69/2.07 s(X) -> n__s(X) 3.69/2.07 dbl(X) -> n__dbl(X) 3.69/2.07 dbls(X) -> n__dbls(X) 3.69/2.07 sel(X1, X2) -> n__sel(X1, X2) 3.69/2.07 indx(X1, X2) -> n__indx(X1, X2) 3.69/2.07 from(X) -> n__from(X) 3.69/2.07 activate(n__s(X)) -> s(X) 3.69/2.07 activate(n__dbl(X)) -> dbl(activate(X)) 3.69/2.07 activate(n__dbls(X)) -> dbls(activate(X)) 3.69/2.07 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 3.69/2.07 activate(n__indx(X1, X2)) -> indx(activate(X1), X2) 3.69/2.07 activate(n__from(X)) -> from(X) 3.69/2.07 activate(X) -> X 3.69/2.07 3.69/2.07 S is empty. 3.69/2.07 Rewrite Strategy: FULL 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (6) LowerBoundPropagationProof (FINISHED) 3.69/2.07 Propagated lower bound. 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (7) 3.69/2.07 BOUNDS(n^1, INF) 3.69/2.07 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (8) 3.69/2.07 Obligation: 3.69/2.07 Analyzing the following TRS for decreasing loops: 3.69/2.07 3.69/2.07 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.69/2.07 3.69/2.07 3.69/2.07 The TRS R consists of the following rules: 3.69/2.07 3.69/2.07 dbl(0) -> 0 3.69/2.07 dbl(s(X)) -> s(n__s(n__dbl(activate(X)))) 3.69/2.07 dbls(nil) -> nil 3.69/2.07 dbls(cons(X, Y)) -> cons(n__dbl(activate(X)), n__dbls(activate(Y))) 3.69/2.07 sel(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel(s(X), cons(Y, Z)) -> sel(activate(X), activate(Z)) 3.69/2.07 indx(nil, X) -> nil 3.69/2.07 indx(cons(X, Y), Z) -> cons(n__sel(activate(X), activate(Z)), n__indx(activate(Y), activate(Z))) 3.69/2.07 from(X) -> cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 dbl1(0) -> 01 3.69/2.07 dbl1(s(X)) -> s1(s1(dbl1(activate(X)))) 3.69/2.07 sel1(0, cons(X, Y)) -> activate(X) 3.69/2.07 sel1(s(X), cons(Y, Z)) -> sel1(activate(X), activate(Z)) 3.69/2.07 quote(0) -> 01 3.69/2.07 quote(s(X)) -> s1(quote(activate(X))) 3.69/2.07 quote(dbl(X)) -> dbl1(X) 3.69/2.07 quote(sel(X, Y)) -> sel1(X, Y) 3.69/2.07 s(X) -> n__s(X) 3.69/2.07 dbl(X) -> n__dbl(X) 3.69/2.07 dbls(X) -> n__dbls(X) 3.69/2.07 sel(X1, X2) -> n__sel(X1, X2) 3.69/2.07 indx(X1, X2) -> n__indx(X1, X2) 3.69/2.07 from(X) -> n__from(X) 3.69/2.07 activate(n__s(X)) -> s(X) 3.69/2.07 activate(n__dbl(X)) -> dbl(activate(X)) 3.69/2.07 activate(n__dbls(X)) -> dbls(activate(X)) 3.69/2.07 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 3.69/2.07 activate(n__indx(X1, X2)) -> indx(activate(X1), X2) 3.69/2.07 activate(n__from(X)) -> from(X) 3.69/2.07 activate(X) -> X 3.69/2.07 3.69/2.07 S is empty. 3.69/2.07 Rewrite Strategy: FULL 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (9) DecreasingLoopProof (FINISHED) 3.69/2.07 The following loop(s) give(s) rise to the lower bound EXP: 3.69/2.07 3.69/2.07 The rewrite sequence 3.69/2.07 3.69/2.07 activate(n__from(X)) ->^+ cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 3.69/2.07 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 3.69/2.07 3.69/2.07 The pumping substitution is [X / n__from(X)]. 3.69/2.07 3.69/2.07 The result substitution is [ ]. 3.69/2.07 3.69/2.07 3.69/2.07 3.69/2.07 The rewrite sequence 3.69/2.07 3.69/2.07 activate(n__from(X)) ->^+ cons(activate(X), n__from(n__s(activate(X)))) 3.69/2.07 3.69/2.07 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0,0]. 3.69/2.07 3.69/2.07 The pumping substitution is [X / n__from(X)]. 3.69/2.07 3.69/2.07 The result substitution is [ ]. 3.69/2.07 3.69/2.07 3.69/2.07 3.69/2.07 3.69/2.07 ---------------------------------------- 3.69/2.07 3.69/2.07 (10) 3.69/2.07 BOUNDS(EXP, INF) 4.02/2.10 EOF