In this note we develop a framework for computing upper and lower bounds of an exponential form for a class of stochastic recursive equations with uniformly recurrent Markov modulated inputs. These bounds generalize Kingman's bounds for queues with renewal inputs. Copyright Springer-Verlag...