Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Lamperti, Gianfranco; | Scandale, Michele
Affiliations: Dipartimento di Ingegneria dell'Informazione, Universitร di Brescia, Brescia, Italy. E-mail: lamperti@ing.unibs.it | Dipartimento di Elettronica e Informazione, Politecnico di Milano, Milano, Italy. E-mail: scandale@elet.polimi.it
Note: [] Corresponding author: Gianfranco Lamperti, Dipartimento di Ingegneria dell'Informazione, Universitร di Brescia, Via Branze 38, 25123 Brescia, Italy. E-mail: lamperti@ing.unibs.it
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.
Keywords: Diagnosis, monitoring, active systems, discrete-event systems, temporal observations, acyclic automata, determinization, incremental techniques
DOI: 10.3233/AIC-130574
Journal: AI Communications, vol. 26, no. 4, pp. 373-393, 2013
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
ๅฆๆๆจๅจๅบ็ๆน้ข้่ฆๅธฎๅฉๆๆไปปไฝๅปบ, ไปถ่ณ: editorial@iospress.nl