Name
Abstract | ||
|---|---|---|
A general way to make a smaller model of a large system, or to represent the fact that the observations possible on it are limited, is to apply an abstraction A to it. If the system is modeled by a finite-state machine M, the abstraction consists of three partitions, one for each of the state, input, and output sets. States, inputs, or outputs lumped together in one block by the partition are indistinguishable from each other, resulting in a nondeterministic machine M/sub A/. An observer of M/sub A/, whose task is to detect erroneous behavior in M, is prevented by the abstraction from seeing some of the faults. The authors investigate the choice of an abstraction that is optimal with respect to immediately detectable faults in the output map. It is shown that this requires solving an NP-complete 'set-partitioning' problem. A polynomial-time algorithm for finding an approximately optimal partition of either the states or the inputs of M, together with a way to check the goodness of the approximation is given. This algorithm also solves the undetectable fault minimization problem exactly, and in polynomial time. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1109/12.127444 | Computers, IEEE Transactions |
Keywords | Field | DocType |
undetectable fault minimization problem,optimal partition,nondeterministic machine,detectable fault,immediately-detectable output faults,output map,finite-state machine,finite-state machines,abstraction a,large system,polynomial-time algorithm,output set,computational complexity,np complete,indexing terms,data structures,finite automata,approximation algorithms,artificial intelligence,abstraction,fault detection,polynomials,very large scale integration,finite state machine,solid modeling,polynomial time,finite state machines | Data structure,Abstraction,Nondeterministic algorithm,Computer science,Parallel computing,Algorithm,Finite-state machine,Minimisation (psychology),Time complexity,Observer (quantum physics),Computational complexity theory | Journal |
Volume | Issue | ISSN |
41 | 3 | 0018-9340 |
Citations | PageRank | References |
5 | 0.64 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kostas N. Oikonomou | 1 | 26 | 5.20 |