Optimize the removal of epsilon symbols from an automaton

VeriFIT / mata

A fast and simple automata library

MIT License

22 stars 13 forks source link

Optimize the removal of epsilon symbols from an automaton #240

Open Adda0 opened 1 year ago

Adda0 commented 1 year ago

We need to optimize the algorithm for the removal of epsilon symbols from an automaton. To achieve that, we need to work on optimizing:

[ ] Epsilon closure, whose current implementation is expensive. We need to optimize it substantially.
[ ] Mata::Nfa::remove_epsilon() implementation.

vhavlena commented 1 year ago

I am currently working on it. It seems that the main inefficiency follows from the epsilon-closure computation. It seems that the best (performance-wise) way is to project the transition relation only to epsilons and then to use Purdom's or Floyd-Warshal's algorithm.