4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 4, 2018 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
    Commented Jun 4, 2018 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
    Commented Jun 4, 2018 at 8:05

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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