Determinization and minimization of finite acyclic automata by incremental techniques. (21st January 2015)

• Record Type: Journal Article
• Authors: Lamperti, Gianfranco; Scandale, Michele; Zanella, Marina
• Is Part Of: Software, practice & experience. Volume 46:Number 4(2016)
• Page Start: 513
• Page End: 549
• Publication Date: 2015-01-21
• Subjects: acyclic finite automata -- determinization -- minimization -- incremental techniques; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2309
• Languages: English
• ISSNs: 0038-0644

Abstract

SUMMARY: The determinization of a nondeterministic finite automaton (FA) N is the process of generating a deterministic FA (DFA) D equivalent to (sharing the same regular language of) N . The minimization of D is the process of generating the minimal DFA ℳ equivalent to D . 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 N augments over time: after each augmentation, determinization and minimization of N 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.