

2013/02/08, MC103, 14:30  15:30
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 finitestate 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 namedropping 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 WisconsinMilwaukee
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.


