Разделение списков слов

Существует открытая проблема в формальных языках, известная как проблема разделения; который кратко изложен как заданные две отдельные строки длины , насколько большой DFA требуется, чтобы «разделить» их, то есть принять одну строку, но отклонить другую.$n$

Вот некоторые соответствующие документы 1 , 2 . (У меня есть еще несколько, но у меня недостаточно репутации, чтобы публиковать их).

Все они обсуждают проблему разделения двух разных строк. Мне интересно , если ли какая - либо работа в области разделения списков строк, значение , придаваемое два списка строк, и B , какого размера требуется DFA принимать каждую строку в A и отклонять каждую строку в B . Эта проблема эквивалентна регулярному гольфу.$A$$B$$A$$B$

Есть несколько основных вопросов, над которыми я работал, например, если один из списков имеет размер или все строки имеют разную длину.$1$

Я искал вокруг, но не нашел никаких бумаг, которые имеют дело с этим типом проблемы. Были ли проведены какие-либо исследования в этой области?

Заранее спасибо.

$K$$L$$M$$K \subseteq M$$M \cap L = \emptyset$

$K$$L$$M$

В статье 2013 года авторы указывают:

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

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

Вы также можете взглянуть на интерполяцию Крейга , похожую проблему на логических формулах. Интерполяция используется, например, при проверке моделей на основе SAT, в настройках, которые, я думаю, ближе к тому, что вы ищете (особенно в отношении конечности входных данных). Эта статья должна стать хорошей отправной точкой.

$A$$B$

Это называется «Проблема разделения слов». Слайды Шаллита в значительной степени охватывают все, что известно о проблеме (см. Слайды1 и слайды2 ).