Constraint Markov Chains

Date: Thursday, November 18, 2010
Speaker: Benoit Delahaye
Venue: IST Austria

Notions of specification, implementation, satisfaction, and refinement,together with operators supporting stepwise design, constitute aspecification theory. We construct such a theory for Markov Chains(MCs) employing a new abstraction: Constraint Markov Chains.Constraint MCs permit rich constraints on probability distributions and thusgeneralize prior abstractions such as Interval MCs. Linear (polynomial)constraints suffice for closure under conjunction (respectively parallelcomposition). This is the first specification theory for MCs with suchclosure properties. Despite the generality, all operators and relationsare computable.

Posted in RiSE Seminar