Incremental Determinization of Expanding Automata

Subset Construction (SC) is the classical algorithm for the determinization of a nondeterministic finite automaton (NFA) into an equivalent deterministic one (DFA). Although SC works fine in most application domains, it may be inappropriate when the NFA expands over time and determinization is required after each expansion, such as in diagnosis of active systems in artificial intelligence, or in model-based testing in software engineering. For such an expanding automaton, the IDEA algorithm (Incremental Determinization of Expanding Automata) may be more suitable. Given an NFA N, an equivalent DFA D, and an expansion DN of N, the determinization of N' = N + DN into D' is performed based not only on N' but also on DN and D. Rather than starting from scratch the generation of the DFA D' equivalent to N', IDEA applies the set of actions which are sufficient for transforming D into D'. This way, a possibly large part of the determinization process is avoided. Experiments show that the degree of convenience in determinizing expanding automata using IDEA rather than SC largely depends on the nature of the expanding automaton in the actual application domain.