You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
After the work done on developing the IncrementalAutomatonMinimiser, it has become clear that closer integration with Automaton would be very helpful. See #19 for more.
Therefore, this issue proposes to rework Automaton in order to ensure all operations are incremental and do not do work proportional to the number of states. To make this happen requires:
Maintaining parent pointers for all states. This is necessary for all incremental algorithms and, in particular, enables incremental minimisation and compaction.
Resolving the issues of dangling cycles. That is, after a rewrite a set of states forming a cycle may not be garbage collected. Since the automaton is rooted, we can consider least common ancestors as one alternative approach.
Resolving the issue of making substitute() incremental. This algorithm is currently not incremental and I'm not sure how best to make it so.
These issues are really central to improving the overall performance of the compiler.
The text was updated successfully, but these errors were encountered:
After the work done on developing the
IncrementalAutomatonMinimiser
, it has become clear that closer integration withAutomaton
would be very helpful. See #19 for more.Therefore, this issue proposes to rework
Automaton
in order to ensure all operations are incremental and do not do work proportional to the number of states. To make this happen requires:rewrite
a set of states forming a cycle may not be garbage collected. Since the automaton is rooted, we can consider least common ancestors as one alternative approach.substitute()
incremental. This algorithm is currently not incremental and I'm not sure how best to make it so.These issues are really central to improving the overall performance of the compiler.
The text was updated successfully, but these errors were encountered: