Model Checking Markov Chains Against Unambiguous Buchi Automata
  We give a polynomial-time algorithm for model checking finite Markov chains against omega-regular specifications given as unambiguous Buchi automata. 
Michael Benedikt, Rastislav Lenhardt, James Worrell
cs.LO cs.FL