Determinization and minimization of finite acyclic automata by incremental techniques |
| |
| Authors: | Gianfranco Lamperti Michele Scandale Marina Zanella |
| |
| Affiliation: | 1. Dipartimento di Ingegneria dell'Informazione, Università di Brescia, Brescia, Italy;2. Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milan, Italy |
| |
| Abstract: | The determinization of a nondeterministic finite automaton (FA)  is the process of generating a deterministic FA (DFA)  equivalent to (sharing the same regular language of)  . The minimization of  is the process of generating the minimal DFA  equivalent to  . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where  augments over time: after each augmentation, determinization and minimization of  into  is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model‐based diagnosis and monitoring of active systems, the algorithm is general‐purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd. |
| |
| Keywords: | acyclic finite automata determinization minimization incremental techniques |
|
|
