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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 4 '18 at 7:25
  • 1
    $\begingroup$ Thanks @EmilJeřábek. Do you have any pointer to an algorithm that computes such a minimal LTS in polynomial time? $\endgroup$ – Akram El-Korashy Jun 4 '18 at 7:50
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Jun 4 '18 at 8:05

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.