3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ It sounds like you want to look at coding theory, although that is usually concerned with packing instead of covering. $\endgroup$
    – Douglas Zare
    Commented Nov 24, 2011 at 0:01

1 Answer 1

Reset to default
3
$\begingroup$

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.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .