Title: 	Approximate Simulations for Probabilistic I/O Automata

Speaker: Sayan Mitra

Place: 	32-G531
Time: 	noon-1:30pm
Date: 	Friday, October 27, 2006

Abstract: The  classical notion of implementation based on exact 
equality of traces is fragile when we consider hybrid and probabilistic 
automata.  This is because small perturbations to the parameters of an 
automaton produces traces with slightly different numbers (timing or 
probability information), thus breaking the equality between traces. It 
is well known that this problem can be overcome by replacing exact
equality with a metric defining similarity between traces.  Based on 
this approach, we develop a theory of approximate implementations for 
Probabilistic I/O Automata. We formalize the distance between two 
automata by  the uniform metric on the set of trace distributions 
produced by them and propose Approximate Simulation Functions for 
proving approximate implementations. This  allows us to deduce simple 
properties like: if automaton  A \epsilon-implements B and  if B hits 
unsafe states with  probability at most p, then  the same probability 
for A is at most p + \epsilon. Approximate simulations also useful for  
proving robustness. I will discuss some applications, connections to the 
classical simulation, and possible extensions to automata with 
continuous state spaces.