Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: " For each α 2 there is an infinite binary word with critical exponent α"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: For each α 2 there is an infinite binary word with critical exponent α. | For each a 2 there is an infinite binary word with critical exponent a James D. Currie Narad Rampersady Department of Mathematics and Statistics University of Winnipeg Winnipeg Manitoba R3B 2E9 CANADA e-mail j.currie@uwinnipeg.ca n.rampersad@uwinnipeg.ca Submitted Feb 28 2008 Accepted Aug 25 2008 Published Aug 31 2008 Mathematics Subject Classification 68R15 Abstract The critical exponent of an infinite word w is the supremum of all rational numbers a such that w contains an a-power. We resolve an open question of Krieger and Shallit by showing that for each a 2 there is an infinite binary word with critical exponent a. Keywords Combinatorics on words repetitions critical exponent 1 Introduction If a is a rational number a word w is an a-power if there exist words x and x and a positive integer n with x a prefix of x such that w xnx and a n x x . We refer to x as a period of w. A word is a-power-free if none of its subwords is a d-power with d a otherwise we say the word contains an a-power. The critical exponent of an infinite word w is defined as supfa 2 Q w contains an a-power . Critical exponents of certain classes of infinite words such as Sturmian words 8 10 and words generated by iterated morphisms 5 6 have received particular attention. Krieger and Shallit 7 proved that for every real number a 1 there is an infinite word with critical exponent a. As a tends to 1 the number of letters required to construct The author s research was supported by an NSERC operating grant. yThe author is supported by an NSERC Post-doctoral Fellowship. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N34 1 such words tends to infinity. However for a 7 3 Shur 9 gave a construction over a binary alphabet. For a 2 Krieger and Shallit gave a construction over a four-letter alphabet and left it as an open problem to determine if for every real number a 2 2 7 3 there is an infinite binary word with critical exponent a. Currie Rampersad and Shallit 3 gave examples of such words for a .