62.19/23.45 WORST_CASE(NON_POLY, ?) 62.19/23.46 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 62.19/23.46 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 62.19/23.46 62.19/23.46 62.19/23.46 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 62.19/23.46 62.19/23.46 (0) CpxTRS 62.19/23.46 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 62.19/23.46 (2) TRS for Loop Detection 62.19/23.46 (3) DecreasingLoopProof [LOWER BOUND(ID), 1344 ms] 62.19/23.46 (4) BEST 62.19/23.46 (5) proven lower bound 62.19/23.46 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 62.19/23.46 (7) BOUNDS(n^1, INF) 62.19/23.46 (8) TRS for Loop Detection 62.19/23.46 (9) DecreasingLoopProof [FINISHED, 18.8 s] 62.19/23.46 (10) BOUNDS(EXP, INF) 62.19/23.46 62.19/23.46 62.19/23.46 ---------------------------------------- 62.19/23.46 62.19/23.46 (0) 62.19/23.46 Obligation: 62.19/23.46 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 62.19/23.46 62.19/23.46 62.19/23.46 The TRS R consists of the following rules: 62.19/23.46 62.19/23.46 U101(tt, V1, V2) -> U102(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.46 U102(tt, V1, V2) -> U103(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.46 U103(tt, V1, V2) -> U104(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U104(tt, V1, V2) -> U105(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U105(tt, V2) -> U106(isLNat(activate(V2))) 62.19/23.48 U106(tt) -> tt 62.19/23.48 U11(tt, N, XS) -> U12(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U111(tt, V2) -> U112(isLNatKind(activate(V2))) 62.19/23.48 U112(tt) -> tt 62.19/23.48 U12(tt, N, XS) -> U13(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U121(tt, V2) -> U122(isLNatKind(activate(V2))) 62.19/23.48 U122(tt) -> tt 62.19/23.48 U13(tt, N, XS) -> U14(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U131(tt) -> tt 62.19/23.48 U14(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 62.19/23.48 U141(tt) -> tt 62.19/23.48 U151(tt) -> tt 62.19/23.48 U161(tt) -> tt 62.19/23.48 U171(tt, V2) -> U172(isLNatKind(activate(V2))) 62.19/23.48 U172(tt) -> tt 62.19/23.48 U181(tt, V1) -> U182(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U182(tt, V1) -> U183(isLNat(activate(V1))) 62.19/23.48 U183(tt) -> tt 62.19/23.48 U191(tt, V1) -> U192(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U192(tt, V1) -> U193(isNatural(activate(V1))) 62.19/23.48 U193(tt) -> tt 62.19/23.48 U201(tt, V1, V2) -> U202(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U202(tt, V1, V2) -> U203(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U203(tt, V1, V2) -> U204(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U204(tt, V1, V2) -> U205(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U205(tt, V2) -> U206(isLNat(activate(V2))) 62.19/23.48 U206(tt) -> tt 62.19/23.48 U21(tt, X, Y) -> U22(isLNatKind(activate(X)), activate(X), activate(Y)) 62.19/23.48 U211(tt) -> tt 62.19/23.48 U22(tt, X, Y) -> U23(isLNat(activate(Y)), activate(X), activate(Y)) 62.19/23.48 U221(tt) -> tt 62.19/23.48 U23(tt, X, Y) -> U24(isLNatKind(activate(Y)), activate(X)) 62.19/23.48 U231(tt, V2) -> U232(isLNatKind(activate(V2))) 62.19/23.48 U232(tt) -> tt 62.19/23.48 U24(tt, X) -> activate(X) 62.19/23.48 U241(tt, V1, V2) -> U242(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U242(tt, V1, V2) -> U243(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U243(tt, V1, V2) -> U244(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U244(tt, V1, V2) -> U245(isLNat(activate(V1)), activate(V2)) 62.19/23.48 U245(tt, V2) -> U246(isLNat(activate(V2))) 62.19/23.48 U246(tt) -> tt 62.19/23.48 U251(tt, V1, V2) -> U252(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U252(tt, V1, V2) -> U253(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U253(tt, V1, V2) -> U254(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U254(tt, V1, V2) -> U255(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U255(tt, V2) -> U256(isLNat(activate(V2))) 62.19/23.48 U256(tt) -> tt 62.19/23.48 U261(tt, V2) -> U262(isLNatKind(activate(V2))) 62.19/23.48 U262(tt) -> tt 62.19/23.48 U271(tt, V2) -> U272(isLNatKind(activate(V2))) 62.19/23.48 U272(tt) -> tt 62.19/23.48 U281(tt, N) -> U282(isNaturalKind(activate(N)), activate(N)) 62.19/23.48 U282(tt, N) -> cons(activate(N), n__natsFrom(s(activate(N)))) 62.19/23.48 U291(tt, N, XS) -> U292(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U292(tt, N, XS) -> U293(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U293(tt, N, XS) -> U294(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U294(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 62.19/23.48 U301(tt, X, Y) -> U302(isLNatKind(activate(X)), activate(Y)) 62.19/23.48 U302(tt, Y) -> U303(isLNat(activate(Y)), activate(Y)) 62.19/23.48 U303(tt, Y) -> U304(isLNatKind(activate(Y)), activate(Y)) 62.19/23.48 U304(tt, Y) -> activate(Y) 62.19/23.48 U31(tt, N, XS) -> U32(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U311(tt, XS) -> U312(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U312(tt, XS) -> pair(nil, activate(XS)) 62.19/23.48 U32(tt, N, XS) -> U33(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U321(tt, N, X, XS) -> U322(isNaturalKind(activate(N)), activate(N), activate(X), activate(XS)) 62.19/23.48 U322(tt, N, X, XS) -> U323(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U323(tt, N, X, XS) -> U324(isNaturalKind(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U324(tt, N, X, XS) -> U325(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U325(tt, N, X, XS) -> U326(isLNatKind(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U326(tt, N, X, XS) -> U327(splitAt(activate(N), activate(XS)), activate(X)) 62.19/23.48 U327(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 62.19/23.48 U33(tt, N, XS) -> U34(isLNatKind(activate(XS)), activate(N)) 62.19/23.48 U331(tt, N, XS) -> U332(isNaturalKind(activate(N)), activate(XS)) 62.19/23.48 U332(tt, XS) -> U333(isLNat(activate(XS)), activate(XS)) 62.19/23.48 U333(tt, XS) -> U334(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U334(tt, XS) -> activate(XS) 62.19/23.48 U34(tt, N) -> activate(N) 62.19/23.48 U341(tt, N, XS) -> U342(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U342(tt, N, XS) -> U343(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U343(tt, N, XS) -> U344(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U344(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 62.19/23.48 U41(tt, V1, V2) -> U42(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U42(tt, V1, V2) -> U43(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U43(tt, V1, V2) -> U44(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U44(tt, V1, V2) -> U45(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U45(tt, V2) -> U46(isLNat(activate(V2))) 62.19/23.48 U46(tt) -> tt 62.19/23.48 U51(tt, V1, V2) -> U52(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U52(tt, V1, V2) -> U53(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U53(tt, V1, V2) -> U54(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U54(tt, V1, V2) -> U55(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U55(tt, V2) -> U56(isLNat(activate(V2))) 62.19/23.48 U56(tt) -> tt 62.19/23.48 U61(tt, V1) -> U62(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U62(tt, V1) -> U63(isPLNat(activate(V1))) 62.19/23.48 U63(tt) -> tt 62.19/23.48 U71(tt, V1) -> U72(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U72(tt, V1) -> U73(isNatural(activate(V1))) 62.19/23.48 U73(tt) -> tt 62.19/23.48 U81(tt, V1) -> U82(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U82(tt, V1) -> U83(isPLNat(activate(V1))) 62.19/23.48 U83(tt) -> tt 62.19/23.48 U91(tt, V1) -> U92(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U92(tt, V1) -> U93(isLNat(activate(V1))) 62.19/23.48 U93(tt) -> tt 62.19/23.48 afterNth(N, XS) -> U11(isNatural(N), N, XS) 62.19/23.48 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 62.19/23.48 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 62.19/23.48 isLNat(n__nil) -> tt 62.19/23.48 isLNat(n__afterNth(V1, V2)) -> U41(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__cons(V1, V2)) -> U51(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__fst(V1)) -> U61(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__natsFrom(V1)) -> U71(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__snd(V1)) -> U81(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__tail(V1)) -> U91(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__take(V1, V2)) -> U101(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNatKind(n__nil) -> tt 62.19/23.48 isLNatKind(n__afterNth(V1, V2)) -> U111(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__cons(V1, V2)) -> U121(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__fst(V1)) -> U131(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__natsFrom(V1)) -> U141(isNaturalKind(activate(V1))) 62.19/23.48 isLNatKind(n__snd(V1)) -> U151(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__tail(V1)) -> U161(isLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__take(V1, V2)) -> U171(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isNatural(n__0) -> tt 62.19/23.48 isNatural(n__head(V1)) -> U181(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__s(V1)) -> U191(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__sel(V1, V2)) -> U201(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isNaturalKind(n__0) -> tt 62.19/23.48 isNaturalKind(n__head(V1)) -> U211(isLNatKind(activate(V1))) 62.19/23.48 isNaturalKind(n__s(V1)) -> U221(isNaturalKind(activate(V1))) 62.19/23.48 isNaturalKind(n__sel(V1, V2)) -> U231(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNat(n__pair(V1, V2)) -> U241(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNat(n__splitAt(V1, V2)) -> U251(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNatKind(n__pair(V1, V2)) -> U261(isLNatKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNatKind(n__splitAt(V1, V2)) -> U271(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 natsFrom(N) -> U281(isNatural(N), N) 62.19/23.48 sel(N, XS) -> U291(isNatural(N), N, XS) 62.19/23.48 snd(pair(X, Y)) -> U301(isLNat(X), X, Y) 62.19/23.48 splitAt(0, XS) -> U311(isLNat(XS), XS) 62.19/23.48 splitAt(s(N), cons(X, XS)) -> U321(isNatural(N), N, X, activate(XS)) 62.19/23.48 tail(cons(N, XS)) -> U331(isNatural(N), N, activate(XS)) 62.19/23.48 take(N, XS) -> U341(isNatural(N), N, XS) 62.19/23.48 natsFrom(X) -> n__natsFrom(X) 62.19/23.48 nil -> n__nil 62.19/23.48 afterNth(X1, X2) -> n__afterNth(X1, X2) 62.19/23.48 cons(X1, X2) -> n__cons(X1, X2) 62.19/23.48 fst(X) -> n__fst(X) 62.19/23.48 snd(X) -> n__snd(X) 62.19/23.48 tail(X) -> n__tail(X) 62.19/23.48 take(X1, X2) -> n__take(X1, X2) 62.19/23.48 0 -> n__0 62.19/23.48 head(X) -> n__head(X) 62.19/23.48 s(X) -> n__s(X) 62.19/23.48 sel(X1, X2) -> n__sel(X1, X2) 62.19/23.48 pair(X1, X2) -> n__pair(X1, X2) 62.19/23.48 splitAt(X1, X2) -> n__splitAt(X1, X2) 62.19/23.48 activate(n__natsFrom(X)) -> natsFrom(X) 62.19/23.48 activate(n__nil) -> nil 62.19/23.48 activate(n__afterNth(X1, X2)) -> afterNth(X1, X2) 62.19/23.48 activate(n__cons(X1, X2)) -> cons(X1, X2) 62.19/23.48 activate(n__fst(X)) -> fst(X) 62.19/23.48 activate(n__snd(X)) -> snd(X) 62.19/23.48 activate(n__tail(X)) -> tail(X) 62.19/23.48 activate(n__take(X1, X2)) -> take(X1, X2) 62.19/23.48 activate(n__0) -> 0 62.19/23.48 activate(n__head(X)) -> head(X) 62.19/23.48 activate(n__s(X)) -> s(X) 62.19/23.48 activate(n__sel(X1, X2)) -> sel(X1, X2) 62.19/23.48 activate(n__pair(X1, X2)) -> pair(X1, X2) 62.19/23.48 activate(n__splitAt(X1, X2)) -> splitAt(X1, X2) 62.19/23.48 activate(X) -> X 62.19/23.48 62.19/23.48 S is empty. 62.19/23.48 Rewrite Strategy: FULL 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 62.19/23.48 Transformed a relative TRS into a decreasing-loop problem. 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (2) 62.19/23.48 Obligation: 62.19/23.48 Analyzing the following TRS for decreasing loops: 62.19/23.48 62.19/23.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 62.19/23.48 62.19/23.48 62.19/23.48 The TRS R consists of the following rules: 62.19/23.48 62.19/23.48 U101(tt, V1, V2) -> U102(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U102(tt, V1, V2) -> U103(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U103(tt, V1, V2) -> U104(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U104(tt, V1, V2) -> U105(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U105(tt, V2) -> U106(isLNat(activate(V2))) 62.19/23.48 U106(tt) -> tt 62.19/23.48 U11(tt, N, XS) -> U12(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U111(tt, V2) -> U112(isLNatKind(activate(V2))) 62.19/23.48 U112(tt) -> tt 62.19/23.48 U12(tt, N, XS) -> U13(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U121(tt, V2) -> U122(isLNatKind(activate(V2))) 62.19/23.48 U122(tt) -> tt 62.19/23.48 U13(tt, N, XS) -> U14(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U131(tt) -> tt 62.19/23.48 U14(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 62.19/23.48 U141(tt) -> tt 62.19/23.48 U151(tt) -> tt 62.19/23.48 U161(tt) -> tt 62.19/23.48 U171(tt, V2) -> U172(isLNatKind(activate(V2))) 62.19/23.48 U172(tt) -> tt 62.19/23.48 U181(tt, V1) -> U182(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U182(tt, V1) -> U183(isLNat(activate(V1))) 62.19/23.48 U183(tt) -> tt 62.19/23.48 U191(tt, V1) -> U192(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U192(tt, V1) -> U193(isNatural(activate(V1))) 62.19/23.48 U193(tt) -> tt 62.19/23.48 U201(tt, V1, V2) -> U202(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U202(tt, V1, V2) -> U203(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U203(tt, V1, V2) -> U204(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U204(tt, V1, V2) -> U205(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U205(tt, V2) -> U206(isLNat(activate(V2))) 62.19/23.48 U206(tt) -> tt 62.19/23.48 U21(tt, X, Y) -> U22(isLNatKind(activate(X)), activate(X), activate(Y)) 62.19/23.48 U211(tt) -> tt 62.19/23.48 U22(tt, X, Y) -> U23(isLNat(activate(Y)), activate(X), activate(Y)) 62.19/23.48 U221(tt) -> tt 62.19/23.48 U23(tt, X, Y) -> U24(isLNatKind(activate(Y)), activate(X)) 62.19/23.48 U231(tt, V2) -> U232(isLNatKind(activate(V2))) 62.19/23.48 U232(tt) -> tt 62.19/23.48 U24(tt, X) -> activate(X) 62.19/23.48 U241(tt, V1, V2) -> U242(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U242(tt, V1, V2) -> U243(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U243(tt, V1, V2) -> U244(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U244(tt, V1, V2) -> U245(isLNat(activate(V1)), activate(V2)) 62.19/23.48 U245(tt, V2) -> U246(isLNat(activate(V2))) 62.19/23.48 U246(tt) -> tt 62.19/23.48 U251(tt, V1, V2) -> U252(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U252(tt, V1, V2) -> U253(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U253(tt, V1, V2) -> U254(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U254(tt, V1, V2) -> U255(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U255(tt, V2) -> U256(isLNat(activate(V2))) 62.19/23.48 U256(tt) -> tt 62.19/23.48 U261(tt, V2) -> U262(isLNatKind(activate(V2))) 62.19/23.48 U262(tt) -> tt 62.19/23.48 U271(tt, V2) -> U272(isLNatKind(activate(V2))) 62.19/23.48 U272(tt) -> tt 62.19/23.48 U281(tt, N) -> U282(isNaturalKind(activate(N)), activate(N)) 62.19/23.48 U282(tt, N) -> cons(activate(N), n__natsFrom(s(activate(N)))) 62.19/23.48 U291(tt, N, XS) -> U292(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U292(tt, N, XS) -> U293(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U293(tt, N, XS) -> U294(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U294(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 62.19/23.48 U301(tt, X, Y) -> U302(isLNatKind(activate(X)), activate(Y)) 62.19/23.48 U302(tt, Y) -> U303(isLNat(activate(Y)), activate(Y)) 62.19/23.48 U303(tt, Y) -> U304(isLNatKind(activate(Y)), activate(Y)) 62.19/23.48 U304(tt, Y) -> activate(Y) 62.19/23.48 U31(tt, N, XS) -> U32(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U311(tt, XS) -> U312(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U312(tt, XS) -> pair(nil, activate(XS)) 62.19/23.48 U32(tt, N, XS) -> U33(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U321(tt, N, X, XS) -> U322(isNaturalKind(activate(N)), activate(N), activate(X), activate(XS)) 62.19/23.48 U322(tt, N, X, XS) -> U323(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U323(tt, N, X, XS) -> U324(isNaturalKind(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U324(tt, N, X, XS) -> U325(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U325(tt, N, X, XS) -> U326(isLNatKind(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U326(tt, N, X, XS) -> U327(splitAt(activate(N), activate(XS)), activate(X)) 62.19/23.48 U327(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 62.19/23.48 U33(tt, N, XS) -> U34(isLNatKind(activate(XS)), activate(N)) 62.19/23.48 U331(tt, N, XS) -> U332(isNaturalKind(activate(N)), activate(XS)) 62.19/23.48 U332(tt, XS) -> U333(isLNat(activate(XS)), activate(XS)) 62.19/23.48 U333(tt, XS) -> U334(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U334(tt, XS) -> activate(XS) 62.19/23.48 U34(tt, N) -> activate(N) 62.19/23.48 U341(tt, N, XS) -> U342(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U342(tt, N, XS) -> U343(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U343(tt, N, XS) -> U344(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U344(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 62.19/23.48 U41(tt, V1, V2) -> U42(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U42(tt, V1, V2) -> U43(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U43(tt, V1, V2) -> U44(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U44(tt, V1, V2) -> U45(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U45(tt, V2) -> U46(isLNat(activate(V2))) 62.19/23.48 U46(tt) -> tt 62.19/23.48 U51(tt, V1, V2) -> U52(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U52(tt, V1, V2) -> U53(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U53(tt, V1, V2) -> U54(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U54(tt, V1, V2) -> U55(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U55(tt, V2) -> U56(isLNat(activate(V2))) 62.19/23.48 U56(tt) -> tt 62.19/23.48 U61(tt, V1) -> U62(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U62(tt, V1) -> U63(isPLNat(activate(V1))) 62.19/23.48 U63(tt) -> tt 62.19/23.48 U71(tt, V1) -> U72(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U72(tt, V1) -> U73(isNatural(activate(V1))) 62.19/23.48 U73(tt) -> tt 62.19/23.48 U81(tt, V1) -> U82(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U82(tt, V1) -> U83(isPLNat(activate(V1))) 62.19/23.48 U83(tt) -> tt 62.19/23.48 U91(tt, V1) -> U92(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U92(tt, V1) -> U93(isLNat(activate(V1))) 62.19/23.48 U93(tt) -> tt 62.19/23.48 afterNth(N, XS) -> U11(isNatural(N), N, XS) 62.19/23.48 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 62.19/23.48 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 62.19/23.48 isLNat(n__nil) -> tt 62.19/23.48 isLNat(n__afterNth(V1, V2)) -> U41(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__cons(V1, V2)) -> U51(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__fst(V1)) -> U61(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__natsFrom(V1)) -> U71(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__snd(V1)) -> U81(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__tail(V1)) -> U91(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__take(V1, V2)) -> U101(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNatKind(n__nil) -> tt 62.19/23.48 isLNatKind(n__afterNth(V1, V2)) -> U111(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__cons(V1, V2)) -> U121(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__fst(V1)) -> U131(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__natsFrom(V1)) -> U141(isNaturalKind(activate(V1))) 62.19/23.48 isLNatKind(n__snd(V1)) -> U151(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__tail(V1)) -> U161(isLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__take(V1, V2)) -> U171(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isNatural(n__0) -> tt 62.19/23.48 isNatural(n__head(V1)) -> U181(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__s(V1)) -> U191(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__sel(V1, V2)) -> U201(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isNaturalKind(n__0) -> tt 62.19/23.48 isNaturalKind(n__head(V1)) -> U211(isLNatKind(activate(V1))) 62.19/23.48 isNaturalKind(n__s(V1)) -> U221(isNaturalKind(activate(V1))) 62.19/23.48 isNaturalKind(n__sel(V1, V2)) -> U231(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNat(n__pair(V1, V2)) -> U241(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNat(n__splitAt(V1, V2)) -> U251(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNatKind(n__pair(V1, V2)) -> U261(isLNatKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNatKind(n__splitAt(V1, V2)) -> U271(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 natsFrom(N) -> U281(isNatural(N), N) 62.19/23.48 sel(N, XS) -> U291(isNatural(N), N, XS) 62.19/23.48 snd(pair(X, Y)) -> U301(isLNat(X), X, Y) 62.19/23.48 splitAt(0, XS) -> U311(isLNat(XS), XS) 62.19/23.48 splitAt(s(N), cons(X, XS)) -> U321(isNatural(N), N, X, activate(XS)) 62.19/23.48 tail(cons(N, XS)) -> U331(isNatural(N), N, activate(XS)) 62.19/23.48 take(N, XS) -> U341(isNatural(N), N, XS) 62.19/23.48 natsFrom(X) -> n__natsFrom(X) 62.19/23.48 nil -> n__nil 62.19/23.48 afterNth(X1, X2) -> n__afterNth(X1, X2) 62.19/23.48 cons(X1, X2) -> n__cons(X1, X2) 62.19/23.48 fst(X) -> n__fst(X) 62.19/23.48 snd(X) -> n__snd(X) 62.19/23.48 tail(X) -> n__tail(X) 62.19/23.48 take(X1, X2) -> n__take(X1, X2) 62.19/23.48 0 -> n__0 62.19/23.48 head(X) -> n__head(X) 62.19/23.48 s(X) -> n__s(X) 62.19/23.48 sel(X1, X2) -> n__sel(X1, X2) 62.19/23.48 pair(X1, X2) -> n__pair(X1, X2) 62.19/23.48 splitAt(X1, X2) -> n__splitAt(X1, X2) 62.19/23.48 activate(n__natsFrom(X)) -> natsFrom(X) 62.19/23.48 activate(n__nil) -> nil 62.19/23.48 activate(n__afterNth(X1, X2)) -> afterNth(X1, X2) 62.19/23.48 activate(n__cons(X1, X2)) -> cons(X1, X2) 62.19/23.48 activate(n__fst(X)) -> fst(X) 62.19/23.48 activate(n__snd(X)) -> snd(X) 62.19/23.48 activate(n__tail(X)) -> tail(X) 62.19/23.48 activate(n__take(X1, X2)) -> take(X1, X2) 62.19/23.48 activate(n__0) -> 0 62.19/23.48 activate(n__head(X)) -> head(X) 62.19/23.48 activate(n__s(X)) -> s(X) 62.19/23.48 activate(n__sel(X1, X2)) -> sel(X1, X2) 62.19/23.48 activate(n__pair(X1, X2)) -> pair(X1, X2) 62.19/23.48 activate(n__splitAt(X1, X2)) -> splitAt(X1, X2) 62.19/23.48 activate(X) -> X 62.19/23.48 62.19/23.48 S is empty. 62.19/23.48 Rewrite Strategy: FULL 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (3) DecreasingLoopProof (LOWER BOUND(ID)) 62.19/23.48 The following loop(s) give(s) rise to the lower bound Omega(n^1): 62.19/23.48 62.19/23.48 The rewrite sequence 62.19/23.48 62.19/23.48 isNaturalKind(n__sel(V1, V2)) ->^+ U231(isNaturalKind(V1), activate(V2)) 62.19/23.48 62.19/23.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 62.19/23.48 62.19/23.48 The pumping substitution is [V1 / n__sel(V1, V2)]. 62.19/23.48 62.19/23.48 The result substitution is [ ]. 62.19/23.48 62.19/23.48 62.19/23.48 62.19/23.48 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (4) 62.19/23.48 Complex Obligation (BEST) 62.19/23.48 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (5) 62.19/23.48 Obligation: 62.19/23.48 Proved the lower bound n^1 for the following obligation: 62.19/23.48 62.19/23.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 62.19/23.48 62.19/23.48 62.19/23.48 The TRS R consists of the following rules: 62.19/23.48 62.19/23.48 U101(tt, V1, V2) -> U102(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U102(tt, V1, V2) -> U103(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U103(tt, V1, V2) -> U104(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U104(tt, V1, V2) -> U105(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U105(tt, V2) -> U106(isLNat(activate(V2))) 62.19/23.48 U106(tt) -> tt 62.19/23.48 U11(tt, N, XS) -> U12(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U111(tt, V2) -> U112(isLNatKind(activate(V2))) 62.19/23.48 U112(tt) -> tt 62.19/23.48 U12(tt, N, XS) -> U13(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U121(tt, V2) -> U122(isLNatKind(activate(V2))) 62.19/23.48 U122(tt) -> tt 62.19/23.48 U13(tt, N, XS) -> U14(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U131(tt) -> tt 62.19/23.48 U14(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 62.19/23.48 U141(tt) -> tt 62.19/23.48 U151(tt) -> tt 62.19/23.48 U161(tt) -> tt 62.19/23.48 U171(tt, V2) -> U172(isLNatKind(activate(V2))) 62.19/23.48 U172(tt) -> tt 62.19/23.48 U181(tt, V1) -> U182(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U182(tt, V1) -> U183(isLNat(activate(V1))) 62.19/23.48 U183(tt) -> tt 62.19/23.48 U191(tt, V1) -> U192(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U192(tt, V1) -> U193(isNatural(activate(V1))) 62.19/23.48 U193(tt) -> tt 62.19/23.48 U201(tt, V1, V2) -> U202(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U202(tt, V1, V2) -> U203(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U203(tt, V1, V2) -> U204(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U204(tt, V1, V2) -> U205(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U205(tt, V2) -> U206(isLNat(activate(V2))) 62.19/23.48 U206(tt) -> tt 62.19/23.48 U21(tt, X, Y) -> U22(isLNatKind(activate(X)), activate(X), activate(Y)) 62.19/23.48 U211(tt) -> tt 62.19/23.48 U22(tt, X, Y) -> U23(isLNat(activate(Y)), activate(X), activate(Y)) 62.19/23.48 U221(tt) -> tt 62.19/23.48 U23(tt, X, Y) -> U24(isLNatKind(activate(Y)), activate(X)) 62.19/23.48 U231(tt, V2) -> U232(isLNatKind(activate(V2))) 62.19/23.48 U232(tt) -> tt 62.19/23.48 U24(tt, X) -> activate(X) 62.19/23.48 U241(tt, V1, V2) -> U242(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U242(tt, V1, V2) -> U243(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U243(tt, V1, V2) -> U244(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U244(tt, V1, V2) -> U245(isLNat(activate(V1)), activate(V2)) 62.19/23.48 U245(tt, V2) -> U246(isLNat(activate(V2))) 62.19/23.48 U246(tt) -> tt 62.19/23.48 U251(tt, V1, V2) -> U252(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U252(tt, V1, V2) -> U253(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U253(tt, V1, V2) -> U254(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U254(tt, V1, V2) -> U255(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U255(tt, V2) -> U256(isLNat(activate(V2))) 62.19/23.48 U256(tt) -> tt 62.19/23.48 U261(tt, V2) -> U262(isLNatKind(activate(V2))) 62.19/23.48 U262(tt) -> tt 62.19/23.48 U271(tt, V2) -> U272(isLNatKind(activate(V2))) 62.19/23.48 U272(tt) -> tt 62.19/23.48 U281(tt, N) -> U282(isNaturalKind(activate(N)), activate(N)) 62.19/23.48 U282(tt, N) -> cons(activate(N), n__natsFrom(s(activate(N)))) 62.19/23.48 U291(tt, N, XS) -> U292(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U292(tt, N, XS) -> U293(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U293(tt, N, XS) -> U294(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U294(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 62.19/23.48 U301(tt, X, Y) -> U302(isLNatKind(activate(X)), activate(Y)) 62.19/23.48 U302(tt, Y) -> U303(isLNat(activate(Y)), activate(Y)) 62.19/23.48 U303(tt, Y) -> U304(isLNatKind(activate(Y)), activate(Y)) 62.19/23.48 U304(tt, Y) -> activate(Y) 62.19/23.48 U31(tt, N, XS) -> U32(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U311(tt, XS) -> U312(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U312(tt, XS) -> pair(nil, activate(XS)) 62.19/23.48 U32(tt, N, XS) -> U33(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U321(tt, N, X, XS) -> U322(isNaturalKind(activate(N)), activate(N), activate(X), activate(XS)) 62.19/23.48 U322(tt, N, X, XS) -> U323(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U323(tt, N, X, XS) -> U324(isNaturalKind(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U324(tt, N, X, XS) -> U325(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U325(tt, N, X, XS) -> U326(isLNatKind(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U326(tt, N, X, XS) -> U327(splitAt(activate(N), activate(XS)), activate(X)) 62.19/23.48 U327(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 62.19/23.48 U33(tt, N, XS) -> U34(isLNatKind(activate(XS)), activate(N)) 62.19/23.48 U331(tt, N, XS) -> U332(isNaturalKind(activate(N)), activate(XS)) 62.19/23.48 U332(tt, XS) -> U333(isLNat(activate(XS)), activate(XS)) 62.19/23.48 U333(tt, XS) -> U334(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U334(tt, XS) -> activate(XS) 62.19/23.48 U34(tt, N) -> activate(N) 62.19/23.48 U341(tt, N, XS) -> U342(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U342(tt, N, XS) -> U343(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U343(tt, N, XS) -> U344(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U344(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 62.19/23.48 U41(tt, V1, V2) -> U42(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U42(tt, V1, V2) -> U43(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U43(tt, V1, V2) -> U44(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U44(tt, V1, V2) -> U45(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U45(tt, V2) -> U46(isLNat(activate(V2))) 62.19/23.48 U46(tt) -> tt 62.19/23.48 U51(tt, V1, V2) -> U52(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U52(tt, V1, V2) -> U53(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U53(tt, V1, V2) -> U54(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U54(tt, V1, V2) -> U55(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U55(tt, V2) -> U56(isLNat(activate(V2))) 62.19/23.48 U56(tt) -> tt 62.19/23.48 U61(tt, V1) -> U62(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U62(tt, V1) -> U63(isPLNat(activate(V1))) 62.19/23.48 U63(tt) -> tt 62.19/23.48 U71(tt, V1) -> U72(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U72(tt, V1) -> U73(isNatural(activate(V1))) 62.19/23.48 U73(tt) -> tt 62.19/23.48 U81(tt, V1) -> U82(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U82(tt, V1) -> U83(isPLNat(activate(V1))) 62.19/23.48 U83(tt) -> tt 62.19/23.48 U91(tt, V1) -> U92(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U92(tt, V1) -> U93(isLNat(activate(V1))) 62.19/23.48 U93(tt) -> tt 62.19/23.48 afterNth(N, XS) -> U11(isNatural(N), N, XS) 62.19/23.48 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 62.19/23.48 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 62.19/23.48 isLNat(n__nil) -> tt 62.19/23.48 isLNat(n__afterNth(V1, V2)) -> U41(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__cons(V1, V2)) -> U51(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__fst(V1)) -> U61(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__natsFrom(V1)) -> U71(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__snd(V1)) -> U81(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__tail(V1)) -> U91(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__take(V1, V2)) -> U101(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNatKind(n__nil) -> tt 62.19/23.48 isLNatKind(n__afterNth(V1, V2)) -> U111(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__cons(V1, V2)) -> U121(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__fst(V1)) -> U131(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__natsFrom(V1)) -> U141(isNaturalKind(activate(V1))) 62.19/23.48 isLNatKind(n__snd(V1)) -> U151(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__tail(V1)) -> U161(isLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__take(V1, V2)) -> U171(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isNatural(n__0) -> tt 62.19/23.48 isNatural(n__head(V1)) -> U181(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__s(V1)) -> U191(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isNatural(n__sel(V1, V2)) -> U201(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isNaturalKind(n__0) -> tt 62.19/23.48 isNaturalKind(n__head(V1)) -> U211(isLNatKind(activate(V1))) 62.19/23.48 isNaturalKind(n__s(V1)) -> U221(isNaturalKind(activate(V1))) 62.19/23.48 isNaturalKind(n__sel(V1, V2)) -> U231(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNat(n__pair(V1, V2)) -> U241(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNat(n__splitAt(V1, V2)) -> U251(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isPLNatKind(n__pair(V1, V2)) -> U261(isLNatKind(activate(V1)), activate(V2)) 62.19/23.48 isPLNatKind(n__splitAt(V1, V2)) -> U271(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 natsFrom(N) -> U281(isNatural(N), N) 62.19/23.48 sel(N, XS) -> U291(isNatural(N), N, XS) 62.19/23.48 snd(pair(X, Y)) -> U301(isLNat(X), X, Y) 62.19/23.48 splitAt(0, XS) -> U311(isLNat(XS), XS) 62.19/23.48 splitAt(s(N), cons(X, XS)) -> U321(isNatural(N), N, X, activate(XS)) 62.19/23.48 tail(cons(N, XS)) -> U331(isNatural(N), N, activate(XS)) 62.19/23.48 take(N, XS) -> U341(isNatural(N), N, XS) 62.19/23.48 natsFrom(X) -> n__natsFrom(X) 62.19/23.48 nil -> n__nil 62.19/23.48 afterNth(X1, X2) -> n__afterNth(X1, X2) 62.19/23.48 cons(X1, X2) -> n__cons(X1, X2) 62.19/23.48 fst(X) -> n__fst(X) 62.19/23.48 snd(X) -> n__snd(X) 62.19/23.48 tail(X) -> n__tail(X) 62.19/23.48 take(X1, X2) -> n__take(X1, X2) 62.19/23.48 0 -> n__0 62.19/23.48 head(X) -> n__head(X) 62.19/23.48 s(X) -> n__s(X) 62.19/23.48 sel(X1, X2) -> n__sel(X1, X2) 62.19/23.48 pair(X1, X2) -> n__pair(X1, X2) 62.19/23.48 splitAt(X1, X2) -> n__splitAt(X1, X2) 62.19/23.48 activate(n__natsFrom(X)) -> natsFrom(X) 62.19/23.48 activate(n__nil) -> nil 62.19/23.48 activate(n__afterNth(X1, X2)) -> afterNth(X1, X2) 62.19/23.48 activate(n__cons(X1, X2)) -> cons(X1, X2) 62.19/23.48 activate(n__fst(X)) -> fst(X) 62.19/23.48 activate(n__snd(X)) -> snd(X) 62.19/23.48 activate(n__tail(X)) -> tail(X) 62.19/23.48 activate(n__take(X1, X2)) -> take(X1, X2) 62.19/23.48 activate(n__0) -> 0 62.19/23.48 activate(n__head(X)) -> head(X) 62.19/23.48 activate(n__s(X)) -> s(X) 62.19/23.48 activate(n__sel(X1, X2)) -> sel(X1, X2) 62.19/23.48 activate(n__pair(X1, X2)) -> pair(X1, X2) 62.19/23.48 activate(n__splitAt(X1, X2)) -> splitAt(X1, X2) 62.19/23.48 activate(X) -> X 62.19/23.48 62.19/23.48 S is empty. 62.19/23.48 Rewrite Strategy: FULL 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (6) LowerBoundPropagationProof (FINISHED) 62.19/23.48 Propagated lower bound. 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (7) 62.19/23.48 BOUNDS(n^1, INF) 62.19/23.48 62.19/23.48 ---------------------------------------- 62.19/23.48 62.19/23.48 (8) 62.19/23.48 Obligation: 62.19/23.48 Analyzing the following TRS for decreasing loops: 62.19/23.48 62.19/23.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 62.19/23.48 62.19/23.48 62.19/23.48 The TRS R consists of the following rules: 62.19/23.48 62.19/23.48 U101(tt, V1, V2) -> U102(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U102(tt, V1, V2) -> U103(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U103(tt, V1, V2) -> U104(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U104(tt, V1, V2) -> U105(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U105(tt, V2) -> U106(isLNat(activate(V2))) 62.19/23.48 U106(tt) -> tt 62.19/23.48 U11(tt, N, XS) -> U12(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U111(tt, V2) -> U112(isLNatKind(activate(V2))) 62.19/23.48 U112(tt) -> tt 62.19/23.48 U12(tt, N, XS) -> U13(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U121(tt, V2) -> U122(isLNatKind(activate(V2))) 62.19/23.48 U122(tt) -> tt 62.19/23.48 U13(tt, N, XS) -> U14(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U131(tt) -> tt 62.19/23.48 U14(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 62.19/23.48 U141(tt) -> tt 62.19/23.48 U151(tt) -> tt 62.19/23.48 U161(tt) -> tt 62.19/23.48 U171(tt, V2) -> U172(isLNatKind(activate(V2))) 62.19/23.48 U172(tt) -> tt 62.19/23.48 U181(tt, V1) -> U182(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U182(tt, V1) -> U183(isLNat(activate(V1))) 62.19/23.48 U183(tt) -> tt 62.19/23.48 U191(tt, V1) -> U192(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U192(tt, V1) -> U193(isNatural(activate(V1))) 62.19/23.48 U193(tt) -> tt 62.19/23.48 U201(tt, V1, V2) -> U202(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U202(tt, V1, V2) -> U203(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U203(tt, V1, V2) -> U204(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U204(tt, V1, V2) -> U205(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U205(tt, V2) -> U206(isLNat(activate(V2))) 62.19/23.48 U206(tt) -> tt 62.19/23.48 U21(tt, X, Y) -> U22(isLNatKind(activate(X)), activate(X), activate(Y)) 62.19/23.48 U211(tt) -> tt 62.19/23.48 U22(tt, X, Y) -> U23(isLNat(activate(Y)), activate(X), activate(Y)) 62.19/23.48 U221(tt) -> tt 62.19/23.48 U23(tt, X, Y) -> U24(isLNatKind(activate(Y)), activate(X)) 62.19/23.48 U231(tt, V2) -> U232(isLNatKind(activate(V2))) 62.19/23.48 U232(tt) -> tt 62.19/23.48 U24(tt, X) -> activate(X) 62.19/23.48 U241(tt, V1, V2) -> U242(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U242(tt, V1, V2) -> U243(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U243(tt, V1, V2) -> U244(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U244(tt, V1, V2) -> U245(isLNat(activate(V1)), activate(V2)) 62.19/23.48 U245(tt, V2) -> U246(isLNat(activate(V2))) 62.19/23.48 U246(tt) -> tt 62.19/23.48 U251(tt, V1, V2) -> U252(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U252(tt, V1, V2) -> U253(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U253(tt, V1, V2) -> U254(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U254(tt, V1, V2) -> U255(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U255(tt, V2) -> U256(isLNat(activate(V2))) 62.19/23.48 U256(tt) -> tt 62.19/23.48 U261(tt, V2) -> U262(isLNatKind(activate(V2))) 62.19/23.48 U262(tt) -> tt 62.19/23.48 U271(tt, V2) -> U272(isLNatKind(activate(V2))) 62.19/23.48 U272(tt) -> tt 62.19/23.48 U281(tt, N) -> U282(isNaturalKind(activate(N)), activate(N)) 62.19/23.48 U282(tt, N) -> cons(activate(N), n__natsFrom(s(activate(N)))) 62.19/23.48 U291(tt, N, XS) -> U292(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U292(tt, N, XS) -> U293(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U293(tt, N, XS) -> U294(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U294(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 62.19/23.48 U301(tt, X, Y) -> U302(isLNatKind(activate(X)), activate(Y)) 62.19/23.48 U302(tt, Y) -> U303(isLNat(activate(Y)), activate(Y)) 62.19/23.48 U303(tt, Y) -> U304(isLNatKind(activate(Y)), activate(Y)) 62.19/23.48 U304(tt, Y) -> activate(Y) 62.19/23.48 U31(tt, N, XS) -> U32(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U311(tt, XS) -> U312(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U312(tt, XS) -> pair(nil, activate(XS)) 62.19/23.48 U32(tt, N, XS) -> U33(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U321(tt, N, X, XS) -> U322(isNaturalKind(activate(N)), activate(N), activate(X), activate(XS)) 62.19/23.48 U322(tt, N, X, XS) -> U323(isNatural(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U323(tt, N, X, XS) -> U324(isNaturalKind(activate(X)), activate(N), activate(X), activate(XS)) 62.19/23.48 U324(tt, N, X, XS) -> U325(isLNat(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U325(tt, N, X, XS) -> U326(isLNatKind(activate(XS)), activate(N), activate(X), activate(XS)) 62.19/23.48 U326(tt, N, X, XS) -> U327(splitAt(activate(N), activate(XS)), activate(X)) 62.19/23.48 U327(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 62.19/23.48 U33(tt, N, XS) -> U34(isLNatKind(activate(XS)), activate(N)) 62.19/23.48 U331(tt, N, XS) -> U332(isNaturalKind(activate(N)), activate(XS)) 62.19/23.48 U332(tt, XS) -> U333(isLNat(activate(XS)), activate(XS)) 62.19/23.48 U333(tt, XS) -> U334(isLNatKind(activate(XS)), activate(XS)) 62.19/23.48 U334(tt, XS) -> activate(XS) 62.19/23.48 U34(tt, N) -> activate(N) 62.19/23.48 U341(tt, N, XS) -> U342(isNaturalKind(activate(N)), activate(N), activate(XS)) 62.19/23.48 U342(tt, N, XS) -> U343(isLNat(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U343(tt, N, XS) -> U344(isLNatKind(activate(XS)), activate(N), activate(XS)) 62.19/23.48 U344(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 62.19/23.48 U41(tt, V1, V2) -> U42(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U42(tt, V1, V2) -> U43(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U43(tt, V1, V2) -> U44(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U44(tt, V1, V2) -> U45(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U45(tt, V2) -> U46(isLNat(activate(V2))) 62.19/23.48 U46(tt) -> tt 62.19/23.48 U51(tt, V1, V2) -> U52(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 U52(tt, V1, V2) -> U53(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U53(tt, V1, V2) -> U54(isLNatKind(activate(V2)), activate(V1), activate(V2)) 62.19/23.48 U54(tt, V1, V2) -> U55(isNatural(activate(V1)), activate(V2)) 62.19/23.48 U55(tt, V2) -> U56(isLNat(activate(V2))) 62.19/23.48 U56(tt) -> tt 62.19/23.48 U61(tt, V1) -> U62(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U62(tt, V1) -> U63(isPLNat(activate(V1))) 62.19/23.48 U63(tt) -> tt 62.19/23.48 U71(tt, V1) -> U72(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 U72(tt, V1) -> U73(isNatural(activate(V1))) 62.19/23.48 U73(tt) -> tt 62.19/23.48 U81(tt, V1) -> U82(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U82(tt, V1) -> U83(isPLNat(activate(V1))) 62.19/23.48 U83(tt) -> tt 62.19/23.48 U91(tt, V1) -> U92(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 U92(tt, V1) -> U93(isLNat(activate(V1))) 62.19/23.48 U93(tt) -> tt 62.19/23.48 afterNth(N, XS) -> U11(isNatural(N), N, XS) 62.19/23.48 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 62.19/23.48 head(cons(N, XS)) -> U31(isNatural(N), N, activate(XS)) 62.19/23.48 isLNat(n__nil) -> tt 62.19/23.48 isLNat(n__afterNth(V1, V2)) -> U41(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__cons(V1, V2)) -> U51(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNat(n__fst(V1)) -> U61(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__natsFrom(V1)) -> U71(isNaturalKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__snd(V1)) -> U81(isPLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__tail(V1)) -> U91(isLNatKind(activate(V1)), activate(V1)) 62.19/23.48 isLNat(n__take(V1, V2)) -> U101(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.19/23.48 isLNatKind(n__nil) -> tt 62.19/23.48 isLNatKind(n__afterNth(V1, V2)) -> U111(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__cons(V1, V2)) -> U121(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isLNatKind(n__fst(V1)) -> U131(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__natsFrom(V1)) -> U141(isNaturalKind(activate(V1))) 62.19/23.48 isLNatKind(n__snd(V1)) -> U151(isPLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__tail(V1)) -> U161(isLNatKind(activate(V1))) 62.19/23.48 isLNatKind(n__take(V1, V2)) -> U171(isNaturalKind(activate(V1)), activate(V2)) 62.19/23.48 isNatural(n__0) -> tt 62.19/23.48 isNatural(n__head(V1)) -> U181(isLNatKind(activate(V1)), activate(V1)) 62.53/23.48 isNatural(n__s(V1)) -> U191(isNaturalKind(activate(V1)), activate(V1)) 62.53/23.48 isNatural(n__sel(V1, V2)) -> U201(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.53/23.48 isNaturalKind(n__0) -> tt 62.53/23.48 isNaturalKind(n__head(V1)) -> U211(isLNatKind(activate(V1))) 62.53/23.48 isNaturalKind(n__s(V1)) -> U221(isNaturalKind(activate(V1))) 62.53/23.48 isNaturalKind(n__sel(V1, V2)) -> U231(isNaturalKind(activate(V1)), activate(V2)) 62.53/23.48 isPLNat(n__pair(V1, V2)) -> U241(isLNatKind(activate(V1)), activate(V1), activate(V2)) 62.53/23.48 isPLNat(n__splitAt(V1, V2)) -> U251(isNaturalKind(activate(V1)), activate(V1), activate(V2)) 62.53/23.48 isPLNatKind(n__pair(V1, V2)) -> U261(isLNatKind(activate(V1)), activate(V2)) 62.53/23.48 isPLNatKind(n__splitAt(V1, V2)) -> U271(isNaturalKind(activate(V1)), activate(V2)) 62.53/23.48 natsFrom(N) -> U281(isNatural(N), N) 62.53/23.48 sel(N, XS) -> U291(isNatural(N), N, XS) 62.53/23.48 snd(pair(X, Y)) -> U301(isLNat(X), X, Y) 62.53/23.48 splitAt(0, XS) -> U311(isLNat(XS), XS) 62.53/23.48 splitAt(s(N), cons(X, XS)) -> U321(isNatural(N), N, X, activate(XS)) 62.53/23.48 tail(cons(N, XS)) -> U331(isNatural(N), N, activate(XS)) 62.53/23.48 take(N, XS) -> U341(isNatural(N), N, XS) 62.53/23.48 natsFrom(X) -> n__natsFrom(X) 62.53/23.48 nil -> n__nil 62.53/23.48 afterNth(X1, X2) -> n__afterNth(X1, X2) 62.53/23.48 cons(X1, X2) -> n__cons(X1, X2) 62.53/23.48 fst(X) -> n__fst(X) 62.53/23.48 snd(X) -> n__snd(X) 62.53/23.48 tail(X) -> n__tail(X) 62.53/23.48 take(X1, X2) -> n__take(X1, X2) 62.53/23.48 0 -> n__0 62.53/23.48 head(X) -> n__head(X) 62.53/23.48 s(X) -> n__s(X) 62.53/23.48 sel(X1, X2) -> n__sel(X1, X2) 62.53/23.48 pair(X1, X2) -> n__pair(X1, X2) 62.53/23.48 splitAt(X1, X2) -> n__splitAt(X1, X2) 62.53/23.48 activate(n__natsFrom(X)) -> natsFrom(X) 62.53/23.48 activate(n__nil) -> nil 62.53/23.48 activate(n__afterNth(X1, X2)) -> afterNth(X1, X2) 62.53/23.48 activate(n__cons(X1, X2)) -> cons(X1, X2) 62.53/23.48 activate(n__fst(X)) -> fst(X) 62.53/23.48 activate(n__snd(X)) -> snd(X) 62.53/23.48 activate(n__tail(X)) -> tail(X) 62.53/23.48 activate(n__take(X1, X2)) -> take(X1, X2) 62.53/23.48 activate(n__0) -> 0 62.53/23.48 activate(n__head(X)) -> head(X) 62.53/23.48 activate(n__s(X)) -> s(X) 62.53/23.48 activate(n__sel(X1, X2)) -> sel(X1, X2) 62.53/23.48 activate(n__pair(X1, X2)) -> pair(X1, X2) 62.53/23.48 activate(n__splitAt(X1, X2)) -> splitAt(X1, X2) 62.53/23.48 activate(X) -> X 62.53/23.48 62.53/23.48 S is empty. 62.53/23.48 Rewrite Strategy: FULL 62.53/23.48 ---------------------------------------- 62.53/23.48 62.53/23.48 (9) DecreasingLoopProof (FINISHED) 62.53/23.48 The following loop(s) give(s) rise to the lower bound EXP: 62.53/23.48 62.53/23.48 The rewrite sequence 62.53/23.48 62.53/23.48 activate(n__take(n__head(V11_0), X2)) ->^+ U341(U181(isLNatKind(activate(V11_0)), activate(V11_0)), n__head(V11_0), X2) 62.53/23.48 62.53/23.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0]. 62.53/23.48 62.53/23.48 The pumping substitution is [V11_0 / n__take(n__head(V11_0), X2)]. 62.53/23.48 62.53/23.48 The result substitution is [ ]. 62.53/23.48 62.53/23.48 62.53/23.48 62.53/23.48 The rewrite sequence 62.53/23.48 62.53/23.48 activate(n__take(n__head(V11_0), X2)) ->^+ U341(U181(isLNatKind(activate(V11_0)), activate(V11_0)), n__head(V11_0), X2) 62.53/23.48 62.53/23.48 gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1]. 62.53/23.48 62.53/23.48 The pumping substitution is [V11_0 / n__take(n__head(V11_0), X2)]. 62.53/23.48 62.53/23.48 The result substitution is [ ]. 62.53/23.48 62.53/23.48 62.53/23.48 62.53/23.48 62.53/23.48 ---------------------------------------- 62.53/23.48 62.53/23.48 (10) 62.53/23.48 BOUNDS(EXP, INF) 62.53/23.50 EOF