Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Restrictions and Generalizations on Comma-Free Codes. | Restrictions and Generalizations on Comma-Free Codes Alexander L. Churchill Student Stanford University California USA achur@ Submitted Feb 13 2008 Accepted Feb 14 2009 Published Feb 20 2009 Mathematics Subject Classifications 94B50 94B65 Abstract A significant sector of coding theory is that of comma-free coding that is codes which can be received without the need of a letter used for word separation. The major difficulty is in finding bounds on the maximum number of comma-free words which can inhabit a dictionary. We introduce a new class called a self-reflective comma-free dictionary and prove a series of bounds on the size of such a dictionary based upon word length and alphabet size. We also introduce other new classes such as self-swappable comma-free codes and comma-free codes in q dimensions and prove preliminary bounds for these classes. Finally we discuss the implications and applications of combining these original concepts including their implications for the NP-complete Post Correspondence Problem. 1 Introduction Comma-free codes Comma-free codes were first introduced by Crick Griffith and Orgel 2 in 1957 as a potential explanation for the fact that DNA codes only twenty amino acids despite the fact that it is a code with word-length three and a four-letter alphabet. While this explanation was revealed to be incorrect comma-free codes are still a major area of exploration in coding theory. Initially we establish definitions. Let n be a fixed positive integer. Consider a dictionary of words in which each word has length k chosen from an n-letter alphabet. Let the alphabet consist of letters a1 a2 3 . an. A set D of k-letter words is called a Comma-Free Dictionary according to Golomb Gordon and Welch 4 if whenever words a1a2 ak and b1 b2 bk are in D the overlaps a2a3 akb1 a3 akb1b2 . akb1 b2 bk-1 are not in D. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R25 1 The major problems investigated have been in determination of the maximum .
