<p>Yes, see for example here:</p>

<p>Johanna Högberg, Andreas Maletti, Jonathan May,
Backward and forward bisimulation minimization of tree automata,
Theoretical Computer Science 410(37), 2009, pp. 3539-3552,
<a href="https://doi.org/10.1016/j.tcs.2009.03.022" rel="nofollow noreferrer">https://doi.org/10.1016/j.tcs.2009.03.022</a></p>

CC BY-SA 4.0
2018-06-09T20:59:21.057Z
2018-06-09T20:59:21.057Z
Hermann Gruber
<p>DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states.
Equivalence is taken to be language equivalence.</p>

<p>Milner introduced the notion of bisimilarity, and in his book on the $\pi$-calculus, he motivates bisimilarity by first studying it as an equivalence relation on (states of) finite automata (interestingly non-deterministic ones).</p>

<p>So, has there been any study of the problem of minimizing an NFA with respect to this equivalence relation, bisimilarity (say of initial states), instead of equivalence of the recognized language?</p>

CC BY-SA 4.0
2018-06-04T07:25:40.370Z
I don't know about NFA, but it is a basic fact that any labelled transition system is bisimilar (even functionally) to a unique minimal system, and this can be computed in polynomial time.
Emil Jeřábek
CC BY-SA 4.0
2018-06-04T07:50:00.537Z
Thanks @EmilJeřábek. Do you have any pointer to an algorithm that computes such a minimal LTS in polynomial time?
Akram El-Korashy
CC BY-SA 4.0
2018-06-04T08:05:37.813Z
Do you know how to compute the largest bisimulation between LTS $A$ and $B$? Well then, given an LTS $A$, compute the largest bisimulation $\sim$ betwen $A$ and $A$; this will be an equivalence relation, and the quotient $A/{\sim}$ (with transitions defined in an obvious way) is the minimal LTS bisimilar to $A$.
Emil Jeřábek
<minimization><nfa><lts-simulations>
Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?
Akram El-Korashy
# Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

(Asked by: username_0 on 2018-06-03)

DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states.
Equivalence is taken to be language equivalence.

Milner introduced the notion of bisimilarity, and in his book on the $\pi$-calculus, he motivates bisimilarity by first studying it as an equivalence relation on (states of) finite automata (interestingly non-deterministic ones).

So, has there been any study of the problem of minimizing an NFA with respect to this equivalence relation, bisimilarity (say of initial states), instead of equivalence of the recognized language?

**Tags:** minimization, nfa, lts-simulations
> **Comments:**
> **username_1**: I don't know about NFA, but it is a basic fact that any labelled transition system is bisimilar (even functionally) to a unique minimal system, and this can be computed in polynomial time.  
> **username_0**: Thanks @EmilJeřábek. Do you have any pointer to an algorithm that computes such a minimal LTS in polynomial time?  
> **username_1**: Do you know how to compute the largest bisimulation between LTS $A$ and $B$? Well then, given an LTS $A$, compute the largest bisimulation $\sim$ betwen $A$ and $A$; this will be an equivalence relation, and the quotient $A/{\sim}$ (with transitions defined in an obvious way) is the minimal LTS bisimilar to $A$.  

---

## 1 answers

### Answer by username_2 on 2018-06-09. Score: 2

Yes, see for example here:

Johanna Högberg, Andreas Maletti, Jonathan May,
Backward and forward bisimulation minimization of tree automata,
Theoretical Computer Science 410(37), 2009, pp. 3539-3552,
<https://doi.org/10.1016/j.tcs.2009.03.022>


---

