5.71/2.28 WORST_CASE(NON_POLY, ?) 5.71/2.31 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.71/2.31 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.71/2.31 5.71/2.31 5.71/2.31 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.71/2.31 5.71/2.31 (0) CpxTRS 5.71/2.31 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 5.71/2.31 (2) TRS for Loop Detection 5.71/2.31 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 5.71/2.31 (4) BEST 5.71/2.31 (5) proven lower bound 5.71/2.31 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 5.71/2.31 (7) BOUNDS(n^1, INF) 5.71/2.31 (8) TRS for Loop Detection 5.71/2.31 (9) DecreasingLoopProof [FINISHED, 408 ms] 5.71/2.31 (10) BOUNDS(EXP, INF) 5.71/2.31 5.71/2.31 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (0) 5.71/2.31 Obligation: 5.71/2.31 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.71/2.31 5.71/2.31 5.71/2.31 The TRS R consists of the following rules: 5.71/2.31 5.71/2.31 U101(tt, V2) -> U102(isLNat(activate(V2))) 5.71/2.31 U102(tt) -> tt 5.71/2.31 U11(tt, N, XS) -> U12(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U111(tt) -> tt 5.71/2.31 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 5.71/2.31 U121(tt) -> tt 5.71/2.31 U131(tt, V2) -> U132(isLNat(activate(V2))) 5.71/2.31 U132(tt) -> tt 5.71/2.31 U141(tt, V2) -> U142(isLNat(activate(V2))) 5.71/2.31 U142(tt) -> tt 5.71/2.31 U151(tt, V2) -> U152(isLNat(activate(V2))) 5.71/2.31 U152(tt) -> tt 5.71/2.31 U161(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 5.71/2.31 U171(tt, N, XS) -> U172(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U172(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 5.71/2.31 U181(tt, Y) -> U182(isLNat(activate(Y)), activate(Y)) 5.71/2.31 U182(tt, Y) -> activate(Y) 5.71/2.31 U191(tt, XS) -> pair(nil, activate(XS)) 5.71/2.31 U201(tt, N, X, XS) -> U202(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 5.71/2.31 U202(tt, N, X, XS) -> U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 5.71/2.31 U203(tt, N, X, XS) -> U204(splitAt(activate(N), activate(XS)), activate(X)) 5.71/2.31 U204(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 5.71/2.31 U21(tt, X, Y) -> U22(isLNat(activate(Y)), activate(X)) 5.71/2.31 U211(tt, XS) -> U212(isLNat(activate(XS)), activate(XS)) 5.71/2.31 U212(tt, XS) -> activate(XS) 5.71/2.31 U22(tt, X) -> activate(X) 5.71/2.31 U221(tt, N, XS) -> U222(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U222(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 5.71/2.31 U31(tt, N, XS) -> U32(isLNat(activate(XS)), activate(N)) 5.71/2.31 U32(tt, N) -> activate(N) 5.71/2.31 U41(tt, V2) -> U42(isLNat(activate(V2))) 5.71/2.31 U42(tt) -> tt 5.71/2.31 U51(tt, V2) -> U52(isLNat(activate(V2))) 5.71/2.31 U52(tt) -> tt 5.71/2.31 U61(tt) -> tt 5.71/2.31 U71(tt) -> tt 5.71/2.31 U81(tt) -> tt 5.71/2.31 U91(tt) -> tt 5.71/2.31 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.71/2.31 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.71/2.31 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 5.71/2.31 isLNat(n__nil) -> tt 5.71/2.31 isLNat(n__afterNth(V1, V2)) -> U41(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__cons(V1, V2)) -> U51(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__fst(V1)) -> U61(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__natsFrom(V1)) -> U71(isNatural(activate(V1))) 5.71/2.31 isLNat(n__snd(V1)) -> U81(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__tail(V1)) -> U91(isLNat(activate(V1))) 5.71/2.31 isLNat(n__take(V1, V2)) -> U101(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isNatural(n__0) -> tt 5.71/2.31 isNatural(n__head(V1)) -> U111(isLNat(activate(V1))) 5.71/2.31 isNatural(n__s(V1)) -> U121(isNatural(activate(V1))) 5.71/2.31 isNatural(n__sel(V1, V2)) -> U131(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__pair(V1, V2)) -> U141(isLNat(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__splitAt(V1, V2)) -> U151(isNatural(activate(V1)), activate(V2)) 5.71/2.31 natsFrom(N) -> U161(isNatural(N), N) 5.71/2.31 sel(N, XS) -> U171(isNatural(N), N, XS) 5.71/2.31 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.71/2.31 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.71/2.31 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, activate(XS)) 5.71/2.31 tail(cons(N, XS)) -> U211(isNatural(N), activate(XS)) 5.71/2.31 take(N, XS) -> U221(isNatural(N), N, XS) 5.71/2.31 natsFrom(X) -> n__natsFrom(X) 5.71/2.31 s(X) -> n__s(X) 5.71/2.31 nil -> n__nil 5.71/2.31 afterNth(X1, X2) -> n__afterNth(X1, X2) 5.71/2.31 cons(X1, X2) -> n__cons(X1, X2) 5.71/2.31 fst(X) -> n__fst(X) 5.71/2.31 snd(X) -> n__snd(X) 5.71/2.31 tail(X) -> n__tail(X) 5.71/2.31 take(X1, X2) -> n__take(X1, X2) 5.71/2.31 0 -> n__0 5.71/2.31 head(X) -> n__head(X) 5.71/2.31 sel(X1, X2) -> n__sel(X1, X2) 5.71/2.31 pair(X1, X2) -> n__pair(X1, X2) 5.71/2.31 splitAt(X1, X2) -> n__splitAt(X1, X2) 5.71/2.31 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 5.71/2.31 activate(n__s(X)) -> s(activate(X)) 5.71/2.31 activate(n__nil) -> nil 5.71/2.31 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 5.71/2.31 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 5.71/2.31 activate(n__fst(X)) -> fst(activate(X)) 5.71/2.31 activate(n__snd(X)) -> snd(activate(X)) 5.71/2.31 activate(n__tail(X)) -> tail(activate(X)) 5.71/2.31 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 5.71/2.31 activate(n__0) -> 0 5.71/2.31 activate(n__head(X)) -> head(activate(X)) 5.71/2.31 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 5.71/2.31 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 5.71/2.31 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 5.71/2.31 activate(X) -> X 5.71/2.31 5.71/2.31 S is empty. 5.71/2.31 Rewrite Strategy: FULL 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 5.71/2.31 Transformed a relative TRS into a decreasing-loop problem. 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (2) 5.71/2.31 Obligation: 5.71/2.31 Analyzing the following TRS for decreasing loops: 5.71/2.31 5.71/2.31 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.71/2.31 5.71/2.31 5.71/2.31 The TRS R consists of the following rules: 5.71/2.31 5.71/2.31 U101(tt, V2) -> U102(isLNat(activate(V2))) 5.71/2.31 U102(tt) -> tt 5.71/2.31 U11(tt, N, XS) -> U12(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U111(tt) -> tt 5.71/2.31 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 5.71/2.31 U121(tt) -> tt 5.71/2.31 U131(tt, V2) -> U132(isLNat(activate(V2))) 5.71/2.31 U132(tt) -> tt 5.71/2.31 U141(tt, V2) -> U142(isLNat(activate(V2))) 5.71/2.31 U142(tt) -> tt 5.71/2.31 U151(tt, V2) -> U152(isLNat(activate(V2))) 5.71/2.31 U152(tt) -> tt 5.71/2.31 U161(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 5.71/2.31 U171(tt, N, XS) -> U172(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U172(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 5.71/2.31 U181(tt, Y) -> U182(isLNat(activate(Y)), activate(Y)) 5.71/2.31 U182(tt, Y) -> activate(Y) 5.71/2.31 U191(tt, XS) -> pair(nil, activate(XS)) 5.71/2.31 U201(tt, N, X, XS) -> U202(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 5.71/2.31 U202(tt, N, X, XS) -> U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 5.71/2.31 U203(tt, N, X, XS) -> U204(splitAt(activate(N), activate(XS)), activate(X)) 5.71/2.31 U204(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 5.71/2.31 U21(tt, X, Y) -> U22(isLNat(activate(Y)), activate(X)) 5.71/2.31 U211(tt, XS) -> U212(isLNat(activate(XS)), activate(XS)) 5.71/2.31 U212(tt, XS) -> activate(XS) 5.71/2.31 U22(tt, X) -> activate(X) 5.71/2.31 U221(tt, N, XS) -> U222(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U222(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 5.71/2.31 U31(tt, N, XS) -> U32(isLNat(activate(XS)), activate(N)) 5.71/2.31 U32(tt, N) -> activate(N) 5.71/2.31 U41(tt, V2) -> U42(isLNat(activate(V2))) 5.71/2.31 U42(tt) -> tt 5.71/2.31 U51(tt, V2) -> U52(isLNat(activate(V2))) 5.71/2.31 U52(tt) -> tt 5.71/2.31 U61(tt) -> tt 5.71/2.31 U71(tt) -> tt 5.71/2.31 U81(tt) -> tt 5.71/2.31 U91(tt) -> tt 5.71/2.31 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.71/2.31 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.71/2.31 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 5.71/2.31 isLNat(n__nil) -> tt 5.71/2.31 isLNat(n__afterNth(V1, V2)) -> U41(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__cons(V1, V2)) -> U51(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__fst(V1)) -> U61(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__natsFrom(V1)) -> U71(isNatural(activate(V1))) 5.71/2.31 isLNat(n__snd(V1)) -> U81(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__tail(V1)) -> U91(isLNat(activate(V1))) 5.71/2.31 isLNat(n__take(V1, V2)) -> U101(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isNatural(n__0) -> tt 5.71/2.31 isNatural(n__head(V1)) -> U111(isLNat(activate(V1))) 5.71/2.31 isNatural(n__s(V1)) -> U121(isNatural(activate(V1))) 5.71/2.31 isNatural(n__sel(V1, V2)) -> U131(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__pair(V1, V2)) -> U141(isLNat(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__splitAt(V1, V2)) -> U151(isNatural(activate(V1)), activate(V2)) 5.71/2.31 natsFrom(N) -> U161(isNatural(N), N) 5.71/2.31 sel(N, XS) -> U171(isNatural(N), N, XS) 5.71/2.31 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.71/2.31 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.71/2.31 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, activate(XS)) 5.71/2.31 tail(cons(N, XS)) -> U211(isNatural(N), activate(XS)) 5.71/2.31 take(N, XS) -> U221(isNatural(N), N, XS) 5.71/2.31 natsFrom(X) -> n__natsFrom(X) 5.71/2.31 s(X) -> n__s(X) 5.71/2.31 nil -> n__nil 5.71/2.31 afterNth(X1, X2) -> n__afterNth(X1, X2) 5.71/2.31 cons(X1, X2) -> n__cons(X1, X2) 5.71/2.31 fst(X) -> n__fst(X) 5.71/2.31 snd(X) -> n__snd(X) 5.71/2.31 tail(X) -> n__tail(X) 5.71/2.31 take(X1, X2) -> n__take(X1, X2) 5.71/2.31 0 -> n__0 5.71/2.31 head(X) -> n__head(X) 5.71/2.31 sel(X1, X2) -> n__sel(X1, X2) 5.71/2.31 pair(X1, X2) -> n__pair(X1, X2) 5.71/2.31 splitAt(X1, X2) -> n__splitAt(X1, X2) 5.71/2.31 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 5.71/2.31 activate(n__s(X)) -> s(activate(X)) 5.71/2.31 activate(n__nil) -> nil 5.71/2.31 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 5.71/2.31 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 5.71/2.31 activate(n__fst(X)) -> fst(activate(X)) 5.71/2.31 activate(n__snd(X)) -> snd(activate(X)) 5.71/2.31 activate(n__tail(X)) -> tail(activate(X)) 5.71/2.31 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 5.71/2.31 activate(n__0) -> 0 5.71/2.31 activate(n__head(X)) -> head(activate(X)) 5.71/2.31 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 5.71/2.31 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 5.71/2.31 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 5.71/2.31 activate(X) -> X 5.71/2.31 5.71/2.31 S is empty. 5.71/2.31 Rewrite Strategy: FULL 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (3) DecreasingLoopProof (LOWER BOUND(ID)) 5.71/2.31 The following loop(s) give(s) rise to the lower bound Omega(n^1): 5.71/2.31 5.71/2.31 The rewrite sequence 5.71/2.31 5.71/2.31 activate(n__snd(X)) ->^+ snd(activate(X)) 5.71/2.31 5.71/2.31 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 5.71/2.31 5.71/2.31 The pumping substitution is [X / n__snd(X)]. 5.71/2.31 5.71/2.31 The result substitution is [ ]. 5.71/2.31 5.71/2.31 5.71/2.31 5.71/2.31 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (4) 5.71/2.31 Complex Obligation (BEST) 5.71/2.31 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (5) 5.71/2.31 Obligation: 5.71/2.31 Proved the lower bound n^1 for the following obligation: 5.71/2.31 5.71/2.31 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.71/2.31 5.71/2.31 5.71/2.31 The TRS R consists of the following rules: 5.71/2.31 5.71/2.31 U101(tt, V2) -> U102(isLNat(activate(V2))) 5.71/2.31 U102(tt) -> tt 5.71/2.31 U11(tt, N, XS) -> U12(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U111(tt) -> tt 5.71/2.31 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 5.71/2.31 U121(tt) -> tt 5.71/2.31 U131(tt, V2) -> U132(isLNat(activate(V2))) 5.71/2.31 U132(tt) -> tt 5.71/2.31 U141(tt, V2) -> U142(isLNat(activate(V2))) 5.71/2.31 U142(tt) -> tt 5.71/2.31 U151(tt, V2) -> U152(isLNat(activate(V2))) 5.71/2.31 U152(tt) -> tt 5.71/2.31 U161(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 5.71/2.31 U171(tt, N, XS) -> U172(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U172(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 5.71/2.31 U181(tt, Y) -> U182(isLNat(activate(Y)), activate(Y)) 5.71/2.31 U182(tt, Y) -> activate(Y) 5.71/2.31 U191(tt, XS) -> pair(nil, activate(XS)) 5.71/2.31 U201(tt, N, X, XS) -> U202(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 5.71/2.31 U202(tt, N, X, XS) -> U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 5.71/2.31 U203(tt, N, X, XS) -> U204(splitAt(activate(N), activate(XS)), activate(X)) 5.71/2.31 U204(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 5.71/2.31 U21(tt, X, Y) -> U22(isLNat(activate(Y)), activate(X)) 5.71/2.31 U211(tt, XS) -> U212(isLNat(activate(XS)), activate(XS)) 5.71/2.31 U212(tt, XS) -> activate(XS) 5.71/2.31 U22(tt, X) -> activate(X) 5.71/2.31 U221(tt, N, XS) -> U222(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U222(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 5.71/2.31 U31(tt, N, XS) -> U32(isLNat(activate(XS)), activate(N)) 5.71/2.31 U32(tt, N) -> activate(N) 5.71/2.31 U41(tt, V2) -> U42(isLNat(activate(V2))) 5.71/2.31 U42(tt) -> tt 5.71/2.31 U51(tt, V2) -> U52(isLNat(activate(V2))) 5.71/2.31 U52(tt) -> tt 5.71/2.31 U61(tt) -> tt 5.71/2.31 U71(tt) -> tt 5.71/2.31 U81(tt) -> tt 5.71/2.31 U91(tt) -> tt 5.71/2.31 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.71/2.31 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.71/2.31 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 5.71/2.31 isLNat(n__nil) -> tt 5.71/2.31 isLNat(n__afterNth(V1, V2)) -> U41(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__cons(V1, V2)) -> U51(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__fst(V1)) -> U61(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__natsFrom(V1)) -> U71(isNatural(activate(V1))) 5.71/2.31 isLNat(n__snd(V1)) -> U81(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__tail(V1)) -> U91(isLNat(activate(V1))) 5.71/2.31 isLNat(n__take(V1, V2)) -> U101(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isNatural(n__0) -> tt 5.71/2.31 isNatural(n__head(V1)) -> U111(isLNat(activate(V1))) 5.71/2.31 isNatural(n__s(V1)) -> U121(isNatural(activate(V1))) 5.71/2.31 isNatural(n__sel(V1, V2)) -> U131(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__pair(V1, V2)) -> U141(isLNat(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__splitAt(V1, V2)) -> U151(isNatural(activate(V1)), activate(V2)) 5.71/2.31 natsFrom(N) -> U161(isNatural(N), N) 5.71/2.31 sel(N, XS) -> U171(isNatural(N), N, XS) 5.71/2.31 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.71/2.31 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.71/2.31 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, activate(XS)) 5.71/2.31 tail(cons(N, XS)) -> U211(isNatural(N), activate(XS)) 5.71/2.31 take(N, XS) -> U221(isNatural(N), N, XS) 5.71/2.31 natsFrom(X) -> n__natsFrom(X) 5.71/2.31 s(X) -> n__s(X) 5.71/2.31 nil -> n__nil 5.71/2.31 afterNth(X1, X2) -> n__afterNth(X1, X2) 5.71/2.31 cons(X1, X2) -> n__cons(X1, X2) 5.71/2.31 fst(X) -> n__fst(X) 5.71/2.31 snd(X) -> n__snd(X) 5.71/2.31 tail(X) -> n__tail(X) 5.71/2.31 take(X1, X2) -> n__take(X1, X2) 5.71/2.31 0 -> n__0 5.71/2.31 head(X) -> n__head(X) 5.71/2.31 sel(X1, X2) -> n__sel(X1, X2) 5.71/2.31 pair(X1, X2) -> n__pair(X1, X2) 5.71/2.31 splitAt(X1, X2) -> n__splitAt(X1, X2) 5.71/2.31 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 5.71/2.31 activate(n__s(X)) -> s(activate(X)) 5.71/2.31 activate(n__nil) -> nil 5.71/2.31 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 5.71/2.31 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 5.71/2.31 activate(n__fst(X)) -> fst(activate(X)) 5.71/2.31 activate(n__snd(X)) -> snd(activate(X)) 5.71/2.31 activate(n__tail(X)) -> tail(activate(X)) 5.71/2.31 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 5.71/2.31 activate(n__0) -> 0 5.71/2.31 activate(n__head(X)) -> head(activate(X)) 5.71/2.31 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 5.71/2.31 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 5.71/2.31 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 5.71/2.31 activate(X) -> X 5.71/2.31 5.71/2.31 S is empty. 5.71/2.31 Rewrite Strategy: FULL 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (6) LowerBoundPropagationProof (FINISHED) 5.71/2.31 Propagated lower bound. 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (7) 5.71/2.31 BOUNDS(n^1, INF) 5.71/2.31 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (8) 5.71/2.31 Obligation: 5.71/2.31 Analyzing the following TRS for decreasing loops: 5.71/2.31 5.71/2.31 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.71/2.31 5.71/2.31 5.71/2.31 The TRS R consists of the following rules: 5.71/2.31 5.71/2.31 U101(tt, V2) -> U102(isLNat(activate(V2))) 5.71/2.31 U102(tt) -> tt 5.71/2.31 U11(tt, N, XS) -> U12(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U111(tt) -> tt 5.71/2.31 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 5.71/2.31 U121(tt) -> tt 5.71/2.31 U131(tt, V2) -> U132(isLNat(activate(V2))) 5.71/2.31 U132(tt) -> tt 5.71/2.31 U141(tt, V2) -> U142(isLNat(activate(V2))) 5.71/2.31 U142(tt) -> tt 5.71/2.31 U151(tt, V2) -> U152(isLNat(activate(V2))) 5.71/2.31 U152(tt) -> tt 5.71/2.31 U161(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 5.71/2.31 U171(tt, N, XS) -> U172(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U172(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 5.71/2.31 U181(tt, Y) -> U182(isLNat(activate(Y)), activate(Y)) 5.71/2.31 U182(tt, Y) -> activate(Y) 5.71/2.31 U191(tt, XS) -> pair(nil, activate(XS)) 5.71/2.31 U201(tt, N, X, XS) -> U202(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 5.71/2.31 U202(tt, N, X, XS) -> U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 5.71/2.31 U203(tt, N, X, XS) -> U204(splitAt(activate(N), activate(XS)), activate(X)) 5.71/2.31 U204(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 5.71/2.31 U21(tt, X, Y) -> U22(isLNat(activate(Y)), activate(X)) 5.71/2.31 U211(tt, XS) -> U212(isLNat(activate(XS)), activate(XS)) 5.71/2.31 U212(tt, XS) -> activate(XS) 5.71/2.31 U22(tt, X) -> activate(X) 5.71/2.31 U221(tt, N, XS) -> U222(isLNat(activate(XS)), activate(N), activate(XS)) 5.71/2.31 U222(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 5.71/2.31 U31(tt, N, XS) -> U32(isLNat(activate(XS)), activate(N)) 5.71/2.31 U32(tt, N) -> activate(N) 5.71/2.31 U41(tt, V2) -> U42(isLNat(activate(V2))) 5.71/2.31 U42(tt) -> tt 5.71/2.31 U51(tt, V2) -> U52(isLNat(activate(V2))) 5.71/2.31 U52(tt) -> tt 5.71/2.31 U61(tt) -> tt 5.71/2.31 U71(tt) -> tt 5.71/2.31 U81(tt) -> tt 5.71/2.31 U91(tt) -> tt 5.71/2.31 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.71/2.31 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.71/2.31 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 5.71/2.31 isLNat(n__nil) -> tt 5.71/2.31 isLNat(n__afterNth(V1, V2)) -> U41(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__cons(V1, V2)) -> U51(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isLNat(n__fst(V1)) -> U61(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__natsFrom(V1)) -> U71(isNatural(activate(V1))) 5.71/2.31 isLNat(n__snd(V1)) -> U81(isPLNat(activate(V1))) 5.71/2.31 isLNat(n__tail(V1)) -> U91(isLNat(activate(V1))) 5.71/2.31 isLNat(n__take(V1, V2)) -> U101(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isNatural(n__0) -> tt 5.71/2.31 isNatural(n__head(V1)) -> U111(isLNat(activate(V1))) 5.71/2.31 isNatural(n__s(V1)) -> U121(isNatural(activate(V1))) 5.71/2.31 isNatural(n__sel(V1, V2)) -> U131(isNatural(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__pair(V1, V2)) -> U141(isLNat(activate(V1)), activate(V2)) 5.71/2.31 isPLNat(n__splitAt(V1, V2)) -> U151(isNatural(activate(V1)), activate(V2)) 5.71/2.31 natsFrom(N) -> U161(isNatural(N), N) 5.71/2.31 sel(N, XS) -> U171(isNatural(N), N, XS) 5.71/2.31 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.71/2.31 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.71/2.31 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, activate(XS)) 5.71/2.31 tail(cons(N, XS)) -> U211(isNatural(N), activate(XS)) 5.71/2.31 take(N, XS) -> U221(isNatural(N), N, XS) 5.71/2.31 natsFrom(X) -> n__natsFrom(X) 5.71/2.31 s(X) -> n__s(X) 5.71/2.31 nil -> n__nil 5.71/2.31 afterNth(X1, X2) -> n__afterNth(X1, X2) 5.71/2.31 cons(X1, X2) -> n__cons(X1, X2) 5.71/2.31 fst(X) -> n__fst(X) 5.71/2.31 snd(X) -> n__snd(X) 5.71/2.31 tail(X) -> n__tail(X) 5.71/2.31 take(X1, X2) -> n__take(X1, X2) 5.71/2.31 0 -> n__0 5.71/2.31 head(X) -> n__head(X) 5.71/2.31 sel(X1, X2) -> n__sel(X1, X2) 5.71/2.31 pair(X1, X2) -> n__pair(X1, X2) 5.71/2.31 splitAt(X1, X2) -> n__splitAt(X1, X2) 5.71/2.31 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 5.71/2.31 activate(n__s(X)) -> s(activate(X)) 5.71/2.31 activate(n__nil) -> nil 5.71/2.31 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 5.71/2.31 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 5.71/2.31 activate(n__fst(X)) -> fst(activate(X)) 5.71/2.31 activate(n__snd(X)) -> snd(activate(X)) 5.71/2.31 activate(n__tail(X)) -> tail(activate(X)) 5.71/2.31 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 5.71/2.31 activate(n__0) -> 0 5.71/2.31 activate(n__head(X)) -> head(activate(X)) 5.71/2.31 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 5.71/2.31 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 5.71/2.31 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 5.71/2.31 activate(X) -> X 5.71/2.31 5.71/2.31 S is empty. 5.71/2.31 Rewrite Strategy: FULL 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (9) DecreasingLoopProof (FINISHED) 5.71/2.31 The following loop(s) give(s) rise to the lower bound EXP: 5.71/2.31 5.71/2.31 The rewrite sequence 5.71/2.31 5.71/2.31 activate(n__natsFrom(X)) ->^+ U161(isNatural(activate(X)), activate(X)) 5.71/2.31 5.71/2.31 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0]. 5.71/2.31 5.71/2.31 The pumping substitution is [X / n__natsFrom(X)]. 5.71/2.31 5.71/2.31 The result substitution is [ ]. 5.71/2.31 5.71/2.31 5.71/2.31 5.71/2.31 The rewrite sequence 5.71/2.31 5.71/2.31 activate(n__natsFrom(X)) ->^+ U161(isNatural(activate(X)), activate(X)) 5.71/2.31 5.71/2.31 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 5.71/2.31 5.71/2.31 The pumping substitution is [X / n__natsFrom(X)]. 5.71/2.31 5.71/2.31 The result substitution is [ ]. 5.71/2.31 5.71/2.31 5.71/2.31 5.71/2.31 5.71/2.31 ---------------------------------------- 5.71/2.31 5.71/2.31 (10) 5.71/2.31 BOUNDS(EXP, INF) 6.09/2.37 EOF