Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all, I have been interested in La Jolla covering tables lately and I was wondering if there is some theory around sets where the same element is allowed to be present more than once. For example the following block would be considered valid: {1, 1, 1, 2, 3}. Basically given an alphabet {A, B, C, D} and given a word length (k), find the minimum set of words which cover the whole language with a max of N "letter replacements". For example, if the alphabet is binary {0,1} and word length is 3, a set covering "-1" would be { 000, 111} since all other words differ for at most by one char.

P.S. I would also be interested in the algorithms used to generate the tables itself, by I cannot find pointers. Thanks

share|improve this question
    
It sounds like you want to look at coding theory, although that is usually concerned with packing instead of covering. –  Douglas Zare Nov 24 '11 at 0:01
add comment

1 Answer 1

The concept you are referring to is a covering code. These have been extensively studied and a great reference would be the book "Covering Codes" by G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein. (On a side note, the repetition code you give as an example is both a packing and a covering, i.e., a tiling, or perfect code.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.