Coding combinatorial sources with costs

We consider coding infinite sequences of a finite alphabet. The source is defined as a set of sequences (combinatorial source). The problem is to minimize the worst asymptotic compression ratio between each sequence and its coding output among the sequences in the combinatorial source. Ryabko showed that the optimal value coincides with the Hausdorff dimension of the combinatorial source. This correspondence extends the previous work in that the input and output costs are expressed in terms of not lengths but generalized costs. The essential quantity turns out to be the Hausdorff dimension with respect to the measure associated with the input cost. We construct an asymptotically optimal coding procedure, and also show that no coding scheme can beat the lower bound.