Алгебраическое исследование простейших кодов и бескоэффициентных уравнений в словах

Пусть $A=\{a_1,\dots,a_n\}$ – алфавит, $W=\{w_1,\dots,w_m\}$ – $m$-код, то есть множество, состоящее из $m$ слов в алфавите $A$, $|\alpha|$ – длина слова $\alpha$. $\Sigma(W)=\sum_{i=1}^m|w_i|$, $B=\{b_1,\dots,b_m\}$ – алфавит языка сообщений, $A^+=\bigcup_{i=1}^\infty A^i$, $f=f_W\colon B^+\to A^+$, $f(b_i)=w_i$, $f(\alpha\beta)=f(\alpha)f(\beta)$ – алфавитное кодирование,
\begin{gather*} R(W)=\{\langle\mu,\nu\rangle\mid f(\mu)\equiv f(\nu),\mu\not\equiv\nu\},\\ X'(W)=\min\{|\alpha|:\langle\mu,\nu\rangle\in R(W),f(\mu)\equiv f(\nu)\equiv\alpha\},\\ X'(m,N)=\max\{X'(W):|W|=m,\Sigma(W)\leqslant N\}. \end{gather*}
$X'(m,N)$ характеризует наименьшее число сравнений, которое может потребоваться при решении вопроса о взаимной однозначности $f_W$ для $m$-кода $W$ в худшем варианте, при условии, что объем входной информации $\Sigma(W)\leqslant N$ (единица измерения есть сравнение букв алфавита $A$). Доказано, что $X'(3,N)\sim N^2/8$. Показано, что неоднородное уравнение в словах с тремя неизвестными имеет не более одного нетривиального решения с точностью до изоморфизма.
Библиография: 10 названий.