О языках автоматных счетчиковых машин

Изучается класс формальных языков (ЯАСМ), которые допускаются автоматными счетчиковыми машинами. Показывается, что этот класс замкнут относительно операций объединения, регулярного пересечения, конкатенации, бесконечной итерации, гомоморфизма и обратного гомоморфизма. Отсюда следует, что он является полным абстрактным семейством языков со всеми вытекающими из этого свойствами. Более того, класс АСМ-языков замкнут относительно пересечения и полной подстановки, но незамкнут относительно обращения и дополнения. Для класса ЯАСМ разрешимы проблемы пустоты и распознавания слова языка, заданного автоматной счетчиковой машиной, но неразрешимы проблемы включения и эквивалентности языков. Проводится сравнение с другими классами языков — регулярными, контекстно-свободными, контекстно-зависимыми языками и языками сетей Петри.