The Duality of State and Observation

In this talk we consider the problem of representing and reasoning about systems, especially probabilistic systems, with hidden state.  We consider transition systems where the state is not completely visible to an outside observer.  Instead, there are observables that partly identify the state. We show that one can interchange the notions of state and observation and obtain what we call a dual system.  The double dual gives a minimal representation of the behaviour of the original system.  We extend this to nondeterministic systems and to probabilistic transition systems and finally to partially observable Markov decision processes (POMDPs).  In the case of finite automata restricted to one observable, we obtain Brzozowski's algorithm for minimizing finite-state language acceptors.