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