Алгоритм пересечения DFA для особых случаев

9

Меня интересуют эффективные алгоритмы пересечения DFA для особых случаев. А именно, когда DFA пересекаются, подчиняются определенной структуре и / или работают по ограниченному алфавиту. Есть ли источник, где я могу найти алгоритмы таких случаев?

Чтобы не делать вопрос слишком широким, особый интерес представляет следующая структура: все DFA, которые должны пересекаться, работают в двоичном алфавите (0 | 1), они также могут использовать небезразличные символы. Более того, все состояния имеют только один переход, за исключением не более чем K специальных состояний, которые имеют только два перехода (и эти переходы всегда равны 0 или 1, но не все равно). K - целое число, меньше 10 для практических целей. Кроме того, у них есть единственное принимающее государство. Кроме того, известно, что пересечение ВСЕГДА является DFA в форме "полосы", то есть без ветвей, как на следующем изображении:

введите описание изображения здесь

РЕДАКТИРОВАТЬ: Возможно, описание ограничения на входные DFAs не очень ясно. Я постараюсь улучшить это в этом пункте. Вы как вход Т ДКА. Каждый из этих DFA действует только на двоичном алфавите. Каждый из них имеет не более N состояний. Для каждого DFA каждое из его состояний является одним из следующих:

1) принимающее состояние (оно только одно и перехода из него в любое другое состояние нет)

2) состояние с двумя переходами (0 и 1) в одно и то же целевое состояние (большинство состояний этого типа)

3) состояние с двумя переходами (0 и 1) в разные целевые состояния (не более K этого типа)

Гарантируется, что существует только одно принимающее состояние и что в каждом входном DFA имеется не более K состояний типа (3). Это также гарантирует , что пересечение DFA все входную ДКИ является «полосой» (как описано выше), размера меньше , чем N .

РЕДАКТИРОВАТЬ 2: Некоторые дополнительные ограничения, как того требует DW в комментариях:

  • Входные DFA - это DAG.
  • Входные DFA "выровнены", следуя определению DW в комментариях. А именно, вы можете назначить разные целые числа каждому состоянию таким образом, чтобы каждый переход переходил от целого числа u к целому числу v , так что u + 1 = v .
  • Количество допускающих состояний для каждого входного DFA, не превышает K .

Любые идеи? Спасибо.

ale64bit
источник
Как именно вы модель "пофиг"? Кажется, это делает автоматы недетерминированными.
Шал
@Shaull Почему это должно сделать автомат недетерминированным. Это может произойти, только если есть другой переход из того же состояния, который явно исключен.
Бабу
1
Что такое a DFA in form of "strip", i.e., no branches? Есть ли у вас какие-либо конкретные основания полагать, что в вашем случае можно добиться большего успеха, чем стандартный алгоритм?
Бабу
1
Привет. Вычисление фактического пересечения было бы здорово, поскольку это упростило бы многие вещи, но решение пустоты также было бы полезно.
ale64bit
1
только что наткнулся на новую статью о графах пересечений , может быть какая-то из этих теорий актуальна? Не могли бы вы, пожалуйста, расширить свое приложение, упомянутое в вашем комментарии в Театральном информатическом чате ? и пригласить других, чтобы продолжить дальнейшее обсуждение там.
2

Ответы:

9

Да , есть несколько случаев проблемы вставки не пустоты DFA, которые находятся внутри P. Моя магистерская работа посвящена этому вопросу, но, к сожалению, на французском. Тем не менее, большинство результатов появилось здесь в[2],

Когда алфавит унарный, проблема состоит в L-полноте, когда каждый DFA имеет не более двух конечных состояний, и NP-полной в противном случае. В большинстве других случаев это ограничение на переход моноидов автоматов. Например, для моноидов абелевых групповых переходов проблема заключается вСеверная Каролина3когда каждый DFA имеет не более одного конечного состояния и NP-завершен в противном случае; для элементарных 2-групповых моноидов перехода проблемаL-завершение, когда каждый DFA имеет не более двух конечных состояний, и NP-завершение в противном случае.


