  We use Markov categories to develop generalizations of the theory of Markov
chains and hidden Markov models in an abstract setting. This comprises
characterizations of hidden Markov models in terms of local and global
conditional independences as well as existing algorithms for Bayesian filtering
and smoothing applicable in all Markov categories with conditionals. We show
that these algorithms specialize to existing ones such as the Kalman filter,
forward-backward algorithm, and the Rauch-Tung-Striebel smoother when
instantiated in appropriate Markov categories. Under slightly stronger
assumptions, we also prove that the sequence of outputs of the Bayes filter is
itself a Markov chain with a concrete formula for its transition maps.
  There are two main features of this categorical framework. The first is its
generality, as it can be used in any Markov category with conditionals. In
particular, it provides a systematic unified account of hidden Markov models
and algorithms for filtering and smoothing in discrete probability, Gaussian
probability, measure-theoretic probability, possibilistic nondeterminism and
others at the same time. The second feature is the intuitive visual
representation of information flow in these algorithms in terms of string
diagrams.
