Квазисоотношения в свободной группе и проблемы эквивалентности преобразователей

Показано, что соотношение $\prod\limits_{i=1}^s\prod\limits_{j=1}^k(\alpha_j^i)^{\ell_j}=1$ верно в свободной группе $\mathcal{F}$ для любых натуральных чисел $\ell_j$, $1\leqslant j\leqslant k$, если оно верно для любых чисел $0\leqslant\ell_1,\dots, \ell_k\leqslant c$, по крайней мере одно из которых равно нулю, где $c$ конструктивно зависит от $k$, $s$, $\max|\alpha_j^i|$ и $k\geqslant7s+1$. Этот результат используется для решения алгоритмических проблем сравнения отображений, задаваемых преобразователями над размеченными деревьями. В частности, доказана разрешимость проблемы функциональной эквивалентности для машин Тьюринга ограниченного режима, выдающих на выходную ленту слова в алфавите $\Delta$, интерпретируемые как элементы свободной группы $\mathcal{F}(\Delta)$.