Quantified probability logics: expressibility vs. computability

Stanislav Speranski

(Novosibirsk)

The talk is devoted to various formal languages for reasoning about probabilities, namely to those augmented by quantifiers over so-called Bernoulli random variables (which correspond to spinning fair and biased coins). In a sense, such languages enable one to explicitly write specifications in probabilistic terms. Unfortunately, many standard problems concerning these languages turn out to be algorithmically undecidable. Still, understanding/measuring computational complexity of those problems is a very interesting and natural task in its own right --- and this will be the main topic of the talk.
Thursday 4th July 2013, 14:00
Robert Recorde Room
Department of Computer Science