Theoretically effective asymptotically optimal universal coding of partially defined sources

Let $A_0=\{a_i: i\in M\}$ be a finite alphabet of basic symbols, $A=\{a_T: T\in\mathcal{T}\}$, $\mathcal{T}\subseteq 2^M$, — an alphabet of underdetermined symbols. Any symbol $a_i$, $i\in T$, is considered to be a specification of the symbol $a_T$. The symbol $a_M$, denoted by $*$, is called indefinite. An underdetermined source $X$ generates symbols $a_T\in A$ independently with probabilities $p_T$. The entropy of the source $X$ is the quantity
$$ \mathcal{H}(X)= \min_Q\left(-\textstyle\sum\limits_{T\in\mathcal{T}} p_T\log\sum\limits_{i\in T}q_i\right), $$
where the minimum is taken over the set of probability vectors $Q=(q_i, i\in M)$, $\log x=\log_2x$. For source $X$, we consider separable block coding with a block length of $n$. Encoding $K$ of underdetermined words $v\in A^n$ should ensure that the code $K(v)$ of word $v$ allow one to recover some specification of $v$. Coding is universal if it is independent of the probabilities $p_T$, $T\in\mathcal{T}$. Characteristic of coding quality is average code length
$$ \bar l^{(n)}=\frac{1}{n}\textstyle\sum\limits_{v\in A^n}p(v)|K(v)|, $$
where $p(v)=p_{T_1}\ldots p_{T_n}$ is the probability of the appearance of the word $v=a_{T_1}\ldots a_{T_n}$ at the source output, $|K(v)|$ is the codeword length for $v$. Earlier, the author established that for arbitrary source $X$ and for any block coding method, the inequality $\bar l^{(n)}\ge\mathcal{H}(X)$ holds, and that there is universal block coding, for which $\bar l^{(n)}\le\mathcal{H}(X)+\text{O}\Bigl(\dfrac{\log n}{n}\Bigr)$. The upper bound here is obtained by random coding which only establishes existence of the estimation, but does not provide an appropriate algorithm. Important for applications are issues of complexity of procedures. Coding method considered theoretically effective if the complexities of coding and decoding are estimated by a some polynomial of the size $n$ of problem. This paper presents a polynomial coding method for underdetermined sources whose alphabet has the form $A=A_0\cup\{*\}=\{a_0, a_1,\ldots,a_{m-1},*\}$. Such sources are called partially defined. For them, entropy can be explicitly expressed:
$$ \mathcal{H}(P)=(1-p_*)\log(1-p_*)-\textstyle\sum\limits_{i=0}^{m-1}p_i\log p_i. $$
The main content of the paper is the proof of the following result. For a partially defined source $X$, there is an universal method of block coding that provides an estimate of the average length of the code
$$ \bar l^{(n)}\le\mathcal{H}(P) + \text{O}\Bigl(\frac{\log \log n}{\log^{1/2}n}\Bigr) $$
and allows you to encode and decode using RAM-programs with complexity O$(n^2)$. An analogue of this result is also valid for other types of undetermined sources whose entropy is explicitly representable.