6

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.

gsv
  • 421
  • 2
  • 6
  • 1
    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: https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time

     – Hermann Gruber Nov 16 '23 at 07:29

0 Answers0