Minimizing residual finite state automata

Question

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.

References

[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.

Answer 1

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem obtained from the above if we replace "NFA" with "residual finite state automaton".

Jiang and Ravikumar showed that the "DFA $\to$ NFA" problem is PSPACE-complete by a reduction from the "DFA union universality" problem. The latter problem has given a list of DFAs $A_1,A_2,\ldots,A_n$, and asks if $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

Their reduction goes by defining a language $L$ from these DFAs and a suitable integer $k$, such that a DFA accepting $L$ can be constructed in time polynomial in the size of the DFAs $A_i$. Then they show that every NFA (thus a fortiori every RFSA) accepting $L$ needs at least $k$ states in case $\bigcup_{i=1}^nL(A_i)$ is universal and at least $k+1$ states otherwise. Then they construct a $k$-state NFA $N$, which accepts $L$ iff $\bigcup_{i=1}^nL(A_i) = \Sigma^*$.

This proof was reconsidered later by Gruber and Holzer (Developments in Language Theory '06). They use the same reduction to show a slightly different result, which concerns the computational complexity of lower bound techniques for NFAs: An (extended) fooling set for a regular language $R$ is a set $S$ of word pairs $(x_i,y_i)$, such that for each $i$ holds $x_iy_i\in L$ but for all $i\neq j$ holds: $x_iy_j \notin R$ or $x_jy_i\notin R$.

For the above reduction, they show that there is an extended fooling set $S$ of size $k$ in case $\bigcup_{i=1}^nL(A_i)$ is universal. By inspecting the proof by Gruber and Holzer, one readily notes that each "left word" $x_i$ in the set $S$ is such that the NFA $N$ mentioned above can go from the initial state to only a single state $q_i$ on reading $x_i$. That is, the language accepted from state $q$ equals $x_i^{-1}L$, and thus $N$ is a residual finite state automaton.

If the above reasoning contains no mistakes, this yields a reduction from the DFA union universality problem to the "DFA $\to$ RFSA" problem, and thus it is PSPACE-hard. Membership in PSPACE follows along the same lines as for the DFA $\to$ NFA problem, so the "DFA $\to$ RFSA" problem is PSPACE-complete. Being more general but still in PSPACE, the "NFA $\to$ RFSA" problem is PSPACE-complete as well.

For those who want to reconstruct the above argument (please don't take it for granted, my writeup was a bit hasty), I recommend reading the proof of Theorem 15 in the ECCC report cited below. Especially, Figure 5 on page 18 depicts the automaton $N$ which I claim to be a RFSA.

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22(6):1117–1141, December 1993.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity Is Hard. In Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of Lecture Notes in Computer Science, pages 363--374. Springer, June 2006.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Technical Report ECCC TR06-027, Electronic Colloquium on Computational Complexity, 2006.