tailieunhanh - Báo cáo toán học: " A one–sided Zimin construction"

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: A one–sided Zimin construction. | A one-sided Zimin construction L. J. Cummings University of Waterloo ljcummings@ M. Mays West Virginia University mays@ Submitted December 1 2000 Accepted July 23 2001. MR Subject Classifications 68R15 20M35 Abstract A string is Abelian square-free if it contains no Abelian squares that is adjacent substrings which are permutations of each other. An Abelian square-free string is maximal if it cannot be extended to the left or right by concatenating alphabet symbols without introducing an Abelian square. We construct Abelian square-free finite strings which are maximal by modifying a construction of Zimin. The new construction produces maximal strings whose length as a function of alphabet size is much shorter than that in the construction described by Zimin. 1 Introduction Strings are a fundamental data structure. Equivalent names include sequence word vector codeword linear array and list. We take the entries of our strings to be elements of a finite set A a0 . amg called the alphabet. The elements of A will be called entries or letters. Strings may be infinite or finite. Considerable research effort has been directed toward determining those countably infinite strings which do or do not exhibit certain properties but here we will be concerned with finite strings. Any ordered sequence x b1b2 bn of elements chosen from A is called a finite string of length x n over A. In the interest of notational convenience and without loss of generality we often choose A 0 . mg as the alphabet. Every element of the alphabet is also considered to be a string. Two strings x a1a2 ap and y b1b2 bq are equal if and only if p q and ai bi for i 1 . p. For each a 2 A we define the integer-valued function x a to be the number of times that a appears in the string x. The m 1 -tuple x x tt0 x ai x ttm is called the frequency vector of x. We freely concatenate THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R27 1 strings and write the concatenation of strings x .