Restrictions and Generalizations on Comma-Free Codes

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.