EFFICIENT MINIMIZATION OF HOMOGENEOUS FSMS FOR FAULT-DIAGNOSIS

On the base of the Finite State Machine (FSM) model, the fault diagnos is problem deals with the identification of a faulty implementation ag ainst its specification represented by an FSM. In particular, to effic iently identify potential faulty implementations caused by a transfer error in an FSM, cross-verification over the FSM is performed after al l potential faulty FSMs have been minimized. Existing minimization alg orithms become inefficient due to the lack of taking advantage of the homogeneity of these potential faulty FSMs. In this paper, we propose a two-phase algorithm for the efficient and simultaneous minimization of a set of homogeneous faulty FSMs. Disregarding the suspicious trans ition, the first phase of the algorithm performs minimization of these faulty FSMs via a common digraph of th FSMs. These faulty FSMs are co nsidered minimized if the distinguishing sequences of all state-pairs can be discovered from the common digraph. Otherwise, the algorithm in the second phase performs minimization for each faulty FSM by individ ually restoring its corresponding unexpected transition in the reduced common digraph. To demonstrate the efficiency of the two-phase algori thm, we carried out experiments on a number of realistic protocol spec ifications, including the Alternation Bit Protocol (ABP), Transport Pr otocol Class 4 (TP4), and ISDN Basic Rate Interface (BRI) protocol. Ex perimental results show that the algorithm renders the minimization co mplexity greatly reduced for most of the realistic protocol FSMs.