Separando listas de palavras

Há um problema em aberto em idiomas formais conhecido como Problema de Separação; que é brevemente indicado como duas seqüências distintas de comprimento , qual o tamanho de um DFA necessário para "separá-las", o que significa aceitar uma sequência, mas rejeitar a outra.$n$

Aqui estão alguns artigos relevantes 1 , 2 . (Tenho mais alguns, mas não tenho reputação suficiente para publicá-los).

Todos eles discutem o problema de separar duas seqüências distintas. Eu estou querendo saber se houve algum trabalho feito na área de separar listas de cordas, significado dado duas listas de cordas, e B , que tamanho DFA é obrigado a aceitar cada corda em uma e rejeitar todas as cordas em B . Esse problema é equivalente ao regex golf.$A$$B$$A$$B$

Tenho trabalhado em algumas questões básicas, como se uma das listas fosse do tamanho ou se todas as seqüências tivessem comprimentos diferentes.$1$

Estive pesquisando, mas não encontrei nenhum documento que lide com esse tipo de problema. Houve alguma pesquisa nessa área?

Desde já, obrigado.

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

$K$$L$$M$

Em um artigo de 2013 , os autores indicam:

Embora o problema da separação ocorra com frequência, ele ainda não foi estudado sistematicamente, mesmo no caso restrito, ainda desafiador, das linguagens regulares.

Porém, eles mencionam vários casos especiais que foram resolvidos e que certamente abrangem o caso finito.

Você também pode querer analisar o interpolante Craig , um problema semelhante nas fórmulas lógicas. A interpolação é usada, por exemplo, na verificação de modelo baseada em SAT, em um cenário que eu acho que está mais próximo do que você está procurando (especialmente em relação à finitude da entrada). Este documento deve ser um bom ponto de partida.

$A$$B$

Isso é chamado de "O Problema das Palavras Separadoras". Os slides de Shallit cobrem praticamente tudo o que se sabe sobre o problema (consulte os slides1 e os slides2 ).