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.nn
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.AABBAABB
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.11
Estive pesquisando, mas não encontrei nenhum documento que lide com esse tipo de problema. Houve alguma pesquisa nessa área?
fyi igual ao mínimo DFA dado in-words & out-words
— vzn 16/04/2015
O link do VZN é ótimo! No entanto, eu acredito que você pode encontrar ainda mais informações, se você der uma olhada no apêndice: "Computadores e Intratabilidade: Um Guia para a Teoria da NP-completo"
klog(n)log(log(n))klog(n)log(log(n))
Em Gold1978, sabemos que o problema de determinar se duas listas podem ser separadas por um DFA de um determinado tamanho é NP-complete. Se você modificar o problema, digamos, separado por uma máquina de Turing com um limite de tempo escrito em unário, não será sabido se o problema é NP-completo. Foi sugerido que esse problema possa estar relacionado ao problema mínimo do circuito, caso em que resolveria problemas em aberto na complexidade estrutural se você mostrasse que estava em P ou se estava completo em NP.
Possível duplicata de Encontrar a expressão regular mínima é um problema completo do NP?
— Higgs
KKLLMMK⊆MK⊆MM∩L=∅M∩L=∅
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.
Compreendo que você tenha compartilhado isso. Eu não sabia sobre este papel. Obrigado. :)
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 ).
Se você está interessado em encontrar a menor DFA para o caso see especial: cstheory.stackexchange.com/questions/29119/...