  We present an efficient exact algorithm for estimating state sequences from
outputs (or observations) in imprecise hidden Markov models (iHMM), where both
the uncertainty linking one state to the next, and that linking a state to its
output, are represented using coherent lower previsions. The notion of
independence we associate with the credal network representing the iHMM is that
of epistemic irrelevance. We consider as best estimates for state sequences the
(Walley--Sen) maximal sequences for the posterior joint state model conditioned
on the observed output sequence, associated with a gain function that is the
indicator of the state sequence. This corresponds to (and generalises) finding
the state sequence with the highest posterior probability in HMMs with precise
transition and output probabilities (pHMMs). We argue that the computational
complexity is at worst quadratic in the length of the Markov chain, cubic in
the number of states, and essentially linear in the number of maximal state
sequences. For binary iHMMs, we investigate experimentally how the number of
maximal state sequences depends on the model parameters. We also present a
simple toy application in optical character recognition, demonstrating that our
algorithm can be used to robustify the inferences made by precise probability
models.
