Maximum Likelihood Diagnosis in Partially Observable Finite State Machines

In this paper we develop a probabilistic approach for fault diagnosis in deterministic finite state machines (FSMs). The proposed approach determines whether the FSM under consideration is faulty or not by observing (part of) its output sequence. The input sequence applied to the FSM does not need to be fully observable but an a priori probabilistic description of the input sequence is assumed to be available. Given the (partially) observed output sequence of the FSM, we compute the a posteriori probability that this sequence was produced by the fault-free FSM and compare it to the a posteriori probability that it was produced by the faulty one. We also discuss how the approach in the paper relates to the more general problem of observation and fault diagnosis in stochastic discrete event systems in (hidden) Markov models