Paper Info
Title
On a class of optimal abstractions of finite-state machines
Abstract
Anabstraction A of an fsmM consists in partitioning its states, inputs, and outputs into groups, thus turning it into a non-deterministic fsmM A. For fixed sets of states, inputs, and outputs, and abstraction generally maps a number of machinesM defined on these sets into the sameM A. We would like to find anoptimal abstractionA * which minimizes this number, while lumping the states, inputs, and outputs into a specified number of classes. We extend these ideas to an fsmM operating in a random environment, and show that the abstraction results in a probabilistic fsm $$\mathcal{M}_A $$ . Thinking of changes inM's output map as resulting in machinesM≠MM, we want to find anA * that minimizes the number ofMM which are such that the transition probabilities of their abstracted version $$\mathcal{M}_A $$ . SuchMM arise from statistically-undetectable output faults inM. Abstractions are directly applicable to the monitoring of a complex system by an observer for deviations from correct behavior (faults). Complex systems are usually accessible through restricted interfaces, which do not allow the observer to distinguish among all states, inputs, and outputs, thus rendering some faulty transitions undetectable. An optimal interface design will minimize the number of such undetectable faults. Assuming that only single-transition output faults occur inM, we show that each of the classes into which the abstraction lumps the outputs contributes a number of undetectable output faults. We then show that the problem of partitioning the outputs into a given number of classes that minimizes the maximum of these numbers is NP-complete. However, we give (a) an approximate minimization algorithm, running in time linear in the number of classes and quadratic in the number ofM's outputs, and (b) a lower bound on the minimum, computable in the same amount of time. The concept of optimal abstractions is illustrated by numerical results on combinational logic circuits that perform arithmetical operations. The results shed light on the trade-off between model simplification and the ability to detect erroneous behaviors in complex systems.
Year
DOI
Venue
1996
10.1007/BF00709137
Formal Methods in System Design
Keywords
Field
DocType
finite-state machine,monitoring,faults,abstraction,optimal partitioning
Complex system,Abstraction,Computer science,Algorithm,Finite-state machine,Theoretical computer science,Real-time computing,Probabilistic logic,Observer (quantum physics),Rendering (computer graphics),Interface design
Journal
Volume
Issue
ISSN
8
3
0925-9856
Citations 
PageRank 
References 
2
0.43
10
Authors
1
Name
Order
Citations
PageRank
Kostas N. Oikonomou1265.20