Đ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: Weakly Self-Avoiding Words and a Construction of Friedman. | Weakly Self-Avoiding Words and a Construction of Friedman Jeffrey Shallit and Ming-wei Wang Department of Computer Science University of Waterloo Waterloo Ontario Canada N2L 3G1 shallit@graceland.uwaterloo.ca m2wang@math.uwaterloo.ca Submitted September 28 2000 Accepted February 7 2001. MR Subject Classifications 68R15 Primary Abstract H. Friedman obtained remarkable results about the longest finite sequence x over a finite alphabet such that for all i j the word x i.2i is not a subsequence of x j.2j . In this note we consider what happens when subsequence is replaced by subword we call such a sequence a weakly self-avoiding word . We prove that over an alphabet of size 1 or 2 there is an upper bound on the length of weakly self-avoiding words while if the alphabet is of size 3 or more there exists an infinite weakly self-avoiding word. 1 Introduction We say a word y is a subsequence of a word z if y can be obtained by striking out 0 or more symbols from z. For example iron is a subsequence of introduction . We say a word y is a subword of a word z if there exist words w x such that z wyx. For example duct is a subword of introduction . 1 We use the notation x k to denote the k th letter chosen from the string x. We write x a.b to denote the subword of x of length b a 1 starting at position a and ending at position b. Recently H. Friedman has found a remarkable construction that generates extremely large numbers 1 2 . Namely consider words over a finite alphabet E of cardinality k. If Research supported in part by a grant from NSERC. 1Europeans usually use the term factor for what we have called subword and they sometimes use the term subword for what we have called subsequence . THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 N2 1 an infinite word x has the property that for all i j with 0 i j the subword x i.2i is not a subsequence of x j.2j we call it self-avoiding. We apply the same definition for a finite word x of length n imposing the additional restriction .
