Thursday, June 28, 2001, 8:30 am
Professor Jack K. Wolf
Constrained Sequences, Crosswords Puzzles and Shannon
AbstractConstrained sequences are used in many digital communication and storage systems. The foundation for the theory of constrained sequences is contained in Shannon's famous 1948 paper. In this paper, Shannon also comments on the relationship between the redundancy of a language and the existence of crossword puzzles. Here, we consider large constrained sequences and arrays and give a plausibility argument for Shannon's conclusions.