Exact and Approximate Solutions for a Class of Infinite Markovian Models