6
$\begingroup$

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, minimal) DFAs? Updates should preserve determinization and minimality. Can it be done more efficient than straighformard way (building a new automata from scratch using respective operations)? There is a paper "Incremental Construction and Maintenance of Minimal Finite-State Automata", but the proposed algorithm allows one to use only string addition/deletion, not arbitrary union/subtraction.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I am not aware of any such construction. In any case, there are limitations on what you can expect in terms of running time. Even for the good case where the intersection of two DFAs, of size $n$ each, is empty, a subquadratic $o(n^2)$ running time would contradict the strong exponential time hypothesis (SETH). On the other hand, the obvious algorithm has running time $O(n^2 \log n)$ and thus super-quadratic. So there is still room for improvement. Compare this: cstheory.stackexchange.com/questions/29142/… $\endgroup$
    – Hermann Gruber
    Nov 16 at 7:29

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.