Duality for Probabilistic Automata
Prakash Panangaden – 27 February 2013
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. I will explain the category theoretic reason why this works at the end. In this more general version we can handle weighted automata and also probabilistic transition systems.This research began with joint work with colleagues from McGill especially Doina Precup and Chris Hunt. The recent categorical understanding is joint work with Clemens Kupke and Nick Bezhanishvili.
Back