New algorithms for computing asymptotic expansions, without and with explicit upper bounds for remainders, for stationary and quasi-stationary distributions of nonlinearly perturbed semi-Markov processes are presented. The algorithms are based on special techniques of sequential phase space reduction, which can be applied to models with an arbitrary asymptotic communicative structure of phase spaces.