Hidden Discrete Event Systems Models (HDESM) are discrete event dynamical system models whose underlying internal state spaces are not directly observable. Observations on such systems are artifacts of the hidden, internal states and are not deterministically or uniquely associated with the hidden states. The distribution of an observation of a HDESM is typically given by a probability distribution conditioned on the hidden state of the system. Classical linear systems, Hidden Markov Models (HMM) and certain types of Petri Net models are examples of HDESM's. A major challenge in working with this type of model is the estimation of HDESM's hidden states based on a sequence of observations. In some cases, well-known algorithms can be used to solve this problem. In many cases of practical interest, however, the complexity of those algorithms is too high to be practical. New ideas and algorithms are therefore needed for effective solutions to the state estimation problem. In this paper we will investigate sub-classes of HDESM's whose structure would allow efficient state estimation algorithms to exist. Such structures could be related to the sparsity and/or equivalence class structure of transition dynamics within the underlying discrete event system. Efficient algorithms that compute approximate solutions will be investigated with the goal of understanding the trade-offs between computational efficiency and estimation accuracy. Ideas on how to implement such trade-offs also are proposed.
