BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Approximating Labelled Markov Processes by Averaging - Prakash Pan
 angaden\, McGill University
DTSTART:20110225T140000Z
DTEND:20110225T150000Z
UID:TALK28984@talks.cam.ac.uk
CONTACT:Bjarki Holm
DESCRIPTION:Markov processes with continuous state spaces or continuous ti
 me evolution or both arise naturally in many areas of computer science: ro
 botics\, performance evaluation\, modelling and simulation for example. Fo
 r discrete systems there was a pioneering treatment of probabilisitic bisi
 mulation and logical characterizationdue to Larsen and Skou [LS91]. The co
 ntinuous case\, however\, was neglected for a time. For a little over a de
 cade there has been significant activity among computer scientists as it c
 ame to be realized that ideas from process algebra\, like bisimulation and
  the existence of a modal characterization\, would be useful for the study
  of such systems. \n\nIn [BDEP97] continuous-state Markov processes with l
 abels to capture interactions were christened labelled Markov processes (L
 MPs). There is a vast literature on timed systems\, hybrid systems\, robot
 ics and control theory that also refer to such systems.  In [DGJP00\, DGJP
 03] a theory of approximation for LMPs was initiated and was refined and e
 xtended in [DD03\, DDP03]. Finding finite approximations is vital to give 
 a computational handle on such systems. These techniques were adapted to M
 arkov decision processes (MDPs) and applied to find good estimates of valu
 e functions [FPP05]. The previous work was characterized by rather intrica
 te proofs that did not seem to follow from basic ideas in any straightforw
 ard way. For example\, the logical characterization of (probabilistic) bis
 imulation proved first in [DEP98] requires subtle properties of analytic s
 paces and rather painful constructions [Eda99]. Proofs of basic results in
  approximation theory also seemed to be more difficult than they should be
 .\n\nIn recent work we take an entirely new approach\, in some ways "dual"
  to the normal view of probabilistic transition systems. We think of a Mar
 kov process as a transformer of functions defined on it\, rather than as a
  transformer of the state. Thus\, instead of working directly with a Marko
 v kernel _\\tau(s\,A)_ that takes a state _s_ to a probability distributio
 n over the state space\, we think of a Markov process as transforming a fu
 nction _f_ into a new function _\\int f(s')\\tau(s\, ds')_ over the state 
 space. This is the probabilistic analogue of working with predicate transf
 ormers\, a point of view advocated by Kozen [Koz85] in a path-breaking ear
 ly paper on probabilistic systems and logic.\n\nThis new way of looking at
  things leads to three new results: \n\n# It is possible to define bisimul
 ation on general spaces – not just on analytic spaces – and show that 
 it is an equivalence relation with easy categorical constructions. The log
 ical characterization of bisimulation can also be done generally\, and wit
 h no complicated measure theoretic arguments. \n# A new and flexible appro
 ach to approximation based on averaging can be given. This vastly generali
 zes and streamlines the idea of using conditional expectations to compute 
 approximation [DDP03]. \n# It is possible to show that there is a minimal 
 bisimulation equivalent to a process obtained as the limit of finite appro
 ximants. \n\nThere are a number of interesting categorical aspects to this
  work which I will emphasize in the talk. This is joint work with Philippe
  Chaput\, and with Vincent Danos and Gordon Plotkin.\n\n*References*\n\n* 
 [BDEP97] R. Blute\, J. Desharnais\, A. Edalat\, and P. Panangaden. Bisimul
 ation for labelled Markov processes. In _Proceedings of the Twelfth IEEE S
 ymposium On Logic In Computer Science_\, Warsaw\, Poland.\, 1997.\n\n* [DD
 03] Vincent Danos and Josee Desharnais. Labeled Markov Processes: Stronger
  and faster approximations. In _Proceedings of the 18th Symposium on Logic
  in Computer Science_\, Ottawa\, 2003. IEEE.\n\n* [DDP03] Vincent Danos\, 
 Josee Desharnais\, and Prakash Panangaden. Conditional expectation and the
  approximation of labelled Markov processes. In Roberto Amadio and Denis L
 ugiez\, editors\, _CONCUR 2003 - Concurrency Theory_\, volume 2761 of _Lec
 ture Notes In Computer Science_\, pages 477–491. Springer-Verlag\, 2003.
 \n\n* [DEP98] J. Desharnais\, A. Edalat\, and P. Panangaden. A logical cha
 racterization of bisimulation for labelled Markov processes. In _Proceedin
 gs of the 13th IEEE Symposium On Logic In Computer Science_\, Indianapolis
 \, pages 478–489. IEEE Press\, June 1998.\n\n* [DGJP00] J. Desharnais\, 
 V. Gupta\, R. Jagadeesan\, and P. Panangaden. Approximation of labeled Mar
 kov processes. In _Proceedings of the Fifteenth Annual IEEE Symposium On L
 ogic In Computer Science_\, pages 95–106. IEEE Computer Society Press\, 
 June 2000.\n\n* [DGJP03] J. Desharnais\, V. Gupta\, R. Jagadeesan\, and P.
  Panangaden. Approximating labeled Markov processes. _Information and Comp
 utation_\, 184(1):160–200\, July 2003.\n\n* [Eda99] Abbas Edalat. Semi-p
 ullbacks and bisimulation in categories of Markov processes. _Mathematical
  Structures in Computer Science_\, 9(5):523–543\, 1999.\n\n* [FPP05] Nor
 m Ferns\, Prakash Panangaden\, and Doina Precup. Metrics for Markov decisi
 on processes with infinite state spaces. In _Proceedings of the 21st Confe
 rence on Uncertainty in Artificial Intelligence_\, pages 201–208\, July 
 2005.\n\n* [Koz85] D. Kozen. A probabilistic PDL. _Journal of Computer and
  Systems Sciences_\, 30(2):162–178\, 1985.\n\n* [LS91] K. G. Larsen and 
 A. Skou. Bisimulation through probablistic testing. _Information and Compu
 tation_\, 94:1–28\, 1991.
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR