Affiliations: Dipartimento di Ingegneria dell'Informazione, Universitร di Brescia, Brescia, Italy. E-mail: [email protected] | Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy. E-mail: [email protected]
Note: [] Corresponding author: Gianfranco Lamperti, Dipartimento di Ingegneria dell'Informazione, Universitร di Brescia, Via Branze 38, 25123 Brescia, Italy. E-mail: [email protected]
Abstract: A non-functional requirement for model-based diagnosis of active systems is efficient determinization of acyclic automata. In literature, determinization of finite automata is performed by the Subset Construction algorithm (SC): given a nondeterministic automaton ๐ฉ, an equivalent deterministic automaton ๐ is generated, with each state in ๐ being a subset of states in ๐ฉ. However, SC is conceived for monolithic determinization, when ๐ฉ is completely specified. By contrast, monitoring-based diagnosis of active systems requires incremental determinization. We consider the Incremental Determinization Problem for finite acyclic automata: after extending the acyclic automaton ๐ฉ to ๐ฉโฒ by ฮ๐ฉ (by new transitions and, possibly, new states), we require ๐ฉโฒ to be determinized into ๐โฒ based on ๐ and ฮ๐ฉ. Although this problem can be naively solved by applying SC to ๐ฉโฒ (thereby disregarding both ๐ and ฮ๐ฉ), this solution is bound to lead to poor performances, as it does not exploit the incremental nature of ๐ฉโฒ. Therefore, an incremental algorithm is proposed, called ISCA, which extends ๐ into ๐โฒ based on ฮ๐ฉ, rather than starting from scratch the determinization of ๐ฉโฒ. ISCA is a general-purpose algorithm. Evidence from experiments indicates that, in time, ISCA is significantly more efficient than SC in solving incremental determinization problems.
