Temporal determinization of mutating finite automata: Reconstructing or restructuring. (16th December 2019)

• Record Type: Journal Article
• Authors: Lamperti, Gianfranco
• Is Part Of: Software, practice & experience. Volume 50:Number 4(2020)
• Page Start: 335
• Page End: 367
• Publication Date: 2019-12-16
• Subjects: determinization -- finite automata -- mutating automata -- subset construction -- subset restructuring; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2776
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model‐based diagnosis of discrete‐event systems in artificial intelligence and model‐based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction . Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations.