Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The subword complexity of a two-parameter family of sequences"
Đ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 ngành toán học tạp chí toán học quốc tế đề tài: The subword complexity of a two-parameter family of sequences. | The subword complexity of a two-parameter family of sequences Aviezri S. Fraenkel Tamar Seeman Department of Computer Science and Applied Mathematics The Weizmann Institute of Science Rehovot 76100 Israel fraenkel tamars@wisdom.weizmann.ac.il http www.wisdom.weizmann.ac.il fraenkel tamars Jamie Simpson School of Mathematics Curtin University Perth WA 6001 Australia simpson@cs.curtin.edu.au http www.cs.curtin.edu.au s impson RECEIVED 4 14 2000 ACCEPTED 2 06 2001 Abstract We determine the subword complexity of the characteristic functions of a two-parameter family I An y 1 of infinite sequences which are associated with the winning strategies for a family of 2-player games. A special case of the family has the form An _naj for all n e z 0 where a is a fixed positive irrational number. The characteristic functions of such sequences have been shown to have subword complexity n 1. We show that every sequence in the extended family has subword complexity O n . 1 Introduction Denote by z 0 and z 0 the set of nonnegative integers and positive integers respectively. Given two heaps of finitely many tokens we define a 2-player heap game as follows. There are two types of moves THE ELECTRONIC JOURNAL OF COMBINATORICS 8 no. 2 2001 R10 1 1. Remove any positive number of tokens from a single heap. 2. Remove k 0 tokens from one heap and l 0 from the other. Here k and l are constrained by the condition 0 k l sk t where s and t are predetermined positive integers. The player who reaches a state where both heaps are empty wins. The special case s t 1 is the classical Wythoff game 15 16 5 . Fraenkel showed 11 that every possible position in a game of this type can be classified as either a F-position in which the Previous player can win or an -position in which the Next player can win. Thus a winning strategy involves moving from an -position to a F-position. Let P denote the set of all possible F-positions in a game with given values for s and t. Let mex S denote the least .