This paper develops efficient local model-checking algorithms for expressive fragments of the modal Μ-calculus. The time complexity of our procedures matches that of the best existing global algorithms; however, in contrast to those routines, ours explore a system's state space in a need-driven fashion and do not require its a priori construction. Consequently, our algorithms should perform better in practice. Our approach relies on a novel reformulation of the model-checking problem for the modal mucalculus in terms of checking whether certain linear-time temporal formulas are satisfied by generalized Kripke structures that we call and-or Kripke structures.