Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A note on antichains of words"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A note on antichains of words. | A note on antichains of words James D. Currie Department of Mathematics and Statistics University of Winnipeg Winnipeg Manitoba Canada R3B 2E9 currie@uwinnipeg.ca Submitted July 9 1995 Accepted October 14 1995 Abstract We can compress the word banana as xyyz where x b y an z a . We say that banana encounters yy. Thus a coded version of yy shows up in banana . The relation u encounters w is transitive and thus generates an order on words. We study antichains under this order. In particular we show that in this order there is an inhnite antichain of binary words avoiding overlaps. AMS Subject Classification 68R15 06A99 Key Words overlaps. antichains words avoiding patterns 1 Introduction The study of words avoiding patterns is an area of combinatorics on words reaching back at least to the turn of the century when Thue proved 29 that one can find arbitrarily long words over a 3 letter alphabet in which no two adjacent subwords are identical. If w is such a word then w cannot be written w xyyz with y a non-empty word. In modern parlance we would say that w avoids yy. A word which can be written as xyyz is said to encounter yy. Thue also showed that there are arbitrarily long words over a 2 letter alphabet avoiding yyy. One can quickly check that no word of length 4 or more over a 2 letter alphabet avoids yy. We say that yyy is avoidable on 2 letters or 2-avoidable whereas yy is unavoidable on 2 letters. On the other hand yyy is certainly 3-avoidable because any word avoiding yy must avoid yyy also. Bean Ehrenfeucht and McNulty 4 and independently Zimin 30 characterized words which are avoidable on some large enough finite alphabet. If p is a word over an n letter alphabet then This work was supported by an NSERC operating grant. 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R21 2 p is avoidable on some finite alphabet if Zn avoids p where words Zn are defined recursively by Z1 1 Zn 1 Zn n 1 Zn n 2 IN. Thus the pattern abcacb is a pattern over a 3 letter alphabet .