Duality of State and Observation in Automata
Prakash Panangaden , School of Computer Science, McGill University

Abstract:

Duality is a fundamental concept appearing in mathematics, physics and computer science in various guises. Examples are linear programming duality, Stone duality (logic and topology), Gelfand duality (functional analysis) as well as other more exotic dualities in mathematical physics. In this talk I consider the problem of representing and reasoning about systems, especially probabilistic systems, with hidden state. I consider transition systems where the state is not completely visible to an outside observer. Instead, there are observables that partly identify the state. This yields something very much like an automaton as studied in undergraduate classes. I show that one can interchange the notions of state and observation and obtain what can be called a dual system. The double dual gives a minimal representation of the behaviour of the original system. I extend this to probabilistic transition systems and to partially observable Markov decision processes (POMDPs). In the case of finite automata restricted to one observable, one obtains something similar to Brzozowski's algorithm for minimizing finite-state language acceptors. It turns out that there is a categorical way of understanding these results and diverse examples fit into a pleasing general framework. This is joint work with several people: Nick Bezhanishvili, Filippo Bonchi, Marcello Bonsangue, Monica Dinculescu*, Helle Hvid Hansen, Chris Hundt*, Dexter Kozen, Clemens Kupke, Kim Larsen, Radu Mardare, Joelle Pineau*, Doina Precup*, Jan Rutten and Alexandra Silva. Though I will be name-dropping as usual, the talk should be easily accessible to a theoretically inclined undergraduate, perhaps to a graduate student and possibly even to a professor.