/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (4) CdtProblem (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 6 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 129 ms] (12) CdtProblem (13) CdtKnowledgeProof [FINISHED, 2 ms] (14) BOUNDS(1, 1) (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (16) TRS for Loop Detection (17) DecreasingLoopProof [LOWER BOUND(ID), 17.1 s] (18) BEST (19) proven lower bound (20) LowerBoundPropagationProof [FINISHED, 0 ms] (21) BOUNDS(n^1, INF) (22) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) U21(tt, X) -> U22(tt, activate(X)) U22(tt, X) -> activate(X) U31(tt, N) -> U32(tt, activate(N)) U32(tt, N) -> activate(N) U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) U51(tt, Y) -> U52(tt, activate(Y)) U52(tt, Y) -> activate(Y) U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) U71(tt, XS) -> U72(tt, activate(XS)) U72(tt, XS) -> activate(XS) U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) afterNth(N, XS) -> U11(tt, N, XS) fst(pair(X, Y)) -> U21(tt, X) head(cons(N, XS)) -> U31(tt, N) natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> U41(tt, N, XS) snd(pair(X, Y)) -> U51(tt, Y) splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) tail(cons(N, XS)) -> U71(tt, activate(XS)) take(N, XS) -> U81(tt, N, XS) natsFrom(X) -> n__natsFrom(X) activate(n__natsFrom(X)) -> natsFrom(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) U21(tt, z0) -> U22(tt, activate(z0)) U22(tt, z0) -> activate(z0) U31(tt, z0) -> U32(tt, activate(z0)) U32(tt, z0) -> activate(z0) U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) U51(tt, z0) -> U52(tt, activate(z0)) U52(tt, z0) -> activate(z0) U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) U71(tt, z0) -> U72(tt, activate(z0)) U72(tt, z0) -> activate(z0) U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) afterNth(z0, z1) -> U11(tt, z0, z1) fst(pair(z0, z1)) -> U21(tt, z0) head(cons(z0, z1)) -> U31(tt, z0) natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> U41(tt, z0, z1) snd(pair(z0, z1)) -> U51(tt, z1) splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> U71(tt, activate(z1)) take(z0, z1) -> U81(tt, z0, z1) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) U22'(tt, z0) -> c3(ACTIVATE(z0)) U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) U32'(tt, z0) -> c5(ACTIVATE(z0)) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) U52'(tt, z0) -> c9(ACTIVATE(z0)) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U63'(tt, z0, z1, z2) -> c12(U64'(splitAt(activate(z0), activate(z2)), activate(z1)), SPLITAT(activate(z0), activate(z2)), ACTIVATE(z0), ACTIVATE(z2), ACTIVATE(z1)) U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) U72'(tt, z0) -> c15(ACTIVATE(z0)) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) FST(pair(z0, z1)) -> c19(U21'(tt, z0)) HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) NATSFROM(z0) -> c21 NATSFROM(z0) -> c22 SEL(z0, z1) -> c23(U41'(tt, z0, z1)) SND(pair(z0, z1)) -> c24(U51'(tt, z1)) SPLITAT(0, z0) -> c25 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) ACTIVATE(z0) -> c30 S tuples: U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) U22'(tt, z0) -> c3(ACTIVATE(z0)) U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) U32'(tt, z0) -> c5(ACTIVATE(z0)) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) U52'(tt, z0) -> c9(ACTIVATE(z0)) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U63'(tt, z0, z1, z2) -> c12(U64'(splitAt(activate(z0), activate(z2)), activate(z1)), SPLITAT(activate(z0), activate(z2)), ACTIVATE(z0), ACTIVATE(z2), ACTIVATE(z1)) U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) U72'(tt, z0) -> c15(ACTIVATE(z0)) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) FST(pair(z0, z1)) -> c19(U21'(tt, z0)) HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) NATSFROM(z0) -> c21 NATSFROM(z0) -> c22 SEL(z0, z1) -> c23(U41'(tt, z0, z1)) SND(pair(z0, z1)) -> c24(U51'(tt, z1)) SPLITAT(0, z0) -> c25 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) ACTIVATE(z0) -> c30 K tuples:none Defined Rule Symbols: U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, U71_2, U72_2, U81_3, U82_3, afterNth_2, fst_1, head_1, natsFrom_1, sel_2, snd_1, splitAt_2, tail_1, take_2, activate_1 Defined Pair Symbols: U11'_3, U12'_3, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, U71'_2, U72'_2, U81'_3, U82'_3, AFTERNTH_2, FST_1, HEAD_1, NATSFROM_1, SEL_2, SND_1, SPLITAT_2, TAIL_1, TAKE_2, ACTIVATE_1 Compound Symbols: c_3, c1_4, c2_2, c3_1, c4_2, c5_1, c6_3, c7_4, c8_2, c9_1, c10_4, c11_4, c12_5, c13_1, c14_2, c15_1, c16_3, c17_4, c18_1, c19_1, c20_1, c21, c22, c23_1, c24_1, c25, c26_2, c27_2, c28_1, c29_1, c30 ---------------------------------------- (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 2 leading nodes: SEL(z0, z1) -> c23(U41'(tt, z0, z1)) TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) Removed 18 trailing nodes: U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) NATSFROM(z0) -> c22 ACTIVATE(z0) -> c30 NATSFROM(z0) -> c21 SND(pair(z0, z1)) -> c24(U51'(tt, z1)) HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) U22'(tt, z0) -> c3(ACTIVATE(z0)) SPLITAT(0, z0) -> c25 FST(pair(z0, z1)) -> c19(U21'(tt, z0)) U52'(tt, z0) -> c9(ACTIVATE(z0)) U72'(tt, z0) -> c15(ACTIVATE(z0)) U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) U32'(tt, z0) -> c5(ACTIVATE(z0)) ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) U21(tt, z0) -> U22(tt, activate(z0)) U22(tt, z0) -> activate(z0) U31(tt, z0) -> U32(tt, activate(z0)) U32(tt, z0) -> activate(z0) U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) U51(tt, z0) -> U52(tt, activate(z0)) U52(tt, z0) -> activate(z0) U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) U71(tt, z0) -> U72(tt, activate(z0)) U72(tt, z0) -> activate(z0) U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) afterNth(z0, z1) -> U11(tt, z0, z1) fst(pair(z0, z1)) -> U21(tt, z0) head(cons(z0, z1)) -> U31(tt, z0) natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> U41(tt, z0, z1) snd(pair(z0, z1)) -> U51(tt, z1) splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> U71(tt, activate(z1)) take(z0, z1) -> U81(tt, z0, z1) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U63'(tt, z0, z1, z2) -> c12(U64'(splitAt(activate(z0), activate(z2)), activate(z1)), SPLITAT(activate(z0), activate(z2)), ACTIVATE(z0), ACTIVATE(z2), ACTIVATE(z1)) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) S tuples: U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) U63'(tt, z0, z1, z2) -> c12(U64'(splitAt(activate(z0), activate(z2)), activate(z1)), SPLITAT(activate(z0), activate(z2)), ACTIVATE(z0), ACTIVATE(z2), ACTIVATE(z1)) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) K tuples:none Defined Rule Symbols: U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, U71_2, U72_2, U81_3, U82_3, afterNth_2, fst_1, head_1, natsFrom_1, sel_2, snd_1, splitAt_2, tail_1, take_2, activate_1 Defined Pair Symbols: U11'_3, U12'_3, U41'_3, U42'_3, U61'_4, U62'_4, U63'_4, U81'_3, U82'_3, AFTERNTH_2, SPLITAT_2 Compound Symbols: c_3, c1_4, c6_3, c7_4, c10_4, c11_4, c12_5, c16_3, c17_4, c18_1, c26_2 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 26 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) U21(tt, z0) -> U22(tt, activate(z0)) U22(tt, z0) -> activate(z0) U31(tt, z0) -> U32(tt, activate(z0)) U32(tt, z0) -> activate(z0) U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) U51(tt, z0) -> U52(tt, activate(z0)) U52(tt, z0) -> activate(z0) U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) U71(tt, z0) -> U72(tt, activate(z0)) U72(tt, z0) -> activate(z0) U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) afterNth(z0, z1) -> U11(tt, z0, z1) fst(pair(z0, z1)) -> U21(tt, z0) head(cons(z0, z1)) -> U31(tt, z0) natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> U41(tt, z0, z1) snd(pair(z0, z1)) -> U51(tt, z1) splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> U71(tt, activate(z1)) take(z0, z1) -> U81(tt, z0, z1) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) S tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) K tuples:none Defined Rule Symbols: U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, U71_2, U72_2, U81_3, U82_3, afterNth_2, fst_1, head_1, natsFrom_1, sel_2, snd_1, splitAt_2, tail_1, take_2, activate_1 Defined Pair Symbols: AFTERNTH_2, U11'_3, U12'_3, U41'_3, U42'_3, U61'_4, U62'_4, U63'_4, U81'_3, U82'_3, SPLITAT_2 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 ---------------------------------------- (7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) The following tuples could be moved from S to K by knowledge propagation: U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) U21(tt, z0) -> U22(tt, activate(z0)) U22(tt, z0) -> activate(z0) U31(tt, z0) -> U32(tt, activate(z0)) U32(tt, z0) -> activate(z0) U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) U51(tt, z0) -> U52(tt, activate(z0)) U52(tt, z0) -> activate(z0) U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) U71(tt, z0) -> U72(tt, activate(z0)) U72(tt, z0) -> activate(z0) U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) afterNth(z0, z1) -> U11(tt, z0, z1) fst(pair(z0, z1)) -> U21(tt, z0) head(cons(z0, z1)) -> U31(tt, z0) natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) sel(z0, z1) -> U41(tt, z0, z1) snd(pair(z0, z1)) -> U51(tt, z1) splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> U71(tt, activate(z1)) take(z0, z1) -> U81(tt, z0, z1) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 Tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) S tuples: U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) K tuples: U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) Defined Rule Symbols: U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, U71_2, U72_2, U81_3, U82_3, afterNth_2, fst_1, head_1, natsFrom_1, sel_2, snd_1, splitAt_2, tail_1, take_2, activate_1 Defined Pair Symbols: AFTERNTH_2, U11'_3, U12'_3, U41'_3, U42'_3, U61'_4, U62'_4, U63'_4, U81'_3, U82'_3, SPLITAT_2 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 ---------------------------------------- (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) U21(tt, z0) -> U22(tt, activate(z0)) U22(tt, z0) -> activate(z0) U31(tt, z0) -> U32(tt, activate(z0)) U32(tt, z0) -> activate(z0) U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) U51(tt, z0) -> U52(tt, activate(z0)) U52(tt, z0) -> activate(z0) U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) U71(tt, z0) -> U72(tt, activate(z0)) U72(tt, z0) -> activate(z0) U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) afterNth(z0, z1) -> U11(tt, z0, z1) fst(pair(z0, z1)) -> U21(tt, z0) head(cons(z0, z1)) -> U31(tt, z0) sel(z0, z1) -> U41(tt, z0, z1) snd(pair(z0, z1)) -> U51(tt, z1) splitAt(0, z0) -> pair(nil, z0) splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) tail(cons(z0, z1)) -> U71(tt, activate(z1)) take(z0, z1) -> U81(tt, z0, z1) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) Tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) S tuples: U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) K tuples: U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) Defined Rule Symbols: activate_1, natsFrom_1 Defined Pair Symbols: AFTERNTH_2, U11'_3, U12'_3, U41'_3, U42'_3, U61'_4, U62'_4, U63'_4, U81'_3, U82'_3, SPLITAT_2 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 ---------------------------------------- (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) We considered the (Usable) Rules: natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 natsFrom(z0) -> n__natsFrom(z0) And the Tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(AFTERNTH(x_1, x_2)) = [1] + x_1 + x_2 POL(SPLITAT(x_1, x_2)) = x_1 + x_2 POL(U11'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U12'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U41'(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(U42'(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(U61'(x_1, x_2, x_3, x_4)) = x_2 + x_4 POL(U62'(x_1, x_2, x_3, x_4)) = x_2 + x_4 POL(U63'(x_1, x_2, x_3, x_4)) = x_2 + x_4 POL(U81'(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(U82'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(activate(x_1)) = x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1)) = x_1 POL(c16(x_1)) = x_1 POL(c17(x_1)) = x_1 POL(c18(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(c7(x_1)) = x_1 POL(cons(x_1, x_2)) = x_2 POL(n__natsFrom(x_1)) = [1] POL(natsFrom(x_1)) = [1] POL(s(x_1)) = [1] + x_1 POL(tt) = [1] ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__natsFrom(z0)) -> natsFrom(z0) activate(z0) -> z0 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) natsFrom(z0) -> n__natsFrom(z0) Tuples: AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) S tuples: U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) K tuples: U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) Defined Rule Symbols: activate_1, natsFrom_1 Defined Pair Symbols: AFTERNTH_2, U11'_3, U12'_3, U41'_3, U42'_3, U61'_4, U62'_4, U63'_4, U81'_3, U82'_3, SPLITAT_2 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 ---------------------------------------- (13) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) Now S is empty ---------------------------------------- (14) BOUNDS(1, 1) ---------------------------------------- (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (16) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) U21(tt, X) -> U22(tt, activate(X)) U22(tt, X) -> activate(X) U31(tt, N) -> U32(tt, activate(N)) U32(tt, N) -> activate(N) U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) U51(tt, Y) -> U52(tt, activate(Y)) U52(tt, Y) -> activate(Y) U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) U71(tt, XS) -> U72(tt, activate(XS)) U72(tt, XS) -> activate(XS) U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) afterNth(N, XS) -> U11(tt, N, XS) fst(pair(X, Y)) -> U21(tt, X) head(cons(N, XS)) -> U31(tt, N) natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> U41(tt, N, XS) snd(pair(X, Y)) -> U51(tt, Y) splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) tail(cons(N, XS)) -> U71(tt, activate(XS)) take(N, XS) -> U81(tt, N, XS) natsFrom(X) -> n__natsFrom(X) activate(n__natsFrom(X)) -> natsFrom(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (17) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence U63(tt, s(N1_0), X, cons(X2_0, XS3_0)) ->^+ U64(U63(tt, N1_0, activate(X2_0), XS3_0), activate(X)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [N1_0 / s(N1_0), XS3_0 / cons(X2_0, XS3_0)]. The result substitution is [X / activate(X2_0)]. ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) U21(tt, X) -> U22(tt, activate(X)) U22(tt, X) -> activate(X) U31(tt, N) -> U32(tt, activate(N)) U32(tt, N) -> activate(N) U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) U51(tt, Y) -> U52(tt, activate(Y)) U52(tt, Y) -> activate(Y) U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) U71(tt, XS) -> U72(tt, activate(XS)) U72(tt, XS) -> activate(XS) U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) afterNth(N, XS) -> U11(tt, N, XS) fst(pair(X, Y)) -> U21(tt, X) head(cons(N, XS)) -> U31(tt, N) natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> U41(tt, N, XS) snd(pair(X, Y)) -> U51(tt, Y) splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) tail(cons(N, XS)) -> U71(tt, activate(XS)) take(N, XS) -> U81(tt, N, XS) natsFrom(X) -> n__natsFrom(X) activate(n__natsFrom(X)) -> natsFrom(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^1, INF) ---------------------------------------- (22) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) U21(tt, X) -> U22(tt, activate(X)) U22(tt, X) -> activate(X) U31(tt, N) -> U32(tt, activate(N)) U32(tt, N) -> activate(N) U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) U51(tt, Y) -> U52(tt, activate(Y)) U52(tt, Y) -> activate(Y) U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) U71(tt, XS) -> U72(tt, activate(XS)) U72(tt, XS) -> activate(XS) U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) afterNth(N, XS) -> U11(tt, N, XS) fst(pair(X, Y)) -> U21(tt, X) head(cons(N, XS)) -> U31(tt, N) natsFrom(N) -> cons(N, n__natsFrom(s(N))) sel(N, XS) -> U41(tt, N, XS) snd(pair(X, Y)) -> U51(tt, Y) splitAt(0, XS) -> pair(nil, XS) splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) tail(cons(N, XS)) -> U71(tt, activate(XS)) take(N, XS) -> U81(tt, N, XS) natsFrom(X) -> n__natsFrom(X) activate(n__natsFrom(X)) -> natsFrom(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST