Valmari's Algorithm for Minimizing Partial DFAs

[eliotwrobson]

https://arxiv.org/abs/0802.2826

This paper is a more abstract description of Valmari's algorithm for minimizing partial DFAs. It should be easier to read and implement than the paper with the C++ code. Once we get a first iteration of partial DFA support, it would be awesome if we could add this algorithm as the default for minimizing partial DFAs (should be much faster over large alphabets).

Originally posted by @eliotwrobson in #126 (comment)

Note this should only be done after #159.

EDIT: We have closed 159 as not being planned, so we can go ahead with this issue if anyone wants to attempt it. Should give substantial performance improvements for minimizing partial DFAs.

[sracha4355]

Hey I could give it a shot. Are you guys under any time constraint to get this done? Asking because I will be busy with school.

[eliotwrobson]

@sracha4355 that would be awesome! No time constraint, and feel free to put up a draft PR if you ever want any feedback.

[sracha4355]

Any tips on understanding the codebase, I am not an active user. I was just looking for cool projects to contribute to!

[eliotwrobson]

This is actually a fairly good task for someone who is not familiar, as it only involves implementing a single algorithm. The main thing is to take a look at the _minify function in the DFA class (see here), as the new algorithm will be replacing the function there. The other main thing is to understand is how DFAs are represented in the library, and for that I think it should be sufficient to take a look at some of the examples in the documentation: https://github.com/caleb531/automata/blob/main/docs/fa/examples.md

Basically, the transitions are represented with a nested dictionary, and that is the main structure this algorithm will be operating on.

[EduardoGoulart1]

@sracha4355 are you still looking into it? Otherwise I could give it a try in the next days

[eliotwrobson]

@EduardoGoulart1 this issue has been open for a while, so if you have the time I'd say go ahead and start working!

[sracha4355]

@EduardoGoulart1 Hey, I was planning on tackling this issue once school ends, which is in 2 weeks. But if you would like to work on this, go ahead! If you want to collaborate let me know.

[EduardoGoulart1]

@EduardoGoulart1 Hey, I was planning on tackling this issue once school ends, which is in 2 weeks. But if you would like to work on this, go ahead! If you want to collaborate let me know.

@sracha4355 Could you please update us here when you start to work on it? I can wait until the turn of the year. But it would be good to have it merged rather soonish

[sracha4355]

@EduardoGoulart1 you can go ahead and work on it!

[eliotwrobson]

Don't worry too much about doing overlapping work. I think this algorithm is pretty tricky to implement correctly and might even take a few attempts to get right.