Об уравнениях и неравенствах в словах и длинах

Через $\Pi_{m}$, как обычно, мы обозначаем свободную полугруппу с пустым словом в качестве нейтрального элемента ранга $m$ со свободными образующими $a_1,\ldots,a_m$. В теории уравнений на свободной полугруппе $\Pi_{m}$ хорошо известен открытый уже более 40 лет вопрос об алгоритмической разрешимости проблемы совместности для систем уравнений в словах и длинах, т.е. систем вида
$$ \underset{i=1}{\overset{k}{\&}} \, w_i (x_1, \ldots , x_n, a_1, \ldots , a_m) \, = \, u_i(x_1, \ldots , x_n, a_1, \ldots , a_m)\; \& \; \underset{\{ i, j \}\, \in \, A}{\&} \; |x_i| \, = \, |x_j|, $$
где через $|w|\, = \, |u|$, как обычно, обозначается предикат " длины слов $w$ и $u$ равны". Изучение таких систем уравнений в словах и длинах было начато в начале 70-ых годов прошлого века в работах Ю.В. Матиясевича [15] и Н.К. Косовского [9], [10], [11].
В настоящей заметке доказывается алгоритмическая неразрешимость проблемы совместности для систем уравнений и неравенств в словах и длинах на свободной нециклической полугруппе $\Pi_{m}$: показано, что при $m \geq 2$ не возможно создать алгоритм, позволяющий для произвольной системы неравенств и равенств вида
$$ \underset{i=1}{\overset{k}{\&}} \, w_i (x_1,\ldots,x_n,a_1,\ldots,a_m)\, \leq \, u_i (x_1,\ldots,x_n,a_1,\ldots,a_m)\; \& \; \underset{\{ i, j \}\, \in \, A}{\&} \; |x_i| \, = \, |x_j|, $$
где $w_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ и $u_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ – слова в алфавите
$$ \lbrace\,x_1,x_2,\ldots,x_n, a_1,a_2,\ldots,a_m\,\rbrace , $$
определить, имеет ли она решение в свободной полугруппе $\Pi_{m}$, где через $w\, \leq \, u$ обозначается предикат " последовательность букв $w$ является подпоследовательностью последовательности букв $u$".
Библиография: 19 названий.