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 N, an equivalent deterministic automaton D is generated, with each state in D being a subset of states in N. However, SC is conceived for monolithic determinization, when N 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 N to N' by DN (by new transitions and, possibly, new states), we require N' to be determinized into D' based on D and DN. Although this problem can be naively solved by applying SC to N' (thereby disregarding both D and DN), this solution is bound to lead to poor performances, as it does not exploit the incremental nature of N'. Therefore, an incremental algorithm is proposed, called ISCA, which extends D into D' based on DN, rather than starting from scratch the determinization of N'. 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.

From diagnosis of active systems to incremental determinization of finite acyclic automata

LAMPERTI, Gian Franco;
2013-01-01

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 N, an equivalent deterministic automaton D is generated, with each state in D being a subset of states in N. However, SC is conceived for monolithic determinization, when N 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 N to N' by DN (by new transitions and, possibly, new states), we require N' to be determinized into D' based on D and DN. Although this problem can be naively solved by applying SC to N' (thereby disregarding both D and DN), this solution is bound to lead to poor performances, as it does not exploit the incremental nature of N'. Therefore, an incremental algorithm is proposed, called ISCA, which extends D into D' based on DN, rather than starting from scratch the determinization of N'. 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/431506
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 10
social impact