3.09/1.59 WORST_CASE(NON_POLY, ?) 3.09/1.60 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 3.09/1.60 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.09/1.60 3.09/1.60 3.09/1.60 The Runtime Complexity of the given Name of obligation not specified could be proven to be BOUNDS(INF, INF). 3.09/1.60 3.09/1.60 (0) Name of obligation not specified 3.09/1.60 (1) ExtraVarProof [FINISHED, 0 ms] 3.09/1.60 (2) BOUNDS(INF, INF) 3.09/1.60 3.09/1.60 3.09/1.60 ---------------------------------------- 3.09/1.60 3.09/1.60 (0) 3.09/1.60 Obligation: 3.09/1.60 The Runtime Complexity of the given Name of obligation not specified could be proven to be BOUNDS(INF, INF). 3.09/1.60 3.09/1.60 3.09/1.60 The TRS R consists of the following rules: 3.09/1.60 3.09/1.60 U14(tt) -> snd(splitAt(N, XS)) 3.09/1.60 U24(tt) -> X 3.09/1.60 U282(tt) -> cons(N) 3.09/1.60 U294(tt) -> head(afterNth(N, XS)) 3.09/1.60 U304(tt) -> Y 3.09/1.60 U312(tt) -> pair(nil, XS) 3.09/1.60 U326(tt) -> U327(splitAt(N, XS)) 3.09/1.60 U327(pair(YS, ZS)) -> pair(cons(X), ZS) 3.09/1.60 U334(tt) -> XS 3.09/1.60 U34(tt) -> N 3.09/1.60 U344(tt) -> fst(splitAt(N, XS)) 3.09/1.60 U101(tt) -> U102(isNaturalKind) 3.09/1.60 U102(tt) -> U103(isLNatKind) 3.09/1.60 U103(tt) -> U104(isLNatKind) 3.09/1.60 U104(tt) -> U105(isNatural) 3.09/1.60 U105(tt) -> U106(isLNat) 3.09/1.60 U106(tt) -> tt 3.09/1.60 U11(tt) -> U12(isNaturalKind) 3.09/1.60 U111(tt) -> U112(isLNatKind) 3.09/1.60 U112(tt) -> tt 3.09/1.60 U12(tt) -> U13(isLNat) 3.09/1.60 U121(tt) -> U122(isLNatKind) 3.09/1.60 U122(tt) -> tt 3.09/1.60 U13(tt) -> U14(isLNatKind) 3.09/1.60 U131(tt) -> tt 3.09/1.60 U141(tt) -> tt 3.09/1.60 U151(tt) -> tt 3.09/1.60 U161(tt) -> tt 3.09/1.60 U171(tt) -> U172(isLNatKind) 3.09/1.60 U172(tt) -> tt 3.09/1.60 U181(tt) -> U182(isLNatKind) 3.09/1.60 U182(tt) -> U183(isLNat) 3.09/1.60 U183(tt) -> tt 3.09/1.60 U191(tt) -> U192(isNaturalKind) 3.09/1.60 U192(tt) -> U193(isNatural) 3.09/1.60 U193(tt) -> tt 3.09/1.60 U201(tt) -> U202(isNaturalKind) 3.09/1.60 U202(tt) -> U203(isLNatKind) 3.09/1.60 U203(tt) -> U204(isLNatKind) 3.09/1.60 U204(tt) -> U205(isNatural) 3.09/1.60 U205(tt) -> U206(isLNat) 3.09/1.60 U206(tt) -> tt 3.09/1.60 U21(tt) -> U22(isLNatKind) 3.09/1.60 U211(tt) -> tt 3.09/1.60 U22(tt) -> U23(isLNat) 3.09/1.60 U221(tt) -> tt 3.09/1.60 U23(tt) -> U24(isLNatKind) 3.09/1.60 U231(tt) -> U232(isLNatKind) 3.09/1.60 U232(tt) -> tt 3.09/1.60 U241(tt) -> U242(isLNatKind) 3.09/1.60 U242(tt) -> U243(isLNatKind) 3.09/1.60 U243(tt) -> U244(isLNatKind) 3.09/1.60 U244(tt) -> U245(isLNat) 3.09/1.60 U245(tt) -> U246(isLNat) 3.09/1.60 U246(tt) -> tt 3.09/1.60 U251(tt) -> U252(isNaturalKind) 3.09/1.60 U252(tt) -> U253(isLNatKind) 3.09/1.60 U253(tt) -> U254(isLNatKind) 3.09/1.60 U254(tt) -> U255(isNatural) 3.09/1.60 U255(tt) -> U256(isLNat) 3.09/1.60 U256(tt) -> tt 3.09/1.60 U261(tt) -> U262(isLNatKind) 3.09/1.60 U262(tt) -> tt 3.09/1.60 U271(tt) -> U272(isLNatKind) 3.09/1.60 U272(tt) -> tt 3.09/1.60 U281(tt) -> U282(isNaturalKind) 3.09/1.60 U291(tt) -> U292(isNaturalKind) 3.09/1.60 U292(tt) -> U293(isLNat) 3.09/1.60 U293(tt) -> U294(isLNatKind) 3.09/1.60 U301(tt) -> U302(isLNatKind) 3.09/1.60 U302(tt) -> U303(isLNat) 3.09/1.60 U303(tt) -> U304(isLNatKind) 3.09/1.60 U31(tt) -> U32(isNaturalKind) 3.09/1.60 U311(tt) -> U312(isLNatKind) 3.09/1.60 U32(tt) -> U33(isLNat) 3.09/1.60 U321(tt) -> U322(isNaturalKind) 3.09/1.60 U322(tt) -> U323(isNatural) 3.09/1.60 U323(tt) -> U324(isNaturalKind) 3.09/1.60 U324(tt) -> U325(isLNat) 3.09/1.60 U325(tt) -> U326(isLNatKind) 3.09/1.60 U33(tt) -> U34(isLNatKind) 3.09/1.60 U331(tt) -> U332(isNaturalKind) 3.09/1.60 U332(tt) -> U333(isLNat) 3.09/1.60 U333(tt) -> U334(isLNatKind) 3.09/1.60 U341(tt) -> U342(isNaturalKind) 3.09/1.60 U342(tt) -> U343(isLNat) 3.09/1.60 U343(tt) -> U344(isLNatKind) 3.09/1.60 U41(tt) -> U42(isNaturalKind) 3.09/1.60 U42(tt) -> U43(isLNatKind) 3.09/1.60 U43(tt) -> U44(isLNatKind) 3.09/1.60 U44(tt) -> U45(isNatural) 3.09/1.60 U45(tt) -> U46(isLNat) 3.09/1.60 U46(tt) -> tt 3.09/1.60 U51(tt) -> U52(isNaturalKind) 3.09/1.60 U52(tt) -> U53(isLNatKind) 3.09/1.60 U53(tt) -> U54(isLNatKind) 3.09/1.60 U54(tt) -> U55(isNatural) 3.09/1.60 U55(tt) -> U56(isLNat) 3.09/1.60 U56(tt) -> tt 3.09/1.60 U61(tt) -> U62(isPLNatKind) 3.09/1.60 U62(tt) -> U63(isPLNat) 3.09/1.60 U63(tt) -> tt 3.09/1.60 U71(tt) -> U72(isNaturalKind) 3.09/1.60 U72(tt) -> U73(isNatural) 3.09/1.60 U73(tt) -> tt 3.09/1.60 U81(tt) -> U82(isPLNatKind) 3.09/1.60 U82(tt) -> U83(isPLNat) 3.09/1.60 U83(tt) -> tt 3.09/1.60 U91(tt) -> U92(isLNatKind) 3.09/1.60 U92(tt) -> U93(isLNat) 3.09/1.60 U93(tt) -> tt 3.09/1.60 afterNth(N, XS) -> U11(isNatural) 3.09/1.60 fst(pair(X, Y)) -> U21(isLNat) 3.09/1.60 head(cons(N)) -> U31(isNatural) 3.09/1.60 isLNat -> tt 3.09/1.60 isLNat -> U41(isNaturalKind) 3.09/1.60 isLNat -> U51(isNaturalKind) 3.09/1.60 isLNat -> U61(isPLNatKind) 3.09/1.60 isLNat -> U71(isNaturalKind) 3.09/1.60 isLNat -> U81(isPLNatKind) 3.09/1.60 isLNat -> U91(isLNatKind) 3.09/1.60 isLNat -> U101(isNaturalKind) 3.09/1.60 isLNatKind -> tt 3.09/1.60 isLNatKind -> U111(isNaturalKind) 3.09/1.60 isLNatKind -> U121(isNaturalKind) 3.09/1.60 isLNatKind -> U131(isPLNatKind) 3.09/1.60 isLNatKind -> U141(isNaturalKind) 3.09/1.60 isLNatKind -> U151(isPLNatKind) 3.09/1.60 isLNatKind -> U161(isLNatKind) 3.09/1.60 isLNatKind -> U171(isNaturalKind) 3.09/1.60 isNatural -> tt 3.09/1.60 isNatural -> U181(isLNatKind) 3.09/1.60 isNatural -> U191(isNaturalKind) 3.09/1.60 isNatural -> U201(isNaturalKind) 3.09/1.60 isNaturalKind -> tt 3.09/1.60 isNaturalKind -> U211(isLNatKind) 3.09/1.60 isNaturalKind -> U221(isNaturalKind) 3.09/1.60 isNaturalKind -> U231(isNaturalKind) 3.09/1.60 isPLNat -> U241(isLNatKind) 3.09/1.60 isPLNat -> U251(isNaturalKind) 3.09/1.60 isPLNatKind -> U261(isLNatKind) 3.09/1.60 isPLNatKind -> U271(isNaturalKind) 3.09/1.60 natsFrom(N) -> U281(isNatural) 3.09/1.60 sel(N, XS) -> U291(isNatural) 3.09/1.60 snd(pair(X, Y)) -> U301(isLNat) 3.09/1.60 splitAt(0, XS) -> U311(isLNat) 3.09/1.60 splitAt(s(N), cons(X)) -> U321(isNatural) 3.09/1.60 tail(cons(N)) -> U331(isNatural) 3.09/1.60 take(N, XS) -> U341(isNatural) 3.09/1.60 3.09/1.60 3.09/1.60 ---------------------------------------- 3.09/1.60 3.09/1.60 (1) ExtraVarProof (FINISHED) 3.09/1.60 unbounded runtime complexity due to extra variable on rhs 3.09/1.60 ---------------------------------------- 3.09/1.60 3.09/1.60 (2) 3.09/1.60 BOUNDS(INF, INF) 3.32/1.63 EOF