Algoritmo de interseção do DFA para casos especiais

9

Estou interessado em algoritmos eficientes para interseção do DFA em casos especiais. Ou seja, quando os DFAs se cruzam, obedecem a uma certa estrutura e / ou operam com um alfabeto limitado. Existe alguma fonte onde eu possa encontrar algoritmos nesses casos?

Para não tornar a pergunta muito ampla, a seguinte estrutura é de particular interesse: todos os DFAs a cruzar operam no alfabeto binário (0 | 1), eles também podem usar símbolos de não se importar. Além disso, todos os estados têm apenas uma transição, exceto no máximo K estados especiais, que possuem apenas duas transições (e essas transições são sempre 0 ou 1, mas não se importam). K é um número inteiro menor que 10 para fins práticos. Além disso, eles têm um único estado de aceitação. Além disso, sabe-se que a interseção SEMPRE é um DFA na forma de "faixa", ou seja, sem ramificações, como na imagem a seguir:

insira a descrição da imagem aqui

EDIT: Talvez a descrição da restrição nos DFAs de entrada não esteja muito clara. Vou tentar melhorá-lo neste parágrafo. Você tem como entrada T DFAs. Cada um desses DFAs opera apenas no alfabeto binário. Cada um deles tem no máximo N estados. Para cada DFA, cada um de seus estados é um dos seguintes:

1) o estado de aceitação (é apenas um e não há transição para outro estado)

2) um estado com duas transições (0 e 1) para o mesmo estado de destino (a maioria dos estados é desse tipo)

3) um estado com duas transições (0 e 1) para diferentes estados-alvo (no máximo K desse tipo)

É garantido que haja apenas um estado de aceitação e que haja no máximo K estados do tipo (3) em cada DFA de entrada. Também é garantido que a intersecção DFA de todos os AFDs de entrada é uma "tira" (como descrito acima), de tamanho menor do que N .

EDIT2: Algumas restrições adicionais, conforme solicitado pela DW nos comentários:

  • Os DFAs de entrada são DAGs.
  • Os DFAs de entrada são "nivelados", seguindo a definição de DW nos comentários. Ou seja, você pode atribuir números inteiros diferentes a todos os estados, de forma que todas as transições passem de um número inteiro u para um número inteiro v , de modo que u + 1 = v .
  • O número de estados de aceitação para cada entrada DFA, não exceda K .

Alguma ideia? Obrigado.

ale64bit
fonte
Como exatamente você modela "não se importa"? Parece tornar os autômatos não determinísticos, de certa forma.
Shaull
@ Shaull Por que deveria tornar o autômato não determinístico. Isso pode acontecer apenas se houver outra transição do mesmo estado, explicitamente excluída.
babou
11
O que é a DFA in form of "strip", i.e., no branches? Você tem algum motivo específico para acreditar que alguém pode fazer melhor do que o algoritmo padrão no seu caso?
babou
11
Oi. Computar a interseção real seria ótimo, pois simplificaria muitas coisas, mas decidir o vazio também seria útil.
ale64bit
11
acabei de ler um novo artigo sobre gráficos de interseção , alguma dessa teoria poderia ser relevante? você poderia expandir a sua aplicação mencionada no seu comentário no Chat Teórico da Ciência da Computação ? e convide outras pessoas para continuar a discussão lá.
vzn 6/01/2015

Respostas:

9

Sim , existem alguns casos do problema de inserção de não-vazio do DFA que estão dentro de P. Minha tese de mestrado é dedicada a essa questão, mas infelizmente é em francês. No entanto, a maioria dos resultados apareceu aqui em .[2]

Quando o alfabeto é unário, o problema é L-completo quando cada DFA possui no máximo dois estados finais e NP-completo, caso contrário. A maioria dos outros casos são restrições aos monóides de transição dos autômatos. Por exemplo, para monoides de transição de grupo abeliano, o problema está no quando cada DFA tem no máximo um estado final e NP-completo caso contrário; para monoides de transição de dois grupos elementares, o problema é L-completo quando cada DFA possui no máximo dois estados finais e NP-completo, caso contrário.NC3


[1 1]{0 0,1 1}vocêvvocêv

  1. L-completo para um estado final em cada DFA,
  2. NL completo para dois estados finais em cada DFA e
  3. NP-completo para três ou mais estados finais em cada DFA.

KK=2

Portanto, não , não acho que exista um algoritmo eficiente para o seu problema.

[3]


x2x3x5

gadget de redução

Observe que os autômatos são árvores (e, portanto, DAGs), são nivelados e têm três estados finais. Na verdade, os três estados finais podem ser mesclados em um único, se um estiver satisfeito com os DAGs. Além disso, apenas dois estados têm duas transições de saída (distintas).

  1. Michael Blondin. Complexidade do problema de impressora de automação, M.Sc. tese, Universidade de Montreal, 2012.
  2. Michael Blondin, Andreas Krebs e Pierre McKenzie. A complexidade da interseção de autômatos finitos com poucos estados finais, Complexidade computacional (CC), 2014.
  3. Michael Wehar. Resultados da dureza para o não vazio de interseção. ICALP, 2014.
Michael Blondin
fonte
2
Muito obrigado! Eu aceito sua resposta. A questão se originou de alguns testes práticos em que tudo se reduziu após várias etapas na interseção das soluções de muitos DFA com essas características particulares. No entanto, observamos que, embora no final nós obtivéssemos um DFA simples, o processo nunca terminou por causa dos DFAs intermediários (enquanto se cruzavam sequencialmente) crescendo rapidamente em um número exponencial de estados. Assim, a questão de como obter a resposta sem passar pelos passos "ingênuos" intermediários.
ale64bit
11
Muito obrigado (e desculpe-me por não estar claro, estou abaixo de iniciante nesta área). Agora há algo que eu não entendo. Você menciona que "em forma de árvore" significa "caminho exclusivo da raiz para todos os outros nós". Mas, por exemplo, na imagem que você postou na edição, isso não seria uma árvore (a menos que você conte as transições 0/1 como um único rótulo)?
ale64bit
11
Você está certo, mas meu entendimento era que você permite transições "não me importo". Não é o caso?
Michael Blondin
2
Olá Michael. Obrigado pela resposta agradável. Eu espero que tudo esteja bem. :)
Michael Wehar
2
@ MichaelWehar No caso de você corrigir k e c, você menciona que pode resolver o problema "rapidamente". Mas você não menciona a complexidade do tempo, apenas a complexidade do espaço. O que exatamente "rapidamente" significa nesse contexto?
ale64bit