4.63/2.00 WORST_CASE(NON_POLY, ?) 4.93/2.02 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.93/2.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.93/2.02 4.93/2.02 4.93/2.02 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.93/2.02 4.93/2.02 (0) CpxTRS 4.93/2.02 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 4.93/2.02 (2) TRS for Loop Detection 4.93/2.02 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 4.93/2.02 (4) BEST 4.93/2.02 (5) proven lower bound 4.93/2.02 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 4.93/2.02 (7) BOUNDS(n^1, INF) 4.93/2.02 (8) TRS for Loop Detection 4.93/2.02 (9) DecreasingLoopProof [FINISHED, 281 ms] 4.93/2.02 (10) BOUNDS(EXP, INF) 4.93/2.02 4.93/2.02 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (0) 4.93/2.02 Obligation: 4.93/2.02 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.93/2.02 4.93/2.02 4.93/2.02 The TRS R consists of the following rules: 4.93/2.02 4.93/2.02 U101(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 4.93/2.02 U11(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 4.93/2.02 U21(tt, X) -> activate(X) 4.93/2.02 U31(tt, N) -> activate(N) 4.93/2.02 U41(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 4.93/2.02 U51(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 4.93/2.02 U61(tt, Y) -> activate(Y) 4.93/2.02 U71(tt, XS) -> pair(nil, activate(XS)) 4.93/2.02 U81(tt, N, X, XS) -> U82(splitAt(activate(N), activate(XS)), activate(X)) 4.93/2.02 U82(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 4.93/2.02 U91(tt, XS) -> activate(XS) 4.93/2.02 afterNth(N, XS) -> U11(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 and(tt, X) -> activate(X) 4.93/2.02 fst(pair(X, Y)) -> U21(and(isLNat(X), n__isLNat(Y)), X) 4.93/2.02 head(cons(N, XS)) -> U31(and(isNatural(N), n__isLNat(activate(XS))), N) 4.93/2.02 isLNat(n__nil) -> tt 4.93/2.02 isLNat(n__afterNth(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__cons(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__fst(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__natsFrom(V1)) -> isNatural(activate(V1)) 4.93/2.02 isLNat(n__snd(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__tail(V1)) -> isLNat(activate(V1)) 4.93/2.02 isLNat(n__take(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isNatural(n__0) -> tt 4.93/2.02 isNatural(n__head(V1)) -> isLNat(activate(V1)) 4.93/2.02 isNatural(n__s(V1)) -> isNatural(activate(V1)) 4.93/2.02 isNatural(n__sel(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__pair(V1, V2)) -> and(isLNat(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__splitAt(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 natsFrom(N) -> U41(isNatural(N), N) 4.93/2.02 sel(N, XS) -> U51(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 snd(pair(X, Y)) -> U61(and(isLNat(X), n__isLNat(Y)), Y) 4.93/2.02 splitAt(0, XS) -> U71(isLNat(XS), XS) 4.93/2.02 splitAt(s(N), cons(X, XS)) -> U81(and(isNatural(N), n__and(n__isNatural(X), n__isLNat(activate(XS)))), N, X, activate(XS)) 4.93/2.02 tail(cons(N, XS)) -> U91(and(isNatural(N), n__isLNat(activate(XS))), activate(XS)) 4.93/2.02 take(N, XS) -> U101(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 natsFrom(X) -> n__natsFrom(X) 4.93/2.02 s(X) -> n__s(X) 4.93/2.02 isLNat(X) -> n__isLNat(X) 4.93/2.02 nil -> n__nil 4.93/2.02 afterNth(X1, X2) -> n__afterNth(X1, X2) 4.93/2.02 cons(X1, X2) -> n__cons(X1, X2) 4.93/2.02 fst(X) -> n__fst(X) 4.93/2.02 snd(X) -> n__snd(X) 4.93/2.02 tail(X) -> n__tail(X) 4.93/2.02 take(X1, X2) -> n__take(X1, X2) 4.93/2.02 0 -> n__0 4.93/2.02 head(X) -> n__head(X) 4.93/2.02 sel(X1, X2) -> n__sel(X1, X2) 4.93/2.02 pair(X1, X2) -> n__pair(X1, X2) 4.93/2.02 splitAt(X1, X2) -> n__splitAt(X1, X2) 4.93/2.02 and(X1, X2) -> n__and(X1, X2) 4.93/2.02 isNatural(X) -> n__isNatural(X) 4.93/2.02 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 4.93/2.02 activate(n__s(X)) -> s(activate(X)) 4.93/2.02 activate(n__isLNat(X)) -> isLNat(X) 4.93/2.02 activate(n__nil) -> nil 4.93/2.02 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 4.93/2.02 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 4.93/2.02 activate(n__fst(X)) -> fst(activate(X)) 4.93/2.02 activate(n__snd(X)) -> snd(activate(X)) 4.93/2.02 activate(n__tail(X)) -> tail(activate(X)) 4.93/2.02 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 4.93/2.02 activate(n__0) -> 0 4.93/2.02 activate(n__head(X)) -> head(activate(X)) 4.93/2.02 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 4.93/2.02 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 4.93/2.02 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 4.93/2.02 activate(n__and(X1, X2)) -> and(activate(X1), X2) 4.93/2.02 activate(n__isNatural(X)) -> isNatural(X) 4.93/2.02 activate(X) -> X 4.93/2.02 4.93/2.02 S is empty. 4.93/2.02 Rewrite Strategy: FULL 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 4.93/2.02 Transformed a relative TRS into a decreasing-loop problem. 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (2) 4.93/2.02 Obligation: 4.93/2.02 Analyzing the following TRS for decreasing loops: 4.93/2.02 4.93/2.02 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.93/2.02 4.93/2.02 4.93/2.02 The TRS R consists of the following rules: 4.93/2.02 4.93/2.02 U101(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 4.93/2.02 U11(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 4.93/2.02 U21(tt, X) -> activate(X) 4.93/2.02 U31(tt, N) -> activate(N) 4.93/2.02 U41(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 4.93/2.02 U51(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 4.93/2.02 U61(tt, Y) -> activate(Y) 4.93/2.02 U71(tt, XS) -> pair(nil, activate(XS)) 4.93/2.02 U81(tt, N, X, XS) -> U82(splitAt(activate(N), activate(XS)), activate(X)) 4.93/2.02 U82(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 4.93/2.02 U91(tt, XS) -> activate(XS) 4.93/2.02 afterNth(N, XS) -> U11(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 and(tt, X) -> activate(X) 4.93/2.02 fst(pair(X, Y)) -> U21(and(isLNat(X), n__isLNat(Y)), X) 4.93/2.02 head(cons(N, XS)) -> U31(and(isNatural(N), n__isLNat(activate(XS))), N) 4.93/2.02 isLNat(n__nil) -> tt 4.93/2.02 isLNat(n__afterNth(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__cons(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__fst(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__natsFrom(V1)) -> isNatural(activate(V1)) 4.93/2.02 isLNat(n__snd(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__tail(V1)) -> isLNat(activate(V1)) 4.93/2.02 isLNat(n__take(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isNatural(n__0) -> tt 4.93/2.02 isNatural(n__head(V1)) -> isLNat(activate(V1)) 4.93/2.02 isNatural(n__s(V1)) -> isNatural(activate(V1)) 4.93/2.02 isNatural(n__sel(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__pair(V1, V2)) -> and(isLNat(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__splitAt(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 natsFrom(N) -> U41(isNatural(N), N) 4.93/2.02 sel(N, XS) -> U51(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 snd(pair(X, Y)) -> U61(and(isLNat(X), n__isLNat(Y)), Y) 4.93/2.02 splitAt(0, XS) -> U71(isLNat(XS), XS) 4.93/2.02 splitAt(s(N), cons(X, XS)) -> U81(and(isNatural(N), n__and(n__isNatural(X), n__isLNat(activate(XS)))), N, X, activate(XS)) 4.93/2.02 tail(cons(N, XS)) -> U91(and(isNatural(N), n__isLNat(activate(XS))), activate(XS)) 4.93/2.02 take(N, XS) -> U101(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 natsFrom(X) -> n__natsFrom(X) 4.93/2.02 s(X) -> n__s(X) 4.93/2.02 isLNat(X) -> n__isLNat(X) 4.93/2.02 nil -> n__nil 4.93/2.02 afterNth(X1, X2) -> n__afterNth(X1, X2) 4.93/2.02 cons(X1, X2) -> n__cons(X1, X2) 4.93/2.02 fst(X) -> n__fst(X) 4.93/2.02 snd(X) -> n__snd(X) 4.93/2.02 tail(X) -> n__tail(X) 4.93/2.02 take(X1, X2) -> n__take(X1, X2) 4.93/2.02 0 -> n__0 4.93/2.02 head(X) -> n__head(X) 4.93/2.02 sel(X1, X2) -> n__sel(X1, X2) 4.93/2.02 pair(X1, X2) -> n__pair(X1, X2) 4.93/2.02 splitAt(X1, X2) -> n__splitAt(X1, X2) 4.93/2.02 and(X1, X2) -> n__and(X1, X2) 4.93/2.02 isNatural(X) -> n__isNatural(X) 4.93/2.02 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 4.93/2.02 activate(n__s(X)) -> s(activate(X)) 4.93/2.02 activate(n__isLNat(X)) -> isLNat(X) 4.93/2.02 activate(n__nil) -> nil 4.93/2.02 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 4.93/2.02 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 4.93/2.02 activate(n__fst(X)) -> fst(activate(X)) 4.93/2.02 activate(n__snd(X)) -> snd(activate(X)) 4.93/2.02 activate(n__tail(X)) -> tail(activate(X)) 4.93/2.02 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 4.93/2.02 activate(n__0) -> 0 4.93/2.02 activate(n__head(X)) -> head(activate(X)) 4.93/2.02 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 4.93/2.02 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 4.93/2.02 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 4.93/2.02 activate(n__and(X1, X2)) -> and(activate(X1), X2) 4.93/2.02 activate(n__isNatural(X)) -> isNatural(X) 4.93/2.02 activate(X) -> X 4.93/2.02 4.93/2.02 S is empty. 4.93/2.02 Rewrite Strategy: FULL 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (3) DecreasingLoopProof (LOWER BOUND(ID)) 4.93/2.02 The following loop(s) give(s) rise to the lower bound Omega(n^1): 4.93/2.02 4.93/2.02 The rewrite sequence 4.93/2.02 4.93/2.02 activate(n__snd(X)) ->^+ snd(activate(X)) 4.93/2.02 4.93/2.02 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 4.93/2.02 4.93/2.02 The pumping substitution is [X / n__snd(X)]. 4.93/2.02 4.93/2.02 The result substitution is [ ]. 4.93/2.02 4.93/2.02 4.93/2.02 4.93/2.02 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (4) 4.93/2.02 Complex Obligation (BEST) 4.93/2.02 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (5) 4.93/2.02 Obligation: 4.93/2.02 Proved the lower bound n^1 for the following obligation: 4.93/2.02 4.93/2.02 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.93/2.02 4.93/2.02 4.93/2.02 The TRS R consists of the following rules: 4.93/2.02 4.93/2.02 U101(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 4.93/2.02 U11(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 4.93/2.02 U21(tt, X) -> activate(X) 4.93/2.02 U31(tt, N) -> activate(N) 4.93/2.02 U41(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 4.93/2.02 U51(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 4.93/2.02 U61(tt, Y) -> activate(Y) 4.93/2.02 U71(tt, XS) -> pair(nil, activate(XS)) 4.93/2.02 U81(tt, N, X, XS) -> U82(splitAt(activate(N), activate(XS)), activate(X)) 4.93/2.02 U82(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 4.93/2.02 U91(tt, XS) -> activate(XS) 4.93/2.02 afterNth(N, XS) -> U11(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 and(tt, X) -> activate(X) 4.93/2.02 fst(pair(X, Y)) -> U21(and(isLNat(X), n__isLNat(Y)), X) 4.93/2.02 head(cons(N, XS)) -> U31(and(isNatural(N), n__isLNat(activate(XS))), N) 4.93/2.02 isLNat(n__nil) -> tt 4.93/2.02 isLNat(n__afterNth(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__cons(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__fst(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__natsFrom(V1)) -> isNatural(activate(V1)) 4.93/2.02 isLNat(n__snd(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__tail(V1)) -> isLNat(activate(V1)) 4.93/2.02 isLNat(n__take(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isNatural(n__0) -> tt 4.93/2.02 isNatural(n__head(V1)) -> isLNat(activate(V1)) 4.93/2.02 isNatural(n__s(V1)) -> isNatural(activate(V1)) 4.93/2.02 isNatural(n__sel(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__pair(V1, V2)) -> and(isLNat(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__splitAt(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 natsFrom(N) -> U41(isNatural(N), N) 4.93/2.02 sel(N, XS) -> U51(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 snd(pair(X, Y)) -> U61(and(isLNat(X), n__isLNat(Y)), Y) 4.93/2.02 splitAt(0, XS) -> U71(isLNat(XS), XS) 4.93/2.02 splitAt(s(N), cons(X, XS)) -> U81(and(isNatural(N), n__and(n__isNatural(X), n__isLNat(activate(XS)))), N, X, activate(XS)) 4.93/2.02 tail(cons(N, XS)) -> U91(and(isNatural(N), n__isLNat(activate(XS))), activate(XS)) 4.93/2.02 take(N, XS) -> U101(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 natsFrom(X) -> n__natsFrom(X) 4.93/2.02 s(X) -> n__s(X) 4.93/2.02 isLNat(X) -> n__isLNat(X) 4.93/2.02 nil -> n__nil 4.93/2.02 afterNth(X1, X2) -> n__afterNth(X1, X2) 4.93/2.02 cons(X1, X2) -> n__cons(X1, X2) 4.93/2.02 fst(X) -> n__fst(X) 4.93/2.02 snd(X) -> n__snd(X) 4.93/2.02 tail(X) -> n__tail(X) 4.93/2.02 take(X1, X2) -> n__take(X1, X2) 4.93/2.02 0 -> n__0 4.93/2.02 head(X) -> n__head(X) 4.93/2.02 sel(X1, X2) -> n__sel(X1, X2) 4.93/2.02 pair(X1, X2) -> n__pair(X1, X2) 4.93/2.02 splitAt(X1, X2) -> n__splitAt(X1, X2) 4.93/2.02 and(X1, X2) -> n__and(X1, X2) 4.93/2.02 isNatural(X) -> n__isNatural(X) 4.93/2.02 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 4.93/2.02 activate(n__s(X)) -> s(activate(X)) 4.93/2.02 activate(n__isLNat(X)) -> isLNat(X) 4.93/2.02 activate(n__nil) -> nil 4.93/2.02 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 4.93/2.02 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 4.93/2.02 activate(n__fst(X)) -> fst(activate(X)) 4.93/2.02 activate(n__snd(X)) -> snd(activate(X)) 4.93/2.02 activate(n__tail(X)) -> tail(activate(X)) 4.93/2.02 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 4.93/2.02 activate(n__0) -> 0 4.93/2.02 activate(n__head(X)) -> head(activate(X)) 4.93/2.02 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 4.93/2.02 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 4.93/2.02 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 4.93/2.02 activate(n__and(X1, X2)) -> and(activate(X1), X2) 4.93/2.02 activate(n__isNatural(X)) -> isNatural(X) 4.93/2.02 activate(X) -> X 4.93/2.02 4.93/2.02 S is empty. 4.93/2.02 Rewrite Strategy: FULL 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (6) LowerBoundPropagationProof (FINISHED) 4.93/2.02 Propagated lower bound. 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (7) 4.93/2.02 BOUNDS(n^1, INF) 4.93/2.02 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (8) 4.93/2.02 Obligation: 4.93/2.02 Analyzing the following TRS for decreasing loops: 4.93/2.02 4.93/2.02 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 4.93/2.02 4.93/2.02 4.93/2.02 The TRS R consists of the following rules: 4.93/2.02 4.93/2.02 U101(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 4.93/2.02 U11(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 4.93/2.02 U21(tt, X) -> activate(X) 4.93/2.02 U31(tt, N) -> activate(N) 4.93/2.02 U41(tt, N) -> cons(activate(N), n__natsFrom(n__s(activate(N)))) 4.93/2.02 U51(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 4.93/2.02 U61(tt, Y) -> activate(Y) 4.93/2.02 U71(tt, XS) -> pair(nil, activate(XS)) 4.93/2.02 U81(tt, N, X, XS) -> U82(splitAt(activate(N), activate(XS)), activate(X)) 4.93/2.02 U82(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 4.93/2.02 U91(tt, XS) -> activate(XS) 4.93/2.02 afterNth(N, XS) -> U11(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 and(tt, X) -> activate(X) 4.93/2.02 fst(pair(X, Y)) -> U21(and(isLNat(X), n__isLNat(Y)), X) 4.93/2.02 head(cons(N, XS)) -> U31(and(isNatural(N), n__isLNat(activate(XS))), N) 4.93/2.02 isLNat(n__nil) -> tt 4.93/2.02 isLNat(n__afterNth(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__cons(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isLNat(n__fst(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__natsFrom(V1)) -> isNatural(activate(V1)) 4.93/2.02 isLNat(n__snd(V1)) -> isPLNat(activate(V1)) 4.93/2.02 isLNat(n__tail(V1)) -> isLNat(activate(V1)) 4.93/2.02 isLNat(n__take(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isNatural(n__0) -> tt 4.93/2.02 isNatural(n__head(V1)) -> isLNat(activate(V1)) 4.93/2.02 isNatural(n__s(V1)) -> isNatural(activate(V1)) 4.93/2.02 isNatural(n__sel(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__pair(V1, V2)) -> and(isLNat(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 isPLNat(n__splitAt(V1, V2)) -> and(isNatural(activate(V1)), n__isLNat(activate(V2))) 4.93/2.02 natsFrom(N) -> U41(isNatural(N), N) 4.93/2.02 sel(N, XS) -> U51(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 snd(pair(X, Y)) -> U61(and(isLNat(X), n__isLNat(Y)), Y) 4.93/2.02 splitAt(0, XS) -> U71(isLNat(XS), XS) 4.93/2.02 splitAt(s(N), cons(X, XS)) -> U81(and(isNatural(N), n__and(n__isNatural(X), n__isLNat(activate(XS)))), N, X, activate(XS)) 4.93/2.02 tail(cons(N, XS)) -> U91(and(isNatural(N), n__isLNat(activate(XS))), activate(XS)) 4.93/2.02 take(N, XS) -> U101(and(isNatural(N), n__isLNat(XS)), N, XS) 4.93/2.02 natsFrom(X) -> n__natsFrom(X) 4.93/2.02 s(X) -> n__s(X) 4.93/2.02 isLNat(X) -> n__isLNat(X) 4.93/2.02 nil -> n__nil 4.93/2.02 afterNth(X1, X2) -> n__afterNth(X1, X2) 4.93/2.02 cons(X1, X2) -> n__cons(X1, X2) 4.93/2.02 fst(X) -> n__fst(X) 4.93/2.02 snd(X) -> n__snd(X) 4.93/2.02 tail(X) -> n__tail(X) 4.93/2.02 take(X1, X2) -> n__take(X1, X2) 4.93/2.02 0 -> n__0 4.93/2.02 head(X) -> n__head(X) 4.93/2.02 sel(X1, X2) -> n__sel(X1, X2) 4.93/2.02 pair(X1, X2) -> n__pair(X1, X2) 4.93/2.02 splitAt(X1, X2) -> n__splitAt(X1, X2) 4.93/2.02 and(X1, X2) -> n__and(X1, X2) 4.93/2.02 isNatural(X) -> n__isNatural(X) 4.93/2.02 activate(n__natsFrom(X)) -> natsFrom(activate(X)) 4.93/2.02 activate(n__s(X)) -> s(activate(X)) 4.93/2.02 activate(n__isLNat(X)) -> isLNat(X) 4.93/2.02 activate(n__nil) -> nil 4.93/2.02 activate(n__afterNth(X1, X2)) -> afterNth(activate(X1), activate(X2)) 4.93/2.02 activate(n__cons(X1, X2)) -> cons(activate(X1), X2) 4.93/2.02 activate(n__fst(X)) -> fst(activate(X)) 4.93/2.02 activate(n__snd(X)) -> snd(activate(X)) 4.93/2.02 activate(n__tail(X)) -> tail(activate(X)) 4.93/2.02 activate(n__take(X1, X2)) -> take(activate(X1), activate(X2)) 4.93/2.02 activate(n__0) -> 0 4.93/2.02 activate(n__head(X)) -> head(activate(X)) 4.93/2.02 activate(n__sel(X1, X2)) -> sel(activate(X1), activate(X2)) 4.93/2.02 activate(n__pair(X1, X2)) -> pair(activate(X1), activate(X2)) 4.93/2.02 activate(n__splitAt(X1, X2)) -> splitAt(activate(X1), activate(X2)) 4.93/2.02 activate(n__and(X1, X2)) -> and(activate(X1), X2) 4.93/2.02 activate(n__isNatural(X)) -> isNatural(X) 4.93/2.02 activate(X) -> X 4.93/2.02 4.93/2.02 S is empty. 4.93/2.02 Rewrite Strategy: FULL 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (9) DecreasingLoopProof (FINISHED) 4.93/2.02 The following loop(s) give(s) rise to the lower bound EXP: 4.93/2.02 4.93/2.02 The rewrite sequence 4.93/2.02 4.93/2.02 activate(n__natsFrom(X)) ->^+ U41(isNatural(activate(X)), activate(X)) 4.93/2.02 4.93/2.02 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0]. 4.93/2.02 4.93/2.02 The pumping substitution is [X / n__natsFrom(X)]. 4.93/2.02 4.93/2.02 The result substitution is [ ]. 4.93/2.02 4.93/2.02 4.93/2.02 4.93/2.02 The rewrite sequence 4.93/2.02 4.93/2.02 activate(n__natsFrom(X)) ->^+ U41(isNatural(activate(X)), activate(X)) 4.93/2.02 4.93/2.02 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 4.93/2.02 4.93/2.02 The pumping substitution is [X / n__natsFrom(X)]. 4.93/2.02 4.93/2.02 The result substitution is [ ]. 4.93/2.02 4.93/2.02 4.93/2.02 4.93/2.02 4.93/2.02 ---------------------------------------- 4.93/2.02 4.93/2.02 (10) 4.93/2.02 BOUNDS(EXP, INF) 4.93/2.06 EOF