1034.98/263.39 WORST_CASE(NON_POLY, ?) 1035.51/263.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1035.51/263.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1035.51/263.48 1035.51/263.48 1035.51/263.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 1035.51/263.48 1035.51/263.48 (0) CpxTRS 1035.51/263.48 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1035.51/263.48 (2) TRS for Loop Detection 1035.51/263.48 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1035.51/263.48 (4) BEST 1035.51/263.48 (5) proven lower bound 1035.51/263.48 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1035.51/263.48 (7) BOUNDS(n^1, INF) 1035.51/263.48 (8) TRS for Loop Detection 1035.51/263.48 (9) InfiniteLowerBoundProof [FINISHED, 145.2 s] 1035.51/263.48 (10) BOUNDS(INF, INF) 1035.51/263.48 1035.51/263.48 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (0) 1035.51/263.48 Obligation: 1035.51/263.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 1035.51/263.48 1035.51/263.48 1035.51/263.48 The TRS R consists of the following rules: 1035.51/263.48 1035.51/263.48 zeros -> cons(0, n__zeros) 1035.51/263.48 U11(tt, L) -> U12(tt, activate(L)) 1035.51/263.48 U12(tt, L) -> s(length(activate(L))) 1035.51/263.48 U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) 1035.51/263.48 length(nil) -> 0 1035.51/263.48 length(cons(N, L)) -> U11(tt, activate(L)) 1035.51/263.48 take(0, IL) -> nil 1035.51/263.48 take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) 1035.51/263.48 zeros -> n__zeros 1035.51/263.48 take(X1, X2) -> n__take(X1, X2) 1035.51/263.48 activate(n__zeros) -> zeros 1035.51/263.48 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 1035.51/263.48 activate(X) -> X 1035.51/263.48 1035.51/263.48 S is empty. 1035.51/263.48 Rewrite Strategy: FULL 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1035.51/263.48 Transformed a relative TRS into a decreasing-loop problem. 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (2) 1035.51/263.48 Obligation: 1035.51/263.48 Analyzing the following TRS for decreasing loops: 1035.51/263.48 1035.51/263.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 1035.51/263.48 1035.51/263.48 1035.51/263.48 The TRS R consists of the following rules: 1035.51/263.48 1035.51/263.48 zeros -> cons(0, n__zeros) 1035.51/263.48 U11(tt, L) -> U12(tt, activate(L)) 1035.51/263.48 U12(tt, L) -> s(length(activate(L))) 1035.51/263.48 U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) 1035.51/263.48 length(nil) -> 0 1035.51/263.48 length(cons(N, L)) -> U11(tt, activate(L)) 1035.51/263.48 take(0, IL) -> nil 1035.51/263.48 take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) 1035.51/263.48 zeros -> n__zeros 1035.51/263.48 take(X1, X2) -> n__take(X1, X2) 1035.51/263.48 activate(n__zeros) -> zeros 1035.51/263.48 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 1035.51/263.48 activate(X) -> X 1035.51/263.48 1035.51/263.48 S is empty. 1035.51/263.48 Rewrite Strategy: FULL 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1035.51/263.48 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1035.51/263.48 1035.51/263.48 The rewrite sequence 1035.51/263.48 1035.51/263.48 activate(n__take(X1, X2)) ->^+ take(activate(X1), activate(X2)) 1035.51/263.48 1035.51/263.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1035.51/263.48 1035.51/263.48 The pumping substitution is [X1 / n__take(X1, X2)]. 1035.51/263.48 1035.51/263.48 The result substitution is [ ]. 1035.51/263.48 1035.51/263.48 1035.51/263.48 1035.51/263.48 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (4) 1035.51/263.48 Complex Obligation (BEST) 1035.51/263.48 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (5) 1035.51/263.48 Obligation: 1035.51/263.48 Proved the lower bound n^1 for the following obligation: 1035.51/263.48 1035.51/263.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 1035.51/263.48 1035.51/263.48 1035.51/263.48 The TRS R consists of the following rules: 1035.51/263.48 1035.51/263.48 zeros -> cons(0, n__zeros) 1035.51/263.48 U11(tt, L) -> U12(tt, activate(L)) 1035.51/263.48 U12(tt, L) -> s(length(activate(L))) 1035.51/263.48 U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) 1035.51/263.48 length(nil) -> 0 1035.51/263.48 length(cons(N, L)) -> U11(tt, activate(L)) 1035.51/263.48 take(0, IL) -> nil 1035.51/263.48 take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) 1035.51/263.48 zeros -> n__zeros 1035.51/263.48 take(X1, X2) -> n__take(X1, X2) 1035.51/263.48 activate(n__zeros) -> zeros 1035.51/263.48 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 1035.51/263.48 activate(X) -> X 1035.51/263.48 1035.51/263.48 S is empty. 1035.51/263.48 Rewrite Strategy: FULL 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (6) LowerBoundPropagationProof (FINISHED) 1035.51/263.48 Propagated lower bound. 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (7) 1035.51/263.48 BOUNDS(n^1, INF) 1035.51/263.48 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (8) 1035.51/263.48 Obligation: 1035.51/263.48 Analyzing the following TRS for decreasing loops: 1035.51/263.48 1035.51/263.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 1035.51/263.48 1035.51/263.48 1035.51/263.48 The TRS R consists of the following rules: 1035.51/263.48 1035.51/263.48 zeros -> cons(0, n__zeros) 1035.51/263.48 U11(tt, L) -> U12(tt, activate(L)) 1035.51/263.48 U12(tt, L) -> s(length(activate(L))) 1035.51/263.48 U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N)) 1035.51/263.48 U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL))) 1035.51/263.48 length(nil) -> 0 1035.51/263.48 length(cons(N, L)) -> U11(tt, activate(L)) 1035.51/263.48 take(0, IL) -> nil 1035.51/263.48 take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N) 1035.51/263.48 zeros -> n__zeros 1035.51/263.48 take(X1, X2) -> n__take(X1, X2) 1035.51/263.48 activate(n__zeros) -> zeros 1035.51/263.48 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 1035.51/263.48 activate(X) -> X 1035.51/263.48 1035.51/263.48 S is empty. 1035.51/263.48 Rewrite Strategy: FULL 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (9) InfiniteLowerBoundProof (FINISHED) 1035.51/263.48 The following loop proves infinite runtime complexity: 1035.51/263.48 1035.51/263.48 The rewrite sequence 1035.51/263.48 1035.51/263.48 length(cons(N, n__zeros)) ->^+ s(length(cons(0, n__zeros))) 1035.51/263.48 1035.51/263.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1035.51/263.48 1035.51/263.48 The pumping substitution is [ ]. 1035.51/263.48 1035.51/263.48 The result substitution is [N / 0]. 1035.51/263.48 1035.51/263.48 1035.51/263.48 1035.51/263.48 1035.51/263.48 ---------------------------------------- 1035.51/263.48 1035.51/263.48 (10) 1035.51/263.48 BOUNDS(INF, INF) 1035.51/263.56 EOF