Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Extremal infinite overlap-free binary words. | Extremal infinite overlap-free binary words Jean-Paul Allouche CNRS LRI Bâtiment 490 F-91405 Orsay Cedex France allouche@lri.fr James Currie Department of Mathematics University of Winnipeg Winnipeg Manitoba R3B 2E9 Canada currie@io.uwinnipeg.ca Jeffrey Shallit Department of Computer Science University of Waterloo Waterloo Ontario N2L 3G1 Canada shallit@graceland.uwaterloo.ca Submitted August 29 1997 Accepted May 3 1998. Abstract Let t be the infinite fixed point starting with 1 of the morphism ụ 0 01 1 10. An infinite word over 0 1g is said to be overlap-free if it contains no factor of the form axaxa where a 2 0 1g and x 2 0 1g . We prove that the lexicographically least infinite overlap-free binary word beginning with any specified prefix if it exists has a suffix which is a suffix of t. In particular the lexicographically least infinite overlap-free binary word is 001001t . Keywords Homomorphism fixed point overlap-free word. 1991 Mathematics Subject Classification Primary 68R15. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 5 1998 R27 2 1 Introduction Since the pioneering work of Thue 14 15 see also 5 the overlap-free words on a hnite alphabet i.e. those words that do not contain a factor axaxa where x is a word and a a letter have been studied extensively. The question of extremality for the lexicographic order of overlap-free binary inhnite words seems to have been addressed only once Berstel proved 4 see also 5 that the lexicographically greatest inhnite overlap-free word on the binary alphabet 0 1g that begins with 0 is the Thue-Morse sequence t 01101001 which shows once more the ubiquity of this sequence. Recall that t is one of the hxed points of the morphism 0 01 1 10. We let t 10010110 denote the other hxed point. The following natural question then arises what is the lexicographically least overlap-free word on 0 1g that begins with 0 Computing the hrst few terms suggests that this word is 0010011001011001101001 001001t. The main result of this paper is