patternMinor
C(++) library for DFAs - free for academic use
Viewed 0 times
freedfasforlibraryuseacademic
Problem
(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.
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.
Solution
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.
[1] Valmari, Antti. "Fast brief practical DFA minimization." Information Processing Letters 112.6 (2012): 213-217.
Context
StackExchange Computer Science Q#19664, answer score: 2
Revisions (0)
No revisions yet.