Rozdzielanie list słów

Istnieje problem otwarty w językach formalnych znany jako problem oddzielający; co jest krótko określone jako dane dwa odrębne ciągi o długości , jak duży jest DFA, aby je „rozdzielić”, co oznacza przyjęcie jednego ciągu, ale odrzucenie drugiego.$n$

Oto kilka odpowiednich dokumentów 1 , 2 . (Mam jeszcze kilka, ale nie mam wystarczającej reputacji, aby je opublikować).

Wszystkie omawiają problem oddzielenia dwóch różnych ciągów. Zastanawiam się, czy nie było żadnych prace w dziedzinie rozdzielania listy ciągów, znaczeniem nadanym dwie listy ciągów, i B , co rozmiar DFA jest wymagany, aby zaakceptować każdy łańcuch w A i odrzucenia wszelkich ciąg w B . Ten problem jest równoważny wyrażeniom regularnym golfa.$A$$B$$A$$B$

Jest kilka podstawowych pytań, nad którymi pracowałem, np. Czy jedna z list ma rozmiar lub czy wszystkie ciągi mają różną długość.$1$

Szukałem w okolicy, ale nie znalazłem żadnych artykułów, które mogłyby poradzić sobie z tego rodzaju problemem. Czy przeprowadzono jakieś badania w tej dziedzinie?

Z góry dziękuję.

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

$K$$L$$M$

W artykule z 2013 r. Autorzy wskazują:

Chociaż często występuje problem separacji, nie był on jednak systematycznie badany, nawet w ograniczonym, ale wciąż trudnym przypadku zwykłych języków.

Wspominają jednak o kilku szczególnych przypadkach, które zostały rozwiązane, i które z pewnością obejmują przypadek skończony.

Możesz także przyjrzeć się interpolantowi Craiga , podobnemu problemowi związanemu z formułami logicznymi. Interpolacja jest używana na przykład przy sprawdzaniu modelu opartym na SAT, w otoczeniu, które moim zdaniem jest bliższe temu, czego szukasz (szczególnie w odniesieniu do skończoności danych wejściowych). Ten artykuł powinien być dobrym punktem wyjścia.

$A$$B$

Nazywa się to „Problemem słów oddzielających”. Slajdy Shallit obejmują w zasadzie wszystko, co wiadomo na temat problemu (patrz slajdy1 i slajdy2 ).