کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420066 | 683891 | 2007 | 6 صفحه PDF | دانلود رایگان |
In this paper a recurrence relation satisfied by the number L(n)L(n) of words of length n over an alphabet A of cardinality m (m⩾2)(m⩾2) not containing the factor (aba)k(aba)k(a≠b)(a≠b) is deduced. Let knkn be a sequence of positive integers. From [I. Tomescu, A threshold property concerning words containing all short factors, Bull. EATCS 64 (1998) 166–170] it follows that if limsupn→∞k(n)/lnn<1/(3lnm) then almost all words of length n over A contain the factor (aba)kn(aba)kn as n→∞n→∞. Using the properties of the roots of the recurrence satisfied by L(n)L(n) it is shown that if limsupn→∞k(n)/lnn>1/(3lnm) then this property is false. Moreover, if limn→∞(lnn-3klnm)=η∈Rlimn→∞(lnn-3klnm)=η∈R then limn→∞|W(n,(aba)kn,A)|/mn=1-exp(-(1-1/m3)exp(η))limn→∞|W(n,(aba)kn,A)|/mn=1-exp(-(1-1/m3)exp(η)), where W(n,(aba)kn,A)W(n,(aba)kn,A) denotes the set of words of length n over A containing the factor (aba)kn(aba)kn.
Journal: Discrete Applied Mathematics - Volume 155, Issue 11, 1 June 2007, Pages 1506–1511