Restrictions and generalizations on comma-free codes (Q1010931)

Summary: 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.