computing the minimal NFA for a DFA Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?
This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special cases, less powerful models of NFAs, ...) See below for some references.

T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617–627, 1970.

A. Malcher. Minimizing finite automata is computationally hard. Theoretical Computer Science 327:375-390, 2004.

L. Polák. Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science, 16(5):999–1010, 2005.

G. Gramlich and G. Schnitger. Minimizing NFAs and Regular Expressions. Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 399–411. 

H. Gruber and M. Holzer. Inapproximability of nondeterministic state
and transition complexity assuming P &lt;> NP. Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205–216.

H. Gruber and M. Holzer. Computational complexity of NFA minimization for finite and unary languages. Language and Automata Theory and Applications (LATA 2007), pp. 261–272.

H. Björklund and W. Martens. The tractability frontier for NFA minimization. International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5126, pp. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Reducing Nondeterministic Finite Automata with SAT Solvers. Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, 81–92.

EDIT (June 8, 2015)

Update: The following paper presents a heuristic algorithm for reducing the size of nondeterministic Büchi automata, along with experiments on random automata. As they state in the conclusion, their method applies to NFAs as well: "While we presented our methods in the context of Büchi automata, most of them trivially carry over to the simpler case of automata over finite words."

Richard Mayr, Lorenzo Clemente. Advanced Automata Minimization. POPL 2013. Extended Technical Report EDI-INF-RR-1414.

Their command-line tool Reduce v1.2 can be invoked with the option "-finite" for reducing a given NFA. The implementation is open source and released under the GNU General Public License.