Fault Identification Using a Finite State Machine Model with Unreliable Partially Observed Data Sequences

Abstract

In this paper we address the problem of minimum cost identification of a finite state machine using a trace of its event history. The motivation for this work is fault identification in communication systems. Other applications are possible as well. The event history we are using for the identification is partially observed, i.e., it is known to be a member of a regular language. Any string which belongs in this regular language is a possible trace of the FSM’s event history. Furthermore, the event history is assumed to be corrupted with deletions, additions, and changes of symbols. The finite state machine to be estimated is related to a known finite state machine by performing an unknown number of additions and changes of arcs. An identification algorithm is developed based on a fast algorithm which can correct corrupted data strings generated by a known finite state machine. Examples of the method are provided, including one based on the IEEE 802.2 Logical Link Control protocol. This work is part of a continuing effort to develop a unified approach to fault management in communication networks. © 1993 IEEE