$\Sigma TC$-порождаемые языки и проблемы относительной эквивалентности

Доказана разрешимость проблемы эквивалентности для машин Тьюринга ограниченного режима с выходной лентой относительно любого входного $\Sigma TC$-порождаемого языка. Такие языки порождаются обобщенными конечными преобразователями с конечноповоротными счетчиками над бесконечными размеченными деревьями. Доказана $\Sigma TC$-порождаемость многих языков (контекстно-свободных, распознаваемых гнездовыми машинами Тьюринга ограниченного режима и других). Показано, что для последовательностных преобразователей с двумя состояниями неразрешима проблема эквивалентности относительно регулярного языка.