Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения

Изучаются алгоритмические проблемы для уравнений в свободных моноидах и полугруппах (уравнения в словах и длинах) с дополнительными ограничениями на решения. Доказывается, что невозможно построить алгоритм, позволяющий по произвольной системе уравнений в словах и длинах в свободном моноиде (свободной полугруппе) ранга 2 с одним дополнительным ограничением на решение в форме принадлежности одной его компоненты языку сбалансированных слов или равенства проекций двух компонент решения на одну выделенную свободную образующую определить, имеет ли она решение. Аналогичный результат установлен для систем неравенств в словах.