Separando listas de palavras

10

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.ABAB

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.

MRC
fonte
2
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"
Michael Wehar
klog(n)log(log(n))
11
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.
Michael Wehar

Respostas:

8

KLMKMML=

KLM

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.

Boson
fonte
Compreendo que você tenha compartilhado isso. Eu não sabia sobre este papel. Obrigado. :)
Michael Wehar
3

AB

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 ).

RB
fonte
Se você está interessado em encontrar a menor DFA para o caso see especial: cstheory.stackexchange.com/questions/29119/...
Michael Wehar