4
$\begingroup$

I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time algorithm.

What I mean by this is an algorithm which may run in exponential time in the worst cases, but which uses some sort of heuristic to speed up the process, albiet not enough to make it exponential.

I'm only using this to try to get a better idea of what the minimal NFAs of certain languages look like. I'm not using it in any production code, so it doesn't need to be blazingly fast.

For example, the Antichains algorithm for NFAs does equivalence testing which is usually fast but sometimes has exponential explosion. I'm looking for something similar, but for minimization.

Note that I'm NOT looking for things like equivalences, etc. which run efficiently but don't produce a minimal NFA.

Bonus points to anyone who find one with an implementation, and quadruple bonus points if it's in Prolog or Python. If the tool I'm looking for doesn't exist, I'd be happy if anyone gave any old implementation of NFA minimization.

Improve this question
$\endgroup$
1
  • $\begingroup$ this is basically a question on average case complexity. it depends on the "distribution" of inputs. hence an empirical study/survey would be useful. unf there seems to be little empirical study in the area. also, the question seems not so clear on whether an approximation or an exact solution is required. heuristics almost always are associated with approximations. $\endgroup$
    – vzn
    Commented Sep 25, 2013 at 15:12

3 Answers 3

Reset to default
3
$\begingroup$

SAT solvers have been pretty good at this. See [1] for more; the method produces a minimal automaton in almost all cases. Following some references, Tsyganov [2] combined the Kameda-Weiner with local search methods.

I don't know if there are readily available implementations out there, but at least [1] describes the reduction to SAT. One can then use any available SAT solver.

[1] Geldenhuys, Jaco, Brink Van Der Merwe, and Lynette Van Zijl. "Reducing nondeterministic finite automata with SAT solvers." Finite-State Methods and Natural Language Processing. Springer Berlin Heidelberg, 2010. 81-92.

[2] Tsyganov, Andrey V. "Local Search Heuristics for NFA State Minimization Problem." International Journal of Communications, Network and System Sciences 5 (2012).

Improve this answer
$\endgroup$
2
$\begingroup$

I've implemented the Kameda-Weiner algorithm; see the source on Github. Note, however, that a minimal NFA is not generally unique (there may be multiple solutions), so I don't know if I'd say it's "exact" as in your question.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm not worried about it being unique, I'm worried about it being exact in the sense that there is 0 probability that the output is not one of the minimal NFAs for the given regular language. $\endgroup$
    – Joey Eremondi
    Commented Aug 25, 2013 at 5:44
  • 1
    $\begingroup$ In that case, it is exact. It will always give a minimal NFA. $\endgroup$
    – Brent
    Commented Aug 25, 2013 at 15:53
  • $\begingroup$ Source code alone is not considered an answer on this site. What is the idea of the algorithm? Is it sometimes fast? Can you quantify this? $\endgroup$
    – Raphael
    Commented Aug 26, 2013 at 7:20
  • $\begingroup$ I guess I should have just made a comment then. ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1671587 $\endgroup$
    – Brent
    Commented Aug 26, 2013 at 14:32
  • $\begingroup$ if its an implementation of a standard or published algorithm (which it is, as brent stated in answer), seems like reasonable/fair answer. as for jmites defn of "exact" in the above comment, it doesnt make sense to me, can someone explain it? it seems opposite ie think that an exact solution would be one of the minimal NFAs of the language acc to some defn of "minimal" (eg # of states)... $\endgroup$
    – vzn
    Commented Sep 25, 2013 at 15:15
1
$\begingroup$

The title of the question insists on an exact algorithm, but then you say it would "use some sort of heuristic to speed up the process". Generally, heuristics are associated with inexact solutions. This following paper is more focused on an inexact solution i.e. heuristics, but has some discussion and further references on the general minimization problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For heuristics, what I mean is, say there are several paths to search, the heuristic would try to speed up the search by guessing which path we should search first. For example, A* is exact, but beat's Dijkstra's in terms of speed because of a heuristic. $\endgroup$
    – Joey Eremondi
    Commented Sep 26, 2013 at 3:22
  • $\begingroup$ generally a heuristic can only improve performance in average case for a particular input distribution, and then other distributions exist that push heuristics away from that improved performance. (in other words, like greedy algorithms seeking out local optima.) $\endgroup$
    – vzn
    Commented Sep 26, 2013 at 21:23

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.