Decremental subset construction

Finite automata are exploited in several domains, including language processing, artificial intelligence, automatic control, and software engineering. Let N be a nondeterministic finite automaton (NFA) and D the deterministic finite automaton (DFA) equivalent to N. Assume to decrement N by DN, thus obtaining the decremented NFA N' = N - DN, where some states and/or transitions are missing. Consider determinizing N'. Instead of determinizing N' from scratch using the classical Subset Construction algorithm, we propose Decremental Subset Construction, an algorithm which generates the DFA D' equivalent to N' by updating D based on N and DN. This way, only the actions necessary to transform D into D' are applied. Although evidence from worst-case complexity analysis indicates that Decremental Subset Construction is not better than Subset Construction, in practice, when N is large and DN relatively small, Decremental Subset Construction may outperform Subset Construction significantly.