PDA with independent counters

Магазинные автоматы с независимыми счётчиками (МПНС) объединяют возможности МП-автоматов и сетей Петри. Они были предложены в работах [21, 15] как средство для распознавания языков, порождаемых категориальными грамматиками зависимостей (КГЗ). КГЗ представляют собой классические категориальные грамматики, расширенные ориентированными поляризованными валентностями. Они позволяют выразить как проективные, так и непроективные зависимости между словами предложения. МПНС — это обычный МП-автомат, к которому добавлено конечное число счётчиков. Независимость счётчиков означает, что их содержимое не влияет на выбор очередного действия автомата. В первой части статьи мы сравниваем несколько вариантов определения МПНС и доказываем эквивалентность двух вариантов МПНС: без синтаксических пустых циклов и без семантических пустых циклов. Отмечаем также некоторые связи между МПНС-языками и языками сетей Петри. Мы показываем, что МПНС эквивалентны стек+бэг МП-автоматам (СБМПА), предложенным независимо Сёгаардом (Søgaard), и что \linebreak СБМПА без пустых циклов распознают в точности КГЗ-языки. Мультимодальные категориальные грамматики зависимостей (ммКГЗ) были введены в [4] как расширения КГЗ, позволяющие управлять пересечениями некоторых зависимостей. Класс ммКГЗ-языков достаточно богат и обладает многими свойствами замкнутости, в частности, он образует абстрактное семейство языков. Во второй части статьи мы расширяем МПНС и определяем МП-автоматы со стеками независимых счётчиков (МПСНС). Это расширение двоякое: (1) каждый счётчик представляет стек натуральных чисел и (2) добавляется функция, которая позволяет уменьшать число на вершине стека счётчика, только если вершины всех связанных с ним счётчиков равны нулю. Наш основной результат утверждает, что МПСНС допускают в точности класс ммКГЗ-языков.