4
$\begingroup$

(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.)

I'm currently working on a project to do with regular overapproximations for context free languages. For this purpose, I need to implement stuff that requires me to represent regular languages in a minimized form, intersect them, complement them, etc. - i.e. everything that's easy and quick to do with DFAs. However, I'm having a hard time finding still-maintained libraries for DFAs in C++. I could find libfa which does everything quite nicely, but that's as far as I've gotten. Grail hasn't been maintained in 15+ years and the download link is dead. FAdo seemed interesting initially, but it's in Python and I can't determine whether there's a way to use it as a C++ library, or whether it offers the functionality I mentioned above (the Docs are a bit slim).

Do you know of C(++) libraries for DFAs that offer minimization, intersection and complementation that are free for academic use? I'd like to have at least one alternative to libfa that I can use.

$\endgroup$
  • $\begingroup$ @Juho Thanks! Turns out my advisor is perfectly happy with just using one library, so I'll probably stick with libfa because it offers stuff for basically anything you might want to do with finite automata. $\endgroup$ – G. Bach Jan 15 '14 at 19:59
  • $\begingroup$ SO also has an allergy to people asking for software recommendations. As a result there's now a special site for that softwarerecs.stackexchange.com . But I think questions about highly specialized software (like this one) are better asked on sites where the "hardcore" domain knowledge resides. $\endgroup$ – Fizz Feb 25 '15 at 10:46
  • 1
    $\begingroup$ Note that for weighted automata there's OpenFST. But I suspect it would be kludgy/inefficient to use it for non-weighted automata. The same goes for carmel. $\endgroup$ – Fizz Feb 25 '15 at 11:11
2
$\begingroup$

I don't know of a full blown library, but based on [1] there is a really fast practical C++ implementation available from the author's homepage here.


[1] Valmari, Antti. "Fast brief practical DFA minimization." Information Processing Letters 112.6 (2012): 213-217.

$\endgroup$
  • $\begingroup$ Yeah, minimization is a much more common problem [encountered in practice] than the others mentioned in the question. $\endgroup$ – Fizz Feb 25 '15 at 10:48

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.