Позвольте мне теперь обратиться к вашему более точному вопросу, который можно найти только в [1], Предположим, вы получили DFA, работающие над{0,1} и в форме деревьев, то есть существует государство U (начальное состояние) такое, что для каждого состояния v существует уникальный путь от U в v, Тогда, решение о пересечении не пустоты таково:

  1. L-полная для одного конечного состояния в каждом DFA,
  2. NL-завершение для двух конечных состояний в каждом DFA и
  3. NP-завершение для трех или более конечных состояний в каждом DFA.

Результаты по твердости остаются в силе, даже если вы «разветвляетесь» соответственно 0, 1 или 2 раза (это ваш К). Теперь, если ваши DFA являются ориентированными ациклическими графами, а не деревьями, проблема в NP-полноте даже с одним конечным состоянием в каждом DFA иКзнак равно2; снижение довольно простое и происходит от монотонности 1-в-3-3-SAT.

Поэтому нет , я не думаю, что есть эффективный алгоритм для вашей проблемы.

Теперь, если число автоматов фиксировано, вы можете обсудить это с Майклом Вехаром, который недавно опубликовал[3],


РЕДАКТИРОВАТЬ: Поскольку ОП редактировал его вопрос, позвольте мне уточнить мой ответ с его новыми требованиями. Рассмотрим задачу NP-complete Monotone 1-in-3 3-SAT, где вам дается формула в 3-CNF без отрицания, и где вы должны определить, есть ли присваивание, делающее ровно одну переменную истинной в каждом предложении. Вы можете свести эту проблему к проблеме пересечения не пустоты следующим образом. Например, для оговоркиИкс2Икс3Икс5Вы строите следующий автомат:

гаджет сокращения

Обратите внимание, что автоматы являются деревьями (и, следовательно, DAG), выровнены и имеют три конечных состояния. На самом деле, три конечных состояния могут быть объединены в одно, если один удовлетворен DAG. Более того, только два состояния имеют два (разных) исходящих перехода.

  1. Майкл Блондин. Complexité raffinée du problème d'intersection d'automates, M.Sc. диссертация, Университет Монреаля, 2012.
  2. Майкл Блондин, Андреас Кребс и Пьер МакКензи. Сложность пересекающихся конечных автоматов с несколькими конечными состояниями, вычислительная сложность (CC), 2014.
  3. Майкл Вехар. Результаты твердости для непустоты пересечения. ICALP, 2014.
Майкл Блондин
источник
2
Большое спасибо! Я принимаю ваш ответ. Вопрос возник из некоторых практических тестов, где после многих шагов все сводилось к пересечению решений многих DFA с этими конкретными характеристиками. Тем не менее, мы заметили, что хотя в конце мы получили бы простой DFA, процесс так и не завершился из-за того, что промежуточные DFA (при последовательном пересечении) дико перерастали в экспоненциальное число состояний. Таким образом, вопрос о том, как получить ответ, не пройдя через посреднические «наивные» шаги.
ale64bit
1
Большое спасибо (и извините за непонятность, я ниже начинающих в этой области). Теперь есть кое-что, чего я не понимаю. Вы упоминаете, что «в форме дерева» означает «уникальный путь от корня ко всем остальным узлам». Но, например, на изображении, которое вы разместили в редактировании, это не было бы деревом (если вы не считаете переходы 0/1 как одну метку)?
ale64bit
1
Вы правы, но, насколько я понимаю, вы допускаете переходы "пофиг". Разве это не так?
Майкл Блондин
2
Привет майкл Спасибо за хороший ответ. Я надеюсь, что все хорошо. :)
Майкл Вехар
2
@MichaelWehar Если вы исправите k и c, вы упоминаете, что можете решить проблему «быстро». Но вы не упоминаете сложность времени, только сложность пространства. Что именно «быстро» означает в этом контексте?
ale64bit