3.40/1.66 WORST_CASE(NON_POLY, ?) 3.40/1.67 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.40/1.67 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.40/1.67 3.40/1.67 3.40/1.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.40/1.67 3.40/1.67 (0) CpxTRS 3.40/1.67 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 3.40/1.67 (2) TRS for Loop Detection 3.40/1.67 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 3.40/1.67 (4) BEST 3.40/1.67 (5) proven lower bound 3.40/1.67 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 3.40/1.67 (7) BOUNDS(n^1, INF) 3.40/1.67 (8) TRS for Loop Detection 3.40/1.67 (9) DecreasingLoopProof [FINISHED, 0 ms] 3.40/1.67 (10) BOUNDS(EXP, INF) 3.40/1.67 3.40/1.67 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (0) 3.40/1.67 Obligation: 3.40/1.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.40/1.67 3.40/1.67 3.40/1.67 The TRS R consists of the following rules: 3.40/1.67 3.40/1.67 natsFrom(N) -> cons(N, n__natsFrom(n__s(N))) 3.40/1.67 fst(pair(XS, YS)) -> XS 3.40/1.67 snd(pair(XS, YS)) -> YS 3.40/1.67 splitAt(0, XS) -> pair(nil, XS) 3.40/1.67 splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS)) 3.40/1.67 u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS) 3.40/1.67 head(cons(N, XS)) -> N 3.40/1.67 tail(cons(N, XS)) -> activate(XS) 3.40/1.67 sel(N, XS) -> head(afterNth(N, XS)) 3.40/1.67 take(N, XS) -> fst(splitAt(N, XS)) 3.40/1.67 afterNth(N, XS) -> snd(splitAt(N, XS)) 3.40/1.67 natsFrom(X) -> n__natsFrom(X) 3.40/1.67 s(X) -> n__s(X) 3.40/1.67 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 3.40/1.67 activate(n__s(X)) -> s(activate(X)) 3.40/1.67 activate(X) -> X 3.40/1.67 3.40/1.67 S is empty. 3.40/1.67 Rewrite Strategy: FULL 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 3.40/1.67 Transformed a relative TRS into a decreasing-loop problem. 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (2) 3.40/1.67 Obligation: 3.40/1.67 Analyzing the following TRS for decreasing loops: 3.40/1.67 3.40/1.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.40/1.67 3.40/1.67 3.40/1.67 The TRS R consists of the following rules: 3.40/1.67 3.40/1.67 natsFrom(N) -> cons(N, n__natsFrom(n__s(N))) 3.40/1.67 fst(pair(XS, YS)) -> XS 3.40/1.67 snd(pair(XS, YS)) -> YS 3.40/1.67 splitAt(0, XS) -> pair(nil, XS) 3.40/1.67 splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS)) 3.40/1.67 u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS) 3.40/1.67 head(cons(N, XS)) -> N 3.40/1.67 tail(cons(N, XS)) -> activate(XS) 3.40/1.67 sel(N, XS) -> head(afterNth(N, XS)) 3.40/1.67 take(N, XS) -> fst(splitAt(N, XS)) 3.40/1.67 afterNth(N, XS) -> snd(splitAt(N, XS)) 3.40/1.67 natsFrom(X) -> n__natsFrom(X) 3.40/1.67 s(X) -> n__s(X) 3.40/1.67 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 3.40/1.67 activate(n__s(X)) -> s(activate(X)) 3.40/1.67 activate(X) -> X 3.40/1.67 3.40/1.67 S is empty. 3.40/1.67 Rewrite Strategy: FULL 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (3) DecreasingLoopProof (LOWER BOUND(ID)) 3.40/1.67 The following loop(s) give(s) rise to the lower bound Omega(n^1): 3.40/1.67 3.40/1.67 The rewrite sequence 3.40/1.67 3.40/1.67 activate(n__s(X)) ->^+ s(activate(X)) 3.40/1.67 3.40/1.67 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 3.40/1.67 3.40/1.67 The pumping substitution is [X / n__s(X)]. 3.40/1.67 3.40/1.67 The result substitution is [ ]. 3.40/1.67 3.40/1.67 3.40/1.67 3.40/1.67 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (4) 3.40/1.67 Complex Obligation (BEST) 3.40/1.67 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (5) 3.40/1.67 Obligation: 3.40/1.67 Proved the lower bound n^1 for the following obligation: 3.40/1.67 3.40/1.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.40/1.67 3.40/1.67 3.40/1.67 The TRS R consists of the following rules: 3.40/1.67 3.40/1.67 natsFrom(N) -> cons(N, n__natsFrom(n__s(N))) 3.40/1.67 fst(pair(XS, YS)) -> XS 3.40/1.67 snd(pair(XS, YS)) -> YS 3.40/1.67 splitAt(0, XS) -> pair(nil, XS) 3.40/1.67 splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS)) 3.40/1.67 u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS) 3.40/1.67 head(cons(N, XS)) -> N 3.40/1.67 tail(cons(N, XS)) -> activate(XS) 3.40/1.67 sel(N, XS) -> head(afterNth(N, XS)) 3.40/1.67 take(N, XS) -> fst(splitAt(N, XS)) 3.40/1.67 afterNth(N, XS) -> snd(splitAt(N, XS)) 3.40/1.67 natsFrom(X) -> n__natsFrom(X) 3.40/1.67 s(X) -> n__s(X) 3.40/1.67 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 3.40/1.67 activate(n__s(X)) -> s(activate(X)) 3.40/1.67 activate(X) -> X 3.40/1.67 3.40/1.67 S is empty. 3.40/1.67 Rewrite Strategy: FULL 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (6) LowerBoundPropagationProof (FINISHED) 3.40/1.67 Propagated lower bound. 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (7) 3.40/1.67 BOUNDS(n^1, INF) 3.40/1.67 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (8) 3.40/1.67 Obligation: 3.40/1.67 Analyzing the following TRS for decreasing loops: 3.40/1.67 3.40/1.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 3.40/1.67 3.40/1.67 3.40/1.67 The TRS R consists of the following rules: 3.40/1.67 3.40/1.67 natsFrom(N) -> cons(N, n__natsFrom(n__s(N))) 3.40/1.67 fst(pair(XS, YS)) -> XS 3.40/1.67 snd(pair(XS, YS)) -> YS 3.40/1.67 splitAt(0, XS) -> pair(nil, XS) 3.40/1.67 splitAt(s(N), cons(X, XS)) -> u(splitAt(N, activate(XS)), N, X, activate(XS)) 3.40/1.67 u(pair(YS, ZS), N, X, XS) -> pair(cons(activate(X), YS), ZS) 3.40/1.67 head(cons(N, XS)) -> N 3.40/1.67 tail(cons(N, XS)) -> activate(XS) 3.40/1.67 sel(N, XS) -> head(afterNth(N, XS)) 3.40/1.67 take(N, XS) -> fst(splitAt(N, XS)) 3.40/1.67 afterNth(N, XS) -> snd(splitAt(N, XS)) 3.40/1.67 natsFrom(X) -> n__natsFrom(X) 3.40/1.67 s(X) -> n__s(X) 3.40/1.67 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 3.40/1.67 activate(n__s(X)) -> s(activate(X)) 3.40/1.67 activate(X) -> X 3.40/1.67 3.40/1.67 S is empty. 3.40/1.67 Rewrite Strategy: FULL 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (9) DecreasingLoopProof (FINISHED) 3.40/1.67 The following loop(s) give(s) rise to the lower bound EXP: 3.40/1.67 3.40/1.67 The rewrite sequence 3.40/1.67 3.40/1.67 activate(n__natsFrom(X)) ->^+ cons(activate(X), n__natsFrom(n__s(activate(X)))) 3.40/1.67 3.40/1.67 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 3.40/1.67 3.40/1.67 The pumping substitution is [X / n__natsFrom(X)]. 3.40/1.67 3.40/1.67 The result substitution is [ ]. 3.40/1.67 3.40/1.67 3.40/1.67 3.40/1.67 The rewrite sequence 3.40/1.67 3.40/1.67 activate(n__natsFrom(X)) ->^+ cons(activate(X), n__natsFrom(n__s(activate(X)))) 3.40/1.67 3.40/1.67 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0,0]. 3.40/1.67 3.40/1.67 The pumping substitution is [X / n__natsFrom(X)]. 3.40/1.67 3.40/1.67 The result substitution is [ ]. 3.40/1.67 3.40/1.67 3.40/1.67 3.40/1.67 3.40/1.67 ---------------------------------------- 3.40/1.67 3.40/1.67 (10) 3.40/1.67 BOUNDS(EXP, INF) 3.40/1.72 EOF