806.25/291.60 WORST_CASE(Omega(n^1), O(n^1)) 806.25/291.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 806.25/291.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 806.25/291.61 806.25/291.61 806.25/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 806.25/291.61 806.25/291.61 (0) CpxTRS 806.25/291.61 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 806.25/291.61 (2) CdtProblem 806.25/291.61 (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 806.25/291.61 (4) CdtProblem 806.25/291.61 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 806.25/291.61 (6) CdtProblem 806.25/291.61 (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 806.25/291.61 (8) CdtProblem 806.25/291.61 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 806.25/291.61 (10) CdtProblem 806.25/291.61 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 130 ms] 806.25/291.61 (12) CdtProblem 806.25/291.61 (13) CdtKnowledgeProof [FINISHED, 0 ms] 806.25/291.61 (14) BOUNDS(1, 1) 806.25/291.61 (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 806.25/291.61 (16) TRS for Loop Detection 806.25/291.61 (17) DecreasingLoopProof [LOWER BOUND(ID), 18.9 s] 806.25/291.61 (18) BEST 806.25/291.61 (19) proven lower bound 806.25/291.61 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 806.25/291.61 (21) BOUNDS(n^1, INF) 806.25/291.61 (22) TRS for Loop Detection 806.25/291.61 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (0) 806.25/291.61 Obligation: 806.25/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 806.25/291.61 806.25/291.61 806.25/291.61 The TRS R consists of the following rules: 806.25/291.61 806.25/291.61 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 806.25/291.61 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 806.25/291.61 U21(tt, X) -> U22(tt, activate(X)) 806.25/291.61 U22(tt, X) -> activate(X) 806.25/291.61 U31(tt, N) -> U32(tt, activate(N)) 806.25/291.61 U32(tt, N) -> activate(N) 806.25/291.61 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 806.25/291.61 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 806.25/291.61 U51(tt, Y) -> U52(tt, activate(Y)) 806.25/291.61 U52(tt, Y) -> activate(Y) 806.25/291.61 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 806.25/291.61 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 806.25/291.61 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 806.25/291.61 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 806.25/291.61 U71(tt, XS) -> U72(tt, activate(XS)) 806.25/291.61 U72(tt, XS) -> activate(XS) 806.25/291.61 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 806.25/291.61 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 806.25/291.61 afterNth(N, XS) -> U11(tt, N, XS) 806.25/291.61 fst(pair(X, Y)) -> U21(tt, X) 806.25/291.61 head(cons(N, XS)) -> U31(tt, N) 806.25/291.61 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 806.25/291.61 sel(N, XS) -> U41(tt, N, XS) 806.25/291.61 snd(pair(X, Y)) -> U51(tt, Y) 806.25/291.61 splitAt(0, XS) -> pair(nil, XS) 806.25/291.61 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 806.25/291.61 tail(cons(N, XS)) -> U71(tt, activate(XS)) 806.25/291.61 take(N, XS) -> U81(tt, N, XS) 806.25/291.61 natsFrom(X) -> n__natsFrom(X) 806.25/291.61 activate(n__natsFrom(X)) -> natsFrom(X) 806.25/291.61 activate(X) -> X 806.25/291.61 806.25/291.61 S is empty. 806.25/291.61 Rewrite Strategy: INNERMOST 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 806.25/291.61 Converted Cpx (relative) TRS to CDT 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (2) 806.25/291.61 Obligation: 806.25/291.61 Complexity Dependency Tuples Problem 806.25/291.61 806.25/291.61 Rules: 806.25/291.61 U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) 806.25/291.61 U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) 806.25/291.61 U21(tt, z0) -> U22(tt, activate(z0)) 806.25/291.61 U22(tt, z0) -> activate(z0) 806.25/291.61 U31(tt, z0) -> U32(tt, activate(z0)) 806.25/291.61 U32(tt, z0) -> activate(z0) 806.25/291.61 U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) 806.25/291.61 U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) 806.25/291.61 U51(tt, z0) -> U52(tt, activate(z0)) 806.25/291.61 U52(tt, z0) -> activate(z0) 806.25/291.61 U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) 806.25/291.61 U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) 806.25/291.61 U71(tt, z0) -> U72(tt, activate(z0)) 806.25/291.61 U72(tt, z0) -> activate(z0) 806.25/291.61 U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) 806.25/291.61 U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) 806.25/291.61 afterNth(z0, z1) -> U11(tt, z0, z1) 806.25/291.61 fst(pair(z0, z1)) -> U21(tt, z0) 806.25/291.61 head(cons(z0, z1)) -> U31(tt, z0) 806.25/291.61 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.61 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.61 sel(z0, z1) -> U41(tt, z0, z1) 806.25/291.61 snd(pair(z0, z1)) -> U51(tt, z1) 806.25/291.61 splitAt(0, z0) -> pair(nil, z0) 806.25/291.61 splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) 806.25/291.61 tail(cons(z0, z1)) -> U71(tt, activate(z1)) 806.25/291.61 take(z0, z1) -> U81(tt, z0, z1) 806.25/291.61 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.61 activate(z0) -> z0 806.25/291.61 Tuples: 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U22'(tt, z0) -> c3(ACTIVATE(z0)) 806.25/291.61 U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U32'(tt, z0) -> c5(ACTIVATE(z0)) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U52'(tt, z0) -> c9(ACTIVATE(z0)) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 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)) 806.25/291.61 U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) 806.25/291.61 U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U72'(tt, z0) -> c15(ACTIVATE(z0)) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 FST(pair(z0, z1)) -> c19(U21'(tt, z0)) 806.25/291.61 HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) 806.25/291.61 NATSFROM(z0) -> c21 806.25/291.61 NATSFROM(z0) -> c22 806.25/291.61 SEL(z0, z1) -> c23(U41'(tt, z0, z1)) 806.25/291.61 SND(pair(z0, z1)) -> c24(U51'(tt, z1)) 806.25/291.61 SPLITAT(0, z0) -> c25 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) 806.25/291.61 TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) 806.25/291.61 TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) 806.25/291.61 ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) 806.25/291.61 ACTIVATE(z0) -> c30 806.25/291.61 S tuples: 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U22'(tt, z0) -> c3(ACTIVATE(z0)) 806.25/291.61 U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U32'(tt, z0) -> c5(ACTIVATE(z0)) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U52'(tt, z0) -> c9(ACTIVATE(z0)) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 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)) 806.25/291.61 U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) 806.25/291.61 U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U72'(tt, z0) -> c15(ACTIVATE(z0)) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 FST(pair(z0, z1)) -> c19(U21'(tt, z0)) 806.25/291.61 HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) 806.25/291.61 NATSFROM(z0) -> c21 806.25/291.61 NATSFROM(z0) -> c22 806.25/291.61 SEL(z0, z1) -> c23(U41'(tt, z0, z1)) 806.25/291.61 SND(pair(z0, z1)) -> c24(U51'(tt, z1)) 806.25/291.61 SPLITAT(0, z0) -> c25 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) 806.25/291.61 TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) 806.25/291.61 TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) 806.25/291.61 ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) 806.25/291.61 ACTIVATE(z0) -> c30 806.25/291.61 K tuples:none 806.25/291.61 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 806.25/291.61 806.25/291.61 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 806.25/291.61 806.25/291.61 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 806.25/291.61 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) 806.25/291.61 Removed 2 leading nodes: 806.25/291.61 SEL(z0, z1) -> c23(U41'(tt, z0, z1)) 806.25/291.61 TAKE(z0, z1) -> c28(U81'(tt, z0, z1)) 806.25/291.61 Removed 18 trailing nodes: 806.25/291.61 FST(pair(z0, z1)) -> c19(U21'(tt, z0)) 806.25/291.61 HEAD(cons(z0, z1)) -> c20(U31'(tt, z0)) 806.25/291.61 U72'(tt, z0) -> c15(ACTIVATE(z0)) 806.25/291.61 TAIL(cons(z0, z1)) -> c27(U71'(tt, activate(z1)), ACTIVATE(z1)) 806.25/291.61 U52'(tt, z0) -> c9(ACTIVATE(z0)) 806.25/291.61 NATSFROM(z0) -> c21 806.25/291.61 U22'(tt, z0) -> c3(ACTIVATE(z0)) 806.25/291.61 U71'(tt, z0) -> c14(U72'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 SND(pair(z0, z1)) -> c24(U51'(tt, z1)) 806.25/291.61 U31'(tt, z0) -> c4(U32'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 SPLITAT(0, z0) -> c25 806.25/291.61 NATSFROM(z0) -> c22 806.25/291.61 U32'(tt, z0) -> c5(ACTIVATE(z0)) 806.25/291.61 ACTIVATE(z0) -> c30 806.25/291.61 ACTIVATE(n__natsFrom(z0)) -> c29(NATSFROM(z0)) 806.25/291.61 U51'(tt, z0) -> c8(U52'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 U64'(pair(z0, z1), z2) -> c13(ACTIVATE(z2)) 806.25/291.61 U21'(tt, z0) -> c2(U22'(tt, activate(z0)), ACTIVATE(z0)) 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (4) 806.25/291.61 Obligation: 806.25/291.61 Complexity Dependency Tuples Problem 806.25/291.61 806.25/291.61 Rules: 806.25/291.61 U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) 806.25/291.61 U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) 806.25/291.61 U21(tt, z0) -> U22(tt, activate(z0)) 806.25/291.61 U22(tt, z0) -> activate(z0) 806.25/291.61 U31(tt, z0) -> U32(tt, activate(z0)) 806.25/291.61 U32(tt, z0) -> activate(z0) 806.25/291.61 U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) 806.25/291.61 U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) 806.25/291.61 U51(tt, z0) -> U52(tt, activate(z0)) 806.25/291.61 U52(tt, z0) -> activate(z0) 806.25/291.61 U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) 806.25/291.61 U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) 806.25/291.61 U71(tt, z0) -> U72(tt, activate(z0)) 806.25/291.61 U72(tt, z0) -> activate(z0) 806.25/291.61 U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) 806.25/291.61 U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) 806.25/291.61 afterNth(z0, z1) -> U11(tt, z0, z1) 806.25/291.61 fst(pair(z0, z1)) -> U21(tt, z0) 806.25/291.61 head(cons(z0, z1)) -> U31(tt, z0) 806.25/291.61 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.61 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.61 sel(z0, z1) -> U41(tt, z0, z1) 806.25/291.61 snd(pair(z0, z1)) -> U51(tt, z1) 806.25/291.61 splitAt(0, z0) -> pair(nil, z0) 806.25/291.61 splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) 806.25/291.61 tail(cons(z0, z1)) -> U71(tt, activate(z1)) 806.25/291.61 take(z0, z1) -> U81(tt, z0, z1) 806.25/291.61 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.61 activate(z0) -> z0 806.25/291.61 Tuples: 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 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)) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) 806.25/291.61 S tuples: 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U12'(tt, z0, z1) -> c1(SND(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U42'(tt, z0, z1) -> c7(HEAD(afterNth(activate(z0), activate(z1))), AFTERNTH(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2)), ACTIVATE(z0), ACTIVATE(z1), ACTIVATE(z2)) 806.25/291.61 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)) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 U82'(tt, z0, z1) -> c17(FST(splitAt(activate(z0), activate(z1))), SPLITAT(activate(z0), activate(z1)), ACTIVATE(z0), ACTIVATE(z1)) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2)), ACTIVATE(z2)) 806.25/291.61 K tuples:none 806.25/291.61 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 806.25/291.61 806.25/291.61 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 806.25/291.61 806.25/291.61 Compound Symbols: c_3, c1_4, c6_3, c7_4, c10_4, c11_4, c12_5, c16_3, c17_4, c18_1, c26_2 806.25/291.61 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 806.25/291.61 Removed 26 trailing tuple parts 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (6) 806.25/291.61 Obligation: 806.25/291.61 Complexity Dependency Tuples Problem 806.25/291.61 806.25/291.61 Rules: 806.25/291.61 U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) 806.25/291.61 U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) 806.25/291.61 U21(tt, z0) -> U22(tt, activate(z0)) 806.25/291.61 U22(tt, z0) -> activate(z0) 806.25/291.61 U31(tt, z0) -> U32(tt, activate(z0)) 806.25/291.61 U32(tt, z0) -> activate(z0) 806.25/291.61 U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) 806.25/291.61 U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) 806.25/291.61 U51(tt, z0) -> U52(tt, activate(z0)) 806.25/291.61 U52(tt, z0) -> activate(z0) 806.25/291.61 U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) 806.25/291.61 U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) 806.25/291.61 U71(tt, z0) -> U72(tt, activate(z0)) 806.25/291.61 U72(tt, z0) -> activate(z0) 806.25/291.61 U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) 806.25/291.61 U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) 806.25/291.61 afterNth(z0, z1) -> U11(tt, z0, z1) 806.25/291.61 fst(pair(z0, z1)) -> U21(tt, z0) 806.25/291.61 head(cons(z0, z1)) -> U31(tt, z0) 806.25/291.61 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.61 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.61 sel(z0, z1) -> U41(tt, z0, z1) 806.25/291.61 snd(pair(z0, z1)) -> U51(tt, z1) 806.25/291.61 splitAt(0, z0) -> pair(nil, z0) 806.25/291.61 splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) 806.25/291.61 tail(cons(z0, z1)) -> U71(tt, activate(z1)) 806.25/291.61 take(z0, z1) -> U81(tt, z0, z1) 806.25/291.61 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.61 activate(z0) -> z0 806.25/291.61 Tuples: 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 S tuples: 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 K tuples:none 806.25/291.61 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 806.25/291.61 806.25/291.61 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 806.25/291.61 806.25/291.61 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 806.25/291.61 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 806.25/291.61 The following tuples could be moved from S to K by knowledge propagation: 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (8) 806.25/291.61 Obligation: 806.25/291.61 Complexity Dependency Tuples Problem 806.25/291.61 806.25/291.61 Rules: 806.25/291.61 U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) 806.25/291.61 U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) 806.25/291.61 U21(tt, z0) -> U22(tt, activate(z0)) 806.25/291.61 U22(tt, z0) -> activate(z0) 806.25/291.61 U31(tt, z0) -> U32(tt, activate(z0)) 806.25/291.61 U32(tt, z0) -> activate(z0) 806.25/291.61 U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) 806.25/291.61 U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) 806.25/291.61 U51(tt, z0) -> U52(tt, activate(z0)) 806.25/291.61 U52(tt, z0) -> activate(z0) 806.25/291.61 U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) 806.25/291.61 U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) 806.25/291.61 U71(tt, z0) -> U72(tt, activate(z0)) 806.25/291.61 U72(tt, z0) -> activate(z0) 806.25/291.61 U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) 806.25/291.61 U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) 806.25/291.61 afterNth(z0, z1) -> U11(tt, z0, z1) 806.25/291.61 fst(pair(z0, z1)) -> U21(tt, z0) 806.25/291.61 head(cons(z0, z1)) -> U31(tt, z0) 806.25/291.61 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.61 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.61 sel(z0, z1) -> U41(tt, z0, z1) 806.25/291.61 snd(pair(z0, z1)) -> U51(tt, z1) 806.25/291.61 splitAt(0, z0) -> pair(nil, z0) 806.25/291.61 splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) 806.25/291.61 tail(cons(z0, z1)) -> U71(tt, activate(z1)) 806.25/291.61 take(z0, z1) -> U81(tt, z0, z1) 806.25/291.61 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.61 activate(z0) -> z0 806.25/291.61 Tuples: 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 S tuples: 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 K tuples: 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 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 806.25/291.61 806.25/291.61 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 806.25/291.61 806.25/291.61 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 806.25/291.61 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 806.25/291.61 The following rules are not usable and were removed: 806.25/291.61 U11(tt, z0, z1) -> U12(tt, activate(z0), activate(z1)) 806.25/291.61 U12(tt, z0, z1) -> snd(splitAt(activate(z0), activate(z1))) 806.25/291.61 U21(tt, z0) -> U22(tt, activate(z0)) 806.25/291.61 U22(tt, z0) -> activate(z0) 806.25/291.61 U31(tt, z0) -> U32(tt, activate(z0)) 806.25/291.61 U32(tt, z0) -> activate(z0) 806.25/291.61 U41(tt, z0, z1) -> U42(tt, activate(z0), activate(z1)) 806.25/291.61 U42(tt, z0, z1) -> head(afterNth(activate(z0), activate(z1))) 806.25/291.61 U51(tt, z0) -> U52(tt, activate(z0)) 806.25/291.61 U52(tt, z0) -> activate(z0) 806.25/291.61 U61(tt, z0, z1, z2) -> U62(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U62(tt, z0, z1, z2) -> U63(tt, activate(z0), activate(z1), activate(z2)) 806.25/291.61 U63(tt, z0, z1, z2) -> U64(splitAt(activate(z0), activate(z2)), activate(z1)) 806.25/291.61 U64(pair(z0, z1), z2) -> pair(cons(activate(z2), z0), z1) 806.25/291.61 U71(tt, z0) -> U72(tt, activate(z0)) 806.25/291.61 U72(tt, z0) -> activate(z0) 806.25/291.61 U81(tt, z0, z1) -> U82(tt, activate(z0), activate(z1)) 806.25/291.61 U82(tt, z0, z1) -> fst(splitAt(activate(z0), activate(z1))) 806.25/291.61 afterNth(z0, z1) -> U11(tt, z0, z1) 806.25/291.61 fst(pair(z0, z1)) -> U21(tt, z0) 806.25/291.61 head(cons(z0, z1)) -> U31(tt, z0) 806.25/291.61 sel(z0, z1) -> U41(tt, z0, z1) 806.25/291.61 snd(pair(z0, z1)) -> U51(tt, z1) 806.25/291.61 splitAt(0, z0) -> pair(nil, z0) 806.25/291.61 splitAt(s(z0), cons(z1, z2)) -> U61(tt, z0, z1, activate(z2)) 806.25/291.61 tail(cons(z0, z1)) -> U71(tt, activate(z1)) 806.25/291.61 take(z0, z1) -> U81(tt, z0, z1) 806.25/291.61 806.25/291.61 ---------------------------------------- 806.25/291.61 806.25/291.61 (10) 806.25/291.61 Obligation: 806.25/291.61 Complexity Dependency Tuples Problem 806.25/291.61 806.25/291.61 Rules: 806.25/291.61 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.61 activate(z0) -> z0 806.25/291.61 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.61 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.61 Tuples: 806.25/291.61 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.61 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.61 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.61 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 S tuples: 806.25/291.61 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.61 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.61 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.61 K tuples: 806.25/291.61 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.61 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.62 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.62 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.62 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.62 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 Defined Rule Symbols: activate_1, natsFrom_1 806.25/291.62 806.25/291.62 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 806.25/291.62 806.25/291.62 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 806.25/291.62 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 806.25/291.62 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 806.25/291.62 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.62 We considered the (Usable) Rules: 806.25/291.62 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.62 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.62 activate(z0) -> z0 806.25/291.62 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.62 And the Tuples: 806.25/291.62 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.62 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.62 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.62 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.62 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.62 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.62 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.62 The order we found is given by the following interpretation: 806.25/291.62 806.25/291.62 Polynomial interpretation : 806.25/291.62 806.25/291.62 POL(AFTERNTH(x_1, x_2)) = [2] + [2]x_1 806.25/291.62 POL(SPLITAT(x_1, x_2)) = [2]x_1 806.25/291.62 POL(U11'(x_1, x_2, x_3)) = x_1 + [2]x_2 806.25/291.62 POL(U12'(x_1, x_2, x_3)) = x_1 + [2]x_2 806.25/291.62 POL(U41'(x_1, x_2, x_3)) = [3] + [3]x_1 + [3]x_2 806.25/291.62 POL(U42'(x_1, x_2, x_3)) = [2]x_1 + [2]x_2 806.25/291.62 POL(U61'(x_1, x_2, x_3, x_4)) = [2] + [2]x_2 806.25/291.62 POL(U62'(x_1, x_2, x_3, x_4)) = [2]x_2 806.25/291.62 POL(U63'(x_1, x_2, x_3, x_4)) = [2]x_2 806.25/291.62 POL(U81'(x_1, x_2, x_3)) = [1] + [2]x_2 + x_3 806.25/291.62 POL(U82'(x_1, x_2, x_3)) = [2]x_2 806.25/291.62 POL(activate(x_1)) = x_1 806.25/291.62 POL(c(x_1)) = x_1 806.25/291.62 POL(c1(x_1)) = x_1 806.25/291.62 POL(c10(x_1)) = x_1 806.25/291.62 POL(c11(x_1)) = x_1 806.25/291.62 POL(c12(x_1)) = x_1 806.25/291.62 POL(c16(x_1)) = x_1 806.25/291.62 POL(c17(x_1)) = x_1 806.25/291.62 POL(c18(x_1)) = x_1 806.25/291.62 POL(c26(x_1)) = x_1 806.25/291.62 POL(c6(x_1)) = x_1 806.25/291.62 POL(c7(x_1)) = x_1 806.25/291.62 POL(cons(x_1, x_2)) = x_1 806.25/291.62 POL(n__natsFrom(x_1)) = x_1 806.25/291.62 POL(natsFrom(x_1)) = x_1 806.25/291.62 POL(s(x_1)) = [2] + x_1 806.25/291.62 POL(tt) = [2] 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (12) 806.25/291.62 Obligation: 806.25/291.62 Complexity Dependency Tuples Problem 806.25/291.62 806.25/291.62 Rules: 806.25/291.62 activate(n__natsFrom(z0)) -> natsFrom(z0) 806.25/291.62 activate(z0) -> z0 806.25/291.62 natsFrom(z0) -> cons(z0, n__natsFrom(s(z0))) 806.25/291.62 natsFrom(z0) -> n__natsFrom(z0) 806.25/291.62 Tuples: 806.25/291.62 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.62 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.62 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.62 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.62 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.62 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.62 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.62 S tuples: 806.25/291.62 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.62 K tuples: 806.25/291.62 U41'(tt, z0, z1) -> c6(U42'(tt, activate(z0), activate(z1))) 806.25/291.62 U42'(tt, z0, z1) -> c7(AFTERNTH(activate(z0), activate(z1))) 806.25/291.62 U81'(tt, z0, z1) -> c16(U82'(tt, activate(z0), activate(z1))) 806.25/291.62 U82'(tt, z0, z1) -> c17(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 AFTERNTH(z0, z1) -> c18(U11'(tt, z0, z1)) 806.25/291.62 U11'(tt, z0, z1) -> c(U12'(tt, activate(z0), activate(z1))) 806.25/291.62 U12'(tt, z0, z1) -> c1(SPLITAT(activate(z0), activate(z1))) 806.25/291.62 U61'(tt, z0, z1, z2) -> c10(U62'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.62 Defined Rule Symbols: activate_1, natsFrom_1 806.25/291.62 806.25/291.62 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 806.25/291.62 806.25/291.62 Compound Symbols: c18_1, c_1, c1_1, c6_1, c7_1, c10_1, c11_1, c12_1, c16_1, c17_1, c26_1 806.25/291.62 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (13) CdtKnowledgeProof (FINISHED) 806.25/291.62 The following tuples could be moved from S to K by knowledge propagation: 806.25/291.62 U62'(tt, z0, z1, z2) -> c11(U63'(tt, activate(z0), activate(z1), activate(z2))) 806.25/291.62 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.62 U63'(tt, z0, z1, z2) -> c12(SPLITAT(activate(z0), activate(z2))) 806.25/291.62 SPLITAT(s(z0), cons(z1, z2)) -> c26(U61'(tt, z0, z1, activate(z2))) 806.25/291.62 Now S is empty 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (14) 806.25/291.62 BOUNDS(1, 1) 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 806.25/291.62 Transformed a relative TRS into a decreasing-loop problem. 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (16) 806.25/291.62 Obligation: 806.25/291.62 Analyzing the following TRS for decreasing loops: 806.25/291.62 806.25/291.62 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 806.25/291.62 806.25/291.62 806.25/291.62 The TRS R consists of the following rules: 806.25/291.62 806.25/291.62 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 806.25/291.62 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 806.25/291.62 U21(tt, X) -> U22(tt, activate(X)) 806.25/291.62 U22(tt, X) -> activate(X) 806.25/291.62 U31(tt, N) -> U32(tt, activate(N)) 806.25/291.62 U32(tt, N) -> activate(N) 806.25/291.62 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 806.25/291.62 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 806.25/291.62 U51(tt, Y) -> U52(tt, activate(Y)) 806.25/291.62 U52(tt, Y) -> activate(Y) 806.25/291.62 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 806.25/291.62 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 806.25/291.62 U71(tt, XS) -> U72(tt, activate(XS)) 806.25/291.62 U72(tt, XS) -> activate(XS) 806.25/291.62 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 806.25/291.62 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 806.25/291.62 afterNth(N, XS) -> U11(tt, N, XS) 806.25/291.62 fst(pair(X, Y)) -> U21(tt, X) 806.25/291.62 head(cons(N, XS)) -> U31(tt, N) 806.25/291.62 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 806.25/291.62 sel(N, XS) -> U41(tt, N, XS) 806.25/291.62 snd(pair(X, Y)) -> U51(tt, Y) 806.25/291.62 splitAt(0, XS) -> pair(nil, XS) 806.25/291.62 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 806.25/291.62 tail(cons(N, XS)) -> U71(tt, activate(XS)) 806.25/291.62 take(N, XS) -> U81(tt, N, XS) 806.25/291.62 natsFrom(X) -> n__natsFrom(X) 806.25/291.62 activate(n__natsFrom(X)) -> natsFrom(X) 806.25/291.62 activate(X) -> X 806.25/291.62 806.25/291.62 S is empty. 806.25/291.62 Rewrite Strategy: INNERMOST 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (17) DecreasingLoopProof (LOWER BOUND(ID)) 806.25/291.62 The following loop(s) give(s) rise to the lower bound Omega(n^1): 806.25/291.62 806.25/291.62 The rewrite sequence 806.25/291.62 806.25/291.62 U63(tt, s(N1_0), X, cons(X2_0, XS3_0)) ->^+ U64(U63(tt, N1_0, activate(X2_0), XS3_0), activate(X)) 806.25/291.62 806.25/291.62 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 806.25/291.62 806.25/291.62 The pumping substitution is [N1_0 / s(N1_0), XS3_0 / cons(X2_0, XS3_0)]. 806.25/291.62 806.25/291.62 The result substitution is [X / activate(X2_0)]. 806.25/291.62 806.25/291.62 806.25/291.62 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (18) 806.25/291.62 Complex Obligation (BEST) 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (19) 806.25/291.62 Obligation: 806.25/291.62 Proved the lower bound n^1 for the following obligation: 806.25/291.62 806.25/291.62 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 806.25/291.62 806.25/291.62 806.25/291.62 The TRS R consists of the following rules: 806.25/291.62 806.25/291.62 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 806.25/291.62 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 806.25/291.62 U21(tt, X) -> U22(tt, activate(X)) 806.25/291.62 U22(tt, X) -> activate(X) 806.25/291.62 U31(tt, N) -> U32(tt, activate(N)) 806.25/291.62 U32(tt, N) -> activate(N) 806.25/291.62 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 806.25/291.62 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 806.25/291.62 U51(tt, Y) -> U52(tt, activate(Y)) 806.25/291.62 U52(tt, Y) -> activate(Y) 806.25/291.62 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 806.25/291.62 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 806.25/291.62 U71(tt, XS) -> U72(tt, activate(XS)) 806.25/291.62 U72(tt, XS) -> activate(XS) 806.25/291.62 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 806.25/291.62 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 806.25/291.62 afterNth(N, XS) -> U11(tt, N, XS) 806.25/291.62 fst(pair(X, Y)) -> U21(tt, X) 806.25/291.62 head(cons(N, XS)) -> U31(tt, N) 806.25/291.62 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 806.25/291.62 sel(N, XS) -> U41(tt, N, XS) 806.25/291.62 snd(pair(X, Y)) -> U51(tt, Y) 806.25/291.62 splitAt(0, XS) -> pair(nil, XS) 806.25/291.62 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 806.25/291.62 tail(cons(N, XS)) -> U71(tt, activate(XS)) 806.25/291.62 take(N, XS) -> U81(tt, N, XS) 806.25/291.62 natsFrom(X) -> n__natsFrom(X) 806.25/291.62 activate(n__natsFrom(X)) -> natsFrom(X) 806.25/291.62 activate(X) -> X 806.25/291.62 806.25/291.62 S is empty. 806.25/291.62 Rewrite Strategy: INNERMOST 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (20) LowerBoundPropagationProof (FINISHED) 806.25/291.62 Propagated lower bound. 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (21) 806.25/291.62 BOUNDS(n^1, INF) 806.25/291.62 806.25/291.62 ---------------------------------------- 806.25/291.62 806.25/291.62 (22) 806.25/291.62 Obligation: 806.25/291.62 Analyzing the following TRS for decreasing loops: 806.25/291.62 806.25/291.62 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 806.25/291.62 806.25/291.62 806.25/291.62 The TRS R consists of the following rules: 806.25/291.62 806.25/291.62 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 806.25/291.62 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 806.25/291.62 U21(tt, X) -> U22(tt, activate(X)) 806.25/291.62 U22(tt, X) -> activate(X) 806.25/291.62 U31(tt, N) -> U32(tt, activate(N)) 806.25/291.62 U32(tt, N) -> activate(N) 806.25/291.62 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 806.25/291.62 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 806.25/291.62 U51(tt, Y) -> U52(tt, activate(Y)) 806.25/291.62 U52(tt, Y) -> activate(Y) 806.25/291.62 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 806.25/291.62 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 806.25/291.62 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 806.25/291.62 U71(tt, XS) -> U72(tt, activate(XS)) 806.25/291.62 U72(tt, XS) -> activate(XS) 806.25/291.62 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 806.25/291.62 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 806.25/291.62 afterNth(N, XS) -> U11(tt, N, XS) 806.25/291.62 fst(pair(X, Y)) -> U21(tt, X) 806.25/291.62 head(cons(N, XS)) -> U31(tt, N) 806.25/291.62 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 806.25/291.62 sel(N, XS) -> U41(tt, N, XS) 806.25/291.62 snd(pair(X, Y)) -> U51(tt, Y) 806.25/291.62 splitAt(0, XS) -> pair(nil, XS) 806.25/291.62 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 806.25/291.62 tail(cons(N, XS)) -> U71(tt, activate(XS)) 806.25/291.62 take(N, XS) -> U81(tt, N, XS) 806.25/291.62 natsFrom(X) -> n__natsFrom(X) 806.25/291.62 activate(n__natsFrom(X)) -> natsFrom(X) 806.25/291.62 activate(X) -> X 806.25/291.62 806.25/291.62 S is empty. 806.25/291.62 Rewrite Strategy: INNERMOST 806.38/291.69 EOF