Abstractions of finite-state machines and optimality with respect to immediately-detectable next-state faults

摘要

Abstraction is the process of lumping together some of the inputs, states, and outputs of a finite-state system (machine) M to transform it into a smaller, generally nondeterministic system M/sub A/. Theoretically, abstraction can be viewed as a method for approximate system simplification, and practically it finds application to system monitoring. Large and complex systems are usually observable through restricted interfaces, which allow an observer only a lumped (abstracted) view of the system, and render some erroneous behaviors undetectable. In spite of the nondeterminism introduced by the abstraction, there is still a class of faults in the system (changes in the next-state or output maps) which are immediately-detectable upon occurrence. Here the author studies the problem of finding an abstraction for an FSM which groups the inputs, states, and outputs into a specified number of classes, while maximizing the number of immediately-detectable (i.d.) next-state faults of multiplicity 1. Assuming that a partition of the machine's outputs is given, the author shows that the optimal choice of either the state or the input partition is an NP-hard or NP-complete problem. However, the author gives a polynomial-time algorithm that finds an approximately optimal partition of the machine's inputs for any given partition of the states. The author also provides a bound on the optimum, computable in polynomial time. Numerical experiments with the algorithm on randomly-generated machines with two types of state partitions, suggest that (a) the optimal number of i.d. next-state faults increases linearly with the number of blocks of the input partition, and (b) that more faults are i.d. in machines with "sparse" structure and with less uniform state partitions.