search

caleb531 / automata

A Python library for simulating finite automata, pushdown automata, and Turing machines
https://caleb531.github.io/automata/
MIT License
349 stars 64 forks source link

Valmari's Algorithm for Minimizing Partial DFAs #161

Open eliotwrobson opened 1 year ago

eliotwrobson commented 1 year ago

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 https://github.com/caleb531/automata/issues/126#issuecomment-1595611839

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 commented 1 year ago

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 commented 1 year ago

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

sracha4355 commented 1 year ago

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

eliotwrobson commented 1 year ago

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 commented 11 months ago

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

eliotwrobson commented 11 months ago

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

sracha4355 commented 11 months ago

@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 commented 11 months ago

@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 commented 11 months ago

@EduardoGoulart1 you can go ahead and work on it!

eliotwrobson commented 10 months ago

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.