Duality of State and Observation in Automata
Prakash Panangaden - School of Computer Science, McGill University
Feb. 8, 2013, 1 p.m. - Feb. 8, 2013, 2 p.m.
MC103
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. Prakash works in the area between logic and probability and particularly on approximating Markov processes on continuous state spaces. He also works on programming language semantics, duality theory for automata, relativistic effects in quantum information theory, some physics and some mathematics. He is a member of the RL Lab at McGill University and interacts also with the CQI Lab as well as the CompLogic group. He is also an associate member of the Department of Mathematics and Statistics and an affiliate member of the Perimeter Institute. Prakash grew up in India and attended the Indian Institute of Technology, Kanpur. Since he studied Physics rather than Management he was not sought after in the Indian marriage market and went to the US to study, first at the University of Chicago, then at the University of Wisconsin-Milwaukee where he got a PhD in Physics. He later got an MS in computer science from the University of Utah and wormed his way onto the faculty of the Computer Science Department of Cornell University. There he met and married a Canadian who complained that it was not cold enough in the US so he moved to McGill University where he has spent a couple of delightful decades with a bunch of fabulous colleagues and wonderful students.
