Какие известные модели автоматов имеют полиномиально разрешимую локализацию?

Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2$M_1, M_2$$L(M_1) \subseteq L(M_2)$

Очевидные из них, которые приходят на ум, - это DFA и счетные машины с ограниченным реверсом, в которых количество счетчиков фиксировано (см. Эту статью ).

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

Чем мощнее автоматы, тем лучше. Например, DFA недостаточно для решения моей проблемы, и счетчики не могут сделать это с фиксированным количеством счетчиков. (Естественно, если вы становитесь слишком могущественным, то сдерживание может быть либо внутренним, как для NFA, либо неразрешимым для CFG).

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

Между прочим, недетерминированный вариант визуально проталкиваемых автоматов экспоненциально более лаконичен, чем детерминированный вариант, но там проблема включения языка является EXPTIME-полной и, следовательно, неразрешимой.

Alur, R .; Madhusudan, P. (2009). « Добавление структуры вложенности в слова ». Журнал ACM 56 (3): 1–43.

Если в вашей области видимости находятся бесконечные слова, вы можете обобщить DFA (с условием четности) на так называемые автоматы Good-for-Games (GFG), которые по-прежнему содержат полиномиальную оболочку.

NFA - это GFG, если существует стратегия , которая с учетом уже прочитанного префикса, текущего состояния и буквы выбирает переход для перехода в следующее состояние. Стратегия σ должна гарантировать, что для каждого w на языке автомата прогон, полученный от σ на w, является приемлемым.$\sigma:A^*\times Q\times A\to \Delta$$\sigma$$w$$\sigma$$w$

Контейнер для этих автоматов находится в P для любого фиксированного условия четности (путем сокращения до игр четности) и в Quasi-P, если индекс четности является частью входных данных. Они могут быть экспоненциально меньше, чем любой эквивалентный DFA [3].

Однако, если говорить ограниченно, это всего лишь DFA с возможными бесполезными дополнительными переходами, поэтому они не приносят ничего нового.

Вот несколько ссылок:

[1] Решение игр без определения , Henzinger, Piterman, в CSL 2006

[2] Недетерминизм в присутствии разнообразного или неизвестного будущего , Бокер, Куперберг, Купферман, Скшипчак, в ICALP 2013

[3] Об определении автоматов для игр , Куперберг, Скшипчак, в ICALP 2015

Non детерминированным XOR автомат (NXA) подходит ваш вопрос.

$M$$w\in \Sigma^*$$L(M)$

NXA используются для создания небольших представлений регулярных языков, а также некоторых параметризованных алгоритмов.

$O(|Q|^3$$L(M_1)\subseteq L(M_2)$

$M_1$$M_2$$L(M_2)$$L(M_1)$

$M_2$

Позвольте мне набросать доказательство этого результата.

$M_1$$M_2$$M_2$$L(M_1)\subseteq L(M_2)$

Доказательство.
Шаг 1: Это сводится к универсальности однозначных автоматов.

$M_1$$M_1$

$L(M_1)\subseteq L(M_2)$$L(M_2)\cup L(M_1)^c$

Шаг 2: Бывает, что однозначные автоматы могут рассматриваться как NXA-автоматы (недетерминированные автоматы XOR в предыдущем посте RB) без изменения оценки, которая должна быть изменена (действительно, дизъюнкция по всем запускающим прогонам эквивалентна xor по всем принимающим работает, так как есть не более одного такого запуска). Известно, что для этих автоматов универсальность является полиномиальной (КЭД).

$Z/2Z$

[SH85] Ричард Э. Стернс и Гарри Б. Хант III. О проблемах эквивалентности и содержания для однозначных регулярных выражений, регулярных грамматик и конечных автоматов. SIAM J. Comput., 14 (3): 598-611, 1985.

[S61] Шютценбергер, М.П .: Об определении семейства автоматов. Информация и управление 4, 245–270 (1961)

Регулярные грамматики LL (k) (т.е. грамматики, которые являются и LL (k), и регулярными ), могут быть преобразованы за полиномиальное время в эквивалентные детерминированные конечные автоматы, и, таким образом, локализация и эквивалентность языка могут быть решены в PTIME. См. Теорему 4.2 в следующей статье (и результаты впоследствии для применения этого наблюдения к программным схемам).

Гарри Б. Хант III: Наблюдения за сложностью проблем регулярного выражения , Журнал компьютерных и системных наук 19, 222-236 (1979)