tailieunhanh - Báo cáo toán học: "Weakly Self-Avoiding Words and a Construction of Friedman"

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@ m2wang@ 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 is not a subsequence of x . 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 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 is not a subsequence of x we call it self-avoiding. We apply the same definition for a finite word x of length n imposing the additional restriction .