Geodesic
An algebraic study of the simplest codes and coefficientless equations in words
Sbornik. Mathematics, Tome 36 (1980) no. 4, pp. 495-517 
L. G. Kiseleva. An algebraic study of the simplest codes and coefficientless equations in words. Sbornik. Mathematics, Tome 36 (1980) no. 4, pp. 495-517. http://geodesic.mathdoc.fr/item/SM_1980_36_4_a3/
@article{SM_1980_36_4_a3,
     author = {L. G. Kiseleva},
     title = {An~algebraic study of the simplest codes and coefficientless equations in~words},
     journal = {Sbornik. Mathematics},
     pages = {495--517},
     year = {1980},
     volume = {36},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1980_36_4_a3/}
}
TY  - JOUR
AU  - L. G. Kiseleva
TI  - An algebraic study of the simplest codes and coefficientless equations in words
JO  - Sbornik. Mathematics
PY  - 1980
SP  - 495
EP  - 517
VL  - 36
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_1980_36_4_a3/
LA  - en
ID  - SM_1980_36_4_a3
ER  - 
%0 Journal Article
%A L. G. Kiseleva
%T An algebraic study of the simplest codes and coefficientless equations in words
%J Sbornik. Mathematics
%D 1980
%P 495-517
%V 36
%N 4
%U http://geodesic.mathdoc.fr/item/SM_1980_36_4_a3/
%G en
%F SM_1980_36_4_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] L. G. Budkina, Al. A. Markov, “Ob $F$-polugruppakh s tremya obrazuyuschimi”, Matem. zametki, 14:2 (1973), 267–277 | MR | Zbl

[2] A. Klifford, G. Preston, Algebraicheskaya teoriya polugrupp, t. 2, izd-vo “Mir”, Moskva, 1972

[3] E. S. Lyapin, A. E. Evseev, Algebra i teoriya chisel, t. I, izd-vo “Prosveschenie”, Moskva, 1974 | MR

[4] Al. A. Markov, “Nerekurrentnoe kodirovanie”, Problemy kibernetiki, vyp. 8, Fizmatgiz, Moskva, 1962 | MR

[5] Al. A. Markov, “O dline sootnoshenii v $F$-polugruppakh”, III Vsesoyuznaya konferentsiya po problemam teoreticheskoi kibernetiki. Tezisy dokladov, Novosibirsk, 1974

[6] Al. A. Markov, “Osnovaniya obschei teorii kodov”, Problemy kibernetiki, vyp. 31, Fizmatgiz, Moskva, 1976

[7] Yu. I. Khmelevskii, “Uravneniya v svobodnoi polugruppe”, Trudy Matem. in-ta im. V. A. Steklova, CVII (1971)

[8] A. Lentin, Equations dans les monoides libres, Gautier–Villard, Paris, 1972 | MR | Zbl

[9] Al. A. Markov, “On finitely generated subsemigroups of a free semigroup”, Semigroup Forum, 3 (1971), 251–258 | DOI | MR | Zbl

[10] L. Redei, The theory of finitely generated commutative semigroups, Pergamon Press, 1965 | MR | Zbl