Abstract

A set D of k -letter words is called a comma-free dictionary (2), if whenever ( a 1 a 2 . . . a k ) and ( b 1 b 2 . . . b k ) are in D , the "overlaps" ( a 2 a 3 . . . a k b 1 ), ( a 3 a 4 . . . a k b 1 b 2 ), . . . , ( a k b 1 . . . b k -1) are not in D . We say that two k -letter words are in the same equivalence class if one is a cyclic permutation of the other. An equivalence class is called complete if it contains k distinct members. Comma-freedom is violated if we choose words from incomplete equivalence classes, or if more than one word is chosen from the same complete class.