Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement that one of either should arrive should allow us to save on bits.
To give a specific application: say the receiver and I have a DFA, and I want to send some word in the language described by the automaton. I can do this by encoding a path over the automaton as an n-ary string. But if there are several paths over the automaton, I don't care which the receiver decodes, so long as it decodes to the right word.
Is there research into this question? Are there google-able phrases that I don't know about?
Also, if we use a probabilistic DFA, it defines a probability distribution over the words in its language. By the Kraft inequality, there exists a coding for this probability whereby the length of the code for word W is equal to the logarithm of P(W). However if we use a specific path A over the automaton to encode W, that path may only contribute part of the probability mass of P(W). Say there are two paths A and B that produce W, so that P(A) + P(B) = P(W). Is there a scheme that allows us to send a message with length log(P(W)) that decodes into either A or B?
compressed(A)
instead). That would be trivial, so that's why I wanted to clarify the domain assumptions. $\endgroup$