Residual finite state automata (RFSAs, defined in [DLT02]) are NFAs that have some nice features in common with DFAs. In particular, there is always a canonical minimum sized RFSA for every regular language, and the language recognized by each state in the RFSA is a residual, just like in a DFA. However, whereas a minimum DFAs states form a bijection with all residuals, the canonical RFSAs states are in bijection with the prime residuals; there can be exponentially fewer of these, so RFSAs can be much more compact than DFAs for representing regular languages.
However, I can't tell if there is an efficient algorithm for minimizing RFSAs or if there is a hardness result. What is the complexity of minimizing RFSAs?
From browsing [BBCF10], it doesn't seem like this is common knowledge. On the one hand, I expect this to be difficult because a lot of simple questions about RFSAs like "is this NFA an RFSA?" are very hard, PSPACE-complete in this case. On the other hand, [BHKL09] shows that canonical RFSAs are efficiently learnable in Angluin's minimally-adequate teacher model [A87], and efficiently learning a minimum RFSA and minimizing RFSAs seems like it should be of equal difficulty. However, as far as I can tell [BHKL09]'s algorithm does not imply a minimization algorithm, since the size of counter-examples is not bounded and it is not clear how to efficiently test RFSAs for equality to simulate the counter-example oracle. Testing two NFAs for equality is PSPACE-complete, for example.
[A87] Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75: 87-106
[BBCF10] Berstel, J., Boasson, L., Carton, O., & Fagnot, I. (2010). Minimization of automata. arXiv:1010.5318.
[BHKL09] Bollig, B., Habermehl, P., Kern, C., & Leucker, M. (2009). Angluin-Style Learning of NFA. In IJCAI, 9: 1004-1009.
[DLT02] Denis, F., Lemay, A., & Terlutte, A. (2002). Residual finite state automata. Fundamenta Informaticae, 51(4): 339-368.