| Abstract: |
In society, laziness is generally considered as a negative feature, if not a capital fault. Not so in computer science, where lazy techniques are widespread, either to improve efficiency or to allow for computation of unbounded objects, such as infinite lists in modern functional languages. We bring the idea of lazy computation to the context of model-based diagnosis of active systems. Up to a decade ago, all approaches to diagnosis of discrete-event systems required the generation of the global system model, a technique that is impractical when the system is large and distributed. To overcome this limitation, a lazy approach was then devised in the context of diagnosis of active systems, which works with no need for the global system model. However, a similar drawback arose a few years later, when uncertain temporal observations were proposed. In order to reconstruct the system behavior based on an uncertain observation, an index space is generated as the determinization of a nondeterministic automaton derived from the graph of the uncertain observation, the prefix space. The point is that the prefix space and the index space suffer from the same computational difficulties as the system model. To confine the explosion of memory space when dealing with diagnosis of active systems with uncertain observations, a laziness-based, circular-pruning technique is presented. Experimental results offer evidence for the considerable effectiveness of the approach, both in space and time reduction. |