TAILIEUCHUNG - Báo cáo toán học: "Gray Codes for A-Free Strings"

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: Gray Codes for A-Free Strings. | Gray Codes for A-Free Strings Matthew B. Squire IBM Corporation Dept NFVA Bldg 664 . Box 12195 Research Triangle Park NC 27709 Email msquire@vnet. Submitted July 10 1995 Accepted February 14 1996. Abstract For any q 2 let q 0 . q 1g and fix a string A over q. The A-free strings of length n are the strings in n which do not contain A as a contiguous substring. In this paper we investigate the possibility of listing the A-free strings of length n so that successive strings differ in only one position and by 1 in that position. Such a listing is a Gray code for the A-free strings of length n. We identify those q and A such that for infinitely many n 0 a Gray code for the A-free strings of length n is prohibited by a parity problem. Our parity argument uses techniques similar to those of Guibas and Odlyzko Journal of Combinatorial Theory A 30 1981 pp. 183-208 who enumerated the A-free strings of length n. When q is even we also give the complementary positive result for those A for which an infinite number of parity problems do not exist we construct a Gray code for the A-free strings of length n for all n 0. Mathematical Review Subject Numbers 68R15 05A15. 1 Introduction Fix q 2 and let q 0 . q 1g. When we refer to strings we mean strings over q. For any strings A and B an A-factor of B is a contiguous substring of B equal to A. Fix a string A and let F n F n A be the strings of length n which do not have an A-factor. The set F n consists of the A-free strings of length n. We are interested in Gray codes for F n . A Gray code for a set is a listing of its elements so that successive elements are similar. Define two strings in n to be Research supported by National Science Foundation Grant No. DMS9302505. THE ELECTRONIC .JOURNAL OF COMBINATORICS 3 1996 R17 2 similar if they differ in exactly one position and by 1 in that position. When q is even the addition is done modulo q but the addition is not modular for odd q. Given S c n we can form a graph whose .

• Báo cáo khoa học
• tài liệu báo cáo nghiện cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội