An~algebraic study of the simplest codes and coefficientless equations in~words

L. G. Kiseleva

Sbornik. Mathematics, Tome 36 (1980) no. 4, pp. 495-517

Résumé

Let $A=\{a_1,\dots,a_n\}$ be an alphabet and let $W=\{w_1,\dots,w_m\}$ be an $m$-code, i.e. a set consisting of $m$ words in the alphabet $A$; let $|\alpha|$ denote the length of a word $\alpha$. Suppose that $\Sigma(W)=\sum_{i=1}^m|w_i|$, that $B=\{b_1,\dots,b_m\}$ is the alphabet of the message language, and $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)$ is an alphabetic encoding, \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):\vert W\vert=m,\Sigma(W)\leqslant N\}. \end{gather*} $X'(m,N)$ characterizes the smallest number of comparisons which are needed to solve the problem of $f_W$ being one-to-one for the $m$-code $W$ in the worst case when the size of the input information $\Sigma(W)\leqslant N$ (the unit of measurement is a comparison of letters from $A$). It is proved that $X'(3,N)\sim N^2/8$. We show that a nonhomogeneous equation in words in three unknowns has at most one nontrivial solution, up to isomorphism. Bibliography: 10 titles.