computando o NFA mínimo para um DFA

Há muitos anos, ouvi dizer que calcular o mínimo de AFN (autômato finito não determinístico) a partir de um AFD (determinístico) era uma questão em aberto, em oposição à direção vice-versa conhecida há décadas e que é bem pesquisada com um eficiente algoritmo. Alguém criou um algoritmo? $O(n \lg n)$

Uma pesquisa rápida me deu este artigo que prova que é definitivamente um problema difícil. Aparentemente, nenhum algoritmo é dado.

[1] Problemas mínimos de NFA são difíceis / Tao Jiang e B. Ravikumar

Lembrei-me desse problema pela seguinte pergunta no site CS.SE, para a qual um algoritmo de minimização DFA-> NFA estaria intimamente relacionado. Esta pergunta a seguir me parece estar em nível de pesquisa. Sugeri migrar para o TCS e escrevi uma resposta sugerindo um ataque estatístico / empírico.

[2] Quais são as condições para um NFA para seu DFA equivalente ter o tamanho máximo?

ds.algorithms reference-request fl.formal-languages automata-theory optimization vzn
fonte

O artigo que você cita mostra a integridade do PSPACE. Em particular, o problema está no PSPACE, o que sugere imediatamente um algoritmo. Que tipo de algoritmo você está procurando? Práticas e / ou heurísticas? Limites mais conhecidos no expoente do tempo de execução? Algo mais?

Joshua Grochow 23/03

Não é tão incomum, na verdade. Antes que o problema fosse conhecido como completo no PSPACE, todas as tentativas de desenvolver algoritmos eficientes falharam, tão pouco foi publicado. Depois que o problema era conhecido como completo no PSPACE, ninguém tentou desenvolver algoritmos eficientes, porque eles sabiam que iriam falhar, então menos ainda foi publicado.

Jeffε

(1) O que significa “direção vice-versa conhecida há décadas e bem pesquisada com um algoritmo O (n lg n) eficiente”? O DFA mínimo para um NFA com n estados pode ter tamanho exponencial em n, portanto, seria necessária alguma codificação de saída não trivial. (2) Não existe "o" mínimo NFA para um determinado idioma regular. Compare isso com a existência do DFA mínimo.

Tsuyoshi Ito

JEFFE você tem um bom argumento, mas tenho certeza de que existem muitos problemas completos no Pspace que ainda possuem algoritmos sofisticados que tiram proveito da estrutura do problema, além de apenas enumerar todas as soluções possíveis, verdade? admita, não consigo pensar em nada da minha cabeça. Talvez você possa? acho que isso seria outra pergunta interessante a ser feita aqui.

vzn

@vzn: existem dois não-isomórficas NFAs 2 de estado para a linguagem de

a^{+}

$a^+$

mikero

Respostas:

Este é realmente um problema teimoso - e bem estudado -. Em relação aos resultados positivos, um algoritmo exato de Kameda e Weiner, uma abordagem heurística de Polák e uma abordagem recente usando solucionadores SAT de Geldenhuys et al. vêm à mente. Mas parece haver resultados muito mais negativos descartando outras abordagens possíveis (por exemplo, algoritmos de aproximação, casos especiais, modelos menos poderosos de NFAs, ...) Veja abaixo algumas referências.

T. Kameda e P. Weiner. Na minimização de estado de autômatos finitos não determinísticos. IEEE Transactions on Computers, C-19 (7): 617-627, 1970.

A. Malcher. Minimizar autômatos finitos é computacionalmente difícil. Teórico Computer Science 327: 375-390, 2004.

L. Polák. Minimalizações de NFA usando o autômato universal. International Journal of Foundations of Computer Science, 16 (5): 999-1010, 2005.

G. Gramlich e G. Schnitger. Minimizando NFAs e expressões regulares. Simpósio sobre Aspectos Teóricos da Ciência da Computação (STACS 2005), LNCS 3404, pp. 399–411.

H. Gruber e M. Holzer. Inaproximabilidade do estado não determinístico e da complexidade da transição, assumindo P <> NP.Desenvolvimentos em teoria da linguagem (DLT 2007), LNCS 4588, pp. 205-216.

H. Gruber e M. Holzer. Complexidade computacional da minimização de NFA para linguagens finitas e unárias.Teoria e aplicações de idiomas e autômatos (LATA 2007), pp. 261–272.

H. Björklund e W. Martens. A fronteira de tratabilidade para a minimização de NFA.Colóquio Internacional sobre Autômatos, Idiomas e Programação (ICALP 2008), LNCS 5126, pp. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Reduzindo autômatos finitos não determinísticos com solventes SAT.Métodos de estado finito e processamento de linguagem natural (FSMNLP 2009), LNCS 6062, 81–92.

EDIT (8 de junho de 2015)

Atualização: O artigo a seguir apresenta um algoritmo heurístico para reduzir o tamanho de autômatos não determinísticos de Büchi, juntamente com experimentos em autômatos aleatórios. Como afirmam na conclusão, o método deles também se aplica aos NFAs: "Embora apresentemos nossos métodos no contexto dos autômatos Büchi, a maioria deles é trivialmente transferida para o caso mais simples de autômato com palavras finitas".

Richard Mayr, Lorenzo Clemente. Minimização Avançada de Autômatos. POPL 2013. Relatório Técnico Ampliado EDI-INF-RR-1414.

A ferramenta de linha de comando Reduce v1.2 pode ser chamada com a opção "-finite" para reduzir um determinado NFA. A implementação é de código aberto e liberada sob a GNU General Public License.

Hermann Gruber
fonte

Você sabe se existem implementações de código-fonte aberto?

jmite

Olá Hermann, muito obrigado por todas as informações! Eu sei que, dado um NFA, é difícil encontrar o menor NFA equivalente. Mas, o que acontece com o seguinte: Dado um DFA, encontre o menor NFA equivalente. Isso é difícil? Quão difícil?

Michael Wehar

Desculpe, eu vejo agora! O primeiro artigo listado trata disso: springerlink.com/content/y61724u571v487x5 Além disso, outro artigo que você listou aborda isso para idiomas regulares finitos: hermann-gruber.com/data/lata07-final.pdf Obrigado por esclarecer isso para mim! :)

Michael Wehar