calcular el NFA mínimo para un DFA

Hace muchos años escuché que calcular el mínimo NFA (autómata finito no determinista) de un DFA (determinista) era una pregunta abierta, en oposición a la dirección inversa que se conoce desde hace décadas y está bien investigada con un eficiente ( n lg n ) algoritmo. ¿Alguien ha ideado un algoritmo?$O(n \lg n)$

Una búsqueda rápida me dio este documento que demuestra que definitivamente es un problema difícil. Aparentemente, no se da ningún algoritmo.

[1] Los problemas mínimos de la NFA son difíciles / Tao Jiang y B. Ravikumar

La siguiente pregunta me recordó este problema en el sitio CS.SE para el cual un algoritmo de minimización DFA-> NFA estaría estrechamente relacionado. La siguiente pregunta me parece a nivel de investigación. Sugerí migrarlo a TCS y escribí una respuesta sugiriendo un ataque estadístico / empírico.

[2] ¿Cuáles son las condiciones para que un NFA para su DFA equivalente tenga un tamaño máximo?

Este es realmente un problema obstinado y bien estudiado. En cuanto a los resultados positivos, un algoritmo exacto de Kameda y Weiner, un enfoque heurístico de Polák y un enfoque reciente con solucionadores SAT de Geldenhuys et al. se me ocurre. Pero parece haber resultados mucho más negativos que descartan otros enfoques posibles (por ejemplo, algoritmos de aproximación, casos especiales, modelos menos potentes de NFA, ...) Consulte a continuación algunas referencias.

T. Kameda y P. Weiner. Sobre la minimización del estado de autómatas finitos no deterministas. IEEE Transactions on Computers, C-19 (7): 617–627, 1970.

A. Malcher. Minimizar autómatas finitos es computacionalmente difícil. Theoretical Computer Science 327: 375-390, 2004.

L. Polák. Minimalizaciones de NFA utilizando el autómata universal. Revista Internacional de Fundaciones de Ciencias de la Computación, 16 (5): 999-1010, 2005.

G. Gramlich y G. Schnitger. Minimización de NFA y expresiones regulares. Simposio sobre aspectos teóricos de la informática (STACS 2005), LNCS 3404, pp. 399–411.

H. Gruber y M. Holzer. Inaproximidad del estado no determinista y la complejidad de la transición suponiendo P <> NP. Desarrollos en teoría del lenguaje (DLT 2007), LNCS 4588, pp. 205–216.

H. Gruber y M. Holzer. Complejidad computacional de la minimización de NFA para lenguajes finitos y unarios. Teoría y aplicaciones de lenguaje y autómatas (LATA 2007), págs. 261–272.

H. Björklund y W. Martens. La frontera de trazabilidad para la minimización de NFA. Coloquio internacional sobre autómatas, idiomas y programación (ICALP 2008), LNCS 5126, págs. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Reducción de autómatas finitos no deterministas con solucionadores SAT. Métodos de estado finito y procesamiento del lenguaje natural (FSMNLP 2009), LNCS 6062, 81–92.

EDITAR (8 de junio de 2015)

Actualización: El siguiente documento presenta un algoritmo heurístico para reducir el tamaño de los autómatas no deterministas de Büchi, junto con experimentos con autómatas aleatorios. Como afirman en la conclusión, su método se aplica también a los NFA: "Si bien presentamos nuestros métodos en el contexto de los autómatas de Büchi, la mayoría de ellos trivialmente se trasladan al caso más simple de autómatas sobre palabras finitas".

Richard Mayr, Lorenzo Clemente. Minimización avanzada de autómatas. POPL 2013. Informe técnico ampliado EDI-INF-RR-1414.

Su herramienta de línea de comandos Reduce v1.2 se puede invocar con la opción "-finite" para reducir un NFA determinado. La implementación es de código abierto y se publica bajo la Licencia Pública General de GNU.