On the undecidability of computing stationary distributions and large deviation rates for constrained random walks

We consider a constrained homogeneous random walk in [Z.sup.d.sub.+]. Such random walks are used to model various stochastic processes, most importantly multiclass Markovian queueing networks operating under state-dependent scheduling policies. [...]