Approximate Verification and Enumeration problems

演讲人: Michel de Rougemont 法国巴黎第二大学
时间: 2012-06-14 14:00-2012-06-14 15:00
地点:FIT 1-222

 We consider Verification problems, such as the Equivalence of Automata, Probabilistic Automata, and MDP's (Markov Decision Processes). The enumeration problem consists in enumerating words which distinguish two Automata and strategies which distinguish two MDPs. As these problems are hard in some sense, we present probabilistic methods in the case of Probabilistic Automata and Approximate methods (in the sense of Property Testing) for Automata and MDP's.


 Michel de Rougemont is a Professor of Computer Science at the University Paris II, and at LIAFA-CNRS. He obtained his Ph.D. in 1983 from UCLA and his Habilitation in 1988 from the University of Paris-South. He joined the University Paris II in 1995 and LIAFA in 2010. He works in Logic and Complexity and more recently on problems with uncertainty.