News
- 4th August 2011
Prakash Panangaden talk. 2pm.
Title: The Duality of State and Observation
Abstract: 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. This is joint work with colleagues from McGill: Doina Precup and Joelle Pineau and my former student Chris Hunt.
Events
Past Events
- 1st-2nd June 2011
Bart Jacobs visited.
- 17th May 2011
Phil Scott talk.
Title: Traced categories: algebraic structure of feedback and partial feedback in networks
Abstract: In the late '80s/early '90s an algebraic structure dealing with cyclic operations emerged from various fields, including flowchart schemes, dataflow networks with feedback, action calculi, proof theory, as well as algebraic topology and knot theory. This structure is now known as a "traced monoidal category" , after the influential paper of Joyal, Street and Verity, who studied such categories in pure mathematics, but with an eye to applications in many fields. The concept also occurs as a basic structure in network algebra. Since then, these categories have been studied, with variations, in many areas of mathematics, logic and theoretical computer science, Recently, there has been a trend to consider partial traces and trace ideals; indeed it appears that such algebraic structures may be relevant to several areas, including biology and physics, or indeed to any field where cyclic networks are used. We give an introduction to the subject, along with some recent advances.
- 13th May 2011
- 21st-25th April 2011
Janis Voigtländer visited.
- 17th February 2011
Nicola Gambino talk. 12pm. Location 14.15.
Title: Voevodsky's Univalence Axiom
Abstract: Vladimir Voevodsky has recently introduced a semantics for constructive type theory in which types are interpreted as simplicial sets. This semantics validates not only the usual rules for identity types but also an additional rule, called the Univalence Axiom. The aim of the talk is to explain the statement of the Univalence Axiom and outline Voevodsky's proof that it implies a form of function extensionality.
- 2nd December 2010
- 3rd December 2010
- 22nd-26th November 2010
Wouter Swierstra visiting.
- 24th November 2010