<p>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".</p>

<p>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^*$. </p>

<p>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 <em>a fortiori</em> 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^*$. </p>

<p>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$.</p>

<p>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.</p>

<p>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. </p>

<p>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. </p>

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

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2016-11-26T23:17:05.800Z
2016-11-26T23:17:05.800Z
Hermann Gruber
<p><a href="http://egtheory.wordpress.com/2013/10/01/nfa-limits/#rfsa" rel="nofollow noreferrer">Residual finite state automata</a> (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.</p>
<p>However, I can't tell if there is an efficient algorithm for minimizing RFSAs or if there is a hardness result. <strong>What is the complexity of minimizing RFSAs?</strong></p>
<p>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 &quot;is this NFA an RFSA?&quot; 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. <a href="https://cs.stackexchange.com/a/9955/55">Testing two NFAs for equality is PSPACE-complete</a>, for example.</p>
<h3>References</h3>
<p>[A87] Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75: 87-106</p>
<p>[BBCF10] Berstel, J., Boasson, L., Carton, O., &amp; Fagnot, I. (2010). Minimization of automata. <a href="http://arxiv.org/abs/1010.5318" rel="nofollow noreferrer">arXiv:1010.5318</a>.</p>
<p>[BHKL09] Bollig, B., Habermehl, P., Kern, C., &amp; Leucker, M. (2009). Angluin-Style Learning of NFA. In <em>IJCAI</em>, 9: 1004-1009.</p>
<p>[DLT02] Denis, F., Lemay, A., &amp; Terlutte, A. (2002). Residual finite state automata. <em>Fundamenta Informaticae</em>, 51(4): 339-368.</p>

CC BY-SA 3.0
2013-10-03T09:23:10.057Z
RFSAs aren't defined syntatically (like DFAs or NFAs) but semantically as a subclass of NFAs that satisfy a certain hard to decide condition. So I am not sure that the question of minimizing a RFSA is really meaningful. Could you be more specific about the problem? Are you given a NFA that is known to be a RFSA? Are you provided with evidence that it is in fact a RFSA such as a string w for each state q such that the language generated by q is the residual $w^{-1}L$?
Alexander Clark
CC BY-SA 3.0
2013-10-03T15:57:52.043Z
I am interested in either/all of the following options: (1) you are given a DFA (all minimum DFAs are RFSAs) and I want you to return a minimal RFSA that recognizes the same language (or some decision variant like: does one exist of size less than k where k is also given as input). (2) you are given an NFA (that might or might not be small, and might or might not be an RFSA) and asked to generate the minimal RFSA; in this case complexity is obvious measured in the size of input+output. I am even interested in (3) you are promised (but no certificate given) that an NFA is RFSA, is it minimal?
Artem Kaznatcheev
<cc.complexity-theory><ds.algorithms><automata-theory><lg.learning><minimization>
Minimizing residual finite state automata
Artem Kaznatcheev
# Minimizing residual finite state automata

(Asked by: username_0 on 2013-10-02)

[Residual finite state automata](http://egtheory.wordpress.com/2013/10/01/nfa-limits/#rfsa) (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](https://cs.stackexchange.com/a/9955/55), 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](http://arxiv.org/abs/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.

**Tags:** cc.complexity-theory, ds.algorithms, automata-theory, lg.learning, minimization

> **Comments:**
> **username_1**: RFSAs aren't defined syntatically (like DFAs or NFAs) but semantically as a subclass of NFAs that satisfy a certain hard to decide condition. So I am not sure that the question of minimizing a RFSA is really meaningful. Could you be more specific about the problem? Are you given a NFA that is known to be a RFSA? Are you provided with evidence that it is in fact a RFSA such as a string w for each state q such that the language generated by q is the residual $w^{-1}L$?  
> **username_0**: I am interested in either/all of the following options: (1) you are given a DFA (all minimum DFAs are RFSAs) and I want you to return a minimal RFSA that recognizes the same language (or some decision variant like: does one exist of size less than k where k is also given as input). (2) you are given an NFA (that might or might not be small, and might or might not be an RFSA) and asked to generate the minimal RFSA; in this case complexity is obvious measured in the size of input+output. I am even interested in (3) you are promised (but no certificate given) that an NFA is RFSA, is it minimal?  

---

## 1 answers

### Answer by username_2 on 2016-11-26. Score: 4

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.

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

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


---

